Yahoo Interview Question
Software Engineer / DevelopersKay your solution is neat. Could there be more ways of solving this with the same efficiency?
Please find the solution with O(n):
1) Have a queue that will have last M elements traversed by the pointer X.
2) Now traverse the linked list with pointer X.
2.1) Add queue with current traversed value.
2.2) Dequeue the element if Total of elements exceeds the Last M lements.
3) Once you reach the last elements, the element that you dequeue from the queue will be Mth Last element of the Linked list.
Have 2 pointers, say 'p' and 'q'. Initially they point to the head of the linked list. Now, increment the 'p' pointer 'm' times. Then, go on incrementing both 'p' and 'q' pointers by 1, till the 'p' pointer reaches the end i.e. null.
- kay June 08, 2007Pointer 'q' is your solution!!