Daniel Morales - Software Engineer

2024-12-24

Ruby Data Structures Challenge #2 - For Beginners

Now you have an idea about how to solve the coding challenges (or at least) how they are structured, read and solved. 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 at this point you should know about the basis of Ruby and Data Structures.

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 that are 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 are both valid sequences of the array

Expected Results

As you will see the expected results talk by themselves and can explain the expected behavior of your algorithm. When we see different inputs you 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 a bit more examples to test in this challenge. Some of them should return true while others should return false. It depends on the sequence.

Following the Framework to Solve Coding Challenges

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

- Use an online stopwatch
- Read carefully the problem
- Never try to see the result until you try it by yourself.
- What's the expected output from the challenge?
- Did I solve a similar problem before? How?
- Start your own documentation or cheatsheet
- Solve problem first in a paper or a whiteboard
- Start using the Ruby Interactive Console (IRB) or the text editor
- Solve it first via "brute force"
- 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 it is probably that you solved it with a different approach and that's ok, even that what matters: “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

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 a time while you try to figure out what's happening here. You should know what we’re doing here

Next step should be to refactor a while or even rethink the solution to have better code. You can start figuring out other kinds of solutions and that’s ok. However for now is enough to continue

I hope you learned a lot with this excescrise and let’s keep our progress

Thanks for reading

DanielM