Find Unreachable Objects in a Heap Graph

Problem Statement

In embedded runtimes and garbage collection systems, identifying orphaned memory blocks is essential for preventing memory leaks and reclaiming unused resources.

Implement a function that simulates the mark phase of a tracing garbage collector. You are given:

• roots: A list of memory addresses (integers) residing on the stack or in global registers.
• heap: A list of tuples (address, references) representing all blocks currently allocated in the heap, given in their original allocation order. Each references list contains memory addresses that the object points to.

An object in the heap is considered reachable if:

1. It is directly referenced by a valid address in roots, or
2. It can be reached by following a chain of references starting from any reachable heap object.

Your task is to identify and return all addresses in heap that are unreachable, preserving their original order of appearance in heap.

Requirements & Edge Cases

• Dangling pointers: An address listed in roots or inside a references list might not exist in heap. Pointers to non-existent addresses should be safely ignored and not traversed.
• Cycles and self-references: The graph may contain cycles and nodes that point to themselves. Your traversal must terminate without infinite recursion or looping.
• Efficiency: Expected time complexity must be O(V + E) where V is the number of heap objects and E is the total number of references.

Function Signature

def find_unreachable_objects(
    roots: list[int],
    heap: list[tuple[int, list[int]]]
) -> list[int]:
    pass

Examples

Example 1

roots = [10, 99]  # 99 is a dangling pointer
heap = [
    (10, [20]),
    (20, [10, 30]),
    (30, []),
    (40, [50]),
    (50, [40])
]
# Output: [40, 50]

Explanation: Starting from root 10, we visit 10 -> 20 -> 30. Address 99 does not exist in heap and is skipped. Objects 40 and 50 point to each other in an isolated cycle, making them unreachable.

Example 2

roots = []
heap = [
    (1, [1]),
    (2, [])
]
# Output: [1, 2]

Explanation: With no valid roots, all heap objects are unreachable.