Amazon Interview Question SDE-2s
Country: United States
Interview Type: Phone Interview
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++) {
heap.add(new ArrayElement(list.get(i)[0], i));
arrNumElement[i]--;
}
while (!heap.isEmpty()) {
ArrayElement curr = heap.poll();
result.add(curr.data);
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);
heap.add(next);
}
}
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;
}
}
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) {
list.add(entry.getKey());
count--;
}
}
return list.stream().mapToInt(i -> i).toArray();
}
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]++;
result.add(minElement);
minElement = Integer.MAX_VALUE;
minIndex = -1;
} else {
break;
}
}
return result;
}
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();
result.add(node.arr[node.index]);
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;
}
}
}
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.LinkedList;
import java.util.PriorityQueue;
public class Main {
static int[] sort(LinkedList<int[]> list) {
//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]++;
heap.add(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]++;
heap.add(listTh);
}
}
return res;
}
public static void main(String[] args){
int a[] = { 2, 5, 8};
int b[] = {1, 5};
int c[] = {0,99, 289};
LinkedList<int[]> list = new LinkedList<>();
list.add(a);
list.add(b);
list.add(c);
System.out.println(Arrays.toString(sort(list)));
}
}
[0, 1, 2, 5, 5, 8, 99, 289]
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 << " ";
}
This takes the advantage of sorted array
package com.amazon.arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
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);
}
LinkedList<int[]> fList = new LinkedList<int[]>();
for(Map.Entry<Integer, int[]> s : m.entrySet()){
fList.add(s.getValue());
}
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};
List<int[]> lst = new LinkedList<int[]>();
lst.add(first);
lst.add(sec);
lst.add(third);
lst.add(fourth);
mergerLists(lst);
}
}
package com.amazon.arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
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);
}
LinkedList<int[]> fList = new LinkedList<int[]>();
for(Map.Entry<Integer, int[]> s : m.entrySet()){
fList.add(s.getValue());
}
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};
List<int[]> lst = new LinkedList<int[]>();
lst.add(first);
lst.add(sec);
lst.add(third);
lst.add(fourth);
mergerLists(lst);
}
}
package com.amazon.arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
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);
}
LinkedList<int[]> fList = new LinkedList<int[]>();
for(Map.Entry<Integer, int[]> s : m.entrySet()){
fList.add(s.getValue());
}
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};
List<int[]> lst = new LinkedList<int[]>();
lst.add(first);
lst.add(sec);
lst.add(third);
lst.add(fourth);
mergerLists(lst);
}
}
Assume the number of arrays in the given list are 'k'.
- teli.vaibhav October 11, 20151) 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.