Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
April 10th, 2013, 06:16 PM
 so.very.tired
Contributing User

Join Date: Nov 2012
Posts: 127
Time spent in forums: 1 Day 7 h 16 m 14 sec
Reputation Power: 2
A true challenge.

I need to find an algorithm for the following problem:

Given two linked lists that intersect somewhere in the middle and merges into one list, I need to find an algorithm that finds the intersection point, with these limitations:
1. I'm not allowed to change, add or remove any data from the linked list (including its pointers).
2. I'm not allowed to use hash table (any other data starcture is acceptable - linked lists, arrays, pointers, counters).
3. given the following lists:

complexity should be O(K) (K=max{L,M})
(in the given situation, N is significantly bigger than K, therefore O(N) complexity will not be a good idea).

Is this problem have a solution?

#2
April 12th, 2013, 04:55 PM
 MBirchmeier
I <3 ASCII

Join Date: Aug 2003
Posts: 2,399
Time spent in forums: 1 Month 2 Weeks 2 Days 21 h 23 m 18 sec
Reputation Power: 1232
I can't do it in O(K) but I can do it between O(K log K) and O(K^2) with a binary tree.

I don't think it's possible to complete this with linear complexity. (But would be happy to be proven wrong)

-MBirchmeier
__________________
My fiancee's transition from accountant to writer
0x4279 7465 204D 6521

#3
May 4th, 2013, 05:46 AM
 so.very.tired
Contributing User

Join Date: Nov 2012
Posts: 127
Time spent in forums: 1 Day 7 h 16 m 14 sec
Reputation Power: 2
Quote:
 Originally Posted by MBirchmeier I can't do it in O(K) but I can do it between O(K log K) and O(K^2) with a binary tree. I don't think it's possible to complete this with linear complexity. (But would be happy to be proven wrong) -MBirchmeier

I found the solution.
and you're right. It can't be done in O(k), unless you allow manipulation of the list's pointers.
can you figure out how?

Last edited by so.very.tired : May 4th, 2013 at 05:33 PM.

#4
May 7th, 2013, 09:25 PM
 jwdonahue
Contributing User

Join Date: May 2004
Posts: 3,417
Time spent in forums: 3 Weeks 5 Days 12 h 51 m 9 sec
Reputation Power: 886
If you know the length of M and L (if L has a node counter, it should include the length of N) , it's really easy. Just walk down L for L.depth - M.depth, then walk both of them until you hit the common node. Depth counters are cheap if you have just one per list.
__________________
I no longer wish to be associated with this site.

#5
May 14th, 2013, 08:08 AM
 so.very.tired
Contributing User

Join Date: Nov 2012
Posts: 127
Time spent in forums: 1 Day 7 h 16 m 14 sec
Reputation Power: 2
Quote:
 Originally Posted by jwdonahue If you know the length of M and L (if L has a node counter, it should include the length of N) , it's really easy. Just walk down L for L.depth - M.depth, then walk both of them until you hit the common node. Depth counters are cheap if you have just one per list.

if you know the length, then yes, that's pretty easy.
the thing is - you don't know the length of M and L, and any attempt to count them will cost you O(n), and we're looking for O(K).
again - you have to manipulate the pointers somehow...

Last edited by so.very.tired : May 14th, 2013 at 08:12 AM.

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > A true challenge.