How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Solve BST and Grid Query Problems | Uber Coding Question

Quick Overview

This question evaluates understanding of binary search tree order-statistics and grid reachability under threshold constraints, testing competencies in tree traversal and order-sensitive queries, scalable multi-query processing, graph exploration techniques, and dynamic programming for movement-restricted variants, while measuring algorithmic design and complexity analysis. Domain: Coding & Algorithms; level of abstraction: primarily practical application requiring efficient algorithm implementation with a strong conceptual grasp of trade-offs, data-structure selection, and scalability for large inputs.

Solve BST and Grid Query Problems

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Solve the following coding problems. ## Problem A: Find the kth largest value in a BST You are given the root of a binary search tree and an integer `k`. Return the kth largest value among all nodes in the tree. Count each node as one value. If duplicate values exist, count duplicates separately. Discuss at least two approaches, such as a traversal-based approach and an approach that is efficient for repeated queries. ## Problem B: Count reachable grid cells for multiple thresholds You are given an `m x n` grid of positive integers and an array `queries`. For each query value `q`, start from cell `(0, 0)` and move in the four cardinal directions: up, down, left, and right. For that query, you may enter only cells whose value is strictly less than `q`. Return, for every query, the number of distinct cells reachable from `(0, 0)` under that rule. Constraints may be large, for example `m * n` up to `100000` and the number of queries up to `100000`, so solving each query independently may be too slow. Follow-up: How would the approach change if movement were restricted to only right and down? You only need to explain the dynamic programming idea; code is not required.

Quick Answer: This question evaluates understanding of binary search tree order-statistics and grid reachability under threshold constraints, testing competencies in tree traversal and order-sensitive queries, scalable multi-query processing, graph exploration techniques, and dynamic programming for movement-restricted variants, while measuring algorithmic design and complexity analysis. Domain: Coding & Algorithms; level of abstraction: primarily practical application requiring efficient algorithm implementation with a strong conceptual grasp of trade-offs, data-structure selection, and scalability for large inputs.

Part 1: Find the kth Largest Value in a BST

You are given a binary search tree represented as a level-order Python list. Missing children are written as None. Return the kth largest value in the tree, counting duplicate values as separate nodes. Assume the BST rule is: every value in the left subtree is less than or equal to the node value, and every value in the right subtree is greater than or equal to the node value. Interview extension: after solving the single-query version, think about how subtree sizes could be stored to support many kth-largest queries on the same tree efficiently.

Constraints

1 <= number of non-None nodes <= 100000
1 <= k <= number of non-None nodes
-10^9 <= node values <= 10^9
The input list represents a valid BST

Examples

Input: ([5, 3, 7, 2, 4, 6, 8], 1)

Expected Output: 8

Explanation: The values in descending order are [8, 7, 6, 5, 4, 3, 2], so the 1st largest is 8.

Input: ([5, 3, 7, 2, 4, 6, 8], 3)

Expected Output: 6

Explanation: The descending order is [8, 7, 6, 5, 4, 3, 2], so the 3rd largest value is 6.

Input: ([5, 3, 7, 3, 4, 7, 8], 4)

Expected Output: 5

Explanation: Duplicates count separately. The descending order is [8, 7, 7, 5, 4, 3, 3], so the 4th largest is 5.

Input: ([5, 3, 8, None, 4, None, 9], 2)

Expected Output: 8

Explanation: The actual node values are [5, 3, 8, 4, 9]. In descending order they are [9, 8, 5, 4, 3], so the 2nd largest is 8.

Input: ([10], 1)

Expected Output: 10

Explanation: A single-node tree has only one value, so the 1st largest is 10.

Input: ([], 1)

Expected Output: None

Explanation: The tree is empty, so there is no 1st largest value.

Input: ([5, 3, 7], 5)

Expected Output: None

Explanation: There are only 3 actual nodes in the tree, so the 5th largest value does not exist.

Hints

In a BST, a reverse inorder traversal (right -> node -> left) visits values from largest to smallest.
If the same tree must answer many kth-largest queries, think about augmenting each node with the size of its subtree.

Part 2: Count Reachable Grid Cells for Multiple Thresholds

