6 ms·
How do you sort an infinite stream?
by thedance 7y ago
How do you sort an infinite stream?
- glofish 7y agothe post was getting too long to put in all the details, but basically, what I was getting at, imagine the data comes in batches and you have to retain the N largest seen so far
- minimaxir 7y agoIMO, that's not an appropriate question for a data scientist. Maybe it's better for a data engineer or a SRE.
- glofish 7y agoBasically you are saying that you cannot think of a way of doing this, other than the most inefficient way --> hiring a new person This answer would make you fail the interview :-)
- nhumrich 7y agoOr pass the interview if it was a management role
- aprdm 7y agoIt's honestly pretty ridiculous seeing your tone in the comments and how you think that highly about your bad interview questions and your flawed conceptions about the solutions, including CSV and TSV confusion. This smile makes it embarrassing even. Hope I never pass your interview!
- nutjob2 7y agoThe question is ambiguous and misleading or just simply nonsensical. This sort of thing is sadly common in interviews, where the interviewer some arbitrary answer in mind and expects you to read his mind, which is possible only some of the time. By definition you can't sort an infinite list. You've conveniently turned the question, in your mind, into something like "how do you efficiently maintain an ordered list of incoming items?"
- J5892 7y agoO(∞)
- deleted 7y ago[deleted]
- throwlaplace 7y agoby using an N element max/min heap and evicting the max/min when a new element comes in that's less than the max/greater than the min (note this is also a leetcode problem https://leetcode.com/problems/k-closest-points-to-origin/ https://leetcode.com/problems/k-closest-points-to-origin/)
- glofish 7y agonothing wrong with knowing the answer or where to look it up, I don't get what your point is the purpose of the interview is to filter out people that do not know the answer or have pre-learned something and don't fully understand its applications. When you are in a dialog it is a very different dynamic, people that would not ask a question because it is already posted on leetcode are the problem the OP complains about
- deleted 7y ago[deleted]
- ummonk 7y agoYou could have a balanced data structure and keep inserting into it.
- nutjob2 7y agoSorry, you failed the interview! Your algorithm doesn't terminate, it's no better than an empty infinite loop. If a list is sorted, then you'd be able to return the largest value. Since that is impossible the correct answer is that it's impossible.
- downerending 7y agoSince no one else got it, I'd start by allocating an infinite array to ingest the stream into.