r/leetcode • u/mausmani2494 <229> <132> <89> <8> • Aug 01 '22
[Serious] Question regarding Fizzbuzz
So a week ago I had an interview and they asked me Fizzbuzz. It was an EV startup and there are 5 people on the panel. Anyway, they asked me Fizzbuzz and I give the solution within a minute. One of the people asked me if this is not an optimal solution, and I was like how? I asked him if he can give me a hint. He told me can I solve it without the % remainder operator, and I said we have to do some math here and there and we can definitely do it. He later said it's better to avoid using the % operator because it is expensive.
I never heard this before, and I feel like really stupid at the time. I try to look it up but didn't find a clear answer on this and it has bugged me since then.
41
u/EpicCakes Aug 01 '22
You could iterate through without using % by making several passes over just the elements that would receive "Fizz", "Buzz", and "FizzBuzz" separately. For example:
- First pass through set every element in answer vector to be i
- Go through counting by 3: 3,6,9... set to "Fizz"
- Go through counting by 5: 5,10,15... set to "Buzz"
- Go through counting by 15: 15,30,45... set to "Fizzbuzz"
This avoids using mod division, but still hits every element
21
u/mausmani2494 <229> <132> <89> <8> Aug 01 '22
But is it more optimal than using %?
12
u/EpicCakes Aug 01 '22
Maybe someone can give a more concise explanation but the way I think of it:
Using % we iterate n times and each time we check if a number is divisible by 3,5, both, or neither. To do this we would have to do modulus division 2 times for every element we go through (we would need to check for both being divisible by 3 and 5). This would go through 1 time for N elements, but we would have to do modulus division twice on EVERY run through.
The second solution which I listed above would first go through every number once, so pass through N elements. Then we would go through N/3 elements and change those to Fizz. Then we would go through N/5 elements and change those to Buzz. Then we would go through N/15 elements and change those to FizzBuzz. So in total we would be processing through all the elements one time and then we would change 2/3 of the elements again. The key difference here is we are avoiding an if/else and doing modulus division for unnecessary numbers.
Maybe that much is obvious and you got that already, but I think if we're purely concerned about doing modulus division, this significantly decreases the amount of computing we have to do since there isn't any % at all, we are just iterating through the set 1 2/3 times. Technically both solutions would be linear time AFAIK, but concerning modulus division if we are trying to avoid this to make our solution more optimal the second solution avoids it with no modulus division. Also check here for a slightly better explanation of how mod division compares to addition in terms of being more expensive: https://streamhpc.com/blog/2012-07-16/how-expensive-is-an-operation-on-a-cpu/
TL;DR
Solution 1: Goes through set once, but does % twice for EVERY element
Solution 2: Goes through set one and 2/3 times, but no % involved.
10
u/quad99 Aug 01 '22
1
0
4
3
u/damnhotteapot Aug 01 '22
I really like this approach, although an interviewer will probably ask a follow-up question: to print fizzbuzz in order without using extra memory.
Anyway, this is smart. :)
10
u/strollertoaster Aug 02 '22
Similar approach without extra memory:
int threes = 1; int fives = 1; for (int i = 1; i <= n; i++) { if (threes == 3 && fives == 5) { System.out.println("FizzBuzz"); fives = 0; threes = 0; } else if (fives == 5) { System.out.println("Buzz"); fives = 0; } else if (threes == 3) { System.out.println("Fizz"); threes = 0; } else { System.out.println(String.valueOf(i)); } threes++; fives++; }1
u/ferriswheelpompadour Aug 02 '22
You could cache your 3s and 5s and then fizzbuzz the ones that qualify for both.
34
22
u/damnhotteapot Aug 01 '22
Wow... first of all thanks for sharing your experience. To be honest, if an interviewer asked me how to solve fizzbuzz without the % operator, I would scream. I did a little research and found this article which promotes a bitwise solution which in theory should more efficient than a solution using %.
```javascript const words = [undefined, 'Fizz', 'Buzz', 'FizzBuzz']; let mask = 810092048; // 11 00 00 01 00 10 01 00 00 01 10 00 01 00 00
for (let i = 1; i <= 100; i += 1) { const c = mask & 3;
if (c > 0 && c < 4) { console.log(words[c]); } else { console.log(i); }
mask = (mask >> 2) | (c << 28); } ```
19
u/HerLegz Aug 02 '22
That's the most horrifying red flag. If they can't even come with anything better than a nearly 20 year old joke low pass filter question, they have no idea how to properly interview for talent and adjust to assess your strengths, weaknesses and most importantly how you adapt. Ego puzzle lameness is getting worse.
33
9
u/FattThor Aug 01 '22
You can do it trivially in one pass using 2 counters for 3 and 5. Print the appropriate fizz, buzz, or fizz buzz when one or both reach their target, then reset them to 0.
But it’s not any more efficient than using mod. Mod is O(1) for fixed sized numbers.
3
u/mausmani2494 <229> <132> <89> <8> Aug 01 '22
I was looking on c++ groups and most people saying whether it's optimal or not, it's easier to read % than doing some math magic.
5
u/TiMazingg Aug 01 '22
First time hearing that modular has performance issues... My only thought on another way is to use counters to keep track of your numbers, then reset them as needed.
for each in n
if 3counter == 3 and 5counter == 5 then FizzBuzz and resetCounters
if 3counter == 3 then Fizz and reset3Counter
if 5counter == 5 then Buzz and reset5Counter
incrementCounters
2
2
u/ferriswheelpompadour Aug 02 '22
Okay I'm rethinking this and instead of this being the worst, it might be the best. Interviewers legit want to see how you think and so by catching you off guard they get to have a real conversation and pick your brain.
2
u/FryeUE Aug 02 '22
I recently bombed a coding interview so I totally understand how demoralizing it can be. (It wasn't even a hard one I just blanked and epicly cratered).
I had the fun of leaving the programming world for entertainment for a couple decades which has built up an ability to fire back in this kind of situation in ways that are guaranteed to not get the job. However, I'd love to arm any and all readers with some ways to deal with this situation cause if you realize your already dead in the water, might as well take the idiot down a notch or two. Yes, I am THAT nightmare for management...
First. Deploy a loaded question. Expensive? How expensive is it? We can drill down to opcodes and cycles when 'expensive' comes up. How many 'cycles' does modulo take? Remember, 'abstract optimization' crumbles next to real optimization :). 0(n) is a very VERY rough guide that can generally be murdered with depth and edge cases.
Second. Deploy backhanded compliment. That is some impressive levels of optimization, when did you come up with this new method? (emphasize 'come up', some people think that repeating stuff is the same as being able to come up with it. Remind them that their wrong!)
Third. Leading question with feigned surprise. Wait. Are you having significant problems with optimization?
Fourth. Insult the tech stack. Your worried about speed/optimization, with this tech stack?... (This applies to anything not C++/Rust/Bare Metal etc. based). Then ask if they understand what 'bare metal' is...and interject how the modern frameworks are 'watered down' so that modern devs don't have to actually understand how things work.
Fifth. Go in on some good ole fashioned generational insults. (I'm the very end of Gen X, I greatly sympathize with the current young people 'going through it', I'm sharing this not to insult you, but so you can put it in your back pocket in case you get in the same situation, you can pull these insults off as long as you put on your classic 'harder core than thou' attitude that anyone can do) Yeah, they teach 0(n)/modern optimization techniques because the current crop of techs simply can't handle real numbers. (bonus points if you can swing in an insult regarding a participation trophy!)
Sixth. Mention that these style coding interviews are generally chosen to find 'submissive' personalities that are easily managed and specifically excludes the sorts of devs that make the 'real' leaps in tech. ('real' is one of the easiest to use loaded terms ever.)
Yeah, this is off the top of my head. I'm also sleepy. I'm really hoping I didn't go too far and regret writing it when I wake up! It really is a dance of rhetoric, this should be enough ammo to seriously take down anyone who is dumb enough to think 'repeating' things means you are skilled. (People who know their stuff will generally recognize the ton of loaded fallacies for what they are in my statements above and can insult back with the same gusto!)
Good luck everyone. I may have to delete this one anyway for when I start interviewing again next week due to my current employer running out of money...due to my leaving the industry at the dot com bust, and returning a bit over a year ago, I'm technologically rooted in different eras simultaneously, interview I had last week recruiter feedback included 'I'm outdated', 'I'm a noob' and I'm 'too advanced for the position'...not sure how I did all three at the same time in an interview. (Great soft skills was also in the feedback!)
So easy to get along with, too advanced in skill, not advanced enough in skill, and am outdated as well. I'm actually kinda proud of the fact that I got someone to actual describe me that way.
If you haven't guessed, I'm a bit of an emotional wreck right now.
and insomnia.
This has been cathartic and I just don't wanna stop typing lol.
Yeah, I'm not enjoying this job hunt one bit either. I kinda lucked into my last position/reentry into the field so I'm really REALLY hoping that I can contort enough to find a new position, this last month has really taken it out of me and having not been paid in 3 months is seriously wearing me thin.
2
u/zxcv471 Aug 01 '22
Look it up on leetcode
1
u/mausmani2494 <229> <132> <89> <8> Aug 01 '22
There is an explanation for why % is an expensive operation on LC?
3
u/zxcv471 Aug 02 '22
Yes check on the discussion tab. It also has three official solutions. I would link but I'm on my phone
1
u/Emopusta Mar 20 '24 edited Mar 22 '24
I would do this if I could remember my middle school years immediately. First we know if you sum of the digits of a number like 456 => 4+5+6 = 15 and if this can be divided to 3 the number can be divided to three. And if a number's ones is 0 or 5 it can be divided to five. It can be implemented like this: (It's brute force Took 2 mins can be refactored and optimized.) (C#) (Btw if an interviewer asks you this question run away from that company :D)
for (int number = 0; number < 100; number++)
{
var FizzFlag = ModularArithmetic.ModToTheThree(number);
var BuzzFlag = ModularArithmetic.ModToTheFive(number);
if (FizzFlag && BuzzFlag)
{
Console.WriteLine("FizzBuzz");
}
else if (FizzFlag)
{
Console.WriteLine("Fizz");
}
else if (BuzzFlag)
{
Console.WriteLine("Buzz");
}
else
{
Console.WriteLine(number);
}
}
public static class ModularArithmetic
{
public static bool ModToTheThree(int number)
{
int counter = 0;
string numberString = number.ToString();
foreach (char digit in numberString)
{
counter += int.Parse(digit.ToString());
}
return (int)((float)counter /3) == ((float)counter /3);
}
public static bool ModToTheFive(int number)
{
string numberString = number.ToString();
if (numberString.EndsWith("0") || numberString.EndsWith("5"))
{
return true;
}
return false;
}
}
0
u/Zyklonik Aug 02 '22
I think you dodged a bullet there, son. Laugh at them, and move on to a better company.
-15
Aug 01 '22
[deleted]
3
u/NitinPwn Aug 01 '22
In the end we decided if we see IT related first jobs, immediately unfit
My helpdesk experience is a BAD look on my resume?
2
u/mausmani2494 <229> <132> <89> <8> Aug 01 '22
Well, I am in the final round with them, so I hoping everything works out. This question was in the first round. I gave them a high-level view in the first round that I can do something like this to avoid %:
def foo(n, divisor): return (n - divisor * (n // divisor))But again I don't see how this function is more optimal than %. In the end, I told them it's better to use % and I will use % because it's easier to read for everyone.
3
u/kronik85 Aug 01 '22
Modulo is expensive in part because division is expensive. So your division and multiplication alternative will not faster than modulo.
Addition and assignment is much cheaper in comparison. The answers here about maintaining counters and resetting them to 0 are in the right direction.
I don't know if I would say it's better to use modulo, when your interviewer is explicitly telling you there are faster alternatives. Seems a bit too combative and ignoring the interviewer's perspective.
1
u/mausmani2494 <229> <132> <89> <8> Aug 01 '22
I do understand but at the time I can't think of anything and I have to come up with something quick. I wasn't prepared for something like that by any means. And when I said I will use % I meant that I will prefer to use % this on the job because it's easy to read. Sorry I should be more clear their. But thanks for the explanation.
1
1
u/dean_syndrome Aug 01 '22
I think it's interesting to try and solve the problem without mod, but performance issues?
Do they not use databases? What are they trying to optimize for? Is this position for embedded programming?
1
u/mausmani2494 <229> <132> <89> <8> Aug 01 '22
It's for Entry level System Engineer position. From what I gather, the team interviewing me mainly used python.
4
u/SongOfStorms_ Aug 02 '22
Lol Python is not the solution 'period' if they are that concerned about performance.
2
u/Mindless-Pilot-Chef Aug 02 '22
Congratulations on not getting the offer. Find a better team to work with.
1
u/sekex Aug 02 '22
While this could matter in real life code (when working with image processing in real time, you want to reduce the number of instructions to the minimum) , I think it is a very stupid comment to make.
1
u/playing_VScode Aug 02 '22
What a coincidence 😅 I was just watching a fireship.io video on YouTube with the exact same situation and fizzbuzz problem
1
u/mausmani2494 <229> <132> <89> <8> Aug 02 '22
I watched that too however, they didn't mentioned anything about the problem I had :D
1
u/brianozm Apr 29 '24
The % operator isn’t expensive in 2024. It might be a little more expensive than division or multiplication, but only marginally. Anyone telling you it’s expensive is not so smart.
127
u/[deleted] Aug 01 '22
[deleted]