Katkat
Back

Find Heap Objects Not Referenced by the Stack

AndurilSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Implement a simplified mark-and-sweep sweep phase to identify unreferenced heap objects given a list of heap allocations and stack root pointers.

Problem Statement

In a simplified runtime environment, automatic memory reclamation requires identifying heap allocations that are no longer referenced by active execution threads.

You are given:

  • heap_objects: A list of integer memory addresses representing allocated heap blocks.
  • stack_roots: A list of integer memory addresses currently held as references in stack frames.

In this simplified runtime, heap objects do not contain outgoing references to other heap objects (there are no pointer graphs or cycles to traverse). An object is considered reachable if and only if its address appears directly within stack_roots.

Write a function find_unreachable_heap_objects that returns a list of heap object addresses that are not referenced by any stack root. The returned addresses must preserve their relative order from the input heap_objects list.

Requirements

  • The input lists must not be mutated.
  • stack_roots may contain duplicates or addresses that do not exist in heap_objects. Such invalid or redundant roots should be safely ignored.
  • The solution should run with optimal time complexity using fast set membership checks.

Function Signature

def find_unreachable_heap_objects(heap_objects: list[int], stack_roots: list[int]) -> list[int]:
    pass

Constraints

  • 0 <= len(heap_objects) <= 10^5
  • 0 <= len(stack_roots) <= 10^5
  • Addresses are non-negative integers (0 <= address <= 2^63 - 1)

Examples

Example 1

heap_objects = [1000, 1008, 1016, 1024, 1032]
stack_roots = [1008, 9999, 1008, 1032]

output = find_unreachable_heap_objects(heap_objects, stack_roots)
# Output: [1000, 1016, 1024]

Explanation: Addresses 1008 and 1032 are referenced on the stack. Root 9999 points outside the heap and is ignored. Duplicate root 1008 is deduplicated. Addresses 1000, 1016, and 1024 are unreachable and returned in original order.

Example 2

heap_objects = [0x10, 0x20]
stack_roots = []

output = find_unreachable_heap_objects(heap_objects, stack_roots)
# Output: [0x10, 0x20]

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

Edge Cases

  • Either heap_objects or stack_roots is empty.
  • All heap objects are referenced (returns []).
  • No heap objects are referenced (returns a copy of heap_objects).

Hints

Hint 1

Searching through `stack_roots` linearly for each heap object leads to `O(N * M)` time complexity, which is too slow for large inputs.

Hint 2

Convert `stack_roots` into a hash set to achieve `O(1)` average-time membership lookups while automatically discarding duplicate roots.

Hint 3

Iterate through `heap_objects` in order and collect elements that are absent from the set into a new list to avoid mutating the input.

Follow-up questions

  • How would you adapt your solution if heap objects could contain pointers to other heap objects (e.g., full graph traversal via BFS/DFS)?
  • What would change if the heap allocation list is too massive to fit into RAM, but the stack root set fits comfortably?
  • How would you ensure thread-safety if stack roots or heap allocations can be added concurrently while this function runs?