Ghost
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
First - Bring back the original array (un-rotate)
1. find the initial offset (the point of rotation, or first instance of min value) at index, say I - this takes O(n)
2. Divide the array in place - from 0 to I-1 and I to length -1
3. Rotate both arrays (swap first and last) - this takes O(n/2) so O(n)
4. Rotate the final array - still O(n)
Search -
1. Use Binary search to find index of any item on the array in step 4 above - O(logn) - say j
2. Add initial offset (I) , this is your final answer - I+j
Time - O(n)
Space - O(1)
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Any ideas on data structure to be used to store the sorted strings?
- Ghost April 13, 2015