You are given an m x n grid of positive integers and an array queries. For each query value q, start at cell (0, 0) and move in the four cardinal directions: up, down, left, and right. For that query, you may enter only cells whose value is strictly less than q. Return, for every query, the number of distinct cells reachable from (0, 0). The grid and the number of queries can both be large, so solving each query independently is too slow.

Constraints

1 <= m, n
1 <= m * n <= 100000
1 <= len(queries) <= 100000
1 <= grid[r][c], queries[i] <= 10^9

Examples

Input: ([[1,2,3],[2,5,7],[3,5,1]], [5,6,2])

Expected Output: [5, 8, 1]

Explanation: For q=5, only cells with values 1,2,3,2,3 are reachable before the 5-value barriers block access to the bottom-right 1. For q=6, the 5-value cells become usable, so 8 cells are reachable. For q=2, only the starting cell with value 1 is allowed.

Input: ([[5,7],[8,9]], [3,5,6])

Expected Output: [0, 0, 1]

Explanation: The start cell has value 5. It is not strictly less than 3 or 5, so those answers are 0. For q=6, the start cell is valid, but both neighbors are too large, so only 1 cell is reachable.

Input: ([[4]], [4,5,1,5])

Expected Output: [0, 1, 0, 1]

Explanation: This single-cell grid checks strict inequality and duplicate queries. The only cell is counted exactly when q > 4.

Input: ([[1,10,3],[2,9,4],[8,7,5]], [6,11,3,8])

Expected Output: [2, 9, 2, 2]

Explanation: For thresholds 3, 6, and 8, only the cells 1 and 2 are reachable because larger barrier values block access to the rest. When q=11, every cell becomes reachable.

Hints

Process queries in sorted order so you can reuse work from smaller thresholds.
Use a min-heap frontier of discovered cells; when the smallest frontier value becomes allowed, expand from it.

Part 3: Right-and-Down Grid Queries

This is the follow-up variant of the grid problem. You are given an m x n grid of positive integers and an array queries. For each query value q, start at cell (0, 0) and move only right or down. For that query, you may enter only cells whose value is strictly less than q. Return, for every query, the number of distinct cells reachable from (0, 0). Because movement is only right and down, reachability has a dynamic-programming flavor: a cell can become reachable only if it is open and at least one of its top or left neighbors is already reachable.

Constraints

1 <= m, n
1 <= m * n <= 100000
1 <= len(queries) <= 100000
1 <= grid[r][c], queries[i] <= 10^9

Examples

Input: ([[1,2,9],[2,9,3],[3,4,5]], [2,5,10])

Expected Output: [1, 5, 9]

Explanation: For q=2 only the start cell 1 is open. For q=5, five cells are reachable; cell (1,2)=3 is open but blocked because both its top and left predecessors are 9. For q=10, all 9 cells are open and reachable.

Input: ([[5,1],[1,1]], [5,6])

Expected Output: [0, 4]

Explanation: For q=5 the start cell is not allowed because 5 is not strictly less than 5, so nothing is reachable. For q=6 all four cells are allowed and reachable.

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

Expected Output: [0, 1, 1]

Explanation: This is a single-cell grid. The only cell is reachable exactly when the query is greater than 7.

Input: ([[1,3,2],[2,5,4]], [6,3,5])

Expected Output: [6, 2, 5]

Explanation: The queries are not sorted, so answers must be returned in the original order. For q=3 only the start and the cell below it are reachable; for q=5 five cells are reachable; for q=6 all six cells are reachable.

Input: ([[1,1],[1,2]], [2,2,3])

Expected Output: [3, 3, 4]

Explanation: Repeated queries should give repeated answers. With q=2, the three cells with value 1 are reachable. With q=3, all four cells are reachable.

Hints

With only right/down moves, a cell depends only on its top and left neighbors.
Activate cells in increasing value order. When a cell becomes both active and reachable, propagate that reachability forward to already-active children.

Quick Overview

Solve BST and Grid Query Problems

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Part 1: Find the kth Largest Value in a BST

Constraints

1 <= number of non-None nodes <= 100000
1 <= k <= number of non-None nodes
-10^9 <= node values <= 10^9
The input list represents a valid BST

