Interview Question

Software Development Manager Interview

-Chennai

Amazon

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)

Tags:data structures
AnswerAdd Tags

Interview Answers

3 Answers

0

This is Assuming that numbers can't repeat

Assuming that numbers can't repeat on

2

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)

Anonymous on

0

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

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.