## Amazon Interview Question for Software Engineer / Developers

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

Well to get to the point where the entry is, the complexity will be O(1)
But if a chaining mechanism is used, we would have to look at each element in the chain (if the chain is a linked list) and the complexity under worst case condition would be O(n)

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

Vague, really, not incomplete. Part of the question is understanding that it does depend on hashing algorithm.

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

It really depends on the actual implementation.
Chintan, if you believe that it takes O(ln n) to find a duplicate in the linked list, then the linked list(which is used for handling collisions) must be sorted at anytime. If you want to have such a hashtable, the insertion will be O(ln n) as well since it has to be placed at the right position to ensure that the linked list is sorted.

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

The information in the question is incomplete. The worst case time depends on the hash function and the strategy to resolve the conficts. Suppose the hash function is f(i) = 1 and if chaining is used you will always need n comparisons. This time also depends on the size of the hash table and number of nodes already inserted in the hash table, that is load factor of the hash table is also one parameter which would determine this. But in theroetical sense the worst possible time for hashtable insertion is O(n)

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

again an ambiguous question.

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

It really depends what collision technique is being used when doin insertion in hash table.

If we are sure that there will not be any collision then it is o(1).

If it is open addressing, it really depends on hash function we use for rehashing. Could be as much as O(n) or it can be the case that we do not find any empty space because of the nature of the rehasing function and already populated values in hash table.

If chaining is used, worst case can be O(n).

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

Assuming that the hash table is implemented as an array, there are collisions, and chaining is used to handle them.

Insert can still be done in O(1)? If a collision occurs, instead of traversing the entire list and inserting the new value at the end, Insert it at the start.

does this make sense ?

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

It is O(1 + alpha)

where alpha = n/m

m = number of slots in the hash table
n = total number of elements that u are trying to put in the hash table.

--check Introduction to algorithms by cormen

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

O(n) in worst case when all the keys get mapped to the same slot.

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

But, hashtable can't have duplicate value, so in order to find out
whether it is duplicate or not, it first takes o(lon n) time, and
then just 0(1) to insert it. Isn't it?

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.