PracHub
QuestionsLearningGuidesInterview Prep

Quick Overview

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.

  • medium
  • Anduril
  • Coding & Algorithms
  • Software Engineer

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

  1. Build an address-to-reference adjacency map.
  2. Mark from every valid stack root while processing each live object once.
Last updated: Jul 15, 2026

Related Coding Questions

  • Find Heap Objects Not Referenced by the Stack - Anduril (medium)
  • Maximize Profit From Cutting Rods - Anduril (medium)

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.