CareerCup

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

Can you give more examples?

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']]

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.

//With a test
public class App {
static class Order {
		int id;
		List<String> items;
		public Order(int id, List<String> items) {
			this.id = id;
			this.items = items;
		}
		
	}
	public static void main(String[] args) {
		List<Order> orders = new ArrayList<>();
		List<String> l1 = new ArrayList<>();
		List<String> l2 = new ArrayList<>();
		List<String> l3 = new ArrayList<>();
		
		l1.add("A");
		l1.add("B");
		l2.add("B");
		l2.add("C");
		l3.add("K");
		l3.add("P");
		l3.add("L");
		l3.add("A");
		orders.add(new Order(1, l1));
		orders.add(new Order(2, l2));
		orders.add(new Order(3, l3));
		
		Map<String, List<Integer>> maps = new HashMap<>();
		orders.forEach(order -> {
			order.items.forEach(item -> {
				maps.putIfAbsent(item, new ArrayList<>());
				maps.get(item).add(order.id);
			});
		});
		maps.entrySet().stream().forEach(item -> {
			System.out.println(item.getKey()+":"+item.getValue());
		});
	}	
}