Amazon Interview Question for Software Developers


Country: United States




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

I derived at this brute force but there should be a better way

static int[] determineRecommendation(string itemId, string[] purchases)
        {
            var Stronglist = new List<string>();
            var Weaklist = new List<string>();
            var commonList = new List<string>();
            var dict = new Dictionary<string, List<string>>();
            for (int i = 0; i < purchases.Length; i++)
            {
                var splitString = purchases[i].Split(':');
                var customer = splitString[0];
                var item = splitString[1];
                if (dict.ContainsKey(customer))
                {
                    dict[customer].Add(item);
                }
                else
                {
                    var newList = new List<string>();
                    newList.Add(item);
                    dict.Add(customer, newList);
                }
            }

            foreach(var customer in dict.Keys)
            {
                if(dict[customer].Contains(itemId))
                {
                    foreach(var item in dict[customer])
                    {
                        if(item != itemId)
                            Stronglist.Add(item);
                    }
                }
            }
            var strongCount = Stronglist.Count;
            foreach (var customer in dict.Keys)
            {
                foreach (var strong in Stronglist.ToList())
                {
                    if(dict[customer].Contains(strong))
                    {
                        foreach(var item in dict[customer])
                        {
                            if (!Stronglist.Contains(item) && !Weaklist.Contains(item) && item != itemId)
                            {
                                Weaklist.Add(item);
                                Stronglist.Add(item);
                            }
                        }
                    }
                }
            }
            return new int[] { strongCount, Weaklist.Count };

}

- maksymas August 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Convert all in the input into an undirected graph.

QRS     KLM --- TUV
 |       |
ABC --- HIJ     NOP
   \   /
    DEF

Then the problem basically becomes finding the number of direct neighbours and the number of indirect neighbours of a given node.

Perform a breath-first-search from the given node, you need to add a variable to keep track of the current depth. If the current depth is 1 and you found a new node, increment the number of direct neighbours, if it's larger than 1, increment the number of indirect neighbours.

- shane030716 August 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you provide me an implementation ?

- maksymas August 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is my pseudo code ...
need missing contrlos e.g. do not add same item in it's own lists

for each cart_item
add_cart_items_to_strong_list(cart_items_list)
for each store_items
if (is_present_into_strong_weak_lists (cart_item))
add_cart_items_to_weak_list(store_items,cart_item)

- waltzie August 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my code using some kind of graph.

import collections
def recommenderSystem(_data, _find):
    buyers = collections.defaultdict(set) #key will be user, elements will be same elements
    items = collections.defaultdict(set) #key will be item, elements will be other elements
    
    for line in [x.split(":") for x in _data.split("\n")]:
        buyer, item = line[0], line[1]
        buyers[buyer].add(item)
        
        for i_item in buyers[buyer]:
            if i_item != item:
                items[item].add(i_item)
                items[i_item].add(item)
                
    strong_set = items[_find]
    strong = len(strong_set)
    all_set = findAllConnections(items, _find, _find)
    weak_set = all_set - strong_set
    weak = len(weak_set)
    
    print items[_find]
    print weak_set
    
    return strong, weak
    
def findAllConnections(items, key, _find, collect = None):
    collect = set() if collect == None else collect
    for item in items[key]:
        if item != _find and not item in collect:
            collect.add(item)
            findAllConnections(items, item, _find, collect)
    return collect
    
print recommenderSystem("""first:ABC
first:HIJ
sec:HIJ
sec:KLM
third:NOP
fourth:ABC
fourth:QRS
first:DEF
fifth:KLM
fifth:TUV""", "ABC")

- Oladipo September 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my code using graphs:

import collections
def recommenderSystem(_data, _find):
    buyers = collections.defaultdict(set) #key will be user, elements will be same elements
    items = collections.defaultdict(set) #key will be item, elements will be other elements
    
    for line in [x.split(":") for x in _data.split("\n")]:
        buyer, item = line[0], line[1]
        buyers[buyer].add(item)
        
        for i_item in buyers[buyer]:
            if i_item != item:
                items[item].add(i_item)
                items[i_item].add(item)
                
    strong_set = items[_find]
    strong = len(strong_set)
    all_set = findAllConnections(items, _find, _find)
    weak_set = all_set - strong_set
    weak = len(weak_set)
    
    print items[_find]
    print weak_set
    
    return strong, weak
    
def findAllConnections(items, key, _find, collect = None):
    collect = set() if collect == None else collect
    for item in items[key]:
        if item != _find and not item in collect:
            collect.add(item)
            findAllConnections(items, item, _find, collect)
    return collect
    
print recommenderSystem("""first:ABC
first:HIJ
sec:HIJ
sec:KLM
third:NOP
fourth:ABC
fourth:QRS
first:DEF
fifth:KLM
fifth:TUV""", "ABC")

