Hacker News Reader

Comment by dxbydt | Hacker News Reader

Got a dozen solutions to inverse fizzbuzz so far, atleast two of which are O(n). Got some disturbing emails - a recruiter plans to use inverse fizzbuzz at his next interview! Dear God what monster have I unleashed...programmer community, pls forgive me. And a CS prof is going to assign inverse fizzbuzz to his cs 101 students as extra-credit.

View on HN

I believe a constant solution exists, because Fizzbuzz repeats after 8 items. Still working on it...

<EDIT>

Yes, here's a constant solution: http://codepad.org/Id9eu0Ax

It's pretty simple actually (spoiler):

For any sequence containing fizzbuzz, match up the fizzbuzz with 15 and you're done. Any sequence of length >=7, fizzbuzz will be present. Thus, we only need to think about sequences length <7 that don't contain fizzbuzz. Solving this by brute force is constant time, since you only have finite possible inputs.

Yup. I updated my comment with working code. Just figure out the small case, and extrapolate once you find a match.

Nice approach!

It's O(1) to find a candidate solution, but of course it will still be O(N) to verify that the solution really works.

"Any sequence of length >=7, fizzbuzz will be present."

Are you sure? I don't think the challenge said the sequence could not be gappy.

This is resolved in one of the examples given in the introduction where the interviewer agrees that "buzz buzz" is an invalid sequence.

If sequences could be gappy, wouldn't the solution be just mapping fizz to 3, buzz to 5 and fizbuzz to 15? ( or multiples of those numbers, if duplicates aren't allowed )

But in no case would that be the shortest sequence.

For your example a shorter one would be 9,10,15.

If you can assume that you are given a valid fizzbuzz sequence then your solution works. However, look at what it outputs for:

raw_input = ["Fizz","Buzz","Fizz","Fizz","Buzz","Fizz","FizzBuzz","Buzz","Buzz"]

Reply on news.ycombinator.com