Examples

Input: ([5, 3, 7, 2, 4, 6, 8], 1)

Expected Output: 8

Explanation: The values in descending order are [8, 7, 6, 5, 4, 3, 2], so the 1st largest is 8.

Input: ([5, 3, 7, 2, 4, 6, 8], 3)

Expected Output: 6

Explanation: The descending order is [8, 7, 6, 5, 4, 3, 2], so the 3rd largest value is 6.

Input: ([5, 3, 7, 3, 4, 7, 8], 4)

Expected Output: 5

Explanation: Duplicates count separately. The descending order is [8, 7, 7, 5, 4, 3, 3], so the 4th largest is 5.

Input: ([5, 3, 8, None, 4, None, 9], 2)

Expected Output: 8

Explanation: The actual node values are [5, 3, 8, 4, 9]. In descending order they are [9, 8, 5, 4, 3], so the 2nd largest is 8.

Input: ([10], 1)

Expected Output: 10

Explanation: A single-node tree has only one value, so the 1st largest is 10.

Input: ([], 1)

Expected Output: None

Explanation: The tree is empty, so there is no 1st largest value.

Input: ([5, 3, 7], 5)

Expected Output: None

Explanation: There are only 3 actual nodes in the tree, so the 5th largest value does not exist.

Hints

In a BST, a reverse inorder traversal (right -> node -> left) visits values from largest to smallest.
If the same tree must answer many kth-largest queries, think about augmenting each node with the size of its subtree.

Part 2: Count Reachable Grid Cells for Multiple Thresholds

Constraints

1 <= m, n
1 <= m * n <= 100000
1 <= len(queries) <= 100000
1 <= grid[r][c], queries[i] <= 10^9

Examples

Input: ([[1,2,3],[2,5,7],[3,5,1]], [5,6,2])

Expected Output: [5, 8, 1]

Input: ([[5,7],[8,9]], [3,5,6])

Expected Output: [0, 0, 1]

Explanation: The start cell has value 5. It is not strictly less than 3 or 5, so those answers are 0. For q=6, the start cell is valid, but both neighbors are too large, so only 1 cell is reachable.

Input: ([[4]], [4,5,1,5])

Expected Output: [0, 1, 0, 1]

Explanation: This single-cell grid checks strict inequality and duplicate queries. The only cell is counted exactly when q > 4.

Input: ([[1,10,3],[2,9,4],[8,7,5]], [6,11,3,8])

Expected Output: [2, 9, 2, 2]

Explanation: For thresholds 3, 6, and 8, only the cells 1 and 2 are reachable because larger barrier values block access to the rest. When q=11, every cell becomes reachable.

Hints

Process queries in sorted order so you can reuse work from smaller thresholds.
Use a min-heap frontier of discovered cells; when the smallest frontier value becomes allowed, expand from it.

Part 3: Right-and-Down Grid Queries

Constraints

1 <= m, n
1 <= m * n <= 100000
1 <= len(queries) <= 100000
1 <= grid[r][c], queries[i] <= 10^9

Examples

Input: ([[1,2,9],[2,9,3],[3,4,5]], [2,5,10])

Expected Output: [1, 5, 9]

Input: ([[5,1],[1,1]], [5,6])

Expected Output: [0, 4]

Explanation: For q=5 the start cell is not allowed because 5 is not strictly less than 5, so nothing is reachable. For q=6 all four cells are allowed and reachable.

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

Expected Output: [0, 1, 1]

Explanation: This is a single-cell grid. The only cell is reachable exactly when the query is greater than 7.

Input: ([[1,3,2],[2,5,4]], [6,3,5])

Expected Output: [6, 2, 5]

Input: ([[1,1],[1,2]], [2,2,3])

Expected Output: [3, 3, 4]

Explanation: Repeated queries should give repeated answers. With q=2, the three cells with value 1 are reachable. With q=3, all four cells are reachable.

Hints

With only right/down moves, a cell depends only on its top and left neighbors.
Activate cells in increasing value order. When a cell becomes both active and reachable, propagate that reachability forward to already-active children.