Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Friday, November 5, 2010
sharing lists.
Given 2 linked lists find intersection point(s) in the form of X (so the lists share only one element), or Y (so the lists share more than one element). How many other shapes can you have?
The lists are either disjoint or they coverge and stay converged somewhere in a Y shape. The trick is to find where that Y convergence happens. I'm assuming you can't modify the list to hold a bit of data (or you could just set it like a trail of bread crumbs and notice when you've entered a node with the bit set.) I also assume you have limited storage (or you could just make a double linked copy of the sets, or a hash table for that matter.) Answer: start at each node and COUNT the distance to the last node, giving you two distances d1 and d2. Step the longer node forward (d2-d1) nodes (assuming d2 was the larger one.) Now you have a "Y" diagram but you know both forks of the Y have the same size. Step both nodes together, check for convergence, and repeat with pairwise steps until they converge.
If the linked list is singly linked list, then it cannot share more than one element.
ReplyDeleteThe lists are either disjoint or they coverge and stay converged somewhere in a Y shape. The trick is to find where that Y convergence happens. I'm assuming you can't modify the list to hold a bit of data (or you could just set it like a trail of bread crumbs and notice when you've entered a node with the bit set.) I also assume you have limited storage (or you could just make a double linked copy of the sets, or a hash table for that matter.)
ReplyDeleteAnswer: start at each node and COUNT the distance to the last node, giving you two distances d1 and d2. Step the longer node forward (d2-d1) nodes (assuming d2 was the larger one.) Now you have a "Y" diagram but you know both forks of the Y have the same size. Step both nodes together, check for convergence, and repeat with pairwise steps until they converge.