4 ms·
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.or
by harpastum 14y ago
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 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"]