Count Prefix-Matching Simple Paths in a Labeled Graph

Question

The question asks the candidate to find the number of simple paths in an undirected labeled graph that match each prefix of a given string.

Codemia · Accepted Answer

To solve the problem, we need to traverse the graph and count the number of simple paths that match each prefix of the given string. We can use Depth-First Search (DFS) to explore all possible paths starting from each node. For each path we explore, we will check if it matches the current prefix of the string.

1. Initialize a list to store the counts of matching paths for each prefix.
2. For each node in the graph, initiate a DFS traversal.
3. During the DFS, keep track of the current path and the index of the prefix being matched.
4. If the current node's character matches the prefix character, continue the DFS to its neighbors.
5. If the prefix is fully matched, increment the count for that prefix.
6. Backtrack to explore other paths.

The time complexity of this approach is O(N * M), where N is the number of nodes and M is the length of the string. This is because we may need to explore all nodes for each prefix. The space complexity is O(H), where H is the maximum depth of the recursion stack during the DFS.

```python
from collections import defaultdict

def count_prefix_paths(graph, string):
    def dfs(node, index):
        if index == len(string):
            return 1
        count = 0
        for neighbor in graph[node]:
            if graph[node][neighbor] == string[index]:
                count += dfs(neighbor, index + 1)
        return count

result = []
    for i in range(len(string)):
        count = 0
        for node in graph:
            if graph[node] == string[0]:
                count += dfs(node, 1)
        result.append(count)
    return result
```

Interviewers are looking for clarity in the candidate's thought process, the ability to break down the problem into manageable parts, and a solid understanding of graph algorithms. They want to see if the candidate can effectively communicate their approach and reasoning, as well as implement a working solution.

Count Prefix-Matching Simple Paths in a Labeled Graph

Google

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

Google 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