Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
That's a very good analysis but I question your second answer. I feel the total number is unbounded because you can have multiple directed edges from vertex A to vertex B. In your example if this were sorted it would only have one edge. But really it could have 20K edges going from A to B. It really just depends on how they are arranged. Is the question over possibility?..
(V^2 - V)/2 is the maximum number. Let's prove it.
Let G(V, E) be an acyclic graph with the most number of edges. Then:
Claim: There is a (the) sink node with exactly V - 1 incoming edges where a sink node is a vertex with no outgoing edges.
Proof: First note that we have to have a sink node. Otherwise, any vertex will have at least 1 outgoing edge and hence, a cycle.
Now note that for the optimal graph, the sink node must have "V - 1" incoming edges. Simply if it does not, then you can add the missing edges to the sink node and still produce no cycles. Therefore, the graph could not have possibly been optimal.
Therefore, the sink node has "V - 1" incoming edges.
Now the rest is easy. Remove this sink node from this graph and all the edges connected to it. You will get another G(V - 1, E) which is optimal. By recusing, we can go all the way to the graph with one vertex and 0 edges. This way, we are removing
(V - 1), (V - 2), ..., (1) edges to get to that graph. Therefore, the total number of edges is at most (V^2 - V) / 2.
On the other hand, as suggested above, you can indeed construct a graph with this many edges. Add an edge from vertex "0" to all other vertices except itself. Then from vertex "1" to all vertices except {0, 1}. Iterate until exactly "(V^2 - V) / 2" edges are added.
Acyclic undirected graph:
- Victor November 22, 2014V-1 edges. Spanning tree of the graph.
Acyclic directed graph:
Imagine the graph topologically sorted. It can only have edges going down (from top to bottom), otherwise it would have cycles.
The way to maximize the number of edges without creating cycles is to connect a given vertex to all other vertices that are below it (again, imagining the graph in a topological order). For instance, the vertex 0 is connected to 1, 2, 3, ..., V-1; vertex 1 to 2, 3, ..., V-1. So on and so forth.
Therefore, the total number of edges is: Sum (i=0 to V-1) i, which is equal to (V^2-V)/2.