## Amazon Interview Question for Senior Software Development Engineers

Country: India
Interview Type: In-Person

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

1. Use a HashMap<Product> pruchaseMap and store all the purchases made by the customer
2. Keep one more HashMap<Product, Integer> recommendation
2. Get the list of Friends for the customer
3. Iterate through the friends list and in that find the purchases made by the friend
4. If the product present in purchaseMap, omit else, put it in recommendation and increment it's count by 1.
5. After all the friends are evaluated. Sort the recommendation by it's value, i.e. the count

Space Complexity : O(n)
time Complexity : O(n) + O(n*log n)

where n being the total no. of purchases made by all the friends

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

how can this be O(n) + O(n*log n) ???

2. Get the list of Friends for the customer
3. Iterate through the friends list and in that find the purchases made by the friend
So, friends = getFriendsListForUser()
foreach friend : friends
productList = getPurchasesForUser()

iterate thru productList for each friend = n^2 time

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

It's O(n) because n is the number of items purchased in total by all you friends. Another way to right it would be O(k*p) where k is the number of friends and p is the number of items a friend has

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

Aren't you doing a bit of "hand waving" towards the end? You can't just "sort a hashmap". You'd have to move that into a sortable container. However, if you adjust your approach, you'll almost have it.

Have your hashmap store a pointer to a struct. The struct lives within a max-heap, and uses the count as its comparator. So you would do the same thing, but instead of count++, you'd do increase_key() to adjust the location in the heap.

At the end, you just need to suck everything out of the heap, and you're done.

If you use a fibonacci heap, inserts are O(1). Decrease Key is O(1). So that means that you are just O(N), where N is the sum of the number of elements that your friends have bought.

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

1. Get the list of friends for the current customer.
2. Create Hashmap with productId as key and its count as value.
3. For each friend get list of products purchased by him/her.
4. Put the product id in hashmap if the productid is not already present. If already present increment the count by 1.
5. Now After all the friends and products are finished create maxHeap using the HashMap.

Time Complexity : O(no of friends * no. of products)
Space Complexity : O(no. of unique product Ids *2) = (no. of unique product Ids)
2 is multiplied because 1 for hashmap and 1 for max heap.

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

``````public class Recommender {

private final DataService dataService;

public Recommender(DataService dataService) {
this.dataService = dataService;
}

public List<String> getRecommendations(String userId) {
List<String> friends = dataService.getFriendsListForUser(userId);
HashSet<String> userProducts = new HashSet<>(dataService.getPurchasesForUser(userId));
return friends.stream()
.flatMap(f -> dataService.getPurchasesForUser(f).stream())
.filter(p -> !userProducts.contains(p))
.collect(groupingBy(p -> p, counting())).entrySet().stream()
.map(v-> new ItemCount<>(v.getKey(), v.getValue().intValue()))
.sorted()
.map(i->i.item).collect(Collectors.toList());
}
}

class ItemCount<T> implements Comparable<ItemCount<T>>{
public final T item;
private int count = 0;

public ItemCount(T item, int count) {
this.item = item;
this.count = count;
}

@Override
public int compareTo(ItemCount<T> other) {
return -1*Integer.compare(count, other.count);
}
}``````

Comment hidden because of low score. Click to expand.

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.