Amazon Interview Question
Software Engineer / DevelopersLet L1 and L2 be the two lists.
1)find len1 = L1.length, len2 = L2.length
2)reverse the list L1
3)find len3 = L2.length
4)len1 + len2 - 2x = len3 - 1;
5)Now "x" is the common portion of the Y formed by the two list.
6) Reverse back the list L1.
7)(len1 - x/2)th node in the list L1 is the starting point of the Y
1) len1 = L1.length , len2 = L2.length
2) common = len1-len2(whichever is greater accordingly)
3)move forward in the bigger list "common" times
4) now start moving forward in both the lists and compare addresses.
An alternative to scanning both the lists and reversing is as follows:
L1-> 1,2,3,4,5,NULL
L2->4,5,3,4,5, NULL
Advance the L2's node by 1
Compare if L2.Current == L1.Current || L1.Next == L2 || L2.Next == L1
If above fails
Advance the L1's node by 1
Do the above condition
Put this in a while loop until L1 && L2 != NULL
Both Current & Next are addresses.
@KBSorter
Exactly reversing "list1" will make "C point to B", but still "I points C"(we never touched list2).
So i can start from T(list2) and reach A(list1). This is exactly the "len3" i have mentioned in my previous post.
When we again reverse back list1, everything will be fine. C will point back to D. Already I points to C, so we have everything in place.
Another way of representing Thiyaneshwaran solution.
Image inverted tree
. A
.B > > .C > > .D
ACD and BCD are two list. Find BC or AC.
AC + CD = k1 ........(1)
BC+ CD = k2 ........(2)
After Reversing the list BCD to DCB,
. A
.B < < .C < < .D
AC + BC = k3 .......(3)
Solving Equations for three variable in three equations, One can find AC / BC
AC + CD = k1 ........(1)
BC+ CD = k2 ........(2)
AC + BC = k3 .......(3)
Thanks
Ankush
If i'm reading this right, the intersecting node is the converging node. Beyond this node, both lists will have the same number of nodes. So, why can one not do this?
1. Find the length of both lists.
2. Skip longer-shorter nodes on the longer list. (now both nodes are equal in length)
3. do the below
while (list1->next!=null && list2->next!=null) {
if(address of list1->next == address of list2->next) break;
list1 = list1->next;
list2 = list2->next;
}
print the converging node. Additionally we could run counters for both lists and give the index of the converging node.
Alternative Approach:
1) Create a HashMap/Hash Set of Node address values.
2) Start From the head of LL1, and traverse each node, and insert the address of that node in Hash_map. Do this till the First List is exhausted.
3)Now start from head of LinkedList 2, For each node Address, check if the value is already present in hash map. If no then move to next node. If yes, then we have reached the Intersection point
Solution:
1.traverse and find the length of both the lists and now traverse biggest list with big_len-small_len and after that traverse both the list by 1 and you will find them meet at one point if they have any intersection.
2.Create a hashtable.traverse the first list and make entry into the hash table and now traverse the second list and find whether the entry has been already made or not.
@Thiyaneshwaran: Reversing the lists will not work
- kBSorter November 10, 2009A->B->C->D->E
T->F->I->C->D->E
In these two lists, node C is the same memory location. Reversing list1 will make C point to B, breaking the link between C->I.
The correct solution will be to find the difference in length, skip those many nodes in the longer list. Start comparing the next addresses of the nodes in the lists. When there is a match that is when the intersection starts. In the example mentioned above, the difference in length is 1. Hence you start from F->next with A->next. I->next = B->next. That is when you conclude the intersection has started.