Preparing for Technical Interviews in Ruby

As I draw nearer to graduating from my coding bootcamp, I find myself needing to pivot from developing personal projects to preparing for technical interviews. While I intend to continue working on side projects and learning new frameworks, for now it is important that I become comfortable with the technical interviewing process. From everything I have read, interviewing well is a skill that can be learned. I believe that anyone who takes the time to develop their interviewing skills has the potential to be a great engineer because the same skills which lead to interview success (practice, humility, and a willingness to learn) will prove beneficial within a professional setting.

Right now I am focusing on reviewing aspects of pure Ruby that I have not practiced since beginning to learn JavaScript, as well as familiarizing myself with some of the more common algorithms I suspect I may be asked about. One resource I have been using a lot lately is HackerRank. HackerRank is a website with a built-in coding environment that supports multiple languages. The site has an assortment of interesting problems, some of which may closely emulate interview questions. Some employers even ask potential recruits to perform coding challenges through HackerRank. Right now I am working through all of the Ruby problems on the site. In the following paragraph is a solution I wrote earlier today to a HackerRank problem which asked for a basic primality checker. A primality checker is a method that takes in a number, n, and returns true if n is prime or false if n is not. This is a common enough and simple enough problem that I didn’t think it would be unfair to write up a solution for it. First I wrote a solution that represents a “naive” or brute force approach. Then I wrote a solution that is a little bit more optimized. This procedure of finding a working solution and then improving upon it is something to practice for interviews.

Writing a method in Ruby to check whether or not a number is prime:

Remember, a number is prime if it is divisible only by one and itself.

Naively, we might decide that it is sensible to write a prime checker method that uses trial division, i.e. iterating through the range (2...n) to see if any of those numbers can divide cleanly into n. This is probably how you learned to check for whether or not a number was prime in grade school.

First approach:

def prime?(n)
if n <= 1
return false
else
if (2...n).any? { |i| n % i == 0}
return false
else
return true
end
end
end

This is a good first approach. It returns the correct answer, but it is not the fastest or cleanest method we could have used. A second approach can cut down on the number of potential factors we need to iterate through by half. This approach involves iterating through the range (2…Math.sqrt(n).floor). Why can we stop checking for factors at this point? Well, here is an example. Consider the following list of factors whose product equals 100:

1 x 100
2 x 50
4 x 25
5 x 20
10 x 10
20 x 5
25 x 4
50 x 2
100 x 1

As you can see, if you were to check for factors beyond the midpoint of the list (in this case 10 x 10), you would be checking factors you had already checked within the first half of the list. So we can stop checking for factors once we iterate up to Math.sqrt(100).floor. This is not a formal proof by any means, but if you are interested you could read more about this on Wikipedia. At any rate, this finding can be applied to our prime checker method in the following way:

Second approach:

def prime?(n)
if n <= 1
return false
else
if (2...Math.sqrt(n).floor).any? { |i| n % i == 0}
return false
else
return true
end
end
end

While this method requires fewer iterations than the first prime method we wrote, the worst case run-time complexity of the second method is proportional to O(sqrt(n)) rather than O(n). There are even faster primality checker algorithms like the AKS primality test, which you can learn more about here if you are interested.