Algorithm questions. See if you can get these!

[ones3k]

Suppose we have k streams { s0,s1,s2,s3,...,sk }. Each stream contains integers in sorted order, and each stream could potentially be infinite in length. How would you merge these k streams into a new stream S, such that S is in sorted order. Do this as efficiently as possible.

*BY sorted order, i mean that element i is >= element i-1 for all i.

*A stream is just basically an abstraction of a list. All you can do is view the current element, or advance the stream to the next element.

for instance if i have a stream of the set of integers > 0 = {1,2,3,....} and the start of the stream is the 0th element = 1

I can view the current element (1) or i can advance the stream to index 1 and so forth. Get it?

This is enough information to do the problem. It's trickier than you might think. Keep in mind, there is the obvious solution, and then the optimal solution.

 

[PottedMeat]

*sniff* *sniff* - does anyone else smell homework?

 

[dowxp]

I'll upload the .sln zipped in 5 minutes.

but seriously,

insert all integers into a vector. then <function> sort it. done !

 

[ones3k]

You cant insert them all into a vector, they could be infinite streams.

 

[Atheus]

There isn't really enough information there... does increaing order mean each stream goes n=1,2,3,4 or can n+1 be any number higher than n? do they all produce numbers at the same speed or different speeds? or can you request the next n and it will appear immediately?

 

[ones3k]

BY increasing order, i mean that element i is >= element i-1 for all i.

A stream is just basically an abstraction of a list. All you can do is view the current element, or advance the stream to the next element.

for instance if i have a stream of the set of integers > 0 = {1,2,3,....} and the start of the stream is the 0th element = 1

I can view the current element (1) or i can advance the stream to index 1(2) and so forth. Get it?

This is enough information to do the problem.

 

[CTho9305]

It's absolutely trivial (it should be obvious if you've taken an intro programming class or understand the basic sort algorithms), really sounds like a homework question, and is not highly technical.

 

[ones3k]

The obvious solution is selecting the min out of the k streams and incrementing the corresponding stream for every access on the new stream S. This is an O(k) operation. Can you do better than O(k) ? I think you can.

 

[dowxp]

I think I can too.

 

[ones3k]

I dont want to give out the solution, try to get it. Its a fun little problem.

 

[DrPizza]

Okay


Ahhhh, done. That was a fun little problem. I'm not sure that everyone else has had the chance to work on it though. So that you or I don't give away any spoilers, depriving everyone of the fun, why don't we wait until Wednesday, when you can post the solution for everyone By that time, everyone will have had a chance to work it out.

What day is your homework due again?


edit: the only thing worse than someone asking for help with homework is someone denying that it's homework. I can't recall how many times someone has asked for hw help and actually received it. But, if everyone else is like me, we find it very... what's the word?... when someone can't be honest with us.

 

[koshling]

Hint - the solution (I believe) is O(ln k) (for serial hardware at least)

 

[Xyo II]

Originally posted by: CTho9305
It's absolutely trivial (it should be obvious if you've taken an intro programming class or understand the basic sort algorithms), really sounds like a homework question, and is not highly technical.

did somebody say programming forum?

 

[ones3k]

Originally posted by: koshling
Hint - the solution (I believe) is O(ln k) (for serial hardware at least)

lol why would it be ln(k) = log (base e) (k) ? opposed to log(base 2)(k) ??

The solution is is indeed log(k) (base2 of course).

if you access n elements from the composite stream S, the run time will be O(nlog(k))

 

[mjia]

The base doesn't matter in Big-O notation.

 

[imported_plasmasnake]

Base of logs doesn't matter...

Edit: Sorry, mjia beat me to it...

 

[sdifox]

This takes me back to the days of Computability and Complexity. About the only thing I remember from that course is P and NP

 

[Tshirt]

Here's a quick-n-dirty explanation:
You keep a min-heap H of pointers to first elements of the streams.
Then you keep doing
1. m <- extract-min(H) #on the heap,
2. push(sortedList, m.value)
3. m = pop-stream(m.stream) # from the stream of the element
4. insert-heap(H,m) #update the heap

complexity of each operation
1. O(1)
2. O(1)
3. O(1)
4. O(logk)

so you will be able to increase the length of the new sorted stream by O(1) with
time cost of O(logk).

 

[icelazer]

This looks a lot like Question 1

 

[Fox5]

Originally posted by: koshling
Hint - the solution (I believe) is O(ln k) (for serial hardware at least)

That would be execution time, but what's the answer?

During a 3 hour cram session for the AP computer science AB exam last year (I took it on a whim, despite not having the class for it) I came along a lot of crap like this, wikipedia should easily turn up the answer. I'm sure this question was even on the test, though like anything else in a 3 hour cram, it's quickly forgotten.

 

[Matthias99]

Originally posted by: Fox5

Originally posted by: koshling
Hint - the solution (I believe) is O(ln k) (for serial hardware at least)

That would be execution time, but what's the answer?

Basically, take one element off of each incoming stream and build a heap/tree out of them (and keep track of which stream each element came from). Then pull the lowest element out of the heap/tree, and insert the next element from the corresponding stream into the heap/tree. The lowest element in the heap/tree is always the next element in the sorted stream.

Using proper algorithms for the heap/tree, this works out to O(log_2 k) time amortized for each element you process, and requires O(k) storage.

 

[uOpt]

If each of the input stream can be infinite in length, and if the range of the integers is unlimited, you cannot solve this.

To illustrate, your output stream has to start with the lowest number ever appearing in the input stream. But at no point in time you can prove that the lowest number you have seen so far is the lowest you will ever see. So you can never start giving out elements on the output stream.

 

[Matthias99]

Originally posted by: MartinCracauer
If each of the input stream can be infinite in length, and if the range of the integers is unlimited, you cannot solve this.

To illustrate, your output stream has to start with the lowest number ever appearing in the input stream. But at no point in time you can prove that the lowest number you have seen so far is the lowest you will ever see. So you can never start giving out elements on the output stream.

The input streams are sorted (which is kind of important; please read puzzles/problems carefully before responding to them).

You can solve it as I outlined above (and also given later in the other thread referenced above). Indeed, if the input streams were not sorted, it would be impossible to solve (it would require O(n) storage and time, where n is the number of elements in total, and n is potentially infinite).

 

[Wentelteefje]

This reminds me too much of college... I didn't like it back then... Or not this kind of exercices...

Man, it would even take me hours to decypher just what is actually asked, let alone solve it! But nice you can guys can come up with a solution for this! :thumbsup:

 

[uOpt]

Originally posted by: Matthias99
The input streams are sorted (which is kind of important; please read puzzles/problems carefully before responding to them).

Oh. I think that explains why I do badly at puzzles