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.

"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.

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.

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"]