The Problem with the FizzBuzz Problem

http://www.gayle.com/blog/2015/5/31/the-problem-with-the-fizzbuzz-problem

by jasonmp85 • 11 years ago

36 112 11 years ago

VLM• 11 years ago

The TLDR summary of the article is its really easy to get stuck down a mineshaft of "I'm sure they're looking for a more elegant way to do this". (edited to add, because scalability... demand fizzbuzz run 1...1e99 or under some weird time constraints and all bets are off, but no, its 1...100)

The comment on the article of a similar example of print an ASCII art diamond claiming cleanly using symmetry is unusable sticks in my brain a bit. There's gotta be a way! I mean, there has to be, right? But my first bright ideas all involve limitations that would be very non-clean and limitation inducing, although they would be cool applications of symmetry.

gresrun• 11 years ago

This is a bit too involved for a whiteboard problem, IMO, but it isn't that hard to create a relatively clean solution: https://gist.github.com/gresrun/602bd53dad80bb51bb94

detrino2• 11 years ago

I think I found the symmetry: http://ideone.com/KnaAMm

Edit: Now with more symmetry: http://ideone.com/edNgre

detrino2• 11 years ago

Less repetition: http://ideone.com/yPQzy6

lordnacho3• 11 years ago

Here's a similarly simple question that I used on hundreds of people who were trying to get a job at a hedge fund:

You have a dice (1-6). Some guy offers to pay you whatever you roll. What are you willing to pay to play this game?

Somehow, most of the applicants, who all had quantitative degrees, never made it very far. It's actually a warmup (what would you pay for the same, but with a chance to re-roll once?).

I just don't believe that people can't figure out the expectation of a dice roll. It makes no sense to me. Over the years I've concluded it must be because the way it's asked. People think there's something deeper in it than the most straightforward explanation. Or maybe they think they missed some critical detail and are afraid to ask.

Now there are actually some clarifications that would make it more interesting, but I never got anyone to ask those (Is it an eternal game? Do I have a limited pot?).

What was really dispiriting was when someone understood it, and were shocked we'd asked it.

JoeAltmaier7• 11 years ago

I'm willing to pay $0!

No, really, statistics are unintuitive and most people, smart people, don't have a feel for them. Just look at the HN thrash whenever the Monty Hall problem comes up.

Btw its a 'die'. 'Dice' is plural.

apalmer2• 11 years ago

Yeah but he specifically said these are folks with quantitative degrees... I would expect want to be quants applying at a hedge fund to have an understanding of statistics.

dragonwriter• 11 years ago

Btw its a 'die'. 'Dice' is plural.

Most current dictionaries disagree and accept either "die" or "dice" as singular, with "dice" also being plural.

madcaptenor• 11 years ago

Even if you have no risk tolerance, you should be willing to pay up to $1.

ilzmastr• 11 years ago

for those who want more, from: http://www.amazon.com/gp/product/0994103867/ref=pd_lpo_sbs_d...

chapter 4

DenisM• 11 years ago

It's a really nice question! It lends itself to starting with simple answers and gradually building up to a more elaborate and more precise answer. Even absent any stats knowledge you should be able to pledge at least 99 cents per roll, as you're always getting at least a dollar back, right? Woo! I'm winning already! :)

I'm surprised people are having trouble even getting started. Perhaps the interview setting is intimidating? You should run a couple of friends-of-friends through it, and then ask your friends how the subjects felt.

chubot• 11 years ago

If I were completely rational, something less than $3.50, since that's the average of $1 to $6 ?

Is that it? It does seem too simple, or otherwise the wording threw me off too.

lordnacho3• 11 years ago

That's all I was after.

MichaelGG3• 11 years ago

That's disappointing, if you just meant for them to sum up the sides and divide. But at first I thought you meant to figure out the probability of the die being loaded - after the first roll, there's a higher chance of getting the same number than any other. Plus I'm assuming the physics of a loaded die don't just influence one side, but have a non uniform effect.

