First Round Questions (6 year Exp Software Engineer took the interview)
1)In a Given array which contains sorted numbers only one of number matches with that of Index. Find the number Not in O(N).
2)Derive a DataStructure to support the following operations Insert/Delete/Search/GetRandom Value in O(1) & O(logN)

Question

First Round Questions (6 year Exp Software Engineer took the interview)
1)In a Given array which contains sorted numbers only one of number matches with that of Index. Find the number Not in O(N).
2)Derive a DataStructure to support the following operations  Insert/Delete/Search/GetRandom Value in O(1) & O(logN)

Anónimo · Accepted Answer

Problem1 can be solved via binary search. The index to find would be the "turning point" in the array, where all entries before it are smaller, and all entries after it are larger than the indices. Search can be done in O(LogN)

Assuming that numbers can't repeat · Answer

This is Assuming that numbers can't repeat

Anónimo · Answer

Both are straightforward problems.Interviewer was genuine enough to guide when I was deviating from the answers.With Collaborative effort  this was solved. Overall this interview lasted for 45 minutes

Amazon

Pregunta de entrevista de Amazon

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo