?

Log in

No account? Create an account
   Journal    Friends    Archive    Profile    Memories
 

Oh, Go Ahead. Overthink FizzBuzz. - Chalain

Feb. 25th, 2008 06:24 pm Oh, Go Ahead. Overthink FizzBuzz.

I gave the best programming interview answer I may have ever given last Friday.

The interviewer hauled out FizzBuzz and asked me to solve it. It took me a minute to stop laughing.

FizzBuzz is a brain-dead simple programming problem, used pretty much to tell if a developer has a pulse at all. It is simply this: print the numbers from 1 to 100, but print "Fizz" instead of the number if it is divisible by 3, "Buzz" if it is divisible by 5, and "FizzBuzz" if it is divisible by both. It can be a good question to spend 5-10 minutes on at the start of a technical interview, because apparently a large number of interview candidates who claim to be expert programmers turn out to be unable to solve even this simple problem. For the rest of us, Reg Braithewaite reminds you that it is an interview question, and has some good advice for you: Don't Overthink FizzBuzz.

In my case however... I thought about it for a moment, then decided to break this rule.

See, I wasn't given this problem at the beginning of an interview. I was given this question at the end of two days of interviewing. My interviewer, the CTO, had already satisfied himself that I was capable of doing the job. Now he was just interested in the experience of exploring a solution with me.

I started by trying to write a single expression to transform the output as a function of the number, got tangled up in my logic, said "Okay, I'm trying to be too clever. Let me do this the stupid way first." And I wrote a stupid solution. (if (i%3).zero? puts "Fizz" etc.) Elapsed time? Maybe 90 seconds.

I started talking about ways to clean it up and optimize the code, but then I stopped: "You know, the code I wrote is kind of ugly but it is immediately apparent to the reader what I am trying to do. Anybody could read this and debug it. Unless there's a reason to keep going, such as a known performance bottleneck, I say we're done."

The CTO nodded and then confided in me: He had been talking about FizzBuzz with a friend of his, and they had been exchanging solutions. He had come up with four distinct solutions to the problem. I put on my best interviewer face and said, "Show me." And we spent another 20 minutes exploring his solutions, and discussing their merits.

That's when the light went on. FizzBuzz is a well-studied problem, right?

"Hang on a minute, let me drive for a second." I grabbed the keyboard and created a new file, and then wrote:

require 'fizzbuzz'
puts fizzbuzz
The CTO chuckled. "That would only work if you already had--"

But I was already typing again:
# if this require fails, you need to gem install fizzbuzz
require 'fizzbuzz'
puts fizzbuzz
THIS caused the CTO to laugh out loud.

I got the job. I start tomorrow with a great team doing mostly Ruby and a bit of Rails!

But it doesn't end there. I am, if anything, unable to tell when to stop telling a joke. I registered the fizzbuzz project with RubyForge. You can indeed now install the fizzbuzz gem and run it. You're welcome. Contributions are invited.

Homepage: http://fizzbuzz.rubyforge.org
Project: http://rubyforge.org/projects/fizzbuzz/

And, of course, you can install the gem directly. :-)

Oh, and in it I included my own solution to FizzBuzz, one that I think is geniunely original. It took me 2 hours to come up with this idea¹:
(1..100).map {|i| srand(1781773465) if (i%15)==1; [i, "Fizz", "Buzz", "FizzBuzz"][rand(4)]}
For the non-programmers, that makes a list of the four things you could display for each number, then picks one of them at random. If you seed the random number generator appropriately, it will make the correct choice 15 times in a row, which is when the cycle of FizzBuzz repeats itself.

¹ and about 12 hours of processor time to find the magic number 1781773465² ³.

² if you're willing to reorder the array as ["FizzBuzz", "Buzz", i, "Fizz"], you can seed the RNG with 46308667. I find this fascinating because 15 digits of fizzbuzz requires 30 bits of information, but 46308667 only requires 26 bits of storage. It's actually using rand's vast store of deterministic sequences to hide information.

³ this works with Ruby 1.8's RNG. I have tested this on Mac and Linux, but not on Win32 Ruby. YMMV.
Tags:

Current Mood: geekygeeky
Current Music: If Then ... - Candice Pacheco

48 comments - Leave a commentPrevious Entry Share Next Entry

Comments:

From:hitchhiker
Date:February 26th, 2008 03:35 am (UTC)
(Link)
whoa - i love the random number solution. well done!
From:samwibatt
Date:February 26th, 2008 03:48 am (UTC)
(Link)
I got the job. I start tomorrow with a great team doing mostly Ruby and a bit of Rails!

w000000000000000000000t!
From:singingnettle
Date:February 26th, 2008 05:25 am (UTC)
(Link)
Hah!

Congratulations.
From:unspeakablevorn
Date:February 26th, 2008 07:34 am (UTC)
(Link)
"I started by trying to write a single expression to transform the output as a function of the number"

['fizzbuzz', nil, nil, 'fizz', nil, 'buzz', 'fizz', nil, nil, 'fizz', 'buzz', nil, 'fizz', nil, nil][i % 15] || str(i)

Vorn
From:ext_87087
Date:February 26th, 2008 12:58 pm (UTC)
(Link)
['fizzbuzz', 'fizz', 'buzz', i][[i%15,i%3,i%5,0].index(0)]

