Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
1) Find lengths of two linked list O(n1) + O(n2)
2) Find the long list and skip the (long list length - short list length) nodes
3) Now walk the two linked lists together (in parallel one step/move-next at a time), and compare the values of two nodes (just compare node address if the lists are already joined). Return the node value/address where the euality check succeeds. O(min(n1, n2))
???
Why would you blindly skip nodes in the longer list? The question asks you to look for the intersection between the two lists. What guarantee do you have that the first (LongerList.Count - ShorterList.Count) Nodes in the LongerList are going to be non-intersecting elements?
Because when intersection point is somewhere after these nodes only. like 1-2-3-4-5 and 3-4-5. first 2 nodes can be skipped.in a Y shaped intersection.
Walk second list and insert all elements in a hash.
- Anonymous October 29, 2011Walk first list and if an element is already in hash it is the common element.