CareerCup

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.

public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0)
            return null;
        if(lists.length == 1)
            return lists[0];
        
        PriorityQueue<ListNode> q = new PriorityQueue<>(new Comparator<ListNode>(){
           @Override
            public int compare(ListNode l1, ListNode l2){
                return l1.val - l2.val;
            }
        });
        
        for(int i = 0; i < lists.length; i++){
            if(lists[i] != null)
                q.offer(lists[i]);
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while(!q.isEmpty()){
            ListNode n = q.poll();
            p.next = n;
            if(n.next != null)
                q.offer(n.next);
            p = p.next;
        }
        
        return dummy.next;
    }

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");
}
}