## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse: O(n). Coz it would be visiting all the nodes once.
Search : O(log n)
Insert : O(log n)
Delete : O(log n)

Comment hidden because of low score. Click to expand.
1
of 1 vote

for unbalanced (left skewed / right skewed) binary search tree all operations takes O(n) worst case.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Yup, the worst case for all the operation on BST is O(n)

Comment hidden because of low score. Click to expand.
0

Please explain the difference between traversing and searching. To me, their synonymous in this context

Comment hidden because of low score. Click to expand.
0
of 0 vote

Binary Search is a searching algorithm that is used on a certain data structure (ordered array) to find a if an element is within the array through a divide a conquer technique that takes the middle value of the array and compares it to the value in question. If the value is less, then compare the value in question to the lower mid-value and if greater, vice versa until you find the value or determine that it is none of the elements within the array. All a Binary Search Tree is a visual concept that allows one to see this divide a conquer technique in an easier way. For example, given : Array A = {1,2,4,6,10,20,35} we ask if the number 35 is there. First you would compare 20 to 6. 20<,>,= 6? Greater than, so compare the mid value of upper range. 35>,<,=20? greater than, compare next greater mid value. 35>,<, = 35 ? Equal. So it has been search with only three comparisons, with the worst time complexity of O(log(n)).

In a tree, this looks like :

``````6
/	     \
2	       20
/      \      /     \
1      4   10   35``````

The reason 35 is the worst time complexity is because we had to traverse to the very last tier of the tree to find it. The worst time complexity of the binary search is log(n) because in this example, n = 7 elements and log(7) ceils up to 3. 3 comparisons, and thus the more most time it would take for this example to complete its search.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hope you can explain what a BST is. It is a binary tree ie. each node has at most two child nodes. And the other criteria are that the left child is less than or equal to the root node value and the right child is greater than the root node in value - for each node.
Since it is not balanced, the time complexities will be following for worst case:
Lookup/Search = O(n)
Insertion = O(n)
Deletion = O(n)
You can also mention that the worst case occurs when all nodes are inserted on only one side of previous nodes - ie. they become more like a linked list.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I can explain binary tree in O(1) time.

Comment hidden because of low score. Click to expand.
0

lol

Comment hidden because of low score. Click to expand.
-1
of 1 vote

DSs have no time comp.
Only operations do.

Refer to a book no need for a thread

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.