Thread: Two Questions: Reading a word at a time, and list intersection

Originally Posted by drshmoo

So given two char** lists, return the intersection in a char** format. It needs to be relatively fast as the point of this project is speed. I'm thinking I could qsort each list and then compare their contents, but that's technically O(n^2) with cutoff due to the sorted nature (every element still needs to look at every other element up to some point). If anyone knows any algorithms it'd be a great help!

The sorts should take O(n log n) time, so no, it would not be O(n^2).

If one list is already sorted with qsort(), then use bsearch() to perform a search, using the same compare function.

Originally Posted by drshmoo

each word in list1 would need to be checked at list2. Given that they are sorted, there will be a cut off, but there could be a worst case n^2. zubra would have to walk the entirety of list 2 before realizing it can stop looking, for example.

I don't get you. You would be maintaining pointers to elements of both sorted lists. Let's call these pointers p1 and p2, respectively:

Code:

if *p1 == *p2:
    ++p1
    ++p2
    add *p1 to intersection list
else if *p1 < *p2:
    ++p1
else:
    ++p2

So, the above pseudocode would be placed in a loop that terminates as soon as either p1 or p2 points one past the last element of list1 or list2, respectively. This algorithm should take O(n) time since in the worst case you traverse both lists to the end, at the same time, once.

Originally Posted by drshmoo

Does this need equal length lists to work?

No. You can add zzbra to the end of list 2 in the example you provided and then run through the algorithm to help you understand it.

By the way, since you don't need to worry about duplicates, you may find Salem's suggestion easier to implement since you can use bsearch to help you. The time complexity will be the same.

> zubra would have to walk the entirety of list 2 before realizing it can stop looking, for example. I'm sure theres a better way to do this though.
True, but then you know that everything which follows it CANNOT be in the list, since it's sorted and you've already walked off the end.

It's a modified linear search. You always start at the point where you got to (no point in returning to the beginning), and there is no point in going all the way to the end.
list 1: Benny, Calum, Carl, zubra, zzbra
list 2: Aztec, Boris, Carl, zebra

So
Benny starts at Aztec, gives up at Boris
Calum starts at Aztec, gives up at Carl (but notes Boris is the last of the words before it)
Carl starts at Boris(is before Carl, because it was before Calum), stops at Carl (a match), and moves the start point to Carl
zubra starts at Carl, falls off the end of the list
zzbra, well, we've already got past the end, so it's not there.

> zubra would have to walk the entirety of list 2 before realizing it can stop looking, for example. I'm sure theres a better way to do this though.
True, but then you know that everything which follows it CANNOT be in the list, since it's sorted and you've already walked off the end.

It's a modified linear search. You always start at the point where you got to (no point in returning to the beginning), and there is no point in going all the way to the end.
list 1: Benny, Calum, Carl, zubra, zzbra
list 2: Aztec, Boris, Carl, zebra

So
Benny starts at Aztec, gives up at Boris
Calum starts at Aztec, gives up at Carl (but notes Boris is the last of the words before it)
Carl starts at Boris(is before Carl, because it was before Calum), stops at Carl (a match), and moves the start point to Carl
zubra starts at Carl, falls off the end of the list
zzbra, well, we've already got past the end, so it's not there.