Transform string to adjacency list

Question

Given a string representation of a graph where each character represents a node and edges are defined by pairs of characters, transform this string into an adjacency list. The output should be a dictionary where each key is a node and its value is a list of adjacent nodes. For example, the input "ABAC" should produce an adjacency list that reflects the connections between the nodes.

Codemia · Accepted Answer

The problem requires us to transform a string representation of a graph into an adjacency list. Each character in the string represents a node, and edges are defined by pairs of adjacent characters. The adjacency list will be a dictionary where each key is a node and its value is a list of adjacent nodes. This problem aligns with graph representation techniques, specifically focusing on how to build the graph structure from a linear string input. The underlying pattern here is that we need to efficiently traverse the string and build connections based on immediate neighbors, which fits well into a single-pass approach using a dictionary.

1. Initialize an empty dictionary to hold the adjacency list.  
2. Loop through the string from the first character to the second-to-last character. For each character:  
   - If the character is not already in the dictionary, add it with an empty list.  
   - Check the next character (the adjacent one). If it's different, add it to the current character's adjacency list.  
3. After the loop, we should have built the adjacency list.  
For example, for the input 'ABAC':  
- Start with an empty dictionary: {}.  
- At index 0 ('A'), add 'B' to 'A's list: {'A': ['B']}.  
- At index 1 ('B'), add 'A' to 'B's list: {'A': ['B'], 'B': ['A']}.  
- At index 2 ('A'), add 'C' to 'A's list: {'A': ['B', 'C'], 'B': ['A']}.  
- At index 3 ('C'), add 'A' to 'C's list: {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}.  
Thus, the final adjacency list is: {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}.

```python
from collections import defaultdict

def string_to_adjacency_list(graph_string):  
    adjacency_list = defaultdict(list)  
    n = len(graph_string)  
    
    for i in range(n - 1):  
        current_node = graph_string[i]  
        next_node = graph_string[i + 1]  
        if current_node != next_node:  
            adjacency_list[current_node].append(next_node)  
            adjacency_list[next_node].append(current_node)  
    
    return dict(adjacency_list)

# Example usage:
print(string_to_adjacency_list('ABAC'))  # Output: {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
```

The time complexity of this algorithm is O(n), where n is the length of the input string. This is because we are making a single pass through the string to build the adjacency list. The space complexity is also O(n) in the worst case, as we may end up storing each node and its connections in the adjacency list. Given the constraints of the problem, this approach is efficient and appropriate.

1. **Empty String**: If the input string is empty, the output should also be an empty dictionary: `string_to_adjacency_list('')` returns `{}`.  
2. **Single Character**: If the string consists of a single character (e.g., 'A'), the output should be `{'A': []}` since there are no edges.  
3. **Repeated Characters**: For a string like 'AAAA', the output should be `{'A': []}` as there are no adjacent differing characters.  
4. **All Unique Characters**: For an input like 'ABCD', the adjacency list should reflect direct connections between each letter: `{'A': ['B'], 'B': ['A', 'C'], 'C': ['B', 'D'], 'D': ['C']}`.

Transform string to adjacency list

xAI

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

xAI Machine Learning 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