Or maybe by "you have a dice" it means it's mine, and I know it's not loaded (I doubt I'd know, and the cheap DnD dice I own are probably not casino quality). So maybe this guy is trying to take advantage of known quality issues in common dice. For instance. the extra pits on the higher valued sides mean that side is lighter, thus has a higher chance of coming up, right? (The side with 1 pit weighs the most, so I'd expect some bias towards rolling a six.)

Cause if we assume the person offering me money has an angle, well, there's gotta be something, right?

chippy• 11 years ago

You have a dice (1-6). Some guy offers to pay you whatever you roll. What are you willing to pay to play this game?

Could you rephrase the question please, as this is what I take from the above:

Firstly, why should I pay to play it, if some other guy is offering to pay me anyhow? All I would pay is the same unit of time spent rolling the die.

If the time taken to roll a die is worth less than the payout for rolling a 1, then any roll is going to make me money. If it is more then the payout for rolling a 6 then it's not worth rolling at all, and if in between - that's where some gambling comes into play.

nilkn2• 11 years ago

I'm sure you'd get a higher pass rate if you just asked for the expected value of rolling a die. People most likely don't pass because they don't realize that's what you're looking for.

The question is phrased in a more confusing way. You have to realize that what the question really means is more like this: if you were able to play this game repeatedly, what's the most you'd be willing to pay for each time so that you don't lose money on average over time?

For what it's worth, simply asking "how much" you'd be willing to pay is fairly confusing, because ideally you wouldn't pay anything.

This isn't astoundingly hard or anything, but anytime the candidate has to "rewrite" the question the pass rate is going to go down.

I'd recommend setting it up as a carnival game and phrasing it from the perspective of the carnival, not the player. Ask for the minimum price the carnival needs to charge so that they can be confident they at least won't lose money on average over time.

bloaf• 11 years ago

If the person's job is going to be taking well defined problems like "find the expected value of x" and solving them, I'd rather buy software. I would actually want an interview to weed out people who were unable to re-parse confusing real world input, like that problem. I would want employees who could, as a matter of course, take a somewhat ambiguous situation, choose relevant tools (e.g. expected value,) and render a judgment.

notahacker• 11 years ago

Absolutely. In fact, if I was running a hedge fund I'd definitely not want to hire the person that without hesitation signalled willingness to pay the EV of the dice roll: i.e. a person that when offered an opportunity to speculate with the potential for profit and no certainty about the ask price or their own risk tolerance, instantly bids at a price which makes the speculation a zero-sum gamble.

I'm assuming some of the relatively smart candidates that don't leap at the answer are pondering whether they should ask about the interviewer about risk aversion, Sharpe ratios etc, or whether that's a trap and they're supposed to make inferences about a measure of risk adjustment based on the known distribution of dice outcomes. Of course, their over-thinking of the problem would help them rather than harm them if they talked through the problem, but people tend to go very quiet when they're convinced they're under more pressure than they actually are.

discardorama• 11 years ago

I'd pay 0 to play it, and get $3.5 back (on average) on each roll. Nowhere does it say that the 'some guy' can refuse your offer.

shabble2• 11 years ago

Now that's finance-industry thinking!

In fact, does the cost even need to be non-negative? Why not demand a 'playee fee' to be added onto your winnings.

yellowapple2• 11 years ago

You have a dice (1-6). Some guy offers to pay you whatever you roll. What are you willing to pay to play this game?

Is the correct answer not "1"? That would be the maximum I'd be willing to "invest" if that's the highest number that's actually guaranteed.

shabble2• 11 years ago

Is it a fair die? I'd be naturally suspicious of anyone offering me 'free money' in such a game.

But, assuming it was legit, presumably < E[x] = $3.50/game, assuming a decent number of games to average over. If it were a single game, I'm not entirely sure how I'd play - 3/6 outcomes result in losing money at $3.50, but where between $1 (always win - who would play against you?) and $6 (best reward, but -$5 potential loss) I guess that depends on your personal risk tolerance.

On your second point - I think I did originally misunderstand the question, and only on re-reading did it actually make sense. I hope I'd ask for clarification in an interview situation, or at least confirm my understanding is correct if it seemed off.

