Amazon Interview Question
Software DevelopersCountry: United States
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.
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")
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")
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;
}
}
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;
}
}
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;
}
}
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)));
}
}
I derived at this brute force but there should be a better way
}
- maksymas August 29, 2016