Transform array to adjacency list

Question

Convert the given array to tree structure following the specified rules.

Codemia · Accepted Answer

To transform the given array into a tree structure, we need to understand the relationships defined by the values in the array. Each element can represent a node, and its index can represent its parent-child relationships based on specified rules. This problem can be effectively approached using a tree data structure, specifically focusing on creating an adjacency list where each index in the array corresponds to a node, and the values at those indices define the children of that node. The adjacency list is a suitable representation because it allows efficient traversal and storage of the tree structure, which is essential for building the tree from the flat array representation.

1. Create a dictionary to serve as the adjacency list, where each key is an index and each value is a list of its children indices.  
2. Iterate through the array. For each element at index `i`, check its value `val`. If `val` is not -1, it indicates a parent-child relationship where `val` is the parent index.  
3. Append `i` to the list of children for the parent index `val` in the adjacency list.  
4. Continue this process until all elements are processed. For example, for the input `[1, 2, -1, 0, 0]`:  
   - At index 0, value is 1, so add index 0 to the children of index 1.  
   - At index 1, value is 2, so add index 1 to the children of index 2.  
   - At index 2, value is -1, no action needed.  
   - At index 3, value is 0, add index 3 to the children of index 0.  
   - At index 4, value is 0, add index 4 to the children of index 0.  
5. The final adjacency list will indicate the tree structure derived from the array.

Here is the Python code that implements the above approach:

```python
from collections import defaultdict

def transform_to_adjacency_list(arr):
    adjacency_list = defaultdict(list)
    for i, val in enumerate(arr):
        if val != -1:
            adjacency_list[val].append(i)
    return dict(adjacency_list)

# Example usage:
input_array = [1, 2, -1, 0, 0]
output = transform_to_adjacency_list(input_array)
print(output)  # Output: {1: [0], 2: [1], 0: [3, 4]}
```

The time complexity of this solution is O(n), where n is the number of elements in the input array. This is because we perform a single pass through the array to build the adjacency list. The space complexity is also O(n) due to the storage of the adjacency list, which could potentially hold n children if each node had one child. Given the constraints of the problem, this complexity is optimal.

1. **Empty Array**: If the input array is empty `[]`, the output should also be an empty adjacency list `{}`.  
2. **All -1 Values**: An array like `[-1, -1, -1]` should return an empty adjacency list, indicating there are no parent-child relationships.  
3. **Single Node**: An array with one element `[0]` should return `{0: []}` as it has no children.  
4. **Cyclic References**: If the array contains a cycle, like `[1, 2, 0]`, the function should still construct the adjacency list correctly. However, cycles generally need to be checked separately if they impact the intended tree structure.  
5. **Large Input**: Consider handling performance with very large arrays, ensuring that the implementation remains efficient.

Transform array to adjacency list

Waymo

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Waymo 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