So I was asked to create FizzBuzz at an interview... Easy enough but then they s

Question

So I was asked to create FizzBuzz at an interview... Easy enough but then they say what if there is a million data points. ie. divisible by 3 divisble by 5 divisble by 6 up until a billion. What is the best way to implement this. What data structure would you use?

I was lost any help? EDIT:

for(int i = 1; i <100; ++i){
    if((i%3) == 0)
        cout<<"fizz ";
    else if((i%5) ==0)
        cout<<buzz;
}
So if I was to add a billion I would want to have to write a billion if else or switches if the divisor goes up to a billion.

Explanation / Answer

Basically, you would change the FizzBuzz algorithm so that, instead of two hard-coded checks for divisibility, you check for divisibility against all elements of a collection of "tuples", containing the number to check against and the word or syllable that should be substituted.

My C++ is more than a little rusty, but in C# I would use the Dictionary collection, as it would allow me to enumerate the numbers to check against as the collection of Keys. This would be a basic C# implementation:

public void FizzBuzzOnSteroids(Dictionary<int, string> subs, int limit)
{
int i = 1;
while(i <= limit) //a better implementation would allow early cancellation, but meh
{
string res = String.Empty;
bool subbed = false;
foreach(var div in subs.Keys)
{
if(div > i) break; //useful for larger divisor sets

if(i % div == 0)
{
res += subs[div];
subbed = true;
}
}
if(!subbed) res = i.ToString();

Console.Write(res + ", ");
i++;
}
}

...

//Usage, playing a game of "FizzBuzzBat" up to a billion
FizzBuzzOnSteroids(new Dictionary<int,string>{{3, "Fizz"}, {5, "Buzz"}, {7, "Bat"}}, 1000000000);
Output:

1, 2, Fizz, 4, Buzz, Fizz, Bat, 8, Fizz, Buzz, 11, Fizz, 13, Bat, FizzBuzz, 16, 17, Fizz, 19, Buzz, ... 101, Fizz, 103, 104, FizzBuzzBat, 106, 107, Fizz, ...

This is pretty much the most efficient answer if it is given that the divisors will all be perfect primes, like 3, 5, and 7. If that's not a given in this problem, something like a Sieve of Erastothenes might perform better. You would create a memory structure representing an array of strings with an element for each number in the sequence (which must now be finite). Then, take each divisor in order and append the corresponding syllable to each string at an index corresponding to a multiple of that divisor (remember to subtract 1). Finally, output the contents of the array, using the index (+1) as the output for any element with an empty/null string.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.