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

- manoj March 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- User March 29, 2014 | Flag
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

- Anonymous April 01, 2014 | Flag
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.

- rotinom April 11, 2014 | Flag
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.

- kulkarniaks007 April 05, 2014 | Flag Reply
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);
    }
}

- nobody December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More