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
Want to see the real deal?
More inside scoop? View in App
More inside scoop? View in App
blind
SUPPORT
FOLLOW US
DOWNLOAD THE APP:
FOLLOWING
Industries
Job Groups
- Software Engineering
- Product Management
- Information Technology
- Data Science & Analytics
- Management Consulting
- Hardware Engineering
- Design
- Sales
- Security
- Investment Banking & Sell Side
- Marketing
- Private Equity & Buy Side
- Corporate Finance
- Supply Chain
- Business Development
- Human Resources
- Operations
- Legal
- Admin
- Customer Service
- Communications
Return to Office
Work From Home
COVID-19
Layoffs
Investments & Money
Work Visa
Housing
Referrals
Job Openings
Startups
Office Life
Mental Health
HR Issues
Blockchain & Crypto
Fitness & Nutrition
Travel
Health Care & Insurance
Tax
Hobbies & Entertainment
Working Parents
Food & Dining
IPO
Side Jobs
Show more
SUPPORT
FOLLOW US
DOWNLOAD THE APP:
comments
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
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
https://leetcode.com/problems/merge-k-sorted-lists/discuss/1429534/Java-5ms-Priority-Queue-Solution
For each stream you already have hasNext and getNext