Google Interview Question
Software EngineersCountry: United States
Dynamic Programming.
1) First do DFS to count the number of points (only if it's unknown)
2) Then starting from the end nodes (which only have one connected node), maintain a count at every node which indicates all the nodes connected in the graph up till that point, including the node itself. When this number reached n/2 (where n is the number of nodes), that node and any outgoing connecting node (which has not already been considered) represent the two nodes which can subdivide the graph.
Also, since n is even, n/2 is an integer, meaning that when searching, you need to search for when the count reaches exactly n/2.
{{
- EPavlova November 22, 2015Could you clarify more on the problem. What kind of graph is this? What does it mean to subdivide graph equally by 2 points? Some sample.
}}