Want a Free Job Posting?

Buy a job posting today and the second one is on us. For a limited time only. Act Now.

Interview Question

Interview New York, NY

Some problems were quite difficult for this position. Maybe

  the interviewers didn't like me personally. Check if two linked list intersect, if so, find the intersection point. Travelling salesman problem.

Interview Answer

2 Answers


I think the followings are pseudo enough...... --------------------------------------------------------------------------- a = length of ll1, b = length of ll2, c = abs(a-b); do -> ;traverse (longerlist = a > b ? a : b) by c times end do do -> ;traverse (a AND b) in parallel node after node ;if the node at both a and b are the same address -> return this node

Dekus on Sep 17, 2012

@Dekus What do you mean by traverse and in parallel? If you do it in parallel, (i++, j++ equivalent) you are making the assumption that the lists are aligned, and the intersection happens at the same place in both of them. Also, the first portion does not make sense. Consider the case wherethey are singly linked lists and two nodes point to 1. My suggestion: traverse a list, and map (hashtable) the addresses of the next pointers to a boolean. <int32, bool> then go through the other list and check to see if any next pointers are in the hashtable. This would be time: O(N + M) and space: O(N)

Mikhail on Oct 9, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.