CareerCup

1. Find common elements in their adjacency list for person A.
2. Store the number of common elements for A’s 100 friend in an array
3. Use 'min-heap of k elements’ to retain k number of A’s friends with most mutual friends.
4. when A’s friend, say B, add new friends. Recalculate common elements between A and B and run the new number again 'min-heap of k elements’.

This is a classic graph traversal question.
In program, adjacencyMap is used to store edges.
vertexMap stores vertices. An vertex has inDegree and inDegree properties.
An vertex with zero inDegree means a journey starts from the vertex.
Edge's visited flag is used to indicate if an edge has been visited during traversing.
findStartingVerties returns vertices with zero inDegree.

public class Graph {
	Map<String, Set<Edge>> adjacencyMap = new HashMap<>();
	Map<String, Vertex> vertexMap = new HashMap<>();

	public static class Edge {
		protected String source;
		protected String dest;
		boolean visited = false;

		public Edge(String source, String dest) {
			this.source = source;
			this.dest = dest;
		}
	}

	public static class Vertex {
		protected String name;
		protected int inDegree = 0;
		protected int outDegree = 0;

		public Vertex(String name) {
			this.name = name;
		}
	}

	public Graph addEdge(String source, String dest) {
		getEdgeSet(source).add(new Edge(source, dest));
		getVertex(source).outDegree++;
		getVertex(dest).inDegree++;
		return this;
	}

	public void resetVisit() {
		adjacencyMap.values().stream().flatMap(edges -> edges.stream())
				.forEach(e -> e.visited = false);
	}

	private Set<Edge> getEdgeSet(String source) {
		if (!adjacencyMap.containsKey(source)) {
			Set<Edge> edgeSet = new HashSet<Edge>();
			adjacencyMap.put(source, edgeSet);
			return edgeSet;
		} else {
			return adjacencyMap.get(source);
		}
	}

	private Vertex getVertex(String name) {
		Vertex v = null;
		if (!vertexMap.containsKey(name)) {
			v = new Vertex(name);
			vertexMap.put(name, v);
		} else {
			v = vertexMap.get(name);
		}
		return v;
	}

	// depth-first traversal
	public void dft(String vertexName) {
		if (adjacencyMap.containsKey(vertexName)) {
			for (Edge e : adjacencyMap.get(vertexName)) {
				if (e.visited == false) {
					System.out.println(vertexName + "->" + e.dest);
					e.visited = true;
					dft(e.dest);
				}
			}
		}

	}

	public List<Vertex> findStartingVerties() {
		return vertexMap.values().stream().filter(v -> v.inDegree == 0)
				.collect(Collectors.toList());
	}

	public static void main(String[] args) {
		Graph g = new Graph();
		// SFO->LAX, LAX->ATL, ATL->DEN, DEN->BOS, BOS->JFK, JFK->DEN,DEN->PHL
		g.addEdge("SFO", "LAX").addEdge("LAX", "ATL").addEdge("ATL", "DEN")
				.addEdge("DEN", "BOS").addEdge("BOS", "JFK")
				.addEdge("JFK", "DEN").addEdge("DEN", "PHL")
				.addEdge("PHL", "DFW").addEdge("DFW", "SEA")
		        .addEdge("SEA", "DEN").addEdge("DEN", "HOU")
		        .addEdge("HOU", "MIA");
		
		g.findStartingVerties().stream().forEach(v -> {
			g.resetVisit();
			g.dft(v.name);
		});

		// starting from sfo with dft
		g.resetVisit();
		System.out.println("Let's pick SFO as the starting point.");
		g.dft("SFO");
	}
}