Google OA question
Summary
This post details a specific Online Assessment (OA) question from Google, focusing on minimizing the diameter of a tree by performing at most k leaf deletions.
Full Experience
You are given a tree consisting of vertices
You can perform the following operation at most times: delete a single leaf of the tree (the operation can produce new leafs, that can be deleted later). The resulting tree must have as small diameter as possible. Find the minimum possible diameter.
Input Format The first line contains two space separated integers n and k. Each of the next lines contains two space separated integers , describing the current tree edge. It's guaranteed that the given graph is a tree.
Constraints
0<n<=1e5 0<k<n
Sample Input #00
4 0 1 2 2 3 4 3
Sample Output #00 3
Sample Input #01
4 1 2 3 4 3 1 4
Sample Output #01 2
Interview Questions (1)
You are given a tree consisting of vertices
You can perform the following operation at most times: delete a single leaf of the tree (the operation can produce new leafs, that can be deleted later). The resulting tree must have as small diameter as possible. Find the minimum possible diameter.
Input Format The first line contains two space separated integers n and k. Each of the next lines contains two space separated integers , describing the current tree edge. It's guaranteed that the given graph is a tree.
Constraints
0<n<=1e5 0<k<n
Sample Input #00
4 0 1 2 2 3 4 3
Sample Output #00 3
Sample Input #01
4 1 2 3 4 3 1 4
Sample Output #01 2