Optimizing this algorithm

I don't quite understand your question, but binary search is O(logn) which is so much better than O(n).

Here's a simpler problem. Solving this problem will make it easy for you to solve your problem.

You have two stacks of cards. Each stack contains lots and lots of cards, each with a number from 1 to a billion. Each stack is sorted from lowest to highest. Your task is to determine if the two stacks have any cards in common.

But there's a complication. You can only see the card on top of each stack at any one time (no rifling through the stack). And once you take a card off the top of a stack, you have to throw it away and never think about it again. In other words, you only get one pass through the stacks.

How do you do this?

I'll look into hashing. Looks like i'll have to scrap that idea. It's a non-essential part anyways. Spent to much time on this today already. Got a headache...

Quote:

Original post by Sneftel How do you do this?

oooo - pick me pick me *jumps up and down with hand in the air*

Well, Sneftel has the answer for you, but why didn't you just ask your coworker how to do it? If they know how, then it would be a lot faster than posting here and waiting for response.

karg

- Compare the first 3 values for a match.
- Within a loop begin at the beginning of each array.
- Chose the largest result as a baseline and increment the index of the other arrays independantly until their value is greater or equal to the chosen baseline value. Compare for a match after each increment in index.
- repeat until the arrays are exhausted.

OR:

- Within a loop begin at the beginning of each array.
- Compare current three values for match
- Increment the index of the array with the smallest value, but don't overflow it. Establish a Tie-breaking rule for multiple same values.
- Repeat until all arrays are exhausted.

The second method is a cleaner implementation.


[EDIT] - Added the bit about comparing after each increment and put the first comparison before the loop.

[EDIT] - Added second algo.

My coworker is sort of an asshat, i bet this algorithm is probably not even optimizable to O(n). All three arrays have different sets of sorted numbers. There might not even be a number that occurs in all arrays. That's why I need to do this.

Quote:

Original post by Karg Well, Sneftel has the answer for you, but why didn't you just ask your coworker how to do it? If they know how, then it would be a lot faster than posting here and waiting for response.

where's the fun in that?

Quote:

Original post by MOVSW My coworker is sort of an asshat, i bet this algorithm is probably not even optimizable to O(n).

How can you bet that if someone has ALREADY explained how to do it in O(n) in this very thread?

I guess I took to long to write that post.

As a side-note: you can early-out when the values of the 2 remaining arrays are larger than the value of first array to reach the end.

If you're implimenting it as I stated, go with the second, cleaner one. The first implimentation is actually pretty cracked-out in comparison. It was just the first way that came to mind. I'd drop it like a bad habit in favor of the second.

Actually, using a binary search on the two inner loops would increase the speed quite a bit. It would be O(a*logb*logc), which is a lot better than O(a*b*c). (You should also make sure the outer loop works with the smallest array.) However, your co-worker is right, there is an even better way to do it.

bool bDone = false;int ai=0, bi=0, ci=0;while(!bDone){  if(a[ai] == b[bi] && b[bi] == c[ci])    break;  else  {    if(a[ai] <= b[bi] && a[ai] <= c[ci])      ai++;    else if(b[bi] <= a[ai] && b[bi] <= c[ci])      bi++;    else if(c[ci] <= a[ai] && c[ci] <= b[bi])      ci++;    if(ai, bi, or ci went out of bounds)      bDone = true;  }}if(!bDone)  cout << "Match found";

I believe that should do the same thing, and it's O(a+b+c). The algorithm takes advantage of the fact that all three arrays are sorted, and it keeps bumping the index that has the smallest value up until all three match or the end of an array is hit. It would also be easy to modify this algorithm to return a list of matches. Instead of breaking out of the loop, just add the three indices to the end of a list.

EDIT: This is the same solution Ravyne posted, but you didn't seem to notice that he had provided the solution.
EDIT: Either that, or I didn't notice what you meant by "I guess I took to long to write that post." ;-)