Amazon Interview Question Software Developers
Country: United States
Interview Type: Written Test
Priority Queue in java is implemented as a minHeap.You do not have to write the comparator here.
In the solution given, there can be chance that some items are larger and not yet added. So how can you gurrantee that
if (q.size() > i) {
q.poll();
}
this will always return ith largest element?
import java.util.Arrays;
import java.lang.reflect.Array;
import java.lang.Comparable;
public class OrderStatistic<T extends Comparable<T>> {
public T findKthLargest(T [] array, int k) {
validateInputParameters(array, k);
return findKthLargest(array, 0, array.length, k);
}
private void validateInputParameters(T [] array, int k) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array is null or empty");
}
if (k < 0 || k >= array.length) {
throw new IllegalArgumentException("Wrong k = " + k);
}
}
private T findKthLargest(T [] array, int l, int r, int k) {
T medianOfMedians = findMedianOfMedians(array, l, r);
int pos = partition(array, l, r, medianOfMedians);
if (array.length - k - 1 == pos) {
return array[array.length - k - 1];
} else if (array.length - k - 1 > pos) {
return findKthLargest(array, pos + 1, r, k);
} else {
return findKthLargest(array, l, pos, k) ;
}
}
private T findMedianOfMedians(T [] array, int l, int r) {
int n = r - l;
int mediansSize = n / 5;
if (n % 5 != 0) {
++mediansSize;
}
T [] medians = (T []) Array.newInstance(array[0].getClass(), mediansSize);
int i = l;
int index = 0;
while (i + 5 <= r) {
medians[index++] = findMedian(array, i, i + 5);
i += 5;
}
if (i != r) {
medians[index] = findMedian(array, i, r);
}
if (medians.length == 1) {
return medians[0];
} else {
return findKthLargest(medians, 0, medians.length, medians.length / 2);
}
}
private T findMedian(T [] array, int l, int r) {
Arrays.sort(array, l, r);
return array[l + (r - l) / 2];
}
private int partition(T [] array, int l, int r, T pivot) {
int index = l;
for (int i = l; i < r; ++i) {
if (array[i].compareTo(pivot) < 0) {
T t = array[i];
array[i] = array[index];
array[index] = t;
++index;
}
}
return index;
}
}
This problem is called "kth order statistics". Above solution has O(N) time and O(N) space complexities.
Find 1st popular item and delete it. Repeat i times.
String find(List<Item> items, int i) {
List<Item> copy;
int idx, maxIdx, maxQuantity;
String result;
result = "";
if (i <= 0 || i > items.size()) return result;
copy = new ArrayList<Item>();
copy.addAll(items);
maxIdx = 0;
while (true) {
maxQuantity = -1;
for (idx = 0; idx < copy.size(); idx++) {
if (copy.get(idx).quantitySold > maxQuantity) {
maxIdx = idx;
maxQuantity = copy.get(idx).quantitySold;
}
}
i--;
if (i == 0) {
result = copy.get(maxIdx).itemId;
break;
}
copy.remove(copy.get(maxIdx));
}
return result;
}
import java.util.*;
public class PopularItem {
static class Item {
String itemId;
int quantitySold;
public void setItemId(String itemId){
this.itemId = itemId;
}
public void setQuantitySold(int quantitySold){
this.quantitySold = quantitySold;
}
}
/**
* Find the ith most popular item in the list.
*/
private static String find(List<Item> items, int i) {
// your code goes here
Map<Integer, String> itemMap = new HashMap<>();
for(Item item : items) {
itemMap.put(item.quantitySold, item.itemId);
}
TreeMap<Integer, String> sortedItems = new TreeMap<>(itemMap);
String[] sortedItemArray = Arrays.copyOf(sortedItems.values().toArray(), sortedItems.values().toArray().length, String[].class);
return sortedItemArray[i-1];
}
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
List<Item> stringList = new ArrayList<>();
int i = 0;
while(i < 5)
{
System.out.print("Enter Item Id " + (i+1) + ": " );
String itemId = scanner.next();
System.out.print("Enter Item quantity " + (i + 1) + ": ");
int quantity = scanner.nextInt();
Item item = new Item();
item.setItemId(itemId);
item.setQuantitySold(quantity);
stringList.add(item);
i++;
}
System.out.print("Enter Item position : ");
int position = scanner.nextInt();
String newStrings = find(stringList, position);
System.out.println(newStrings);
}
}
order statistics problem based on quick sort partitioning
public class OrderedStatistics {
private static class Item implements Comparable<Item> {
String itemId;
int quantitySold;
public Item(String itemId, int quantitySold) {
this.itemId = itemId;
this.quantitySold = quantitySold;
}
public int compareTo(Item other) {
return other.quantitySold - this.quantitySold;
}
}
public String find(List<Item> items, int index) {
if (index <= 0 || index > items.size()) {
throw new IllegalArgumentException("Unexpected index:" + index);
}
return find(new ArrayList<>(items), index - 1, 0, items.size() - 1);
}
private String find(List<Item> items, int index, int from, int to) {
if (from < to) {
int pivotIndex = partition(items, from, to);
if (pivotIndex == index) {
return items.get(index).itemId;
} else if (pivotIndex < index) {
return find(items, index, pivotIndex + 1, to);
} else { // pivotIndex > index
return find(items, index, from, pivotIndex - 1);
}
}
return items.get(from).itemId;
}
private int partition(List<Item> items, int from, int to) {
Item pivot = items.get(to);
int j = from - 1;
for (int i = from; i < to; i++) {
if (less(items.get(i), pivot)) {
j++;
swap(items, j , i);
}
}
j++;
swap(items, j, to);
return j;
}
private boolean less(Item i1, Item i2) {
return i1.compareTo(i2) < 0;
}
private void swap(List<Item> items, int i, int j) {
if (i != j) {
Item temp = items.get(i);
items.set(i, items.get(j));
items.set(j, temp);
}
}
}
def insert(tree, item):
if item < value(tree):
insert_left(tree, item)
else:
insert_right(tree, item)
def insert_left(tree, item):
if left(tree) is None:
set_left(tree, item)
else:
insert(left(tree), item)
def insert_right(tree, item):
if right(tree) is None:
set_right(tree, item)
else:
insert(right(tree), item)
def set_left(tree, item):
tree[1][0] = make_tree(item)
def set_right(tree, item):
tree[1][1] = make_tree(item)
def make_tree(item):
return [item, [None, None]]
def left(tree):
return tree[1][0]
def right(tree):
return tree[1][1]
def value(tree):
return tree[0]
def visit(tree, f):
if tree == None:
return
visit(left(tree), f)
f(value(tree))
visit(right(tree), f)
def display(tree):
visit(tree, print)
def ith(tree, i):
answer = None
def f(item):
nonlocal i, answer
if i == 0:
answer = item
i -= 1
visit(tree, f)
return answer
def sort(list):
tree = make_tree(list[0])
for item in list[1:]:
insert(tree, item)
return tree
print(ith(sort([5, 4, 6, 1, 8, 2, 10]), 3))
public static void main(String[] args){
List<Item> lst = new ArrayList<>();
for (int i=10; i>0; i--)
{
Item item = new Item();
item.name = "name" + String.valueOf(i);
item.sold_rank =i;
lst.add(item);
}
Item nItem = GetItemByRank(lst, 10);
if(nItem != null)
System.out.println(nItem.name + " " + nItem.sold_rank);
}
// sort [quick] List item and return i-th element
static Item GetItemByRank(List<Item> items, int nRank){
Item item = null;
if(items.size() < nRank)
return item;
// quick sort
partition(items, 0, items.size()-1);
item = items.get(nRank-1);
return item;
}
static void partition(List<Item> items, int lo, int ro){
int pivot = lo + (ro - lo)/2;
Item my_item = items.get(pivot);
int i=lo, j=ro;
while (i<=j)
{
while (items.get(i).sold_rank < my_item.sold_rank)
i++;
while (items.get(j).sold_rank > my_item.sold_rank)
j--;
if(i<=j) {
swap(items, i, j);
i++;
j--;
}
}
if(lo<j)
partition(items, lo, j);
if(ro>i)
partition(items, i, ro);
}
static void swap(List<Item> items, int lo, int ro)
{
Item temp = items.get(lo);
items.set(lo, items.get(ro));
items.set(ro, temp);
}
//
public static void main(String[] args){
List<Item> lst = new ArrayList<>();
for (int i=10; i>0; i--)
{
Item item = new Item();
item.name = "name" + String.valueOf(i);
item.sold_rank =i;
lst.add(item);
}
Item nItem = GetItemByRank(lst, 10);
if(nItem != null)
System.out.println(nItem.name + " " + nItem.sold_rank);
}
// sort [quick] List item and return i-th element
static Item GetItemByRank(List<Item> items, int nRank){
Item item = null;
if(items.size() < nRank)
return item;
// quick sort
partition(items, 0, items.size()-1);
item = items.get(nRank-1);
return item;
}
static void partition(List<Item> items, int lo, int ro){
int pivot = lo + (ro - lo)/2;
Item my_item = items.get(pivot);
int i=lo, j=ro;
while (i<=j)
{
while (items.get(i).sold_rank < my_item.sold_rank)
i++;
while (items.get(j).sold_rank > my_item.sold_rank)
j--;
if(i<=j) {
swap(items, i, j);
i++;
j--;
}
}
if(lo<j)
partition(items, lo, j);
if(ro>i)
partition(items, i, ro);
}
static void swap(List<Item> items, int lo, int ro)
{
Item temp = items.get(lo);
items.set(lo, items.get(ro));
items.set(ro, temp);
}
class Item{
String name;
int sold_rank;
}
A quicksort solution.
struct Item{
string itemId;
int quantitySold;
};
void sortf(vector<Item*> & items, int start, int end){
if(start >= end) return;
int left = start, right = end;
int pivot = items[start]->quantitySold;
while(left < right){
if(items[left]->quantitySold > pivot && items[right]->quantitySold < pivot){
swap(items[left], items[right]);
}
else if(items[left]->quantitySold <= pivot){
left++;
}
else{
right--;
}
}
if(items[right]->quantitySold > pivot){
right--;
}
swap(items[start], items[right]);
sortf(items, start, right - 1);
sortf(items, right + 1, end);
}
void quickSort(vector<Item*> & items){
sortf(items, 0, items.size() - 1);
}
string find(vector<Item*> & items, int i){
quickSort(items);
return items[items.size() - i]->itemId;
}
package com.amazon.arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
/*
*
*
* Alternative: To use MinHeap
*/
class AmazonItems {
public Item getIthItem(List<Item> lst, int k) {
Item item = null;
Map<Item, Integer> itemsMap = new TreeMap<Item, Integer>(
new MyComparator());
Iterator<Item> it = lst.iterator();
while (it.hasNext()) {
Item nextItem = it.next();
itemsMap.put(nextItem, nextItem.getQuantitySold());
}
Item[] itemArray = new Item[lst.size() + 1];
int i = 1;
for (Map.Entry<Item, Integer> items : itemsMap.entrySet()) {
itemArray[i++] = items.getKey();
}
return itemArray[k];
}
}
class MyComparator implements Comparator<Item> {
public int compare(Item o1, Item o2) {
if (o1.getQuantitySold() > o2.getQuantitySold())
return -1;
else if (o1.getQuantitySold() < o2.getQuantitySold())
return 1;
return 0;
}
}
class Item {
private String itemId;
private int quantitySold;
public String getItemId() {
return itemId;
}
public void setItemId(String itemId) {
this.itemId = itemId;
}
public int getQuantitySold() {
return quantitySold;
}
public void setQuantitySold(int quantitySold) {
this.quantitySold = quantitySold;
}
public Item(String itemId, int quantitySold) {
this.itemId = itemId;
this.quantitySold = quantitySold;
}
}
public class ArrayPopularItem {
public static void main(String args[]) {
List<Item> lst = new LinkedList<Item>();
lst.add(new Item("first", 100));
lst.add(new Item("sec", 1000));
lst.add(new Item("third", 200));
lst.add(new Item("fourth", 400));
lst.add(new Item("fifth", 700));
lst.add(new Item("six", 4700));
lst.add(new Item("seven", 11700));
/* new AmazonItems().getIthItem(lst,3); */
System.out.println(" K th item is "
+ new AmazonItems().getIthItem(lst, 5).getQuantitySold());
}
}
Standard solution to finding the k largest is to use a min heap. Insert into the heap until there are more than k items, and then you're left with the k largest.
- louis September 18, 2015/** * Find the ith most popular item in the list. */ static String find(List<Item> items, int i) { if (items.size() < i || i < 1) return null; PriorityQueue<Item> q = new PriorityQueue<Item>(new Comparator<Item>() { @Override public int compare(Item one, Item two) { if (one.quantitySold < two.quantitySold) return -1; if (one.quantitySold == two.quantitySold) return 0; return 1; } }); for (Item item : items) { q.add(item); if (q.size() > i) { q.poll(); } } Item ith = q.poll(); return ith.itemId; }