msane• 11 years ago

That's funny, and totally believable. Still a great question.

Speaking of economics fizzbuzz type interview questions can be understood in terms of risk. People second-guess themselves when asked simple questions which directly addresses their intelligence in the early interview phase because the stakes are suddenly total. The risk of answering a simple question incorrectly is disqualification.

z3t42• 11 years ago

I would say "Tell me more about that guy".

meragrin2• 11 years ago

The question is very misleading. There are very little details and you end with asking for an opinion. It sounds to me like a question about how much risk the person is willing to take rather than a math question. The "What are you willing to pay to play this game?" really needs to be replaced with something else. I would never associate this with a math question unless risk tolerance was included in the details. Any questions I might ask would not clue me into it being a math question either.

stordoff• 11 years ago

You have a dice (1-6). Some guy offers to pay you whatever you roll. What are you willing to pay to play this game?

The thing that would trip me up there is the "what are you willing to pay[?]" part. Instead of just interpreting it as "what is the EV of a fair six-sided die roll?", I start thinking about complicating factors immediately:

* utility function (I wouldn't pay the EV to play as I'd want to expect a profit - if you asked for the break even point/most you would be willing to pay, you would probably get a quicker answer)

* Why pay? He's already offered to pay me :p

* Do I know it is a fair die?

* How much money do I have?

* How many times will the guy pay out? Once, infinitely, or stop after some arbitary/unknown amount?

I'd hope that someone with a related degree would at least have a similar sort of discussion (or offer the EV as the answer initially then have some sort of discussion), but I can see why some people who 'should' know the answer might be tripped up by it.

lizard• 11 years ago

Over the years I've concluded it must be because the way it's asked. People think there's something deeper in it than the most straightforward explanation. Or maybe they think they missed some critical detail and are afraid to ask.

I like your conclusion and I think it's something anyone involved with hiring practices should think about more.

I don't know if I'm the type of person a hedge fund would be looking for, but I would freeze on that question: My first thought would be, I wouldn't be willing to pay to play the game with "some guy" at all. But knowing that's probably not what you're getting at, instead I'm going to have to look for a solution to a problem I've never encountered.

But it goes deeper than that: If someone were to walk up to me and offer to play the game I just could say "No, thanks." and life goes on, a simple and low stress life decision. In a job interview I may be desperate, or at least hopeful, for the job; no thanks isn't going to cut it. You may not realize it, or intend it, but your warm up is asking how I face new challenges in life. No pressure.

Since the situation is new and hypothetical I've also got to consider the hypothetical details. These hypothetical details can branch widely and deeply, reaching into both the hypothetical world you've prompted and the reality that I'm being evaluated without knowing what you are looking for. E.g. Is it a loaded die? That would mean the question is loaded so, no that's a silly question; unless that's exactly the kind of thinking you're looking for, in which case it's an essential question.

