3 ms·
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 n
by dxbydt 14y ago
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.
- harpastum 14y agoI 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 http://codepad.org/Id9eu0Ax
- qiemem 14y agoIt'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.
- harpastum 14y agoYup. I updated my comment with working code. Just figure out the small case, and extrapolate once you find a match.
- igoros 14y agoNice 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.
- Danieru 14y ago"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.
- dastbe 14y agoThis is resolved in one of the examples given in the introduction where the interviewer agrees that "buzz buzz" is an invalid sequence.
- ThePawnBreak 14y agoIf 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 )
- Danieru 14y agoBut in no case would that be the shortest sequence. For your example a shorter one would be 9,10,15.
- dastbe 14y agoIf 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"]