Back-end Engineering Articles

I write and talk about backend stuff like Ruby, Ruby On Rails, Databases, Testing, Architecture / Infrastructure / System Design, Cloud, DevOps, Backgroud Jobs, and more...

Twitter:
@daniel_moralesp

2019-07-26

Ruby Data Structures Challenge #1 - For Beginners

Now we have much knowledge to put into practice. Even in the last blog post, we talked about solving coding challenges. With that post and the previous ones, you have the basics to solve current and following coding challenges. If you don't know our latest blog post, here, you can see a list in order of each one of them.

Articles about Ruby
 
* What's Ruby (Programming Language)?
* Ruby Data Types: Strings, Numbers, and Booleans
* Variables and User Input in Ruby
* Control Flow and Conditionals in Ruby
* Ruby Times Loop and While Loop
* Ruby Each Loop
* Ruby Arrays
* Ruby Strings
* Ruby Hashes
* Ruby Functions
 
Articles about Data Structures
 
* Introduction to Ruby Data Structures and Complexity Analysis
* Relationship Between Memory and Data Structures
* Introduction to Big O Notation
* Introduction to Logarithms in Data Structures
* Framework to Solve Coding Challenges with Ruby


It's essential to have the basics of Ruby and Data Structures before doing coding challenges because it can be tricky if you don't do that. All the articles listed are in order, which is crucial if you don't know where to start or what's steps to follow to have all of these concepts.


Challenge

Write a function that takes in a non-empty array of integers sorted in ascending order and returns a new array of the same length with the squares of the original integers also sorted in ascending order. 

Pay attention to this problem because it might seem very simple. However, you have to consider that while integers in the input array are sorted in ascending order, their squares won't necessarily be as well because of the possible presence of negative numbers. 

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, we have to return the output accordingly. 

Sample Input
Array = [1, 2, 3, 5, 6, 8, 9]

Sample Output
[1, 4, 9, 25, 36, 64, 81]

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

Sample Input
Array = [1]

Sample Output
[1]

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

Sample Input
Array = [-2, -1]

Sample Output
[4, 1] ⇒ Initial result, you have to sort it
[1, 4]

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

Sample Input
Array = [-50, -13, -2, -1, 0, 0, 1, 1, 2, 3, 19, 20]

Sample Output
[2500, 169, 4, 1, 0, 0, 1, 1, 4, 3, 361, 400] ⇒ Initial result, you have to sort it
[0, 0, 1, 1, 1, 3, 4, 4, 169, 361, 400, 2500]

Following the Framework to Solve Coding Challenges

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

  1. 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...
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------

It is a perfect moment to congratulate yourself; you've solved your first coding challenge! 

You can start figuring out other kinds of solutions, and that's ok. 

Our solution

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

def sorted_squared_array(array)
  ## O(n) time | O(n) space
  length = array.length - 1
  current_position = 0
  new_arr = []

  if array.length == 1
    p new_arr << array[current_position] ** 2
  else
    (1..length).each do |i|
      if array[current_position] <= array[i]
        p new_arr << array[current_position] ** 2
        current_position += 1
        if length == current_position
          p new_arr << array[current_position] ** 2
        end
      else
        return false
      end
    end
  end

  return new_arr.sort
end

p sorted_squared_array([1, 2, 3, 5, 6, 8, 9])
# p sorted_squared_array([1])
# p sorted_squared_array([1, 2])
# p sorted_squared_array([1, 2, 3, 4, 5])
# p sorted_squared_array([-2, -1])
# p sorted_squared_array([-5, -4, -3, -2, -1])
# p sorted_squared_array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
# p sorted_squared_array([-1, -1, 2, 3, 3, 3, 4])

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

Thanks for reading
Daniel Morales