Coding Interview Prep: The Validate Subsequence problem.

Another day, Another problem.

Continuing with my series on the coding interview problems. I will be going over the “Validate Subsequence problem”. So what is the problem you might ask? Here it is

“Create a function that, given two non-empty arrays of integers, determines if the second array forms a subsequence within the first one. A subsequence is defined as a set of numbers that, while not necessarily adjacent in the array, maintain the same order as their appearance in the array. For example, [1, 3, 4] is a subsequence of [1, 2, 3, 4], as is [2, 4]. It’s important to note that a single number in the array and the array itself are considered valid subsequences of the array.”

And to test your code, I would like to give you guys a few test cases

{
  "array": [5, 1, 22, 25, 6, -1, 8, 10],
  "sequence": [5, 1, 22, 25, 6, -1, 8, 10],
  "is_valid": true
}

{
  "array": [5, 1, 22, 25, 6, -1, 8, 10],
  "sequence": [5, 1, 22, 6, -1, 8, 10],
  "is_valid": true
}

{
  "array": [5, 1, 22, 25, 6, -1, 8, 10],
  "sequence": [22, 25, 6],
  "is_valid": true
}

{
  "array": [5, 1, 22, 25, 6, -1, 8, 10],
  "sequence": [5, 1, 25, 22, 6, -1, 8, 10],
  "is_valid": false
}

So in short, if the sequence is a “valid subsequence” of the array, return true else return false.

The way to approach I approached this problem was by first looping over the sequence array and then internally looping over the mian array.