Amazon Interview Question
Software Engineer / DevelopersIn one pass:
1. Take two pointers, slow and fast, both pointing to head of list
2. Now move slow point node node next and fast pointer two node next
3. Keep moving until fast pointer reaches to END of list OR 2nd last node (depends on node count in list is odd or even), at this point, slow pointer is at the center of list.
Good thinking. at first it looks like it is faster but theoretically it has the same complexity as scanning the entire list and traversing to the median.
Because the number of element accesses is the same. i.e. for every iteration, slow pointer accesses 1 element and fast pointer accesses 2 elements --> total accesses 3n/2
which is same as normal traversing. i.e. same complexities but
Practically the time and space you are saving is any overhead for every iteration such as incrementing, checking conditions, any variable retrieval etc..
Neo, i feel it shud work faster. Say, if there are 10 elements, the slow pointer is going to move thru 5 elts (1-2-3-4-5) and fast pointer is move thru 5 elts again(2-4-6-8-10).. So ideally wouldnt it be twice the speed, than the normal soln of traversing n finding the median?
Anyway, the interviewer wud be impressed with this soln rather the naive method, for sure. Kudos Anurag!
@AB For the fast pointer to access the elements 2,4,6,... it has to use node.next.next. It uses 2 references. Hence, it uses the same time as the first method. I mean, the interviewer might actually be disappointed that you could not understand that it takes the same time for both and you chose the complicated way.
1. scan the list to compute the length
- Anonymous January 27, 20112. scan again to find the median
O(n)