Amazon Interview Question


Country: United States




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

use connected component approache

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class AmazonG {

	public static void main(String[] args) {
		
		List<Order> list = new ArrayList<>();
		
		List<String> o1 = new ArrayList<>();
		o1.add("Z");
		o1.add("B");
		o1.add("A");
		
		List<String> o2 = new ArrayList<>();
		//o2.add("B");
		o2.add("C");
		
		List<String> o3 = new ArrayList<>();
		o3.add("R");
		o3.add("Z");
		//o3.add("A");
		
		list.add(new Order("O1", o1));
		list.add(new Order("O2", o2));
		list.add(new Order("O3", o3));
		
		merge(list);		

	}
	
	
	static class Order{ 
		String orderId; 
		public Order(String orderId, List<String> items) {
			super();
			this.orderId = orderId;
			this.items = items;
		}
		List<String> items; 
	} 
	
	static class GNode{ 
		String item;
		List<String> orderid = new ArrayList<>();
		List<GNode> list = new ArrayList<>();;
		boolean visited;
		
	}
		
	static void merge(List<Order> list) 
	{
		Map<String, GNode> map = new HashMap<>();
		
		
		for(Order order : list)
		{
			
			String orderid = order.orderId;
			List<String> items = order.items;
			
			GNode prev = null;
			
			for(String item : items) {
				
				GNode g = map.get(item);
				
				if(g == null) {
					
					GNode gnode = new GNode();
					gnode.item = item;
					gnode.orderid.add(orderid);
					map.put(item, gnode);
 					if(prev == null) {
						prev = gnode;
					}
					else {
						prev.list.add(gnode);
						gnode.list.add(prev);
						prev = gnode;
					}
				}
				else {
					g.orderid.add(orderid);
					
					if(prev == null) {
						prev = g;
					}
					else {
						prev.list.add(g);
						g.list.add(prev);
						prev = g;
					}
				}							
			}
			
			
		}
		
		Queue<GNode> q = new LinkedList<>();
		Set<String> current_order_group = new HashSet<>();
				
		for(String key : map.keySet()) {
			GNode g = map.get(key);	
			
			if(!g.visited) {
				q.add(g);
				g.visited = true;
				
				while(!q.isEmpty()) {
					GNode i = q.poll();
					current_order_group.addAll(i.orderid);
					
					List<GNode> i_list = i.list;
					
					for(GNode gg : i_list) {
						if(!gg.visited) {
							q.add(gg);
							gg.visited = true;
						}
					}
					
				}
				
				System.out.println(current_order_group);
				current_order_group.clear();
			}		
		}
	}
}

- muesmat September 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you give more examples?

- funkbuster September 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is very similar to the "Merge Intervals" question. Sharing my solution in Python below.

Order Class

class Order:
  def __init__(self, orderID, items):
    self.orderID = orderID
    self.items = items

  def __repr__(self):
    return '{}->Items{}'.format(self.orderID, self.items)

Group Orders Function

def groupOrders(orders):
  # First sort the items so that we can optimally merge them
  orders.sort(key=lambda o: o.items)

  res = [orders[0]]

  # Iterate through the orders
  for currentOrder in orders[1:]:

    # Represents the overlap / commonality between two orders
    # If overlap is found, then merge them and create a new order with the union of them
    # Else, simply append it to the end of the array.
    foundMerge = False

    for ind2, groupedOrder in enumerate(res):
      overlap = set(currentOrder.items) & set(groupedOrder.items)

      if overlap:
        # If the orderId is already a list, just append, ex:- [O1, O2], O3 -> [O1, O2, O3]
        if type(groupedOrder.orderID) is list:
           groupedOrder.orderID.append(currentOrder.orderID)

        else: # If not a list, create a new list, ex:- O1, O2 -> [O1, O2]
          groupedOrder.orderID = [groupedOrder.orderID , currentOrder.orderID]

        res[ind2] = Order(  groupedOrder.orderID ,
                           set(currentOrder.items) | set(groupedOrder.items) )
        foundMerge = True
        break

    # If there was no overlap, simply append at the end of the array
    if not foundMerge:
      res.append(currentOrder)

  # Return only the orderID as the output
  return [x.orderID for x in res]

Test Code

orders = [ Order('O1', ['A', 'B']) ,
           Order('O2', ['C', 'D'])]
print(groupOrders(orders)) # ['O1', 'O2']

orders = [ Order('O1', ['A', 'B']) ,
           Order('O2', ['A', 'D'])]
print(groupOrders(orders)) # [['O1', 'O2']]

orders = [ Order('O1', ['A', 'B']) ,
           Order('O2', ['B', 'C']),
           Order('O3', ['D', 'E']) ]
print(groupOrders(orders)) # [['O1', 'O2'], 'O3']

orders = [ Order('O1', ['A', 'B']) ,
           Order('O2', ['C', 'D']),
           Order('O3', ['E', 'F']) ]
print(groupOrders(orders)) # ['O1', 'O2', 'O3']

orders = [ Order('O1', ['A', 'B']) ,
           Order('O2', ['A', 'D']),
           Order('O3', ['A', 'E']) ]
print(groupOrders(orders)) # [['O1', 'O2', 'O3']]

- prudent_programmer September 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar to connected component problem.Build graph of Order Id as node

First create a map

A - O1
B - O1, O2
C - O2
D - O3
E - O3

Now join all nodes in graph which has same map key ( in this case join O1 and O2 )

Now find all connected components of graphs.

- vishal September 19, 2018 | 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