Amazon Interview Question for SDE-3s


Country: United States




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

- adr October 01, 2018 | Flag Reply
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]
'''

- prudent_programmer October 01, 2018 | Flag Reply
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;
    }

}

- radobenc October 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, Why dint you use TreeSet ?

- thanga October 16, 2018 | Flag
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 + " ");
}
}
}

- Solution with two different approaches. One of them uses Collections.sort method but other uses PriorityQueue October 18, 2018 | Flag Reply
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 + " ");
}
}
}

- Solution with two different approaches. One of them uses Collections.sort method but other uses PriorityQueue October 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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;
    }

- kvdeshmukh1989 October 19, 2018 | Flag Reply


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