## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: Phone Interview

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

Assume the number of arrays in the given list are 'k'.
1) Create an array of size k so that each index in the array maintains the individual indices from the k arrays index[].
2) Create another array of size 'k' and this array should contain the max number of elements possible in each of the given arrays.
3) Create a MinHeap of size k, with first elements from each array. The MinHeap would be a heap of Objects that contain the (element value, array number that the element came from)
4) Delete the root element from the heap (it would be the minimum element) and add its to the result list.
5) If the array that the deleted element came from is not entirely visited increment the index of this array in the index[] and add this new element at the incremented index to the MinHeap.
6) Repeat steps 4 & 5, until all arrays are not completely visited and then return the result list.

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

if anyone needs help with the explanation given above

``````public List<Integer> join(List<int[]> list) {
List<Integer> result = new ArrayList<>();
int k = list.size();
int[] arrIndexTrack = new int[k];
int[] arrNumElement = new int[k];
for (int i = 0; i < list.size(); i++) {
arrNumElement[i] = list.get(i).length;
}
PriorityQueue<ArrayElement> heap = new PriorityQueue<>(k, new ElementComparator());
for (int i = 0; i < list.size(); i++) {
arrNumElement[i]--;
}
while (!heap.isEmpty()) {
ArrayElement curr = heap.poll();
int which = curr.whichArray;
if (arrNumElement[which] != 0) {
arrNumElement[which]--;
arrIndexTrack[which]++;
int index = arrIndexTrack[which];
ArrayElement next = new ArrayElement(list.get(which)[index], which);
}
}
return result;
}

public class ArrayElement {
int data;
int whichArray;

ArrayElement(int d, int w) {
data = d;
whichArray = w;
}
}

private class ElementComparator implements Comparator<ArrayElement> {
@Override
public int compare(ArrayElement o1, ArrayElement o2) {
return o1.data - o2.data;
}``````

}

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

What is the complexity ?

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

``````public int[] mergeSortedArrays(List<int[]> input) {
TreeMap<Integer, Integer> hash = new TreeMap<>();
for (int[] arr : input) {
for (int i : arr) {
if (!hash.containsKey(i)) hash.put(i, 1);
else {
hash.put(i, hash.get(i) + 1);
}
}
}

ArrayList<Integer> list = new ArrayList<>();
for (Entry<Integer, Integer> entry : hash.entrySet()) {
int count = entry.getValue();
while (count > 0) {
count--;
}
}
return list.stream().mapToInt(i -> i).toArray();
}``````

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

This also does not take advantages of sorted arrays

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

via standard k-way merge

``````public List<Integer> merge(List<int[]> input) {
List<Integer> result = new ArrayList<>();
int[] indexes = new int[input.size()];

int minElement = Integer.MAX_VALUE;
int minIndex = -1;

while (true) {
for (int i = 0; i < input.size(); i++) {
int lastIndex = indexes[i];
int[] currentArray = input.get(i);
if (lastIndex < currentArray.length) {
if (currentArray[lastIndex] < minElement) {
minElement = currentArray[lastIndex];
minIndex = i;
}
}
}

if (minIndex >= 0) {
indexes[minIndex]++;
minElement = Integer.MAX_VALUE;
minIndex = -1;
} else {
break;
}
}

return result;
}``````

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

Solution using heap

``````public class MergeArrays {

public int[] mergeSortedArrays(List<int[]> input) {
PriorityQueue<HeapNode> priorityQueue = new PriorityQueue<>();
input.stream().forEach(arr -> priorityQueue.offer(new HeapNode(arr, 0)));

ArrayList<Integer> result = new ArrayList<>();

while (!priorityQueue.isEmpty()) {
HeapNode node = priorityQueue.poll();
if (node.index < node.arr.length - 1) priorityQueue.offer(new HeapNode(node.arr, node.index + 1));
}
return result.stream().mapToInt(i -> i).toArray();
}

private static class HeapNode implements Comparable {
int[] arr;
int index;

public HeapNode(final int[] input, int i) {
arr = input;
index = i;
}

@Override
public int compareTo(Object o) {
HeapNode other = (HeapNode) o;
if (this.arr[index] < other.arr[other.index]) return -1;
if (this.arr[index] > other.arr[other.index]) return 1;
return 0;
}
}
}``````

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

Use minHeap to store index of List element -- from which int[], a value is extracted.

``````import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
//corner case
if(list == null ) return null;
int size =0;
//calculate size of result array
for(int[] vals: list) {
size += vals.length;
}

//corner case
if(size == 0) return null;

//create result
int res[] = new int[size];

