Ruby FizzBuzz & Fibonacci

Ninth article in the Prepare for a Ruby job interview series. In this one, we'll study two algorithms that are asked quite often in interviews : FizzBuzz and Fibonacci!

FizzBuzz

FizzBuzz is very often asked in an interview and apparently a lot of people cannot do it. The idea behind FizzBuzz is :

> "Write a program that prints the numbers from 1 to 100\. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz".

You should try it by yourself before checking the result. It really shouldn't be hard. Here's my solution :

1.upto(100) do |i|
  if i % 15 == 0
    p 'FizzBuzz'
  elsif i % 5 == 0
    p 'Buzz'
  elsif i % 3 == 0
    p 'Fizz'
  else
    p i
  end
end

An alternative :

def fizzbuzz?(number)
  return 'Fizzbuzz' if number % 15 == 0
  return 'Buzz' if number % 5 == 0
  return 'Fizz' if number % 3 == 0
  number
end

(1..100).each { |i| p fizzbuzz?(i) }

One with a switch :

def fizzbuzz?(number)
  case
  when number % 15 == 0 then 'Fizzbuzz'
  when number % 5 == 0 then 'Buzz'
  when number % 3 == 0 then 'Fizz'
  else number
  end
end

(1..100).each { |i| p fizzbuzz?(i) }

You can easily return an array instead of printing :

def fizzbuzz?(number)
  return 'Fizzbuzz' if number % 15 == 0
  return 'Buzz' if number % 5 == 0
  return 'Fizz' if number % 3 == 0
  number
end

p (1..100).map { |i| fizzbuzz?(i) }

You can also do it in one line... but don't :P

Fibonacci

Fibonacci is also a recurring question during interviews. Pun Intended. :D

Implement a function which returns the nth number in Fibonacci sequences with an input n.

Here's a basic solution :

def fib(n)
  n <= 2 ? 1 : fib(n - 1) + fib(n - 2)
end

p (1..100).map {|i| fib(i)}

The problem is that the performances are awful. We'll talk later about complexity and see how bad this algorithm is.

Here's a faster solution :

 def fib(n)
  return 1 if n <= 2

  fib_index = 3
  a, b = 1, 1

  while fib_index <= n
    c = a + b
    a = b
    b = c
    fib_index += 1
  end

  c
end

p (1..100).map {|i| fib(i)}

You can also use the first solution, if you add cache.

def fib(n, cache)
  return 1 if n <= 2
  return cache[n] if cache[n]
  cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
end

cache = {}
p (1..100).map {|i| fib(i, cache)}

Checkout the next article about Algorithm Complexity.