[interview question] design uber-iterator

VMware
jump++

Go to company page VMware

jump++
Aug 27, 2021 7 Comments

Was asked this in my interview. Posted it in LC but didnt get much response. It's been eating at me as I tring to find a simple and intuitive solution. Its similar to merging 2 sorted arrays but no pointers as this is a stream. Thoughts??

Problem statement:
You're given 2 integer iterator objects of type Stream
//guaranteed to give non decreasing output for getNext
interface Stream{
int getNext();
boolean hasNext();
}

Given Stream s1 and s2, design a datastructure (uber iterator) that takes these streams and outputs getNext andhasNext

class UberIterator{
Stream s1, s2;
int getNext(){
//write code
}
boolean hasNext(){
//write code
}
}

Sample output. Lets say s1 and s2 have the following getNext streams.
s1: 1, 3, 7, 11, 23
s2: 2, 5 , 7, 10, 14

Required Output of UberIterator (getNext): 1, 2, 3, 5, 7, 7, 10, 11, 14, 23

Follow up: How to generalize with n stream objects??? #swe #interview #faang

comments

Want to comment? LOG IN or SIGN UP
TOP 7 Comments
  • Google
    lcxt

    Go to company page Google

    lcxt
    Easy.

    You just always need to store N values and their stream source. One for each non empty stream.

    Then pick the highest value and pull the next one from that stream.

    Store the current state in a heap and call it a day.

    struct s {stream source; int val}
    // Stream containers ordered by min val
    heap[s] streams;
    HasNext(){ return !streams.empty()}
    GetNext(){
    s = streams.Poll();
    v = s.val;
    if s.s.hasnext() {
    s.val = s.s.getnext()
    streams.offer(s)
    }
    return v
    }

    Can't believe I just wrote code in blind
    Aug 27, 2021 0
  • Microsoft
    🐼 🐼

    Go to company page Microsoft

    🐼 🐼
    No pointers, so what? We can store the getNext value of each stream and return the smallest when UberIterator.getNext() is called.
    Aug 27, 2021 2
  • New
    GOhN40

    New

    GOhN40
    I had this question in an interview recently. My answer was O(k) for getNext. After the interview I realized we can put the frontier elements of each stream in a min heap, and getNext will be O(logk). Where k is the number of streams.
    Aug 27, 2021 0
  • Intuit
    l33tgraph

    Go to company page Intuit

    l33tgraph
    just a couple ideas from a minute about thinking about this

    Can't you just keep a priority queue with tuples (value, steam), in the priority queue. There will only be 1 value from each stream in the priority queue at a point in time. when you dequeue from the priority queue you will put the next value of the stream in the queue.

    Another way of doing it is having a pointers to all the streams and calculating the next minimum by scanning those pointers
    Aug 27, 2021 0
  • New
    Hamilton!

    New

    Hamilton!
    Same as this
    https://leetcode.com/problems/merge-k-sorted-lists/discuss/1429534/Java-5ms-Priority-Queue-Solution

    For each stream you already have hasNext and getNext
    Aug 27, 2021 0