Find Unreachable Objects in a Heap Graph
Company: Anduril
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Find Unreachable Objects in a Heap Graph
Heap objects now contain references to other addresses. Each object is represented as `[address, references]`, where `references` is a list of integer addresses. An object is reachable if its address appears in `stack_addresses` or if it can be reached transitively by following references from a reachable object. Return every unreachable address in the same relative order as `heap_objects`.
### Function Signature
```python
def dead_object_addresses(
stack_addresses: list[int],
heap_objects: list[list],
) -> list[int]:
...
```
### Example
```text
Input:
stack_addresses = [10]
heap_objects = [
[10, [20]],
[20, [30]],
[30, [20]],
[40, [10]]
]
Output: [40]
```
### Constraints
- `0 <= len(heap_objects) <= 200_000`
- Heap-object addresses are unique.
- Every object record has exactly two fields: an integer address and a list of integer references.
- The total number of references is at most `400_000`.
- References and stack roots that do not identify a heap object are ignored.
- Cycles and self-references are allowed.
### Clarifications
- Reachability follows outgoing references only.
- Return primitive integer addresses in heap input order and do not mutate the inputs.
### Hints
- Treat addresses as vertices and references as directed relationships.
- Ensure each reachable object is processed at most once, even when cycles exist.
Quick Answer: Find unreachable objects in a heap graph starting from stack-root addresses. Traverse outgoing references while handling cycles, self-links, missing addresses, and large graphs, then return unreachable primitive addresses in original heap order with linear expected work.
Return heap-object addresses not transitively reachable from stack roots, preserving heap input order.
Constraints
- Heap addresses are unique
- Cycles and self-references are allowed
- Unknown roots and references are ignored
Examples
Input: {'stack_addresses': [], 'heap_objects': []}
Expected Output: []
Explanation: An empty heap has no dead objects.
Input: {'stack_addresses': [], 'heap_objects': [[1, []], [2, []]]}
Expected Output: [1, 2]
Explanation: Without roots every object is unreachable.
Hints
- Build an address-to-reference adjacency map.
- Mark from every valid stack root while processing each live object once.