PayPal Interview Question
Software Engineer / DevelopersCountry: India
Your solution is not terribly efficient. How about just using only one pointer. Walk the whole list and find N. Now walk again and report N/3rd node and 2N/3rd node. The O(N) is the same.
Seems like an pretty trivial question. Maybe the interviewer is expecting how will you maintain a linked list such that a 1/3rd and 2/3rd query could be answered as efficiently as possible ?
I second original solution. This problem is a variation of classic "Find the Middle of LL" problem. Original method traverse n + 2n/3 + n/3 = 2n elements in total, whereas your approach traverses n + 2n/3 = 5n/3. But, the former method is likely to have many cache hits, while your approach won't have if the list is too big, say, 10M entries. So the run time would be much faster in original method.
Fastest solution is too obvious. Read the list to an Array, and print n/3rd and 2n/3rd index element. It needs n traverses and O(n) extra memory.
If the interview is not happy with that, give solution based on skip list. O(log N) loop up for k-th position element is achievable on average.
There's definitely not guaranteed to be a big difference in cache performance. I would prefer the two-pass approach because it more easily generalizes to more complicated cases.
Two pass approach is little bit more efficient for it traverses 1 2/3 of the full length of the list, while the one pass approach actually takes two full length traverse (1 + 1/3 + 2/3).
static Node mid;
public static Node FindMid(Node pointer1, Node pointer2)
{
if (pointer1.next != null && pointer1.next.next != null)
{
pointer1 = pointer1.next.next;
FindMid(pointer1, pointer2.next);
}
else
mid = pointer2;
return mid;
}
use 3 pointers...
- Anonymous September 23, 20111st pointer pointing to the 1st node..
2nd pointer pointing to the 2nd node..
3rd pointer pointing to the 3rd node...
1st pointer move one time
2nd pointer move two times..
3rd pointer move three times...
when the third pointer reaches the end of the Linked List..
1st pointer pointing to the 1\3 rd node
2nd pointer pointing to the 2\3 rd node..