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.

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.

Hints

  1. Model object-style prompts as arrays or operation streams when needed.
  2. 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.

Hints

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

Loading coding console...