Katkat
Back

Build a Quadtree and Analyze a Graph

UberSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.