Google OA question

Posted
27 May 2025
415 reads

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.

How it went

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

Questions asked (1)

  1. 01

    Minimize Tree Diameter by Deleting Leaves

    Data Structures & Algorithms · Hard

    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

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!