Solve the following two coding problems.
-
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.
-
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.