Further, I know you already know the answer, and the trick if there is one, so the question might seem simple to you and you might not understand why I don't also just get it (which you admit). This means bad starts and bad questions can make me look bad which I definitely don't want (So, yes, I think there may be a critical detailed I missed, and I'm afraid to ask).

This probably isn't how you or other interviewers intend for candidates to respond to questions. One solution is for candidates to work on "interviewing skills" and get better at provided simple, canned answers. This makes sense if these interviewing skills part of the job but otherwise, in my opinion, distracts from exploring the candidate's talents and doesn't really give a good sense of company fit.

Alternatively, the interviewer could make their intentions and expectations clear for the candidate. For example, send the candidates your warm up questions a week in advance to let them prepare for the interview. When they get there ask them what they came up with and then probe them with deeper questions that get at what you really want to learn. Those who worked on your problems will be better prepared to talk about it.

I would like to see interviews try to draw out the skills the candidates possess and determine if they would benefit the company, rather then being a Company Exam. This might mean letting the candidate actually work with the team on a small problem, or just providing guidance and feedback to help them feel more comfortable talking with you rather than feeding you answers. For example, step them through the original dice game and then ask them to consider the variations.

EDIT: Fixed typos.

JoeAltmaier7• 11 years ago

My sister's question was, how many Ping-Pong balls fit in a semi trailer? She would add no details. The idea was, could they function with limited info, make assumptions, come up with any answer at all. Most couldn't.

bobbytherobot2• 11 years ago

My follow up question if I was in that interview would be, "Is this how you operate, do you not provide critical information or am I a researcher?"

JoeAltmaier7• 11 years ago

Nobody gets all the info they need. You have to learn to operate by your wits. This was in a trucking/hauling company, with 1000's of people on the road responding to situations that changed constantly.

mikeash6• 11 years ago

My follow up to that follow up would be, it's 2015, internet access is ubiquitous, and if you can't find the dimensions of a standard ping pong ball and a standard semi trailer without having your hand held, then we don't need your services.

ianferrel• 11 years ago

This is basically just the "how many piano tuners are there in NYC" question rephrased.

The point is that someone talks through their thought process. The solution is to say, "Well, you need to know the volume of a ping pong ball, the volume of the trailer, and the packing density of spheres. Ping pong balls are a few centimeters across, 3 maybe?, so their volume is about..."

trevyn• 11 years ago

I really don't understand all the vitriol around these types of questions. Yes, rough estimation, sense of magnitude, and ability to apply basic math to solve problems are important real life skills, and very much prerequisites in an engineering discipline. If I asked you to estimate roughly how many thumbnail images would fit in the main memory of your smartphone, would that be a better question? You should also, as an engineer, understand that the ping-pong ball question is merely a different instantiation of the exact same base abstraction.

If you can answer the question easily, humor the interviewer and move on -- because lots of people can't. I actually find it kind of fun, because then you get to see how close you get.

Also, as you become promoted, being able to work autonomously with minimal supervision and incomplete information is indeed part of your job description. If I were hiring someone, I'd want someone with a solid growth trajectory.

hvs• 11 years ago

This also points to a situation that I sometimes find myself, where I try to be "clever" in solving a problem and, even if the solution works, is ultimately more confusing than the straightforward method. As I've maintained more code in my life, I've learned to shy away from being "clever", but it's always there in the back of my mind.

I think this is one of the challenges of functional programming as well. It allows you to be really clever, to the point of unintelligibility.

bobbytherobot2• 11 years ago

I've seen people fail questions for this reason. We even tell them not to go down a certain path, or not to worry about optimizing the solution. But they keep on trying to go down the clever path.

Sevzinn2• 11 years ago

The problem is ego. People don't act like the JSON that computers think like. An array in JSON can represent an unordered set, but people order it according to how they can become superior to others. People should be more like JSON.

MichaelGG3• 11 years ago

People should be more like JSON.

So needlessly verbose and unable to handle comments?

Oh, and unable to intrinsically distinguish dates from text, or real numbers from integers?

apalmer2• 11 years ago

This 'problem' with FizzBuzz is really a 'benefit'. I have seen it time and time again, incredible complex code by intelligent people attempting to chase an 'elegant' design.

Literally its my number one problem with senior developers where I work, refusal to leave working simple readable solutions alone.

chwahoo• 11 years ago

But as she points out, FizzBuzz doesn't do a good job in telling you if you've found one of these developers because the context of interviewing is different than the context of banging out code on the job.

buro92• 11 years ago

However, I have yet to see one that would actually be better in the real world than the simple, obvious solution.

Use counters, avoid modulo, and see a significant performance increase.

Computers suck at division, and FizzBuzz doesn't need division.

The solution is perhaps simpler than the obvious one as even a child could explain how it works.

https://gist.github.com/buro9/5345664#file-fizzbuzz-html

On my laptop, in Firefox:

Fast: 203ms

Slow: 844ms

thedufer• 11 years ago

That depends on how you're defining better. The slow one is somewhat more readable, and since your test runs a million times farther than the 100 that FizzBuzz usually asks for, you're looking at a gain of .6 μs. That's an interesting set of priorities, unless you know something about how often this code runs.

buro92• 11 years ago

I'm not sure anyone imagines running FizzBuzz in production. It is an interview tool only, first to determine whether the candidate can program, but which can also be used as a basis for some interview questions.

The counter example helps to answer whether the candidate understands how numbers are represented by computers and how addition and division function.

It also helps to answer whether a candidate knows what, in such trivial code, could (not must) be optimised were the value of n to increase insignificantly.

As you say, probing questions about how often the code runs, what the value of n is, or various other questions will all vary the answer. But to suggest that the priorities are wrong is a little silly, most interview questions are wrong to some definition.

blacksmythe• 11 years ago

  >> Use counters, avoid modulo,

That is also my solution (although I would use only two counters).

Having a background in hardware engineering and hardware optimization, using a modulo operation unnecessarily seems completely foreign to me.

jasode• 11 years ago

But the smart developer might just identify (intelligently) the potential for a "cool, elegant" solution and never find it. ... They think you want an elegant solution because the simple one is too obvious and it feels like there is an elegant solution.

I think this is the gist of the essay and it's very easily addressed by stating at the beginning, "just code something that works, don't try to come up with the most elegant thing known to mankind."

I don't see this as an issue in real life if some commmon-sense parameters are spelled out upfront. It's a 5-minute sanity check to get past false resumes. That's it.

I guess it's theoretically possible for an algorithms-obsessed programmer to sit there paralyzed for 2 hours on fizzbuzz. You the interviewer then ask him, "is there something about modulus 3 and 5 that's tripping you up?"

He says "Oh, not at all. I was just debating whether I should start with first principles of lambda calculus and have the program replicate itself in millions of successive genetic iterations until the final program writes itself. But then I got on a thought tangent and was thinking if I could just manually write list of the first 100 correct answers and then feed that to a machine learning algorithm that I write. It would classify the intervals and work backward via artificial intelligence to generate the right program. Btw, how much time do I get to work on this?"

I suppose scenarios like that could happen, but I don't worry about it.

hahamrfunnyguy• 11 years ago

Agreed. I was presented a simple challenge during an interview and my first question: Can I brute force the solution? Interviewer's answer: Sure, as long as it works.

I think if the developer doesn't know when to ask the right questions, it hints at a deeper problem.

chucksmash• 11 years ago

I've seen several projects already that were killed by very smart people doing exactly this, writ large. Maybe it's an uninspired view point but I don't think filtering out that hypothetical candidate is necessarily a bad thing either.

talmand4• 11 years ago

I once was doing something very similar to that until I realized it would be more efficient to manually write the sequence to 100 places on a piece of notebook paper instead.

vog• 11 years ago

Oh, not at all. I was just debating whether I should start with first principles of lambda calculus ...

Maybe this is not a false positive at all. Maybe you really shouldn't hire such a person.

If they blow up a simple test that much, what will they do when confronted with a real-world problem? Will they ever get anything done?

userbinator2• 11 years ago

I guess it's theoretically possible for an algorithms-obsessed programmer to sit there paralyzed for 2 hours on fizzbuzz.

In which case fizzbuzz has also served its purpose, by weeding out candidates who would overthink a solution and add gross complexity when it's not necessary.

arenaninja• 11 years ago

I agree. For any interview problem, my approach is to just write something that works. If you can't, talking it out loud helps whoever's interviewing know whether you're genuinely stuck or just fumbling with the keyboard

kstrauser4• 11 years ago

If you can't, talking it out loud helps whoever's interviewing know whether you're genuinely stuck or just fumbling with the keyboard

Absolutely! I'm also explicit about why I'm solving problems the way I am, like "this is going to be my brute force solution, and probably won't be pretty or efficient". This is effective against the occasional interview who does like to trip you up with followups like "wow, I was hoping for a more sophisticated answer" (yeah, you know who you are). I can respond with "as I said, this is a rough draft."

imron• 11 years ago

'The problem with using light grey text on a white background' would also make an excellent article topic.

MollyR• 11 years ago

Yea I don't know how I feel about this article. I know my team lead asks FizzBuzz to all new hires, and he's looking for elegance and robustness even in simple designs because when we work on our complex systems, it matters a lot for having a good code base.

Just the fact they think in terms larger than just the basic code is what I think he looks for.

kstenerud2• 11 years ago

The dumb (or lazy or new) developer will not notice or care about the appearance of a potential cool solution. They'll just bang out whatever works.

The pragmatic programmer (aka the person I want to hire) would also not care about the appearance of a potential cool solution, because experience teaches us that clever solutions tend to increase complexity and cognitive load, increasing not only the bug count, but also maintenance costs.

Yes, by all means be clever where it's warranted (strange constraints, bottlenecks, etc), but please not in regular code!

gharial• 11 years ago

I really couldn't follow his logic at all. Being able to come up with a working (perfectly correct) solution somehow implies a developer is probably "dumb" or "lazy"? As if a truly "smart" or gifted programmer would be unable to come up with a solution because they're just oh so intelligent and clever. You either know how loops work or you don't.

JoeAltmaier7• 11 years ago

Most smart programmers I know would prefer to product a good, or even the best, solution instead of any of the prosaic solutions. Unable to come up with a solution? Probably not. All the given examples are pedestrian. A really clever solution would recurse or search the web for a matching solution page or hash the solution space into a minimal table or something like that.

But agreed a proper programmer would never fail to produce a correct solution.

kelukelugames• 11 years ago

I can't wait for someone to ask me a fizz buzz question. I am going to write this out:

switch n case 1: case 2: print n case 3: print "fizz"

it's going to be so much fun.

henrikschroder2• 11 years ago

1) If you're doing FizzBuzz at an on-site interview, you've failed in your process. FizzBuzz is something you use as early as possible to weed out clearly incompetent developers.