//current idx for each of list ele
int idxs[] = new int[list.size()];

//current index of res
int index = 0;

/**
* min heap that stores index of the list, from which array in the list an element is extracted
*/
PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
Integer first = (Integer) o1;
Integer second = (Integer ) o2;

/**
* compare value at current index in array of the first to value at current index in array of the second
* Substract 1 to get current index
*/
return list.get(first)[idxs[first] -1] - list.get(second)[idxs[second] -1];

}
});

for( int i=0; i < list.size(); i++) {
int[] ar = list.get(i);
if(idxs[i] < ar.length) {
idxs[i]++;

}
}

while( ! heap.isEmpty() ) {
int listTh = heap.poll();
res[index++] = list.get(listTh)[idxs[listTh] - 1];
if(idxs[listTh] < list.get(listTh).length) {
idxs[listTh]++;

}

}

return res;
}
public static void main(String[] args){

int a[] = { 2, 5, 8};
int b[] = {1, 5};
int c[] = {0,99, 289};
System.out.println(Arrays.toString(sort(list)));

}
}``````

[0, 1, 2, 5, 5, 8, 99, 289]

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

``````list<int> listA;
list<int> listB;
list<int> listC;
list<list<int>> list_of_lists;
list<int> acc_list;

for (int i = 0; i < 5; i++) {

listA.push_back(i);
listB.push_back(i * i);
listC.push_back(i * i * i);
}

list_of_lists.push_back(listA);
list_of_lists.push_back(listB);
list_of_lists.push_back(listC);

list<list<int>>::iterator it;
list<int>::iterator ito;

for (it = begin(list_of_lists); it != end(list_of_lists); it++) {

for (ito = begin( (*it) ); ito != end( (*it) ); ito++) {

acc_list.push_back( (*ito) );
}
}

list<int>::iterator iti;

for (iti = begin(acc_list); iti != end(acc_list); iti++) {

cout << *iti << " ";``````

}

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

It is a K-way merge.

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

Do merge sort in recursion ðŸ˜Š

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

This takes the advantage of sorted array

``````package com.amazon.arrays;

import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class ArraysListSorted {

public static void mergerLists(List<int[]> lst){
Map<Integer,int[]> m = new TreeMap<Integer, int[]>();

Iterator<int[]> itr = lst.iterator();
while (itr.hasNext()) {
int[] is = (int[]) itr.next();
m.put(is[is.length-1], is);
}

for(Map.Entry<Integer, int[]> s : m.entrySet()){
}

Iterator<int[]> itrtr = fList.iterator();
while (itrtr.hasNext()) {
int[] temp = itrtr.next();
for(int t : temp){
System.out.print(" "+t+" ");
}
}

}

public static void main(String args[]) {
int[] first = {31,32,33,34,35};
int[] sec = {11,22,33,44,55};
int[] third = {1,2};
int[] fourth = {45,56};

mergerLists(lst);
}

}``````

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

``````package com.amazon.arrays;

import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class ArraysListSorted {

public static void mergerLists(List<int[]> lst){
Map<Integer,int[]> m = new TreeMap<Integer, int[]>();

Iterator<int[]> itr = lst.iterator();
while (itr.hasNext()) {
int[] is = (int[]) itr.next();
m.put(is[is.length-1], is);
}

for(Map.Entry<Integer, int[]> s : m.entrySet()){
}

Iterator<int[]> itrtr = fList.iterator();
while (itrtr.hasNext()) {
int[] temp = itrtr.next();
for(int t : temp){
System.out.print(" "+t+" ");
}
}

}

public static void main(String args[]) {
int[] first = {31,32,33,34,35};
int[] sec = {11,22,33,44,55};
int[] third = {1,2};
int[] fourth = {45,56};

mergerLists(lst);
}

}``````

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

``````package com.amazon.arrays;

import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class ArraysListSorted {

public static void mergerLists(List<int[]> lst){
Map<Integer,int[]> m = new TreeMap<Integer, int[]>();

Iterator<int[]> itr = lst.iterator();
while (itr.hasNext()) {
int[] is = (int[]) itr.next();
m.put(is[is.length-1], is);
}

for(Map.Entry<Integer, int[]> s : m.entrySet()){
}

Iterator<int[]> itrtr = fList.iterator();
while (itrtr.hasNext()) {
int[] temp = itrtr.next();
for(int t : temp){
System.out.print(" "+t+" ");
}
}

}

public static void main(String args[]) {
int[] first = {31,32,33,34,35};
int[] sec = {11,22,33,44,55};
int[] third = {1,2};
int[] fourth = {45,56};

mergerLists(lst);
}

}``````

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.

### 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.