PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep
|Home/Coding & Algorithms/Uber

Build a Quadtree and Analyze a Graph

Last updated: Mar 29, 2026

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.

  • medium
  • Uber
  • Coding & Algorithms
  • Software Engineer

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.

Related Interview Questions

  • Maximize Throughput and Count Trigger Components - Uber (medium)
  • Replace Dashes With Nearest Letters - Uber (medium)
  • Find Earliest Column With One - Uber (easy)
  • Solve Wonderful Strings and Grid Queries - Uber (hard)
  • Count Islands After Land Additions - Uber (medium)
Uber logo
Uber
Dec 28, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
8
0

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.

  1. 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.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Uber•More Software Engineer•Uber Software Engineer•Uber Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.