Amazon Interview Questions – Set 9 (For SDE 2)

Recently I attended Amazon Bangalore interview for SDE 2 position. All f2f and no phone/written screening as I had attended one before and cleared those. Total 4 rounds and below are the details.

Round 1:

Q1. Find sum of all numbers that are formed from root to leaf path (code) expected time complexity O(n)

Q2. Given a string you need to print all possible strings that can be made by placing spaces (zero or one) in between them. For example : ABC -> A BC, AB C, ABC, A B C

Q3. Preorder traversal without using recursion.

Round 2:

Q1. There is a 12 km road and a contractor who is in-charge of repairing it. Contractor updates you about the work which is done in patches. Like “Road between 3.2 km to 7.9 km repaired ”, “Road between 1.21 km to 3.2 km repaired”. You have a manager who enquires about the longest continuous patch so far. It was a long discussion and I gave solution in O(nlogn) where n is the number of updates by the contractor.

Q2. Several Questions were asked from my project.

Round 3:

Q1. Find median of an unsorted array. (code)

Q2. General discussion on heaps

Q3. A stream of characters is coming, at any moment you have to tell ‘k’ elements closest to a given number (code)

Round 4:

Q1. Design data structure that supports insert(), remove(), find-max(), delete-max() operations. All operations should run in O(1) time. Lots of discussion was there, discussed many approaches.

Q2. Check whether given link list represents palindrome.