Detect subsequence in linked list

Question

Given a linked list and a sequence of integers, determine if the sequence is a subsequence of the linked list. The function should return true if the subsequence exists and false otherwise. The linked list is defined by its nodes, and the sequence is provided as an array of integers.

Codemia · Accepted Answer

To determine if a sequence of integers is a subsequence of a linked list, we can employ the two-pointer technique. This technique is particularly effective here because we can traverse both the linked list and the array of integers simultaneously. The linked list can be traversed using a pointer that iterates through each node, while a second pointer can track the current position in the array of integers. This approach is efficient as it allows us to check the subsequence condition in a single pass through the linked list.

1. Initialize two pointers: one for the linked list (`curr_node`) and another for the array (`seq_index`).  
2. Traverse the linked list using the `curr_node`. For each node, check if the node's value matches the current value in the sequence at `seq_index`.  
3. If they match, increment `seq_index` to check the next value in the sequence.  
4. If `seq_index` reaches the length of the sequence, it indicates that all elements have been found in order, so return `True`.  
5. If the linked list ends and `seq_index` has not reached the end of the sequence, return `False`.  
**Example:** For a linked list (1 -> 2 -> 3 -> 4 -> 5) and a sequence [2, 4], the traversal would proceed as follows:  
- `curr_node` points to 1 (no match)  
- `curr_node` points to 2 (match, increment `seq_index`)  
- `curr_node` points to 3 (no match)  
- `curr_node` points to 4 (match, increment `seq_index`)  
- `curr_node` points to 5 (no match)  
- End of list reached, `seq_index` equals the length of sequence, return `True`.

```python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def is_subsequence(head: ListNode, sequence: list) -> bool:
    curr_node = head
    seq_index = 0
    seq_length = len(sequence)

while curr_node and seq_index < seq_length:
        if curr_node.value == sequence[seq_index]:
            seq_index += 1
        curr_node = curr_node.next

return seq_index == seq_length
```

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. This is because we traverse each node at most once. The space complexity is O(1) since we are using only a constant amount of extra space (the pointers and indices). This is efficient given that we do not need to store any additional data structures, making it suitable for large linked lists.

1. **Empty Linked List:** If the linked list is empty (head is None), the function should return `False` unless the sequence is also empty.  
2. **Empty Sequence:** If the sequence is empty, it should return `True` since an empty sequence is trivially a subsequence of any list.  
3. **Single Element Match:** If the linked list has one node and the sequence has one item that matches, it should return `True`. If it does not match, it should return `False`.  
4. **Sequence Longer than List:** If the sequence length is greater than the number of nodes in the linked list, it should return `False`.  
5. **All Elements Match:** If all elements in the sequence are present in the linked list but not in order, it should return `False`.

Detect subsequence in linked list

HRT

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

HRT 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