2) I can see how a clever developer might get stuck in analysis paralysis, but even then you should be able to coax them out of it, and at least get them to write down a little bit of code that does a loop and an if statement, because that's what we're really checking: Can this individual write working code from scratch?

(And if you can't coax them out of it for this, how the hell are you going to be able to do the same for real problems?)

talmand4• 11 years ago

But how do you administer something FizzBuzz outside of an on-site interview? How do you know they actually completed the task without being with them when they did?

I'm guessing Skype interview or something similar?

henrikschroder2• 11 years ago

I'm using a simple shared editor such as collabedit or similar. You send the link to the shared space along with the phone number for the interview, and you let the candidate know that there will be some simple shared exercises so they need to be at a computer.

And then you ask your questions, and do FizzBuzz or similar, and watch them code.

kstrauser4• 11 years ago

If I interview you, you're getting FizzBuzz. I also lay down some ground rules:

- Write it in the language of your choice. It's OK if I don't know that language but be prepared to explain unfamiliar stuff to me.

- I am not a compiler and I don't care about semicolons, misspellings, etc. as long as I can understand the point of the code.

- There aren't any tricks. This is the whole problem.

I do not say anything like "keep it simple" because that can kick candidates into "OH GOD THERE MUST BE A ONE-LINER AND I CAN'T SEE IT" mode. My goal is to make the candidate as comfortable as possible in a potentially stressful situation. I want to give them every chance to succeed.

I've seen people with 10 years as a lead engineer fail horribly. I've seen people blanch at the concept of loops. Loops! The most common failure mode I've seen is for candidates to start throwing in lots of state variables like "is_divisible_by_3" and "has_printed_the_word_fizz", even after I prompt them toward using "else if" or nested if statements.

One guy laughed and said, "I've done this 100 times. Do I really have to?" I laughed, too, and replied "OK, just tell me what you'd do." He spat out some pseudocode that would've worked, I apologized and explained why I make everyone do this, and we swapped funny stories. My company made an offer that day, he accepted, and is still successful in that role.

I've also had people complain that this is beneath them. Too bad. You're asking us to pay 6 figures for your programming skills? Then be prepared to spend 5 minutes demonstrating them. Your GitHub repo may be a clone of other peoples' work for all I know. I can and have ended interviews with candidates who dig in their heels and won't cooperate.

jknipp• 11 years ago

I've started including a small variation of FizzBuzz as part of our developer screening test - varied so you can't copy and paste from google. Very loose guidelines, pick your language, access to the internet, etc. We even give a general outline of what will be tested 24 hours out, and no hard time limit.

3 out of 4 people so far were unable to do the test. One guy boasted 20+ years of development experience and I used to work with him, he didn't even attempt it?!? Frankly, I expect candidates of any worth to feel insulted we are asking them to write this. The guy that did complete it wrote it in Bash, and wasn't strong in that to begin with. Bonus points for learning a language on the fly, that's what I'm looking for.

kstrauser4• 11 years ago

That matches my experiences. The first time I heard of FizzBuzz, I laughed it off as ridiculously easy and not worthwhile for screening. I've since changed my mind.

If a candidate laughs and writes down a canned answer off the top of their head, I count it as "passed" and we move on to other questions. I've been horrified at how often it's been a show-stopper, though.

The guy that did complete it wrote it in Bash, and wasn't strong in that to begin with. Bonus points for learning a language on the fly, that's what I'm looking for.

I'd give that a double thumbs-up for resourcefulness.

ilitirit2• 11 years ago

I did an experiment while interviewing interns once. For half the group, I posed this problem:

Given a log file, with each line prefixed with either WARN, INFO, ERROR or DEBUG, explain briefly how you would determine the number of errors logged assuming that each line corresponds to a single event and vice versa.

For the other half, I posed the same question, but I said the log file was 50MB big. Most people didn't know how to solve the second problem even though given the scales involved the solution is essentially the same.

(By the way, the question wasn't used as part of the criteria for the job)

imaginenore• 11 years ago

No, the solution is not the same. The 50MB one is easier, as it fits in RAM and we know none of the counts exceed 25 million.

With the first one we don't even know if the counts fit into the standard numeric types.

MichaelGG3• 11 years ago

Considering how easy it is to get a linear implementation, why would anyone choose to use a slower method?

TheLoneWolfling4• 11 years ago

Those two are not equivalent. Actually, I'm surprised that people didn't find the first one harder: I've had log files that were larger than RAM before (mainly due to overzealous logging).

userbinator2• 11 years ago

If the first thing your solution does is attempt to read the entire file into memory, then you probably failed the test. The same goes for trying to read an entire line into memory, however long it may be - this is a problem that can be solved with an essentially constant space of around a dozen bytes.

kstrauser4• 11 years ago

Exactly! I've been asked the followup question: "now assume that you have 8 petabytes of log files to search", which leads into distributed computing, realtime vs on-demand collection, eventually consistent counters, the pros and cons of sampling vs exact counts, and so on.

The unbounded form of that question can be astonishingly hard, and for the kinds of jobs I'd be interviewing for I'd expect the challenging next questions.

I'd still answer along the lines of "for a quick solution I'd grep for the error level and count the number of lines, but that's not scalable".

ColinWright3• 11 years ago

So:

    $ grep ^ERROR | wc

wtetzner2• 11 years ago

    $ grep ^ERROR | wc -l

zimpenfish• 11 years ago

Or if you want to avoid a useless use of wc -

    $ grep -c ^ERROR

ilitirit2• 11 years ago

The people who are replying and saying these problems are not the same because of the file size are are seeing the same type of illusion of complexity described in the submission. You count the number of lines you that begin with the word ERROR. That's it. At this scale, the tools you use are, for all intents and purposes, irrelevant.

Saying that the files might not fit into standard numeric types is like writing a custom BigNum implementation when I ask you to write a program that adds two numbers because I might give you value that doesn't fit into an int. It's of course fine to raise it as a potential issue, which would also show you know the practical implications. But what about if I ask you to write FizzBuzz? Are you going to give me the simple answer, or write something needlessly complex because I might test your program with a value like -3x10^78?

Perhaps I should have been clearer that the interns were fresh out of college, or part of a placement program, and that the rest of the interview wasn't technically challenging for anyone with real-world programming experience.

In my case, nearly everyone who struggled with the second question told me they thought there was some significance behind the file size and that made them avoid the obvious answer.

brudgers3• 11 years ago

Internationalization suggests that "Fizz" and "Buzz" be parameterized...and maybe we shouldn't hard code "3" and since magic numbers aren't good practice either...and the possibility of a different search function for the "FizzBuzz" suggests parameterizing that value, too.

Which is to say that one of the problems with FizzBuzz is that the interviewer doesn't take it seriously enough to care about engineering practice at the level that matters. If they did, FizzBuzz would come with a test suite.

jameshart2• 11 years ago

So if you're asked to do fizzbuzz in an interview, feel free to bring these things up. Just don't make it seem like you're looking for excuses not to write code.

If you approach fizzbuzz by saying 'okay, so you want me to write a program that generates this sequence on demand - otherwise we could just precalculate all 100 values - so I'm going to assume that you want something parameterizable. How about we make it take a dictionary of factors that map to certain keywords, and we take { 3: "Fizz", 5: "Buzz" } as an initial testcase?' I'm going to go along with that, so long as the code you write actually works. I might walk you back from internationalizing the output, but points for mentioning it.

TheLoneWolfling4• 11 years ago

That better be an ordered map, there.

brudgers3• 11 years ago

FizzBuzz suffers from the StackOverflow fastest fingers on the internet problem, it favors cursory poorly engineered solutions. By which I mean what is FizzBuzz supposed to do if IO blocks because stdout got redirected to a resource that's not available?

When the code the interviewer wants to see has IO operations spaghettied throughout the business logic rather than separated as a concern, is the exercise selecting for people who are perfectly willing to do only what is asked rather than what is needed?

How many lines of code would FizzBuzz really be if we were serious about it as Engineers?

z3t42• 11 years ago

I think every programmer goes through the "smart" stage, where you start to get confident and write "clever" solutions for simple problems. Where you will hopefully transcend to writing simple solutions for hard problems.

Personally I hate stupid tests like these, just give me a real life problem that you are currently working on ...

Here's my fizzbuzz solution: https://github.com/Z3TA/fizzbuzz/blob/master/fizzbuzz.js

And here's my favorite one, on how it would look like if implemented like most "enterprise code" looks like: https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...

sopooneo• 11 years ago

Out of curiousity, what is an elegant solution for her problem of finding out what year had the most people alive? I can think of a couple brute force methods, but I've not been able to phrase the question properly to find an ideal solution on Google.

gaylemcd2• 11 years ago

Here's a solution that takes O(P + R) time, where P is the number of people and R is the total range of birth years.

First, notice that you don't really care who died when. All that matters is someone died. People's birth and death years are fungible, in a sense. Each birth increases the population by one and each death increases the population by one.

Basically, you'll create an array where the value at each index represents how much the population changed in that year (steps 1 to 3). Then you can use that array to find the highest population (step 4).

1. Get the min birth year and the max birth year.

2. Create an array where the size is the above range. Set to all zeros. Each index will map to / represent a year in the range.

3. Loop through all the people. For each person, increment the index of their birth year and decrement their death year (or the following year, depending on whether or not they're counted as alive the entire year of their death)

4. Just loop through the array, tracking the running sum at each index. The biggest running sum will indicate the highest population.

There are some other good solutions depending on what assumptions you make about P and R's relative size.

TheLoneWolfling4• 11 years ago

Hmm...

If you sort everyone's births and deaths you can just walk through the array keeping track of the number of people alive at each point and the maximum number of people alive at any point (and the year(s) thereof).

O(P log P) (from the sort), no explicit dependance on R. Are there any other good solutions? I cannot imagine that there would be anything that's sublinear in P, so about the only other thing I could imagine would be something that is linear in P and sublinear in R.

dlandis• 11 years ago

In my experience after reading her book and some of her articles I think Gayle (and many other interviewers) underestimates the effect nerves have on certain people. She may be a little too quick to classify certain people as "dumb" when, in fact, some people's brains just totally freeze up during traditional coding interviews. I suspect more outgoing, extroverted people have a hard time fathoming what that's like or even that it is possible.

The Problem with the FizzBuzz Problem

Related Stories