Find Heap Objects Not Referenced by the Stack

Question

The candidate is asked to write a function that identifies heap objects that are not referenced by the stack, effectively determining memory leaks in a given context.

Codemia · Accepted Answer

To identify heap objects not referenced by the stack, we can use a graph traversal approach. The stack can be viewed as a set of roots, and we will traverse from these roots to mark all reachable objects in the heap. Any object that remains unmarked after this traversal is unreferenced.

1. Create a set to keep track of all reachable objects.
2. Use a depth-first search (DFS) starting from each root object in the stack.
3. For each object visited, add it to the set of reachable objects.
4. After the traversal, iterate through the heap objects and check which ones are not in the reachable set.

The time complexity of this algorithm is O(n + m), where n is the number of heap objects and m is the number of references from the stack. The space complexity is O(n) due to the storage of reachable objects.

Here is a simple implementation in Python:
```python
class HeapObject:
    def __init__(self, id):
        self.id = id
        self.references = []

def find_unreferenced_objects(stack_roots, heap_objects):
    reachable = set()

def dfs(obj):
        if obj in reachable:
            return
        reachable.add(obj)
        for ref in obj.references:
            dfs(ref)

for root in stack_roots:
        dfs(root)

unreferenced = [obj for obj in heap_objects if obj not in reachable]
    return unreferenced
```
This code defines a simple `HeapObject` class and a function to find unreferenced objects.

Interviewers will look for clarity in the explanation of the approach, the correctness of the algorithm, and the efficiency of the implementation. They also assess the candidate's ability to discuss trade-offs and potential improvements to the solution.

Find Heap Objects Not Referenced by the Stack

Anduril

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Anduril Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string