Find Heap Objects Not Referenced by the Stack
Company: Anduril
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Find Heap Objects Not Referenced by the Stack
Each heap object has a unique integer address. In this first version, heap objects do not reference one another. An object is reachable exactly when its address appears at least once in `stack_addresses`. Return the addresses of all unreachable objects in the same relative order as `heap_addresses`.
### Function Signature
```python
def dead_object_addresses(
stack_addresses: list[int],
heap_addresses: list[int],
) -> list[int]:
...
```
### Example
```text
Input: stack_addresses = [100, 300, 300]
heap_addresses = [100, 200, 300, 400]
Output: [200, 400]
```
### Constraints
- `0 <= len(stack_addresses), len(heap_addresses) <= 200_000`
- Heap-object addresses are unique.
- A stack address that is not present in `heap_addresses` is ignored.
- Do not mutate the inputs.
### Clarifications
- Duplicate stack addresses do not change reachability.
- Return primitive integer addresses so the result is directly serializable and comparable.
### Hints
- Choose a representation that makes repeated address membership checks efficient.
- Target expected linear time and linear auxiliary space in the number of distinct stack addresses.
Quick Answer: Find heap objects that are not directly referenced by any stack address when heap objects have no outgoing references. Use efficient set membership to return unreachable primitive addresses in input order, ignoring duplicate roots and roots outside the heap without mutating inputs.
Return every unique heap-object address that does not occur in the stack-address list, preserving the heap list's original order. Stack addresses absent from the heap are ignored and inputs are not mutated.
Constraints
- Each heap address is unique.
- Each input may contain up to 200,000 addresses.
- Duplicate stack addresses do not change reachability.
- The output preserves heap order.
Examples
Input: {'stack_addresses':[100,300,300],'heap_addresses':[100,200,300,400]}
Expected Output: [200, 400]
Explanation: The example ignores duplicate references.
Input: {'stack_addresses':[],'heap_addresses':[1,2,3]}
Expected Output: [1, 2, 3]
Explanation: Without stack roots every heap object is dead.
Hints
- Build a set of addresses mentioned by the stack, then scan the heap once.