Pregunta de entrevista de Accenture
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)
Respuesta de la entrevista
Anónimo
16 may 2012
Do something like a Binary Search.Go to the middle element compare the number with the index.If it equals the index.Problem is solved.if the Element is greater than the index Call Binary Search on left half of the array otherwise call it on right half. time complexity O(logn)
1