- Oladipo September 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How many test cases were you guys able to pass for this problem ?

- Aspirant September 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package bfs;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;

public class ItemRecommadation {

static class Node{
String data;
LinkedList<Node> connections = new LinkedList<>();
public Node(String data) {
this.data = data;
}
@Override
public String toString() {
return data;
}
}

public static void main(String[] args) {

String[] purchases = new String[]{"first:ABC","first:HIJ",
"sec:HIJ", "sec:KLM",
"third:NOP","fourth:ABC",
"fourth:QRS", "first:DEF",
"fifth:KLM", "fifth:TUV"};



determineRecommendation("ABC",purchases);
}

private static void determineRecommendation(String itemId, String[] purchases) {
Map<String,Node> nodes = initMap(purchases);

HashSet<String> weakly = new HashSet<>();
HashSet<String> strongly = new HashSet<>();
HashSet<String> visited = new HashSet<>();
LinkedList<Node> list = new LinkedList<>();
list.add(nodes.get(itemId));
visited.add(itemId);
int distance = 0;
LinkedList<Node> nextList = new LinkedList<>();

while(!list.isEmpty()){
Node node = list.remove();
for(Node conn : node.connections){
if(!visited.contains(conn.data)){
nextList.add(conn);
visited.add(conn.data);
}
}
if(list.isEmpty()){
list.addAll(nextList);
distance++;
if(distance == 2){
nextList.forEach(n-> strongly.add(n.data));
}else if(distance>2 && distance%2 == 0){
nextList.forEach(n-> weakly.add(n.data));
}
nextList.clear();
}
}
System.out.println(strongly);
System.out.println(weakly);

}

private static Map<String, Node> initMap(String[] purchases) {
Map<String,Node> map = new HashMap<>();

for (String purchase : purchases) {
String[] custItem = purchase.split(":");
Node customer = map.get(custItem[0]);
Node item = map.get(custItem[1]);
if(customer == null){
customer = new Node(custItem[0]);
map.put(custItem[0], customer);
}
if(item == null){
item = new Node(custItem[1]);
map.put(custItem[1], item);
}
customer.connections.add(item);
item.connections.add(customer);
}
return map;
}


}

- Fatih January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;

public class ItemRecommadation {

    static class Node{
        String data;
        LinkedList<Node> connections = new LinkedList<>();
        public Node(String data) {
            this.data = data;
        }        
        @Override
        public String toString() {
            return data;
        }
    }
    
    public static void main(String[] args) {

        String[] purchases = new String[]{"first:ABC","first:HIJ", 
                "sec:HIJ", "sec:KLM", 
                "third:NOP","fourth:ABC", 
                "fourth:QRS", "first:DEF",
                "fifth:KLM", "fifth:TUV"};
        
        
        
        determineRecommendation("ABC",purchases);
    }
    
    private static void determineRecommendation(String itemId, String[] purchases) {
        Map<String,Node> nodes = initMap(purchases);
        
        HashSet<String> weakly = new HashSet<>();
        HashSet<String> strongly = new HashSet<>();
        HashSet<String> visited = new HashSet<>();
        LinkedList<Node> list = new LinkedList<>();
        list.add(nodes.get(itemId));
        visited.add(itemId);
        int distance = 0;
        LinkedList<Node> nextList = new LinkedList<>();
        
        while(!list.isEmpty()){
            Node node = list.remove();
            for(Node conn : node.connections){
                if(!visited.contains(conn.data)){
                    nextList.add(conn);
                    visited.add(conn.data);
                }
            }
            if(list.isEmpty()){
                list.addAll(nextList);
                distance++;
                if(distance == 2){
                    nextList.forEach(n-> strongly.add(n.data));
                }else if(distance>2 && distance%2 == 0){
                    nextList.forEach(n-> weakly.add(n.data));
                }
                nextList.clear();
            }
        }
        System.out.println(strongly);
        System.out.println(weakly);
        
    }

    private static Map<String, Node> initMap(String[] purchases) {
        Map<String,Node> map = new HashMap<>();
        
        for (String purchase : purchases) {
            String[] custItem = purchase.split(":");
            Node customer = map.get(custItem[0]);
            Node item = map.get(custItem[1]);
            if(customer == null){
                customer = new Node(custItem[0]);
                map.put(custItem[0], customer);
            }
            if(item == null){
                item = new Node(custItem[1]);
                map.put(custItem[1], item);
            }
            customer.connections.add(item);
            item.connections.add(customer);
        }        
        return map;
    }
}

- Fatih January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;

public class ItemRecommadation {

    static class Node{
        String data;
        LinkedList<Node> connections = new LinkedList<>();
        public Node(String data) {
            this.data = data;
        }        
        @Override
        public String toString() {
            return data;
        }
    }
    
