Amazon Interview Question
Software Engineer / Developers@sai
ur code is not clear
first of all before the check, if( m > n), p and q both are already null, doing p->next or q->next will make the pgm crash.
now even if i assume, that u did node *p=L1, *q=L2; before if (m>n), then wat is the use of incrementing ptr p by 1 node or q by 1 node... u r not using m and n later at all.. thr is no loop.. explain wat u r trying to do..
Say, the link lists are of length m and n.
The easiest way is to take each element of first linked list and compare with all the elements of 2nd LL. ... O(m*n)
Sorting the linked list is tougher, but if we can sort in O (n log n), then we sort both the lists and intersection can be found in O (m+n) time.
After sorting, we just go through both LL and compare the elements.
Thus total time complexity would be: O(m log m) + O(n log n) + O(m+n)
== O(m log m) if m > n
How to sort in n log n time??? Can use Merge Sort. Look for a merge sort that is optimized for LL.
If there is no restriction on Space, We can just do the foll:
Say length of List 1 = m . Length of list 2 = n
Iterate through list1 make each element a key in the hash table.And count as value of key.
Iterate through list2. If key already exists, increment count; else skip element.
After the 2nd list is done, all elements in the hash table forms the intersection set.
So this should be O(n+m)=> iteration through both lists + O(n) => Iteration through hashtable. = Linear Time
- Reverse both the linked lists
- Traverse from the head of the reversed linked lists to the nodes of both the LLs.
- If next node is different at any position, then that's the point of intersection
- siva.sai.2020 December 15, 2010