2019-08-02

Ruby Data Structures Challenge #2 - For Beginners

Now you have an idea about solving coding challenges (or at least) structure, read, and crack. Probably you noticed that it is easy to follow through the steps if you stick to the framework to solve coding challenges. So let's see the second challenge.

Note: remember that you should know about the basis of Ruby and Data Structures at this point.

Challenge #2

Given two non-empty arrays of integers, write a function that determines whether the second array is a subsequence of the first one.

A subsequence of an array is a set of numbers that aren't necessarily adjacent in the array but in the same order as they appear in the array. For instance, the numbers [1, 2, 3] for a sequence of the array [1, 2, 3, 4], and so do the numbers [2, 4]. Note that a single number in an array itself is a valid array sequence.

Expected Results

As you will see, the expected results talk by themselves and explain your algorithm's desired behavior. When we see different inputs, we have to return the output accordingly.

Sample Input
Array = [5, 1, 22, 25, 6, -1, 8, 10]
Sequence = [1, 6, -1, 10]

Sample Output
true

----------------------------------

Sample Input
Array = [5, 1, 22, 25, 6, -1, 8, 10]
Sequence = [5, 1, 22, 25, 6, -1, 8, 10]

Sample Output
true

----------------------------------

Sample Input
Array = [5, 1, 22, 25, 6, -1, 8, 10]
Sequence = [22, 25, 6]

Sample Output
true

----------------------------------

Sample Input
Array = [1, 1, 1, 1, 1],
Sequence = [1, 1, 1]

Sample Output
true

----------------------------------

Sample Input
Array = [5, 1, 22, 25, 6, -1, 8, 10],
Sequence = [1, 6, -1, -1]

Sample Output
false

----------------------------------

Sample Input
Array = [5, 1, 22, 25, 6, -1, 8, 10],
Sequence = [1, 6, -1, 5]

Sample Output
false

As you can see, we have more examples to test in this challenge. Some of them should return true, while others should return false. Again, it depends on the sequence.

Following the Framework to Solve Coding Challenges

In one of our last blog posts, we talñked about the framework to solve coding challenges, so now is the time to put that into practice. Remember the steps

1. Use an online stopwatch
2. Read the problem carefully
3. Never try to see the result until you try it yourself.
4. What's the expected output from the challenge?
5. Did I solve a similar problem before? How?
6. Start your own documentation or cheatsheet
7. Solve the problem first on paper or a whiteboard
8. Start using the Ruby Interactive Console (IRB) or the text editor
9. Solve it first via "brute force."
10. Review the time & space complexity

Please take your time to do it by yourself now...

--------------------------------------------------------------------------------------------------------------------------------------------

Our solution

Remember that there are always different ways to solve the same problem. So you probably solved it with a different approach, and that's ok. Actually, what matters is: "you solve it." Now let's check this solution

def is_valid_sequence(array, sequence)
  sequence_arr = []
  original_sequence_length = sequence.length

  # O(n*m) Time | O(n*m) Space
  sequence.each do |i|
    array.each do |x|
      if x == i
        sequence_arr << true

        next_position_array = array.index(x) + 1
        next_position_sequence = sequence.index(i) + 1

        p array = array[next_position_array..-1]
        p sequence = sequence[next_position_sequence..-1]
        # break
      end
    end
  end

  return sequence_arr.length == original_sequence_length ? true : false
end

p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [1, 6, -1, 10])
# p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [5, 1, 22, 25, 6, -1, 8, 10])
# p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [5, 1, 22, 6, -1, 8, 10])
# p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [22, 25, 6])
# p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [1, 6, 10])
# p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [5, 1, 22, 10])
# p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [5, -1, 8, 10])
# p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [25])
# p is_valid_sequence([1, 1, 1, 1, 1], [1, 1, 1])
# p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [5, 1, 22, 25, 6, -1, 8, 10, 12])
# p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [4, 5, 1, 22, 25, 6, -1, 8, 10])
# p is_valid_sequence([5, 1, 22, 25, 6, -1, 8, 10], [5, 1, 22, 23, 6, -1, 8, 10])

Take time while you try to figure out what's happening here. You should know what we're doing here.

The next step should be to refactor or rethink the solution to have better code. After that, you can start figuring out other kinds of solutions, and that's ok. However, for now, it is enough to continue.

I hope you learned a lot with this exercise, and let's keep our progress.

Thanks for reading

Daniel Morales