Hacker News Reader

Comment by tantalor | Hacker News Reader

As written this problem is impossible to solve.

Proof: suppose there is only 1 infinite stream which is always descending. You will never find a lowest value, so you cannot rewrite the stream "in order".

View on HN

The question is not clear but I assume the ordering is meant to be on some kind of timestamp, so the streams would each be increasing

Depends. If there is a minimum value, every value will appear, and you don't want dups, then this is doable. Say the streams are of natural numbers starting with 1, and every natural number will appear within each stream. The obvious thing to do is to not even bother doing anything with the streams except to drain them, and just write the natural numbers in order to stdout! Yes, I'm chuckling.

It's a trivial toy problem. It's not a useful problem to solve. But the question may be there just to get you to think of just this, and to ask questions.

it's not impossible to solve, but there are situations like that which make any solution not work, which was a follow up question

I came looking for how this could possibly be solved. Could you help me understand?

If the input is infinite and unordered and the task is to produce output in order, how do you know when it’s OK to start writing output?

Sorry, I was paraphrasing the question and not giving every detail that I received. They also stated that there are no gaps, the values increment by one, and start at zero.

How is that "in an unordered fashion"? It sounds pretty ordered to me!

The data itself is ordered (which is why the task is to print them in order), but the order you receive the values is can happen in any order (ie the processing was split into multiple threads and each thread is posting back the results from the work).

Ah then that's the classic "merge k sorted streams" question. It's a good question and easy to solve in a coding interview. Good candidate should be able to solve in about 30 minutes. My favorite solution goes something like "put values in a heap and then read them back out" because you only need to read 1 value from each stream at a time.

Yep, that was my same approach as well.

That could be part of the question.

At one job interview I was deliberately given a problem which had no efficient solution. The idea was to find a heuristic which would get close to the optimal solution and run in a reasonable time.

I got one of those at a FAANG interview. I was a bit less experienced and less confident at the time so I left the interview thinking I was misunderstanding some fundamental CS laws.

Reply on news.ycombinator.com