Amazon Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: United States

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

k select algorithm

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

I believe a modified K select would be a good fit too giving an O(n) average case.

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

Find the mode of the sale column from the database

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

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)

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

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.

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

- 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 complexit: O(n)

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

- 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)

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

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.

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

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.

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

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){
}
else{
}
}
//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;
}

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

O(n*i) = O(n) time
O(n) space

Go through the whole list and keep track of the biggest unflagged element (one with most sales)
Flag this element
Repeat i times.
Return last flagged element

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

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

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

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

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

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

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

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

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

static string find(List<Item> items, int rank)
{
if (rank > 0 && items != null && items.Any() && items.Count() >= rank)
{
return items.OrderByDescending(i => i.Count).ElementAt(rank - 1).ID;
} else
return string.Empty;
}

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

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) {

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

Iterator it = l.iterator();
while (it.hasNext()) {
Map.Entry r1 = (Map.Entry) it.next();
mp.put(r1.getKey(), r1.getValue());
}
return mp;
}

}

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

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>();

String ithPopularItem = find(list,3);
System.out.println("ithPopularItem is :: "+ithPopularItem);

}

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

from statistics import mode
#from sales database get all item id

mode(item id)

print (mode)

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

Iterate over the input List... Create a new Linked List which can have maximum length of i (i.e. the moment its length is i+1, remove the tail.), and keep placing the items at the ordered locations.

Return the tail.

Complexity O(N) - O(NlogN).

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.