    public static void main(String[] args) {

        String[] purchases = new String[]{"first:ABC","first:HIJ", 
                "sec:HIJ", "sec:KLM", 
                "third:NOP","fourth:ABC", 
                "fourth:QRS", "first:DEF",
                "fifth:KLM", "fifth:TUV"};
        
        
        
        determineRecommendation("ABC",purchases);
    }
    
    private static void determineRecommendation(String itemId, String[] purchases) {
        Map<String,Node> nodes = initMap(purchases);
        
        HashSet<String> weakly = new HashSet<>();
        HashSet<String> strongly = new HashSet<>();
        HashSet<String> visited = new HashSet<>();
        LinkedList<Node> list = new LinkedList<>();
        list.add(nodes.get(itemId));
        visited.add(itemId);
        int distance = 0;
        LinkedList<Node> nextList = new LinkedList<>();
        
        while(!list.isEmpty()){
            Node node = list.remove();
            for(Node conn : node.connections){
                if(!visited.contains(conn.data)){
                    nextList.add(conn);
                    visited.add(conn.data);
                }
            }
            if(list.isEmpty()){
                list.addAll(nextList);
                distance++;
                if(distance == 2){
                    nextList.forEach(n-> strongly.add(n.data));
                }else if(distance>2 && distance%2 == 0){
                    nextList.forEach(n-> weakly.add(n.data));
                }
                nextList.clear();
            }
        }
        System.out.println(strongly);
        System.out.println(weakly);
        
    }

    private static Map<String, Node> initMap(String[] purchases) {
        Map<String,Node> map = new HashMap<>();
        
        for (String purchase : purchases) {
            String[] custItem = purchase.split(":");
            Node customer = map.get(custItem[0]);
            Node item = map.get(custItem[1]);
            if(customer == null){
                customer = new Node(custItem[0]);
                map.put(custItem[0], customer);
            }
            if(item == null){
                item = new Node(custItem[1]);
                map.put(custItem[1], item);
            }
            customer.connections.add(item);
            item.connections.add(customer);
        }        
        return map;
    }
}

- Fatih January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ShoppingSuggestor {;
public static Map<String,LinkedList<String>> shoppersMap=new HashMap<>();
public static Map<String,LinkedList<String>> itemStrongMap=new HashMap<>();
public static LinkedList<String> weakItemList= new LinkedList<String>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ShoppingSuggestor shop=new ShoppingSuggestor();
		shop.addItem("first", "ABC");
		shop.addItem("first", "HIJ");
		shop.addItem("sec","HIJ");
		shop.addItem("sec", "KLM");
		shop.addItem("third", "NOP");
		shop.addItem("fourth", "ABC");
		shop.addItem("fourth", "QRS");
		shop.addItem("first", "DEF");
		shop.addItem("fifth", "KLM");
		shop.addItem("fifth", "TUV");
		System.out.println("Entries are successfull");
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter itemName name");
		String desiredItem=sc.next();
		for(Map.Entry<String,LinkedList<String>> itemLList:shoppersMap.entrySet())
			shop.createMapFromList(itemLList.getValue());
		for(String item:itemStrongMap.get(desiredItem)){
			if(itemStrongMap.containsKey(item))
				shop.createWeakList(itemStrongMap.get(item),desiredItem);
		}
			System.out.println("["+itemStrongMap.get(desiredItem).size()+","+weakItemList.size()+"]");
		}
	private void createWeakList(LinkedList<String> list,String desiredItem){
		for(String item:list)
			if(!(weakItemList.contains(item)|| item.equalsIgnoreCase(desiredItem) || itemStrongMap.get(desiredItem).contains(item)))
				{weakItemList.add(item);
				createWeakList(itemStrongMap.get(item), desiredItem);
				}
}
	private void createMapFromList(LinkedList<String> list){
		for(String item1:list)
			for(String item2:list )
				if(!item1.equalsIgnoreCase(item2))
			       createItemMap(item1,item2);		
	}
	private  void createItemMap(String itemName, String attachedItem){
		if(itemStrongMap.containsKey(itemName)){
			LinkedList<String> addedItems=itemStrongMap.get(itemName);
			if(!addedItems.contains(attachedItem))
			addedItems.add(attachedItem);
			itemStrongMap.put(itemName, addedItems);
		}else
			itemStrongMap.put(itemName,new LinkedList<String>(Arrays.asList(attachedItem)));		
	}
private void addItem(String customerName, String item){
	if(shoppersMap.containsKey(customerName)){
		LinkedList<String> addedItems=shoppersMap.get(customerName);
		addedItems.add(item);
		shoppersMap.put(customerName, addedItems);
	}else	
		shoppersMap.put(customerName,new LinkedList<String>(Arrays.asList(item)));		
}

}

- Faisal May 06, 2017 | Flag Reply


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