Interesting Question from Hackerrank : "Diameter:


Who cannot access the link I will write it down.

Problem Statement

Diameter

The diameter of a graph is the maximum shortest path between any two nodes.

At the beginning, there is a simple grpah contains exactly 1 node. Then we add new nodes one by one to the graph. Each time when we add a new node to the graph, we also add exactly one edge to connect this node to another node which already exists.

We want to find the diameter of the graph each time we add a new node. Note that each edge cost 1.

Input Format:

First line of the input contains one integer N, indicating how many new nodes we will add.

Then following N lines. The ith line contains an integer X, which means we add the ith node and an edge connecting the Xth node and ith node.

The original node is the 0th node.

Output Format:

Output N lines. The ith line is an integer indicating the diameter of the graph after adding the ith node.

Constraints:

0 < N <= 100000

0 <= Xi < i

i is counting from 1

Sample Input:

5

0

0

1

1

1

Sample Output:

1

2

3

3

3

Explanation:

Firstly the graph contains only node 0. The first line of output is 1 because the diameter becomes 1 when node 1 is added and connected to node 0. Diameter becomes 2 after adding node 2 to node 0. Then adding node 3, 4, 5, all of them are connecting to node 1, caculate the shortest path of all pairs of nodes, the maximum shortest path is 3, so the last 3 lines of output are all 3.

Looking at the constrains it is not possible to calculate diameter everytime we add node to graph using floyd warshal algo.
Any Idea how to approach this kind of question.
Thanks.

Suppose you have a tree consisting of n nodes, where the diameter of the tree is u-----v.

Next, you want to connect a new node w to any node of the existing tree.

It can be easily proved that the new diameter will either be u-----v, w-----u or w-----v.

In this question after each addition of new nodes you would like to know the distance (w, u) and distance (w, v). This can easily be found out either by online / offline construction of LCA data-structure with a pre-processing of O (n log n) and O (log n) per query.

rsaha are you sure that this will always be a tree.
also is there will be n queries each taking nlogn time wouldn’t be this approach will time out …

  1. “Each time when we add a new node to the graph, we also add exactly one edge to connect this node to another node which already exists.”
    This statement clearly says that we will get a tree at each and every step till the end.

  2. There will be n queries. Each will take O (log n) time. O (n log n) is the time taken for pre-processing.