Arnar
From:voxwoman
Date:February 26th, 2008 11:24 am (UTC)
(Link)
I assume you know the early childhood anectdotes regarding Carl Frederich Gauss? (mostly the one where he was in grade school and the teacher, wanting a few minutes break, assigned the class to write out a sequence of numbers - I think all integers 1 to 100, and Gauss came up with a formula to do that in about 5 minutes. Or something.I'd have to look it up, and there's no time now)
From:(Anonymous)
Date:February 26th, 2008 12:40 pm (UTC)

what he did was:

(Link)
he said "well...
100 + 1 == 101
99 + 2 == 101
...
(100-n) * (1+n) == 101
so the sum of all numbers from 1 to 100 == 50 * 101 == 5050
but i don't know what it has to do with fizzbuzz...
From:(Anonymous)
Date:February 26th, 2008 03:29 pm (UTC)

25 bit of fizzbuzz

(Link)
You can use just 25 bits if you make sure the top 5 are zeros:

def fizzbuzz(a)
  [a, "Fizz", "Buzz", "FizzBuzz"][(0x1241843 >> ((a % 15) * 2)) & 3]
end

From:chalain
Date:February 26th, 2008 03:54 pm (UTC)

Re: 25 bit of fizzbuzz

(Link)
Nice! I realized after I wrote it that there is almost certainly less than 30 bits of information. Not sure what the actual information density is, but I wouldn't be surprised if you could get it down to 20 or even 10 bits. (Assuming the only information we're concerned about here is which index to display.)
From:shatterstripes
Date:February 26th, 2008 03:51 pm (UTC)
(Link)
# if this require fails, you need to gem install fizzbuzz

Brilliant!
From:giles_bowkett
Date:February 26th, 2008 10:34 pm (UTC)
(Link)
FizzBuzz is silly, but you might as well use open classes.


From:unspeakablevorn
Date:February 26th, 2008 11:17 pm (UTC)
(Link)
;_;
From:(Anonymous)
Date:February 29th, 2008 11:46 am (UTC)

Room for a boring solution?

(Link)

class FizzBuzzer
  def initialize(range = 1..100)
    @range = range
  end
  
  def to_s
    result.join("\n")
  end
  
  def result
    @range.map do |num|
      if fizzbuzz?(num)
        "FizzBuzz" 
      elsif buzz?(num)
        "Buzz"
      elsif fizz?(num)
        "Fizz"
      else
        num
      end
    end
  end
    
  private
    def fizz?(num)
      num % 3 == 0
    end
    
    def buzz?(num)
      num % 5 == 0
    end
    
    def fizzbuzz?(num)
      fizz?(num) && buzz?(num)
    end
end

if __FILE__ == $0
  puts FizzBuzzer.new
end
From:chalain
Date:February 29th, 2008 04:57 pm (UTC)

Re: Room for a boring solution?

(Link)
You bet! E-mail me your name and I'll add it to the credits. (My e-mail is discoverable at http://rubyforge.org/projects/fizzbuzz/ -- click on "David Brady" to see my profile.)
From:(Anonymous)
Date:November 19th, 2015 06:51 pm (UTC)

A little smaller

(Link)
(1..100).map{|x| (['Fizz'][x%3]||'') + (['Buzz'][x%5]||') || x }
From:chalain
Date:November 19th, 2015 11:37 pm (UTC)

Re: A little smaller

(Link)
I like the abuse of array bounds, but there's a dilemma in the code: The empty string is considered a "truthy" value, so the || x will never be reached, and the output doesn't quite look like what we need.

You COULD reach the x if the earlier phrases omitted the ||'' portions, but you've no doubt already discovered that the "Buzz" case will blow up because you can't add nil + String.

This is very close to the clever way I first tried to solve it during the interview. It just seems neat and clean to pick up a 'Fizz' if (x%3).zero? and then pick up a 'Buzz' if (x%5).zero?, and then pick up x if neither string picked up.

I couldn't work it out back then, but now that I'm reviewing it years later, I can see a way to monkeypatch NilClass to make this approach work... heh.

Thanks!
From:(Anonymous)
Date:November 19th, 2015 07:10 pm (UTC)

another solution using bitwise operations

(Link)
https://gist.github.com/giuseppeg/5939177
From:(Anonymous)
Date:November 19th, 2015 07:13 pm (UTC)

another clever solution using bitwise operations

(Link)
A girl on irc once asked if there is a way to solve FizzBuzz with just one comparison.
Yours is indeed one and it is pretty clever :) Here is another one https://gist.github.com/giuseppeg/5939177
From:(Anonymous)
Date:November 19th, 2015 07:14 pm (UTC)
(Link)
A girl on irc once asked if there is a way to solve FizzBuzz with just one comparison.
Yours is indeed one and it is pretty clever :) Here is another one https://gist.github.com/giuseppeg/5939177
From:(Anonymous)
Date:November 19th, 2015 09:51 pm (UTC)

Elixirgolf.com FizzBuzz

(Link)
Great article thanks. I recently launched the elixirgolf.com web site and there were some really interesting FizzBuzz solutions. Mine used Fermat's little theorem

http://elixirgolf.com/articles/elixir-fizzbuzz-golf/