Subsequence

Unit 2 Session A

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Will either list ever be empty?
  • Potentially, yes. Your code should allow for this.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Take turns looking for each element of the smaller list, in order, until we either find all elements or run out of room to search.

1) First, make a variable to keep track of our current sequence entry
2) Initialize the sequence_index variable to 0
3) Loop through the number array, and each time:
  a) Check if sequence_index is a valid index for sequence
  b) If the index is invalid, we've reached the end of the
     sequence and can return True
  c) If the index is still valid, compare the value at that
     index to the current array value
       i) If it matches, we found the element, and can
          increment sequence by 1
4) If the loop finishes without returning True, we ran out of numbers
   to search, so return False

I-mplement

def is_subsequence(array, sequence):
    seq_idx = 0
    for num in array:
        if seq_idx == len(sequence):
            return True
        if sequence[seq_idx] == num:
            seq_idx += 1
    return False