CareerCup

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

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.

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

class Recommendations {
    public static void main(String[] s) {
        List<String> recommendations = getRecommendations("1");
        System.out.println(recommendations);
    }
 
    public static List<String> getRecommendations(String userId) {
        List<String> friends = getFriendsListForUser(userId);
        List<String> userPurchases = getPurchasesForUser(userId);
        
        Map<String, Integer> freMap = new HashMap<>();
        if(friends != null) {
            for(String friend: friends) {
                List<String> friendPurchases = getPurchasesForUser(friend);
                if(friendPurchases != null) {
                    for(String purchase: friendPurchases) {
                        if(!userPurchases.contains(purchase)) {
                            freMap.put(purchase, freMap.getOrDefault(purchase, 0) + 1);
                        }
                    }
                }
                
            }
        }
        

        List<String> recommendations = new ArrayList<>();
        for(Map.Entry<String, Integer> entry: freMap.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
            recommendations.add(entry.getKey());
        }
        recommendations.sort((a, b) -> freMap.get(b) - freMap.get(a));
        return recommendations;
    }

    public static List<String> getFriendsListForUser(String userId) {
            return Arrays.asList(new String[]{"2","3","4","5"});  
        
    }

    public static List<String> getPurchasesForUser(String userId) {
        if(userId == "1")
            return Arrays.asList(new String[]{"1","3","5","7"});
        if(userId == "2")
            return Arrays.asList(new String[]{"2","4","6","8"});
        if(userId == "3")
            return Arrays.asList(new String[]{"1","2","6","9"});
        if(userId == "4")
            return Arrays.asList(new String[]{"2","6","7","10"});
        if(userId == "5")
            return Arrays.asList(new String[]{"2","9","7","8"});
        return null;
    }
}

should not getPurchasesForUser return customer id also,
how will i know,this produnct is purchased by my friend or not by some body else