Katkat
Back

Compute tree depth and meeting rooms

Zest AIData Scientist · Onsite
HardData ScientistOnsiteCoding & Algorithms

Last updated

This question evaluates skills in tree traversal and recursion for computing maximum depth of a binary tree, alongside interval scheduling and resource allocation for determining the minimum number of meeting rooms, testing reasoning about data structures such as trees and interval endpoints.

Solve both coding problems.

Problem 1: Maximum depth of a binary tree

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes on the longest path from the root node down to a leaf node.

Assumptions:

  • If the tree is empty, return 0.
  • The tree may be highly unbalanced.
  • The number of nodes can be up to 100,000, so consider recursion-depth limitations depending on the language.

Example: Input tree: 3, 9, 20, null, null, 15, 7 Output: 3

Problem 2: Minimum meeting rooms

Given an array of meeting time intervals intervals, where each interval is [start, end), return the minimum number of conference rooms required so that all meetings can be held.

Assumptions:

  • start < end for every meeting.
  • Times are integers.
  • Intervals are half-open, so a meeting ending at time 10 does not conflict with another meeting starting at time 10.
  • The number of intervals can be up to 100,000.

Example: Input: [[0, 30], [5, 10], [15, 20]] Output: 2

Example: Input: [[7, 10], [10, 12]] Output: 1