How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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 Interview 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 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.

Solve BST and Grid Query Problems

Quick Overview