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 Technical Screen rounds at Uber.

What role is this question designed for?

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

Build a Quadtree and Analyze a Graph

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Solve the following two coding problems. 1. **Build a quadtree from an image** You are given an `N x N` matrix of integers representing an image, where `N` is a power of 2. A quadtree node represents a square region of the image. - If all values in the region are the same, the node should be a **leaf** storing that value. - Otherwise, the node should be an **internal node** with exactly four children representing the region's: - top-left quadrant - top-right quadrant - bottom-left quadrant - bottom-right quadrant Design the quadtree node structure and write a function that builds the quadtree for the input matrix. 2. **Find nodes that always lead to terminal nodes** You are given a directed graph with nodes labeled from `0` to `n - 1`, represented as an adjacency list `graph`, where `graph[i]` contains all outgoing neighbors of node `i`. - A **terminal node** is a node with no outgoing edges. - A node is **safe** if every possible path starting from that node eventually ends at a terminal node. Return all safe nodes in ascending order.

Quick Answer: This question evaluates skills in spatial data structures and recursive tree construction (building a quadtree) as well as graph analysis using traversal and cycle/safety detection to identify nodes that necessarily reach terminal nodes.

Build a Quadtree from an Image

Return a nested dictionary quadtree for an N x N matrix where uniform regions become leaves.

Constraints

Inputs are Python literals matching the function signature.
Return a deterministic exact-match value.

Examples

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

Expected Output: {'leaf': True, 'value': 1}

Explanation: Uniform leaf.

Input: ([[1,0],[0,1]],)

Expected Output: {'leaf': False, 'children': [{'leaf': True, 'value': 1}, {'leaf': True, 'value': 0}, {'leaf': True, 'value': 0}, {'leaf': True, 'value': 1}]}

Explanation: Four leaf children.

Input: ([],)

Expected Output: None

Explanation: Empty image.

Hints

Model object-style prompts as arrays or operation streams when needed.
Handle empty and boundary cases before the main logic.

Eventual Safe Nodes in a Directed Graph

Return all nodes from which every path eventually reaches a terminal node.

Constraints

Inputs are Python literals matching the function signature.
Return a deterministic exact-match value.

Examples

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

Expected Output: [2, 4, 5, 6]

Explanation: Classic safe nodes example.

Input: ([[],[0],[1]],)

Expected Output: [0, 1, 2]

Explanation: All nodes safe.

Input: ([[1],[0]],)

Expected Output: []

Explanation: Cycle has no safe nodes.

Hints

Model object-style prompts as arrays or operation streams when needed.
Handle empty and boundary cases before the main logic.

Quick Overview

This question evaluates skills in spatial data structures and recursive tree construction (building a quadtree) as well as graph analysis using traversal and cycle/safety detection to identify nodes that necessarily reach terminal nodes.