Count longest subsequence in graph

Question

Given a directed graph represented by an adjacency list, write a function to count the length of the longest subsequence of vertices that can be traversed in a path. The function should take the number of vertices and the adjacency list as input and return the length of the longest subsequence as output.

Codemia · Accepted Answer

In this problem, we are tasked with determining the length of the longest subsequence of vertices that can be traversed in a directed graph. The key observation here is that this problem can be approached using a **Depth-First Search (DFS)** algorithm combined with **Dynamic Programming**. The reason for using DFS is that we can explore all paths from any vertex, while dynamic programming helps us store the results of already computed paths to avoid redundant calculations. This is especially useful in a directed acyclic graph (DAG) where we can ensure that there are no cycles, allowing us to compute the longest path efficiently.

1. **Input Validation**: Check if the number of vertices is zero. If it is, return 0 immediately as there are no vertices to traverse.
2. **Initialize a DP Array**: Create an array `dp` of size `num_vertices`, initialized to 1, representing the longest path starting from each vertex.
3. **Depth-First Search**: Implement a recursive DFS function that:
   - Takes a vertex as input.
   - If the result for this vertex is already calculated (stored in `dp`), return it.
   - For each neighbor of the vertex, call the DFS function recursively and update the `dp` value for the current vertex based on the longest path found from its neighbors.
4. **Calculate the Longest Path**: For each vertex in the graph, call the DFS function and keep track of the maximum value found in `dp`.
5. **Return the Result**: The maximum value in the `dp` array will be the length of the longest subsequence of vertices that can be traversed in a path.

Here is the Python code implementing the above approach:

```python
def longest_subsequence(num_vertices, adjacency_list):
    if num_vertices == 0:
        return 0

dp = [1] * num_vertices
    visited = [False] * num_vertices

def dfs(vertex):
        if visited[vertex]:
            return dp[vertex]
        visited[vertex] = True
        max_length = 1
        for neighbor in adjacency_list[vertex]:
            max_length = max(max_length, 1 + dfs(neighbor))
        dp[vertex] = max_length
        return dp[vertex]

longest_path = 0
    for i in range(num_vertices):
        longest_path = max(longest_path, dfs(i))

return longest_path
```

This code first checks if there are vertices to process, initializes the dynamic programming array and a visited list, and then performs a DFS from each vertex, updating the longest path found.

The time complexity of this solution is **O(V + E)**, where `V` is the number of vertices and `E` is the number of edges. This is because each vertex and edge is processed once during the DFS. The space complexity is also **O(V)** due to the storage used for the `dp` and `visited` arrays. Given the constraints of the problem, this solution is efficient and should perform well within reasonable limits.

1. **Empty Graph**: If `num_vertices` is 0, the function should return 0. This is handled in the input validation step.
2. **Single Vertex Graph**: If there is only one vertex with no edges, the longest subsequence length should be 1, which is handled by initializing the `dp` array to 1.
3. **Disconnected Graph**: If the graph has multiple disconnected components, the solution will still correctly find the longest path in each component, returning the maximum.
4. **Cycle Detection**: Although the problem states it is a directed graph, if a cycle were present, the current implementation might lead to infinite recursion. We assume that the input graph will be a DAG as per standard graph problems unless stated otherwise.

Count longest subsequence in graph

Doordash

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

Doordash 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