What the FizzBuzz? (A toy problem worth caring about?)
Patreon ➤ / jacobsorber
Courses ➤ jacobsorber.thinkific.com
Website ➤ www.jacobsorber.com
---
What the FizzBuzz? (A toy problem worth caring about?) // This week's video deals with a toy problem (FizzBuzz) that's become rather popular in the last decade as a quick way to evaluate basic programming skills. In this video, we discuss how to solve it a few different ways and why it's interesting.
***
Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.
About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.
More about me and what I do:
www.jacobsorber.com
people.cs.clemson.edu/~jsorber/
persist.cs.clemson.edu/
To Support the Channel:
+ like, subscribe, spread the word
+ contribute via Patreon --- [ / jacobsorber ]
Source code is also available to Patreon supporters. --- [jsorber-youtube-source.heroku...]
Пікірлер: 113
Imagine a coding interview being like generate as many different ways to solve FizzBuzz
@nikozdev
Жыл бұрын
I would ask for 10 😅
@asagiai4965
11 ай бұрын
That is actually a valid way to choose who to hire.
Having been on the hiring side of the interview table, I think I'm with you on "What value are toy problems?" The conceptual questions, effectively design, always seem to be more effective and telling. But that said, the guy who did the absolutely worst on the design question (and I had decided we shouldn't hire him) that we eventually hired, turned out to be one of the absolutely best developers we had. His code was always clean and straight forward. I could hand it to anyone and they would be able to follow what he was doing. When he left the group for family reasons (the job was a hideous commute for him), I was genuinely sorry to see him go. How to interview from the hiring side would be an interesting thing to cover...
When I was fresh out of college, I was asked to do FizzBuzz on an interview for a hackathon type event. The only issue, the question wasn’t *really* FizzBuzz, it asked if a number was a power of 3 or if it was a power of 5. After I struggeld for 5 minutes, the young guy doing the interview proceeded to explain to me the solution *for FizzBuzz*. He left with an air of superiority after telling me I wouldn’t be a good fit, as I stared at the exercise in disbelief and felt relieved of not wasting a whole weekend on that event.
@R4ngeR4pidz
Жыл бұрын
Do you mean multiple? If it's power then I wouldn't say it's similar to fizzbuzz
@unperrier5998
Жыл бұрын
@@R4ngeR4pidz I think that's the point. What he's saying is that the interviewer didn't really know what the code he was given for fizzbuzz was doing and that's the reason why he guessed and ended up asking about powers of 3 and 5 instead... but eventually show the code for a totally different problem indeed.
@HulkRemade
Жыл бұрын
For power of 3 and 5, could you do the same fizzbuzz coding but use log instead of mod?
@unperrier5998
Жыл бұрын
@@HulkRemade log takes one argument. mod takes 2 arguments. what do you mean?
@HulkRemade
Жыл бұрын
@@unperrier5998 Mathematically, I mean, Log has two arguments, a base and a number. If you check if log base 3 of the number is an integer and log base 5 of the number if an integer instead of checking the number mod 3 and the number mod 5
I thought of this way which is similar to the lookup table, just wanted to share it: void fizzbuzz(const int N) { const char *strs[] = { "%d", "Fizz", "Buzz", "FizzBuzz" }; for (int i = 1; i
@michaelclift6849
Жыл бұрын
That's cool. 2 boolean conditions, 4 possible combinations, all covered by the table.
@dexter9313
Жыл бұрын
We pretty much got the same solution with a different syntax, cheers ! const char *lut[] = {"%d ", "Fizz ", "Buzz ", "FizzBuzz "}; for(unsigned int i = 1; i { printf(lut[ !(i % 3) + ((!(i % 5))*2) ], i); }
It shows how much you're gonna care about overall software maintenance for "people" and not so much how fast your code is or how much you know about SIMD/platform specific trivia.
In fizzbuzz5() I would add " " to lookup table strings to get rid of the second printf()
The most efficient solution might be to fill the lookup table during the processing of the first 15 numbers, then for higher numbers just looking them up. That avoids the ugly hand-coding of the table, but still keeps the efficiency of the table compared to manually calculating the values every time.
@unperrier5998
Жыл бұрын
with the caveat of the old tradeoff memory space vs CPU time...
@gregoryfenn1462
Жыл бұрын
Depends how fast the memory access is. In this case the table is small enough to fit in local cache but in general a memory lookup might sometimes be slower than a trivial computation like "i%5==0". It depends on how hard the bool is to compute
@unperrier5998
Жыл бұрын
@@gregoryfenn1462 The tradeoff "cpu vs space" is about how much memory is needed to cahce the result of an expensive computation. The speed of memory and the speed of the CPU are two inputs to the tradeoff decision. Your two examples are corner cases that fall outside of the application of the tradeoff "CPU vs Memory": - if you've got fast memory available (like CPU caches) you should use it. - if your algorithm is fast to compute you should use the CPU. They're no brainers, obvious cases where you won't apply the tradeoff.
@anon_y_mousse
Жыл бұрын
@@gregoryfenn1462 The i%5 operation may be trivial for a human to do in their head, but for computers division is one of the more costly operations. If you're going to be iterating over a large set, generating a lookup table is far more preferential to computing the value each time.
@KarlGeiger0
Жыл бұрын
The DIV (unsigned) and IDIV instructions on x86 ISAs emit both quotient and remainder. Hardware's pretty quick these days. 😉 Compile to assembly with gcc -S -o .s .c if you want to see the instruction stream.
Normal I love to let the initializer list determine the length of the array, but in the case of the lut, I suggest to explicit set to 15. Then the compiler help you count.
A complex, but arguably realistic option, is a function that returns an enum with one of four calculation results and another that prints based on those results. This separates the logic from the output.
@wilfreddv
Жыл бұрын
I smell MVC
Couldn't you put i % 15 == 0 at the top?
When you mentioned a potential lookup table solution, I paused the video and it inspired me this : const char *lut[] = {"%d ", "Fizz ", "Buzz ", "FizzBuzz "}; for(unsigned int i = 1; i { printf(lut[ !(i % 3) + ((!(i % 5))*2) ], i); } I think it's quite elegant.
@michaelclift6849
Жыл бұрын
You're not alone, @ahmad hadwan posted this above.
@dexter9313
Жыл бұрын
@@michaelclift6849 Nice, just saw it. He manage to scram a bitshift instead of the *2, I feel ashamed !
@anon_y_mousse
Жыл бұрын
@@dexter9313 Of course even at -O0 most compilers will turn the multiplication into a shift anyway.
Calculating the lookup table at compile time with C++ constexpr would also be neat.
the lut implementation probably holds the most merit because it eliminates branching (except for loop exit condition of course but the branch predictor should rarely fuck that one up).
Thanks !!
A slight improvement to fizzbuzz3 could be to move the check for divisible by neither to the top and use continue to skip over the other checks. Also I've seen string building method and using a check at the bottom for the string being empty to decide to just print i and newline. Probably makes more sense in python than c though.
@AdroSlice
8 ай бұрын
The fastest solutions in JS I've found were the bruteforce-ternary that covers all 4 cases seperately, as well as the lookup method. Writing to the console is pretty slow, and so is concatenating strings, so you kind of want to avoid both. About your first suggestion: Checking for the most common case first is definitely faster than taking an approach based more on a "logical" order, and definitely presents an improvement over the more primitive solutions. This is part of why it's also more performant to check whether a number is *not* divisible by 3 or 5, which skips an extra check or negation. So the fastest solution in JS is probably this: let output = []; for(let i = 0; i output.push( i % 3 ? i % 5 ? i : "Fizz" : i % 5 ? "Buzz" : "FizzBuzz" ); Let this be a lesson that smarter solutions can very often be inferior to things as primitive as above nested ternary. (Also if you don't like ternary, you can write this just as easily using if-else.)
I'm not a programmer (more of a physics student) but if I were to solve this problem: I would create a mutable empty string variable; if the number is divisible by 3, I would append "Fizz" to it, and if it is divisible by 5, I would append "Buzz". Finally I'd print the string.
What about the solution of adding contents to an output string? It seems more scalable and easier to read.
@nekogod
10 ай бұрын
This is a good way to do it, and it is indeed more scalable, just have it check each number you want to mod check and then if it passes add whatever word to the string and then at the end one final check to see if the string is empty or not. Easy to add new tests and easy to alter the tests/words that get output.
My (totally not Tom Scott's) solution would be: (i don't really know c so i'll use cpp, but i think it could also be done in c with strcat or something) for (int i = 1; i
@Hauketal
Жыл бұрын
Your use of printf is neither appropriate nor correct.
@wojwesoly
Жыл бұрын
@@Hauketal oh yeah that's why you don't write code in youtube comments instead of a code editor, but you get what I meant to write
@wojwesoly
Жыл бұрын
@@Hauketal And why isn't it appropriate btw?
@Hauketal
Жыл бұрын
@@wojwesoly You are just writing constant strings. All that format mechanism in printf is not needed, the much simpler fputs can be used.
My solution would be : const char* fizz = "Fizz"; const char* buzz = "Buzz"; const char* fizzBuzz = "FizzBuzz"; const char* num = "%d"; void fizzBuff(const int n) { for(uint_t i = 1; i
What kind of extension that you use to make your != and -> turns into nice-looking symbols?
Nice as ever. But the loop should go like "i
If you implemented this in C++ you can also do this with either lambdas, templates, and more.
@viacheslav1392
Жыл бұрын
If you implemented this in Java, Rust, C#, Zig ... you can also do this with either lambdas, normal generics and more
Wouldn't we also suggest const bools for readable, DRY, computed logic? Why not just do: const bool Fizz = i%3 > 0; const bool Buzz = i%5 > 0; const bool Num = !(Fizz|Buzz); Etc... This is much more readable and means you only evaluate 2 modulus operations. Or is this a bad method? str = ""; if (Num) str += i; else { if (Fizz) str += "Fizz"; if (Buzz) str += "Buzz"; } str += " "; I've wrote the string construction in pseudocode rather than a more efficient C method because that's not the focus of my question.
@JacobSorber
Жыл бұрын
Looks good to me. Thanks.
Hi Jacob... Thanks for these awesome video's!! They not only help beginner C programmers, but also help more seasoned C programmers to generate more refined, efficient, stable, and secure code... A question -- I wasn't sure where to post this, so thought I would just put it as comment to this video... Is there any way you could make a video on the best recommended method for storing and retrieving user credentials in a file in C? I'm looking at making a CLI interface program that will first ask for a username and password for the user. It will then go out to a file to interrogate to be sure the username/password pair is correct. I'm assuming to store the password as a hash value, and compare hash values during the login process, but should these just be sha256 (or higher), or some other crypto lib? And how would it be used? Thanks again!
@JacobSorber
Жыл бұрын
Thanks, Larry. Great suggestion. I'll see what I can do in a future video.
hi sir I am Little bit confusing about array of pointer to string when it's comes to my mind i am going wrong when I wrote the code using array of pointer to string my actual doubt is char *games[3] = { "roadrash", "nfs", "angrybirds" }; games[0] = "hitman"; // this is working when I use string function like strcpy, strcat ,scanf like below I am getting an error scanf("%s", top_games[0]); strcpy(top_games[0], "mario"); gets(top_games[0]); strcat(top_games[0], "needforspeed"); can you pls help me to understand this topic with your words Thank you so much sir......love from indiaaa
@anon_y_mousse
Жыл бұрын
String literals are read only, if you want space you can copy into use malloc to allocate the space and free when you're done with it. If you want it more simple, change your array from char* to char [N] where N is the maximum length you'll use, say: #define MAX_LENGTH 32 char games[3][MAX_LENGTH] = { "roadrash", "nfs", "angrybirds" }; Then when copying into the array, bounds check against that length with something like memchr. Also, you might want to avoid scanf until you know more about how to use it and instead use fgets.
When I was a kid, it was fizz-fuzz-phooey. If the number is divisible by 4 or has the digit 4 in decimal, it's fizz; if it's divisible by 5 or has a 5 it's fuzz; and if it's divisible by 7 or has a 7 it's phooey.
The implementation I find most elegant uses a match statement. Here's a rust implementation that I'll just assume compiles and works: fn fizzbuzz(n: i32) { for i in 1..=n { match (i%3 == 0, i%5 == 0) { (false, false) => println!("{i}"), (true , false) => println!("Fizz"), (false, true ) => println!("Buzz"), (true , true ) => println!("FizzBuzz"), } } } Personally, I think the "simplicity" of using the "print Fizz" and "print Buzz" statements together to handle the "fizzbuzz" case is misguided. Not only does it make the code less readable, but I think doing so makes it slower, with the multiple calls to a print function. It also makes the program more specialized to this particular case where the fizzbuzz message _is_ just the buzz message appended to the fizz message, and therefore a bit less adaptable.
@neopalm2050
Жыл бұрын
Also, I'm trusting the compiler to know how to best optimize match statements on tuples of booleans. If it doesn't optimize this to something as good or better than some of the 4-entry lookup tables I've seen in other comments, I think that's a problem with the compiler more than this code.
Your fizzbuzz looks great Timmy, now suppose there was a server outage at 4am that was causing your fizzbuzz to fail, you'd die for this company right?
Do other people think that fizzbuzz3 was the most straight forward, cleanest way to write it? And I also wrote a recursive function, which is absolutely unnecessary and wasteful, but works. But shits and giggles, guys.
@Victor_Marius
Жыл бұрын
I think fizzbuzz2 is better. You can scale for more than 2 values pretty easily.
As I write this comment you art at 94.2K subscribers. this is a relatively simple solution base on the one you had. In it I do the check for %3 or %5 at the beginning and within that if statement i check if it is %3 , %5 or both. Else I printed the number. void fizzbuzz(int n) { for(int i=1; i
Honestly I feel these kind of questions are waste of time for most interviews. When I design questions, I just care for giving a realistic toy examples of problems we work with daily... Much better way to judge if a person will be able to do the job or not.. I have seen a lot of fizzbuzzers and array-flippers choking on their 1st real production project code...
You could use a 4 bit wide unsigned bitfield as a counter. Heh. for(int c:4 =1, i= 1; i ... but actually, in an interview, I would say this question gets interesting if various operators are expensive. What if comparisons are expensive? What if mod() is expensive? This is actually an important thought. Old or weak processors take a long time for mod() vs. add or compare. Discrete logic for mod() is huge compared to mod or compare.
@JacobSorber
Жыл бұрын
Good point. Things definitely get interesting if you don't allow mod.
@randomscribblings
Жыл бұрын
@@JacobSorber I'm not even on about mod specifically. Taking about the cost of mod and comparisons is just the jumping point from the trivial toy problem to real problems. Real functions cost and real comparisons cost. How much is relative. Interview questions are most useful if you use them to prompt the applicant to say things off script --- to find what their personality, skills and talents are. Some people are about optimization, some people are about readability. The best, tho, is when you can use the example as a jumping point discuss. If I was being interviewed, I'd want to show that solving the problem, while necessary, was the least of the problems facing me that day. I've been on both sides of the table. As an interviewee, the most complex was at an early video card company that had bet heavily on medical imaging (because the video card market was not kind). I was interviewing for the "tool smith" position. They had a particular problem in that their build process involved nearly 100 separate tools. Anyways... their "question" was a library that purported to be an elevator ... which you linked to and wrote a controller. As I was applying for a tool-smith, I wrote a state machine that could also be linked to --- which solved the stated problem in it's test build --- but was clearly meant to be used to build smarter logic using the state of the state machine rather than simply the sensors. I got the job. On the other side of the table, tho, I've pushed for questions more along the lines of "discuss how to implement " with the goal of opening up the applicant a little --- the point is not eliciting correct code in the interview, but evidence of coherent thinking.
@unperrier5998
Жыл бұрын
@@JacobSorber you can always implement modulus using basic bits manipulation. You could make a video about that too.
@ramakrishna4092
Жыл бұрын
@@JacobSorber hi sir I am Little bit confusing about array of pointer to string when it's comes to my mind i am going wrong when I wrote the code using array of pointer to string my actual doubt is char *games[3] = { "roadrash", "nfs", "angrybirds" }; games[0] = "hitman"; // this is working when I use string function like strcpy, strcat ,scanf like below I am getting an error scanf("%s", top_games[0]); strcpy(top_games[0], "mario"); gets(top_games[0]); strcat(top_games[0], "needforspeed"); can you pls help me to understand this topic with your words Thank you so much sir......love from indiaaa
10:50 this would be my first try on the problem
@lasshrugged
28 күн бұрын
The first time I saw this problem was on a coding interview, and my solution was basically fizzbuzz4.
OMG.. what did I miss ? @5:00 (or around)... void fizzbuzz1(const int N) { } ** Why the const ? This serves no purpose ! it is a parameter passed by value, not a frigging pointer ! whether you modify it or not has no effect - it's a symbol that is local to the function ! And why is this not a static function ? If it were it could potentially be inlined helping the optimizer ! GOOD GRACIOUS !
Wow someone talking about fizzbuzz At the surface looks like an easy, you think you already know it task. But geniuses knows it is much more.
I'm actually rather biased against this type of "show off" interview, where it feels more like you're trying to show how many versions of code you can produce rather than proving that you understand the algorithm that's being asked. I deal mostly with numerical methods, so our focus tends to be speed and reliability, rather than fancy code writing. I'd argue that is more important to make sure that the candidate understands what's being requested, and can come up with at least a reliable code. FizzBuzz has many solutions, but there's little objective improvement between them, while readability is usually subjective and dependent on experience. For example, I'd rather ask the candidate to implement a product between a linearized access 3rd order tensor and a matrix, as this can end up being quite costly in numerical applications.
Uhm, cool! Never head of Fizzbuzz. What do you think about this? I've kinda reversed the flow (first the number, than the Fizz/Buzz). for (int i = 1; i
@arian8791
Жыл бұрын
Not going to work for N having over 4 digits
@Tachi107
Жыл бұрын
@@arian8791 that's right, hadn't thought of that :)
@anon_y_mousse
Жыл бұрын
@@Tachi107 Most terminals would likely interpret that carriage return as a line feed too and it wouldn't behave the way you want either. You'd likely need to use something like curses to get the correct behavior and pad the number with spaces to at least 8 digits to account for FizzBuzz, but then you'd have the same problem if the number were over 8 digits.
@Tachi107
Жыл бұрын
@@anon_y_mousse it worked on my Linux machine. Are you aware of terminals that interpret as ? Windows maybe?
@anon_y_mousse
Жыл бұрын
@@Tachi107 Windows more than likely would, or at least it did in the past. Of course if you're on Windows you might be using a compiler which interprets the same anyway and just generates as if you used , which the C standard allows to be \xd\xa all on its own.
just wanted to share my idea. its not that elegant but im glad i found something else than multiple if statements xd int main(void) { char divid3[3][5] = {"Fizz"}; char divid5[5][5] = {"Buzz"}; for(int i = 1;i { if(printf("%s%s",divid3[i%3],divid5[i%5]) printf("%i", i); } printf(" "); } }
I sometimes wonder if I can manage to get all the way through a talk by Kevlin Henny without him saying "and now we will apply these ideas by coding a new version of FizzBuzz" ;)
Using Forth and function pointers: : zap dup 0 .r ; : fizz ." Fizz" ; : buzz ." Buzz" ; : fizzbuzz fizz buzz ; create foo ' zap , ' fizz , ' buzz , ' fizzbuzz , does> >r dup 5 mod 0= 2* over 3 mod 0= + cells r> + @c execute drop ; : bar 101 1 do i foo space loop ; bar It's about equivalent to: #include int main (void) { char *s[] = { "%d ", "Fizz ", "Buzz ", "Fizzbuzz " }; for (int x = 1; x }
don't use mod or division: fizzbuzz(int n){ int f,b,i; fot ( i=1,f=3,b=5 ; i0) & (b>0) ){ printf("%d", i); }else { if(f==0) { printf("fizz"); f=3;}; if(b==0) { printf("buzz"); b=5;} } printf(" "); } }
Personally, I hate litmus tests. I mean, I understand the reasoning behind it, but the feeling that I'm being "tested" just brings out the spiteful punk in me and just makes me more aggravated at the tester than I am interested in the problem. We all have our own ways of coding.
Please rename fizzBuzz6() to rubeGolbergMachineFB(). 😁
oh fizzbuzz, how many person has write it in 100 line or more 😂😂😂😂😂
call api
@unperrier5998
Жыл бұрын
api response
So much buzz about a simple problem...
Your usage of the UTF "≠" instead of "!=" makes me grind my teeth and consider self harm. Please stop. I mean it, just stop it... it's making me cry now, and I miss the dog I had as a child because I need a hug. For all that is wholly just use "!=" and save all the unborn kittens and whales. Also FWIW, perhaps avoid examples that rely on the bounding of the problem at 20. By that I'm referring to the LUT. Maybe put a NULL at the end of the array and check for it?
@Nathan-pl2cf
Жыл бұрын
The lut is only 15 long because the whole problem cycles (i % 15), not because N is 20
@chopper3lw
Жыл бұрын
@@Nathan-pl2cf My bad, thanks. I was probably overcome and distracted by the sadness resulting from the !=
bro 1 thing plz,,,,,,, plz speak slowly thers no hurrryyyyyy>.
It's a fun problem to poke at. Lookup tables are an exercise creativity/cleverness. Wrote several last spring; got it down to a simple lookup with a single arithmetic operation similar to second to last solution in video. #include #define LIMIT 35 /* ... variants 1 through 9 omitted ... */ static char * fb10(int n) { return (char * []){ "FizzBuzz", "", "", "Fizz", "", "Buzz", "Fizz", "", "", "Fizz", "Buzz", "", "Fizz", "", ""}[n%15]; } void main(void) { for (int i = 1; i printf("%s", fb10(i)) || printf(" %d ", i); printf(" "); } } /* main() */
@JacobSorber
Жыл бұрын
Cool. Thanks.
@KarlGeiger0
Жыл бұрын
@@JacobSorber - Fun to find the fewest operations to do something. Started playing fizzbuzz games after watching Kevlin Henney's 2017 {NDC} talk. kzread.info/dash/bejne/eK13u9iaaafOo6w.html
Actually, you can also use recursion. Like this: #include #include void fizzbuzz(int n) { if(n == 0) return; if(n % 3 == 0) printf("Fizz"); if(n % 5 == 0) printf("Buzz"); if((n % 3 != 0) && (n % 5 != 0)) printf("%d", n); printf(" "); return fizzbuzz(n - 1); } int main(int argc, char* argv[]) { if(argc != 2) { return -1; } int n = atoi(argv[1]); fizzbuzz(n); return 0; }
@anon_y_mousse
Жыл бұрын
You can use recursion, but you shouldn't use recursion. Avoid it at all times and if you see something recursive, convert it.
#include int main(void) { const char *fizz_buzz[] = {"", "Fizz", "Buzz"}; int i = 1; while (i