## PayPal Interview Question for Software Engineer / Developers

Country: India

Comment hidden because of low score. Click to expand.
5
of 5 vote

use 3 pointers...
1st 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..

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

One pass approach is inefficient.. think of large scale.. million/billion list entries.. it gets stumped as it will traverse N+2N/3 times.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0

Always exercise caution when you write pointer1.next.next ... Cos if pointer1.next == null then next.next will be null pointer exception .. I was corrected by the intervievwer on this .. so always check for null condition ..

Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.