FastPrepFind Minimum Possible Diameter
Problems/Find Minimum Possible Diameter

Find Minimum Possible Diameter

Google logoGoogle● HardOA

Updated Sep 2026

QuestionFunctionExamplesConstraints

Problem statement

You are given a tree consisting of n vertices.

You can perform the following operation at most k times: delete a single leaf of the tree (the operation can produce new leaves, 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 n-1 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

Function

findMinimumDiameter(n: int, k: int, edges: int[][]) → int

Examples

Example 1

n = 4k = 0edges = [[1, 2], [2, 3], [4, 3]]return = 3

:3

Example 2

n = 4k = 1edges = [[2, 3], [4, 3], [1, 4]]return = 2

:o

Constraints

  • 1 <= n <= 10^5
  • 0 <= k < n
  • edges.length == n - 1
  • Vertices are numbered from 1 to n, and edges forms a tree.

More Google interview questions

  • Evaluate a Nested Math ExpressionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Distinct Subset SumsONSITE INTERVIEW · Seen Nov 2026
  • Playlist With No Same Artist in a RowONSITE INTERVIEW · Seen Nov 2026
  • Route Pattern MatcherPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
  • Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
  • Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • Minimum HeightSnowflake · OASnowflake interview questions
  • Split Array to Minimize the Largest SumInfosys · OAInfosys interview questions
  • Split Array Largest SumAuxoAI · OA
  • Binary Tree CamerasAmazon · OA · PHONE SCREEN
  • K-th Ancestor Subtree Preorder QueryAdobe · OAAdobe interview questions
  • Minimum Satellite Data Transfer IterationsHSBC · OAHSBC interview questions
  • Data ReorganizationGoldman Sachs · OAGoldman Sachs interview questions
  • Collect Opportunity Data in a TreeSalesforce · OASalesforce interview questions
  • Collect CoinsCisco · OACisco interview questions
  • Uber Circular Shuttle OptimizationUber · OAUber interview questions

Interview reports that mention this question

  • Google OA: What It Tests (2026)

Google interview experiences

  • Google L5 Security Engineer Domain Knowledge Round: 1 Experience
  • Google Software Engineer Onsite Questions: 10 Experiences
  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int findMinimumDiameter(int n, int k, int[][] edges) {
      // write your code here
    }

}
Checking account…