## Amazon Interview Question for SDE-3s

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]
'''``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, Why dint you use TreeSet ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More