Friday, June 22, 2012

Running on linked list :)

As a widely used data structure in both academia and industrial, linked list is a critical concept, which often appears in technical interview. In this blog, I will not show the basic implementation of LL. You may found it in your textbooks. However, few advanced questions in bird view are presented. By analyzing those questions, I hope you could build up a scene that how to manipulate linked list and some properties of LL.
Question 1: find the last K node of a given linked list;
Suppose you have a singly linked list L, please return the last K node in the list.
Solution: this problem is trivial. We could define two pointers, p1 and p2. We move p1 to the K-th node in the list and then move both pointers to the end node concurrently. Once p1 reaches the end, p2 points to the last K-th node.
Question 2: How to detect two linked lists merge or not;
Suppose you have two singly linked list, L1 and L2. Return true if those two lists merge at a arbitrary node; otherwise, return false.
Solution: This question is also trivial. If two lists merge, the end node must be the same. If we go through those two lists and end at the some node, we return true. Otherwise, they do not merge.
The method mentioned above need an assumption, there is no loop in both lists. If there is a loop, the method above will not work. If we could detect whether a loop is in the list, we could have the following generic algorithm to determine the return value.
detect loop
if no loop in both list, compare the end node;
if there are loops, check the node in one loop. If it is also in other loop, then they merge; otherwise, then do not.
Question 3: How to detect loops in a linked list;
Give you a singly LL, detect whether there is a loop in it.
Solution: the answer to this problem is really interesting. We could define two pointer, Fast and Slow. Fast pointer moves two nodes per time and Slow move one step each time. If there is a loop, those two pointers will meet in a position in the loop. In order to make the correctness easier, we assume that the length of the linked is upper bounded. We move the pointers until touch the upper bounder, which could guarantee we wont stop before enter the loop.
If we move this question a little further, how to find the beginning of the loop? Suppose the LL looks as follows:
image
The speed of those two pointers are 2 and 1. when they meet, if the total length of Slow moved is S, the Fast should have moved 2S. In addition, Fast moved n loops more. If the length of loop is r, we have nr = S. S can be replaced by a + x, the distance between loop enter point and meet point. So we have:
a + x = nr =  ( n - 1 )r + L -  a
Then:
a = ( n - 1 )r + ( L - a - x )


( L-a-x ) is the length between the meet point and the next loop enter point. So, if release another two pointers, Slow, at first node and meet point, they must meet at enter point of the loop, as ( n –1 )r will be cancelled by the loop.

Question 4: There is a straight track on the ground. Two robots randomly placed on the track. You need to deploy program on both robots. By executing the same program, they must collide each other.( This is a real interview question from Microsoft Advanced Technology Center in China )
There are four instructions in the instruction set:
  • go left
  • go right
  • check. Return true if the other robot visited current position, otherwise, return false;
  • jump, jump to any position in the program;
Solution: This question is easier than the Question 3. We could write a program like follows:
start:
if(at the position other robots have not reached)
    move_right
if(at the position other robots have reached)
    move_right
    move_right
goto start


The idea of this algorithm is initiative. If one robot found the other one is in front of it( the position visited by the other robot ), it runs faster to catch up.

1 comment:

  1. For a friend who show off in front of me and a friend who is being tortured by Linked List :)

    ReplyDelete