Find Unreachable Objects in a Heap Graph

Question

The question asks the candidate to identify and find unreachable objects in a heap graph, which is a representation of memory allocation in a program.

Codemia · Accepted Answer

To find unreachable objects in a heap graph, I will use a graph traversal technique. The main idea is to traverse the graph starting from the root objects and mark all reachable nodes. After that, any node that remains unmarked is considered unreachable.

I will implement a Depth-First Search (DFS) algorithm to explore the graph. The steps are as follows:
1. Initialize a set to keep track of visited nodes.
2. Start the DFS from each root object, marking all reachable nodes.
3. After the traversal, iterate through all nodes in the heap and collect those that are not in the visited set.

Here is a Python implementation of the above approach:
```python
class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

def find_unreachable_objects(root_nodes):
    visited = set()

def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for child in node.children:
            dfs(child)

# Start DFS from each root node
    for root in root_nodes:
        dfs(root)

# Collect unreachable nodes
    all_nodes = get_all_nodes()  # Assume this function retrieves all nodes in the heap
    unreachable = [node for node in all_nodes if node not in visited]
    return unreachable
```

The time complexity of this algorithm is O(V + E), where V is the number of vertices (nodes) and E is the number of edges (connections) in the graph. The space complexity is O(V) due to the storage of visited nodes in the set.

It is important to handle edge cases such as an empty heap graph or a graph with no root objects. In such cases, the function should return an empty list as there are no unreachable objects.

Find Unreachable Objects in a Heap Graph

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