Amazon Interview Question Software Engineer / Developers
Country: United States
1. We will maintain a HaspMap\directory to store count\quantity sold.
HashMap<String, Integer> frequency; //It will store <ItenID, quantitySold>
2. Maintain a min heap of size i, it will contain only itemIds
3. Now iterate list of items:
Update HashMap
1. If item exists in HashMap than add item.quantitySold in that,
2. If item does not exists in HashMap than add it to HashMap
Update MinHeap
1. If itemID already exists than update\maintain heap with new value of quantity.
2. Else check if its quantity is greater than quantity of head of heap. If it is bigger than replace head and perform heapify.
Time: O(NlogN)
Space O(N)
This seems overly complicated what benefit are you getting from having the heap in your solution? Are you saying your find() method runs in O(nlogn)? if this is the case then why not just sort in decreasing order and then return the ith location.
- override the 'Items' class .compareTo method so Item objects can be compared against one another.
- make sure .compareTo written in descending order
- sort 'items' list using merge sort algorithm.
- return items.get(i).itemId.
Time complexity: O(n log n)
Space complexity: O(n)
Ooverriding the 'Items' class .compareTo method is good approach.
Also we can Using MIN Heap of Size i. Its complexity will narrow down to
nlogi
Heap<Item* > h;
1. Add 1st i objects to Min heap.
2. for each of remaining element in List
3. Check
next object < h.GetMIN()
4. Pop Min(), add next Object. Heapify(). O(logi)
5.
h.GetMIN()
is i-th most popular element.
Overriding CompareTo() is good approach.
Most preferable algo for this will be use MIN HEAP of size i.
Heap<Item*> h;
Algo:
1. Add first i objects to Heap
2. for each remaining element in list
3. if(next obj > h.getMIN()) //CompareTo()
{
Remove MIN, Add next obj. to Heap;
Heapify(); // O(log i)
}
3. H.GetMIN(). is the Most popular item.
This can be done in average O(n) complexity using O(n) memory by using a pivoting and sorting strategy:
String find(List<Item> items, int ith){
if(items == null){
throw new NullPointerException():
}
if(i >= items.size()){
throw new IllegalArgumentException();
}
int offset = 0;
ArrayList<Item> moreSold = null;
ArrayList<Item> lessSold = null;
while(items.size() > 0){
moreSold = new ArrayList<Item>();
lessSold = new ArrayList<Item>();
Iterator<Item> iterator = items.iterator();
//get the pivot point
Item pivot = iterator.next();
//split the items up into larger and smaller groups
while(iterator.hasNext()){
Item temp = iterator.next();
if(temp.quantitySold > pivot.quantitySold){
moreSold.add(temp);
}
else{
lessSold.add(temp);
}
}
//now, figure out which list is which
if(offset + moreSold.size() > ith){
items= moreSold;
}
else if(offset + moreSold.size() + 1 == ith){
return pivot.itemId;
}
else{
offset += (moreSold.size() + 1);
items= lessSold;
}
}
return null;
}
Following is the deterministic select algorithm based on median of medians to retrieve the k=th smallest element guaranteed to work in worst case running time of O(n).
int median5(int a, int b, int c, int d, int e)
{
if (a > b) std::swap(a, b);
if (c > d) std::swap(c, d);
if (a > c)
{
std::swap(b, d);
c = a;
}
a = e;
if (a > b) std::swap(a, b);
if (a > c)
{
std::swap(b, d);
c = a;
}
return std::min(b, c);
}
int partition(int* a, int left, int right, int pivot)
{
std::swap(a[right], a[pivot]);
auto si = left;
for (auto i = left; i <= right; ++i)
{
if (a[i] < a[right])
{
std::swap(a[i], a[si]);
++si;
}
}
std::swap(a[si], a[right]);
return si;
}
int select(int* a, int left, int right, int k);
int med_of_meds(int* a, int left, int right)
{
auto si = left;
for (auto i = left; i <= right; i += 5)
{
auto j = std::min(i + 4, right);
auto med = (i + 4 == j) ? median5(a[i], a[i + 1], a[i + 2], a[i + 3], a[i + 4]) : a[i];
auto pos = i;
for (; pos <= j; ++pos)
{
if (med == a[pos]) break;
}
std::swap(a[si], a[pos]);
++si;
}
return select(a, left, si - 1, std::ceil((si - left) / (double)2));
}
int select(int* a, int left, int right, int k)
{
if (right - left + 1 < k) throw std::exception("impossibru");
if (right == left) return a[left];
auto mm = med_of_meds(a, left, right);
auto pivot = left;
for (; pivot <= right; ++pivot)
{
if (mm == a[pivot]) break;
}
auto pos = partition(a, left, right, pivot);
if (pos - left + 1 == k) return mm;
else if (pos - left + 1 < k)
{
return select(a, pos + 1, right, k - (pos - left + 1));
}
else if (pos - left + 1 > k)
{
return select(a, left, pos - 1, k);
}
}
/// usage
int sa[] = { 5, 17, 92, 43, 55, 14, 2, 8, 75, 6 };
int s1 = select(sa, 0, 9, 1);
int s3 = select(sa, 0, 9, 3);
int s7 = select(sa, 0, 9, 7);
1. We will start with a TreeMap to store the incoming order and total quantity sold sorted based on quantity in decreasing order
1.1 if item is already in map just update the quantity
1.2 if item is not there just add it up into the map
2. As the keys of the maps are already sorted based on decreasing quantity order we can just take the key list and get the top ith order item
insertion time (nlogn)
search time (n) (correct me if i am wrong)
Total efficiency : nlogn
I am guessing since both list and ith element are passed in function.
This problem is more like find Median from a list of elements.
so if we want O(n) then maintain two Heap ( Max Heap of elements below i and Min Heap of elements above i )
and we can run over the list of elements once and find the ith popular element
This can be done in O(n) time and space with a selection-rank algorithm.
Ex.
In this context, ith most popular element will have rank i.
Use quicksort's partition to find the location of a random pivot in the list
If rank == pivot location, then return pivot element
If the target rank is < pivot location, recurse on the left half of the list
Otherwise recurse on the right half of the list
import java.util.*;
public class rihs {
public int privateid;
public int quantity_sold;
public static void main(String[] args) {
HashMap r = new HashMap();
r.put("Iphone", 100);
r.put("Blackberry", 90);
r.put("Samsung", 80);
r.put("Windows", 60);
r.put("Micromax", 44);
r.put("Nokia", 56);
Scanner sc = new Scanner(System.in);
System.out.println("enter the ith popular element");
int i =sc.nextInt();
find_popular(r,i);
}
public static void find_popular(HashMap r,int i) {
int count=0;
Set l = r.entrySet();
Iterator it = l.iterator();
while (it.hasNext()) {
Map.Entry mp = (Map.Entry) it.next();
}
Map r1 = SortedByValues(r);
Set s = r1.entrySet();
Iterator it2 =s.iterator();
while(it2.hasNext())
{
Map.Entry r2 = (Map.Entry)(it2.next());
count = count+1;
if(i<=l.size()) {
if (count == i) {
System.out.println(i + "th popular element is " + r2.getKey() + "Number of
items sold is:" + r2.getValue());
}
}
else
{
System.out.println("Invalid count!!!Try again!");
System.exit(0);
}
}
}
public static HashMap SortedByValues(HashMap r) {
List l = new LinkedList(r.entrySet());
Collections.sort(l, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// System.out.println( "v1:"+((Map.Entry)(o1)).getValue());
//System.out.println("v2:"+((Map.Entry)(o2)).getValue());
return ((Comparable)((Map.Entry) (o2)).getValue()).compareTo(((Map.Entry)
(o1)).getValue());
}
});
HashMap mp = new LinkedHashMap();
Iterator it = l.iterator();
while (it.hasNext()) {
Map.Entry r1 = (Map.Entry) it.next();
mp.put(r1.getKey(), r1.getValue());
}
return mp;
}
}
public static String find(List<Item> items,int i){
System.out.println("List Before ::"+ items);
Collections.sort(items,new Comparator<Item>(){
@Override
public int compare(Item o1, Item o2) {
return o1.quantitySold > o2.quantitySold ? -1 : o1.quantitySold == o2.quantitySold ? 0 : 1;
}
});
System.out.println("List After ::"+ items);
Item item = (Item)items.get(i-1);
return item.getItemID();
}
public static void main(String[] args) {
List<Item> list = new ArrayList<Item>();
list.add(new Item("EarPhones", 85));
list.add(new Item("Mobiles", 100));
list.add(new Item("Battery", 10));
list.add(new Item("Back-Cover", 25));
String ithPopularItem = find(list,3);
System.out.println("ithPopularItem is :: "+ithPopularItem);
}
k select algorithm
- SK May 28, 2015