Quick Overview

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.

Compute tree depth and meeting rooms

Company: Zest AI

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

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`

Overview: 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.

Read the full Zest AI Data Scientist interview experience this question came from

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 along the longest path from the root node down to the farthest leaf node. The tree is provided as a level-order (breadth-first) array `values`, LeetCode-style: index 0 is the root, and `null`/`None` marks a missing child. For example, `[3, 9, 20, null, null, 15, 7]` encodes a tree with root 3, left child 9, right child 20, and 20's children 15 and 7. Notes: - If the tree is empty (`values` is empty or its first element is `null`), return 0. - The tree may be highly unbalanced (a long single chain). - The number of nodes can be up to 100,000, so prefer an iterative solution to avoid hitting the language's recursion-depth limit.

Constraints

  • 0 <= number of nodes <= 100,000
  • Node values fit in a 32-bit integer
  • The tree may be a long single chain (highly unbalanced)
  • An empty tree returns 0

Examples

Input: ([3, 9, 20, None, None, 15, 7],)

Expected Output: 3

Explanation: Root 3 -> right child 20 -> leaf 15 (or 7): the longest path has 3 nodes.

Input: ([],)

Expected Output: 0

Explanation: Empty tree has depth 0.

Hints

  1. Maximum depth equals the number of levels in a breadth-first traversal of the tree.
  2. A recursive depth-first solution is concise, but with up to 100,000 nodes a degenerate chain can overflow the call stack — prefer an iterative BFS or an explicit stack.
  3. When the input is a level-order array, you can reconstruct parent-to-child links in one left-to-right pass using a queue of parents, consuming two array slots (left, right) per parent and skipping nulls.

Minimum Number of Meeting Rooms

Given an array of meeting time intervals `intervals`, where each `intervals[i] = [start, end)` is half-open, return the minimum number of conference rooms required so that all meetings can be held. Because intervals are half-open, a meeting ending at time `10` does not conflict with another meeting starting at time `10` — they can share a room. Notes: - `start < end` for every meeting. - All times are integers. - The number of intervals can be up to 100,000. - If there are no meetings, return 0.

Constraints

  • 0 <= number of intervals <= 100,000
  • intervals[i] = [start, end) with start < end
  • All times are integers
  • Intervals are half-open: a meeting ending at t does not conflict with one starting at t

Examples

Input: ([[0, 30], [5, 10], [15, 20]],)

Expected Output: 2

Explanation: [0,30) overlaps both [5,10) and [15,20), so 2 rooms are needed; [5,10) and [15,20) don't overlap each other.

Input: ([[7, 10], [10, 12]],)

Expected Output: 1

Explanation: Half-open: the meeting ending at 10 does not conflict with the one starting at 10, so one room suffices.

Hints

  1. Decouple starts from ends: sort all start times and all end times into two separate sorted arrays.
  2. Sweep with two pointers. The maximum number of meetings that are simultaneously in progress is the answer.
  3. Because intervals are half-open, treat a start at time t as NON-conflicting with an end at time t — use a strict `start < end` comparison so the ending meeting frees its room first.

Loading coding console...