Given two sorted linked lists, L1 and L2, a solution to compute their intersection L1 intersection L2.
+8
A:
L1_node = L1.head;
L2_node = L2.head;
Result = new SList;
while L1_node != NULL and L2_node != NULL:
if L1_node.value == L2_node.value:
Result.append(L1_node.value)
L1_node = L1_node.next
L2_node = L2_node.next
elif L1_node.value < L2_node.value:
L1_node = L1_node.next
else
L2_node = L2_node.next
(Translate to C yourself.)
KennyTM
2010-01-31 11:19:01
There's an error in that. In the == case, you're not skipping anything - you'll get an infinite series of L1_node.value.
Steve314
2010-01-31 11:26:51
Perhaps it was left as an exercise in debugging for the OP? If I was to hire someone, and posed this exact interview question, and got this exact solution back, I would question his motives for starting a job as a programmer if he simply parroted an answer he found online.
Lasse V. Karlsen
2010-01-31 11:40:26
@Lasse - maybe, and not a bad idea. My error below was deliberate, honest <hides face in shame at blatant lie>.
Steve314
2010-01-31 11:51:19
When it comes to homework and interview questions here on Stack Overflow, my gut reaction is to try to guide the person in the right direction, instead of just dumping the answer on him. When you're hiring programmers, you want people that can think, learn and apply, not people who can use Copy/Paste. Well, know-how of Copy/Paste is a bonus.
Lasse V. Karlsen
2010-01-31 11:53:31
@Lasse - agreed, when I think about it. Anyway, the skipping fix here isn't just a matter of copying one of the other cases - it still has a possible gotcha.
Steve314
2010-01-31 11:56:39
As for the underlying algorithm, one very much like it should be in any half-decent algorithms textbook anyway. Tape may be dead, but there's still arrays, bulk operations on tree data structures etc.
Steve314
2010-01-31 12:00:32
@Steve: Oops. Fixed. Thanks for spotting (and that's why you should use a standard library function instead of make one up yourself).
KennyTM
2010-01-31 13:19:06
@KennyTM - you're making a *unique* assumption - depending on something that Lasse leaves unstated, I think you may find it's still broken ;-)
Steve314
2010-01-31 13:47:56
@Steve: Now I don't know what's wrong. Even if the list has duplicated items (e.g. `[1, 2, 2, 2, 3, 4]` vs `[0, 2, 2, 4]`) the algorithm should still give the correct answer (`[2, 2, 4]`).
KennyTM
2010-01-31 18:38:32
@KennyTM - that's the point. You're assuming that non-unique inputs should lead to non-unique outputs. An intersection is a set operation, which kind of implies that may not be true - a set has unique values, so [2, 2, 4] isn't a set. My own solution (to the union) assumes that the output should be a set, but tolerates non-unique inputs - still producing a uniqued set as output. I made an assumption about an unstated requirement and guessed differently to you - it was seeing you code with a different assumption that made me realise the required output isn't unambiguously defined.
Steve314
2010-02-01 09:12:47
A:
The basic approach to in-order merge-like algorithms is that you never need to consider more than three items at a time - the front items from each input list, plus potentially a saved result.
In this case, I'd use...
loop forever
while in1.value < in2.value : transfer item from in1 to output
while in2.value < in1.value : transfer item from in2 to output
if in1.value == in2.value :
transfer item from in1 to output
discard item from in2
while in1.value == value just transferred : disard item from in1
while in2.value == value just transferred : disard item from in2
Now the nasty - this loop assumes the lists are infinite. How do you handle empty lists? That's fiddly, unless you can reserve a sentinel value which is greater than any legal value that can occur in the list.
If you can't reserve a sentinel, you can fake the effect - write a compare function that checks whether there's a next item in each queue before comparing values, and treats "queue exhausted" as implying the sentinel value.
That gives...
loop forever
while in1.value < in2.value : discard item from in1
while in2.value < in1.value : discard item from in2
if in1 exhausted, break out of loop
if in2 exhausted, break out of loop
if in1.value == in2.value :
transfer item from in1 to output
discard item from in2
while in1.value == value just transferred : discard item from in1
while in2.value == value just transferred : discard item from in2
OOPS
This is a union. Converting to an intersection is left as an exercise for the reader.
EDIT
OK - it is now an intersection. Just discarding the less-than items rather than adding them to the output. Also fixed a typo.
Note - my interpretation was that the output of an intersection should be a set, meaning no duplicates. This tolerates duplicates in the inputs, but the output is duplicate-free.
Steve314
2010-01-31 11:39:50