Questions d'entretien

Entretien pour Software Development Engineer II

-Redmond, WA

Microsoft

You have two linked lists that merge at some node. The lists could be billions of nodes long. Find the node where the lists merge in the most optimal time while using a low amount of memory.

Répondre

Réponses aux questions d'entretien

5 réponse(s)

2

Above answer is not correct. Its a list so you can only start from the begininning. If its a doubly linked list, yes, you can start at the end (and should), but you cannot start "mid-list".

Utilisateur anonyme le

0

I can think of two ways: 1) traverse from both heads, get two length: long, short traverse again starting from Array1[long-short] and Array2[0], looking for the same pointer O(4n) time, O(1) space 2) use a hash table holds all seen pointers. traverse from both heads O(2n) time, O(n) space

Eric le

0

Step 1: if the linked lists are not empty, find the length of each linked list. Since they have a common end point, we will get length of common area of the linked lists too. Step 2: find the difference between the length of both list. Start traverse the biggest list till the difference in length between them, provided one of them is bigger than the other. Step 3: now they are at the same remaining length. Traverse both of the together till both are pointing to the same next node.That node is the common node which is the merging point. If there is no such point, then they are not merged.

BVarghese le

0

Suppose x nodes before merged node for List1, and y nodes before merged node for List 2, z shared nodes for two Lists. List1.Length = x + z List2.Length = y + z Traverse List1, List2 to get their lengths. List1.Length - List2.Length = x - y Starting traverse at same time from (x-y+1)th nodes of List1, and head of List2 (when x>=y) or Starting traverse at same time from (y-x+1)th nodes of List2, and head of List1 (when x<=y) till they point to the same node, that node is merged node. otherwise, no merged node

lol le

2

If the lists have a length value, then you should be able to do this pretty simply. If two lists merge, then they have the same terminal node. That means that from the merge node to the end they have the same length. So if you subtract the smaller lists length from the larger you end up with a great starting point to begin searching. you then increment down the lists from that point on to find the node where both lists meet.

Scott le

Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.