> Q: Assume that you have an infinite stream of data that is coming in from multiple threads in an unordered fashion. Write the stream items to the console in order.
If I were the interviewer I would be interested in what clarifying questions the candidate would ask and/or how they would highlight parameters and assumptions needed because the question is vague to the point of being unanswerable otherwise.
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".
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.
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.
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.
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.
If I were the interviewer I would be interested in what clarifying questions the candidate would ask and/or how they would highlight parameters and assumptions needed because the question is vague to the point of being unanswerable otherwise.