Algorithms and how they used with Ruby

 

Importance of algorithms

An algorithm is a set of rules to follow in order to solve a problem.

We use algorithms to improve the performance of our program using the available resources and get the best combination of speed and use of memory.

They are important because programming languages rely on them and because if we find a problem that has already been solved by an algorithm, we can replicate its technique and when appropriate, use it.

We are going to talk about time, but despite speed is an important factor to consider when using algorithms we should still have our priorities as follows:

  • Make it work
  • Make it right
  • Make it fast.

Time

We can and should calculate the cost of our code. When we talk about cost in the context of algorithms , what we mean is time.

A shorthand to know how long a procedure takes is to ask how many lines of code are involved. But there are more factors to consider. If we want to calculate how long does it takes to find if a word contains a specific letter, well, the answer will depend on the size of the word. The cost of performing a function  varies with the size of the input, so we describe the cost in terms of the size of the input. We call this cost the time complexity of the function.

Time complexity

Time complexity of an algorithm signifies the total time required by the program to run until its completion and in the worst case scenario. It is defined as a function using Big O notation, an asymptotic notation.

n is the size of the input.

O is the worst case scenario.

* The worst case scenario is one where given an input of a certain size, our function takes as long as possible.

The O function is the growth rate in function of the input size n.

Great resources to learn about algorithms and data structures using Ruby:

 

 

Time complexity

  • You can get it counting the number of operations
  • Time complexity is defined as a function using Big O notation.
  • n is the size of the input.
  • O is the worst case scenario.
  • The O function is the growth rate in function of the input size n.

O(1) Constant : odd or even / look up table / check if item in array is null / print first element from a list / find on a map.

O(log n) Logarithmic: find in sorted array with binary search.

O(n) Linear: find max in unsorted array / duplicate elements in array with Hash map / find / print all values.

Algorithms running times:

Factorial complexity(no good),

exponential complexity(no good),

polinomial complexity (no good),

linearithmic complexity (middle point),

linear time complexity (good)(for loop in one level array, searching, printing) O(n),

logarithmic complexity (good) O(log n),

constant time complexity (best one)(swap variables). O(1)

Time Conversion

Problem from Hackerranck.

I am practising algorithms and tried this one today.

I first get the two first characters of the string ‘s’, the ones that represent the hour and change them to a number with parseInt and assign them to the variable hour.

If this variable hour is bigger than 12 I rest 12, if it is equals 12, hour would be the string ’00’ and for the rest of the cases I add 12.

Then I add hour to a substring of the argument without the two first characters and delete the two last characters too, the one that should be “AM” or “PM”.

My solution:

BirthdayCakeCandles

Problem from Hackerrank.

My solution:

 

Mini-Max Sum

Problem from Hackerrank.

My solution:

 

Staircase

Problem from Hackerrank.

My solution:

 

Plus Minus

Problem from Hackerrank.

I was making the mistake of checking if the index was bigger or smaller than zero, instead of checking the value of the integer in that index. I was comparing i instead ,arr[i].

My solution:

 

Diagonal Difference

Problem from Hackerrank.

 

Simply Array Sum

Problem from HackerRank.

Easy problem but I got confused with the index of the array and its value. I was adding i to my result variable and not ar[i].

 

Compare the Triplets

Problem from Hackerrank.

Got some issues figuring out why it didn’t work my function. Two mental notes:

I am still have some problems with indentation and that can cause to put my return value inside the for loop without noticing.

I keep writing the operator “+=” as “=+”. How annoying! I read a good article about it and I finally got it.

My solution: