Amazon Interview Question
SDE-3sCountry: United States
We don't need to know the length of the input streams, just a way to test if the stream is empty. Here is a C++ example to merge heterogeneous streams of arbitrary length:
#include <queue>
#include <iostream>
#include <algorithm>
#include <memory>
#include <iterator>
using namespace std;
class helper_base
{
public:
virtual ~helper_base() {}
virtual void next() = 0;
virtual int get() const = 0;
virtual bool eof() const = 0;
};
template <typename InputIterator>
class helper : public helper_base
{
InputIterator d_in;
InputIterator d_end;
public:
explicit helper(const pair<InputIterator, InputIterator>& range)
: d_in(range.first), d_end(range.second)
{}
void next() override { ++d_in; }
int get() const override { return *d_in; }
bool eof() const override { return d_in == d_end; }
};
template <typename ... InputIteratorPairs, typename OutputIterator>
void merge(OutputIterator out, InputIteratorPairs ... inpairs)
{
vector<shared_ptr<helper_base>> arr =
{make_shared<helper<decltype(inpairs.first)>>(inpairs)...};
arr.erase(remove_if(arr.begin(), arr.end(),
[](shared_ptr<helper_base> stream) { return stream->eof(); }),
arr.end());
auto cmp = [](shared_ptr<helper_base> lh, shared_ptr<helper_base> rh) {
return lh->get() > rh->get();
};
priority_queue<shared_ptr<helper_base>,
vector<shared_ptr<helper_base>>,
decltype(cmp)> pq(arr.begin(), arr.end(), cmp);
while (!pq.empty()) {
auto top = pq.top();
pq.pop();
*out++ = top->get();
top->next();
if (!top->eof()) {
pq.push(top);
}
}
}
int main()
{
const int a[] = {1, 3, 4, 5, 6, 7};
const vector<int> b = { 2, 4, 5, 9};
// merge a,b and stdin stream
merge(ostream_iterator<int>(cout, " "),
make_pair(a, a+sizeof(a)/sizeof(int)),
make_pair(b.begin(), b.end()),
make_pair(istream_iterator<int>(cin), istream_iterator<int>()));
return 0;
}
Pretty straightforward with Priority Queue / Heap. Enqueue the elements as you go along and extract min during every iteration and add it to the result. Presenting my short Python solution below:
Solution
import heapq
def mergeStreams(streams):
heap = []
res = []
for stream in streams:
if stream:
# Get first element and enqueue it
iterator = iter(stream)
heapq.heappush(heap, (next(iterator), iterator))
while heap:
curElem, curIterator = heapq.heappop(heap)
res.append(curElem)
try:
heapq.heappush(heap, (next(curIterator), curIterator))
except StopIteration:
continue
return res
Test Code
streams = [[2,4,5,6,7,8], [1,3,9,12], [10,11,13,14]]
print(mergeStreams(streams))
'''
OUTPUT: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
'''
Using PriorityQueue in Java:
import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;
public class MergeStreams {
public static void main(String[] args) {
System.out.println(Arrays.toString(mergeStreams(
new int[][] { { 2, 4, 5, 6, 7, 8 },
{ 1, 3, 9, 12 },
{ 10, 11, 13, 14 } })));
}
private static int[] mergeStreams(int[][] is) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i = 0; i < is.length; i++) {
for (int j = 0; j < is[i].length; j++)
pq.add(is[i][j]);
}
int[] result = new int[pq.size()];
int counter = 0;
Iterator<Integer> i = pq.iterator();
while (i.hasNext()) {
result[counter++] = pq.remove();
}
return result;
}
}
package SortStreams;
import java.util.*;
public class SortStreamOfNumbers {
private static final Scanner scanner = new Scanner(System.in);
static void sortStreamsCollection(String[] streamsOfNumbers){
List<Integer> allNumbers = new ArrayList<>();
for (String values : streamsOfNumbers) {
String [] tempArr = values.split(" ");
for(String everyNumber : tempArr){
allNumbers.add(Integer.parseInt(everyNumber));
}
}
Collections.sort(allNumbers);
System.out.println(allNumbers);
}
static Integer[] sortStreamsPQ(String[] streamsOfNumbers){
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (String values : streamsOfNumbers) {
String [] tempArr = values.split(" ");
for(String everyNumber : tempArr){
pq.add(Integer.parseInt(everyNumber));
}
}
Iterator myIter = pq.iterator();
Integer [] result = new Integer[pq.size()];
int count = 0;
while(myIter.hasNext()){
result[count++] = (Integer) myIter.next();
myIter.remove();
}
return result;
}
public static void main(String[] args){
int streamCount = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
String[] values = new String[streamCount];
for (int i = 0; i < streamCount; i++) {
String valuesItem = scanner.nextLine();
values[i] = valuesItem;
}
// sortStreamsCollection(values);
Integer[] res = sortStreamsPQ(values);
for (Integer el : res) {
System.out.print(el + " ");
}
}
}
package SortStreams;
import java.util.*;
public class SortStreamOfNumbers {
private static final Scanner scanner = new Scanner(System.in);
static void sortStreamsCollection(String[] streamsOfNumbers){
List<Integer> allNumbers = new ArrayList<>();
for (String values : streamsOfNumbers) {
String [] tempArr = values.split(" ");
for(String everyNumber : tempArr){
allNumbers.add(Integer.parseInt(everyNumber));
}
}
Collections.sort(allNumbers);
System.out.println(allNumbers);
}
static Integer[] sortStreamsPQ(String[] streamsOfNumbers){
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (String values : streamsOfNumbers) {
String [] tempArr = values.split(" ");
for(String everyNumber : tempArr){
pq.add(Integer.parseInt(everyNumber));
}
}
Iterator myIter = pq.iterator();
Integer [] result = new Integer[pq.size()];
int count = 0;
while(myIter.hasNext()){
result[count++] = (Integer) myIter.next();
myIter.remove();
}
return result;
}
public static void main(String[] args){
int streamCount = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
String[] values = new String[streamCount];
for (int i = 0; i < streamCount; i++) {
String valuesItem = scanner.nextLine();
values[i] = valuesItem;
}
// sortStreamsCollection(values);
Integer[] res = sortStreamsPQ(values);
for (Integer el : res) {
System.out.print(el + " ");
}
}
}
static void Main()
{
int[] r1 = { 2, 4, 5, 6, 7, 8 };
int[] r2 = { 1, 3, 9, 12 };
int[] r3 = { 10, 11, 13, 14 };
int l1 = r1.Length;
int l2 = r2.Length;
int l3 = r3.Length;
int[] newstream = new int[l1 + l2 + l3];
int cells = l2 + l1 + l3;
int c1 = 0;
int c2 = 0;
int c3 = 0;
int index = 0;
int smaller = 0;
while (index < cells)
{
smaller = -1;
if (c1 < l1)
smaller = 1;
if (c2 < l2)
if (smaller != -1)
{
if (r2[c2] < r1[c1])
smaller = 2;
}
else smaller = 2;
if (c3 < l3)
if (smaller != -1)
{
if (r3[c3] < r2[c2])
smaller = 3;
}
else smaller = 3;
if (smaller == 1)
{
smaller = r1[c1];
c1++;
}
else if (smaller == 2)
{
smaller = r2[c2];
c2++;
}
else if (smaller == 3)
{
smaller = r3[c3];
c3++;
}
newstream[index] = smaller;
index++;
}
foreach (var item in newstream)
{
Console.WriteLine(item + "\t");
}
}
Assumptions:
1) Number on input streams in known.
2) No random addition of a stream on the fly.
3) The size of input stream is infinite so assuming its a linked list.
- kvdeshmukh1989 October 19, 2018