CS301: Intro to V--
December 3, 2014 3:39 PM   Subscribe

This particular solution to the Fizz Buzz problem is entertaining enough. Further reflection shows that it's actually an example of the Vogon programming language V--.
posted by Fezboy! (140 comments total) 25 users marked this as a favorite
 
Remember, it's not what you know, but who you know.
posted by oceanjesse at 3:48 PM on December 3, 2014 [1 favorite]


I'm trying to figure out what that candidate must have heard to go in that direction. I can only imagine there was some sort of major communication breakdown. Perhaps a language barrier?
posted by lucasks at 3:50 PM on December 3, 2014


I... don't think the interviewee actually exists? Or, dare I say, Matteo either. I think this falls in the long tradition of Software Tall Tales.
posted by muddgirl at 3:54 PM on December 3, 2014 [5 favorites]


While the criticism is misplaced, that's kind of a roundabout solution anyway, and I'm pretty sure it doesn't compile cleanly. I don't think I would have hired him.
posted by vogon_poet at 3:59 PM on December 3, 2014 [19 favorites]


Execute, I implore thee, my foonting turlingcodes,
And hooptiously compile with crinkly bindlewurdles,
Or I will rend thee in the gobberboards
With my diodecruncheon, see if I don't!

I'll show myself out the airlock, now
posted by Greg_Ace at 3:59 PM on December 3, 2014 [22 favorites]


I'd at least be entertained by that solution. And at least s/he knew what a loop was. That puts them ahead of a few of the candidates who showed up at a recruitment event a few weeks ago.
posted by octothorpe at 4:00 PM on December 3, 2014


@muddgirl: I have interviewed candidates with years of experience in the industry that claimed extensive linux kernel development and who couldn't construct a proper for-loop. I believe it.
posted by lucasks at 4:00 PM on December 3, 2014 [2 favorites]


The answer provided is not threat safe - an important consideration in Vogon code.
posted by parki at 4:01 PM on December 3, 2014 [13 favorites]


For other examples of Software Tall Tales (I wish I could put that in Marquee), check out Remy Porter's other articles. I'm quite enjoying the sad tale of Citizen Blaine.
posted by muddgirl at 4:01 PM on December 3, 2014 [2 favorites]


Why do we only hear these stories about software engineers? I assume there are just as many uninformed people apply to Mechanical Engineering or Electrical Engineering positions. Is it just that software devs are overrepresented on the internet? Are they the only ones who ask this sort of correct/incorrect interview questions?
posted by hermanubis at 4:12 PM on December 3, 2014


The job I'm currently in required me to solve fizzbuzz in the interview. I solved it just fine, but in the next question I stumbled horribly over something literally day 1 fundamental to my particular skill set (I could not remember how to use a hash). Interviews are crazy nerve-racking, especially when they are done online while they listen to dead air over the phone as you type.

That said, I was surprised to learn from my now supervisor that most people they interview either fail fizzbuzz or deliver an incredibly complicated solution.
posted by mcstayinskool at 4:15 PM on December 3, 2014 [3 favorites]


I think this falls in the long tradition of Software Tall Tales.

Would that it were true. We interviewed a fair number of nuts at my last job in just two rounds of interviewing. A few highlights:
  • The recent college grad whose entire experience was working for his dad who was a consultant. Fine, no problem, except the answer to literally every question was, "I'd have to ask my dad." I'm not sure he knew his own name.
  • The Oracle consultant with an amazing resume who turned out to be a dude who Oracle sent to potential clients with a paper checklist on a clipboard.
  • I started using a subset of Steve Yegge's interview questions. One of them literally only required you to say, "I'd use a regular expression". It seemed like the easiest question in the world, but by the 4th or 5th time I asked it I was ready to make love to anyone who came near the syllables. One guy (may have been the Oracle fellow) refused to accept the premise of my question and insisted the phone numbers we were trying to replace had to be in an HTML table (we'd made the move to XHTML and CSS a year or two before so this was doubly offensive) and even when I suggested some of the files were PDFs, not HTML, held onto his faith in tables to solve the problem.
posted by yerfatma at 4:35 PM on December 3, 2014 [7 favorites]


That said, I was surprised to learn from my now supervisor that most people they interview either fail fizzbuzz or deliver an incredibly complicated solution.

I hear the same thing from friends in the web app industry. Shocking, yet somehow common.
posted by indubitable at 4:48 PM on December 3, 2014 [1 favorite]


I didn't mean to imply that the story was unbelievable. Believability and universality are the center of any good Software Tall Tale.
posted by muddgirl at 4:49 PM on December 3, 2014


"I'd use a regular expression"

And now you have two problems.

I have had co-workers attempt to parse HTML with regular expressions. They were not on my project, so I said nothing (I was in an evil mood).

I have done poorly in interviews and have witnessed spectacular meltdowns in interviews. I could, potentially, see something like this come out of one. We just hired someone who, apparently, had an appallingly hard time writing a bubble sort in an interview, but when I asked him to discuss the finer details of the web-scraper and text-indexer he built for a school project, he did wonderfully. I hope he works out...
posted by combinatorial explosion at 4:49 PM on December 3, 2014 [1 favorite]


Is one not allowed to use modulo in solving fizzbuzz? Otherwise I’m having a hard time understanding how this is a challenge, and I’m not even really a coder.
posted by El Mariachi at 4:54 PM on December 3, 2014 [1 favorite]


Oh, and I love Enterprise FizzBuzz: "FizzBuzz Enterprise Edition is a no-nonsense implementation of FizzBuzz made by a serious businessman for serious business purposes.". I'm tempted to make a JEE 6/7 version - if only to show the 'proper' patterns for doing this with CDI...
posted by combinatorial explosion at 4:54 PM on December 3, 2014 [9 favorites]


Fizzbuzz isn't supposed to be a "challenge," it's supposed to make sure that you have a basic understanding of what a program is. A lot of people who go through introduction-to-programming courses can tell you what a modulus is if you show it to them but are unable to use them to solve novel problems.
posted by LogicalDash at 5:05 PM on December 3, 2014 [7 favorites]


Is one not allowed to use modulo in solving fizzbuzz?
No, that's basically the idea/expected outcome.
Yes, the idea that it's a challenge is mystifying. And yet, somehow it'll solidly weed out many, many people.
posted by CrystalDave at 5:05 PM on December 3, 2014 [2 favorites]


There was a guy hired at a previous position (I didn't interview him) who was promptly given a senior role and slotted in as the head of a team. (What? Who does that?) A couple of months later, a respected colleague came to me and said, "sonic meat machine, could you look at this code repository and tell me what you think?"

Upon looking at the only check-in in the svn repo, my only response was: "What the fuck?" There was literally no sense in the code; it was as if someone who hadn't even the barest idea of how to begin had been writing code. And yet this goon was sitting in meetings and spouting bullshit with supreme self-confidence. It was bizarre.

I believe pretty much any software "tall tale" propter hoc.
posted by sonic meat machine at 5:07 PM on December 3, 2014 [9 favorites]


In the one interview where I was asked to fizzbuzz, I used floor() instead of modulo().

I remain ashamed.
posted by 256 at 5:11 PM on December 3, 2014


> I have had co-workers attempt to parse HTML with regular expressions. They were not on my project, so I said nothing (I was in an evil mood).

Sure, except the thing yerfatma was talking about was just a simple problem that didn't involve parsing HTML — just looking for a phone-number-type pattern within a bunch of HTML files. Sometimes a regular expression is actually the answer.
posted by savetheclocktower at 5:12 PM on December 3, 2014 [3 favorites]


Why do we only hear these stories about software engineers?

Because for better or worse a) you don't need a formal education in software to work as a programmer and b) a lot of people somehow manage to make it out of CS programs without learning how to program.

Software engineers also tend to get thrown into the deep end straight away whereas civil and mechanical engineers are given escalating responsibilities and have to prove their competence on the job before they have license to mess things up.

Finally too few software shops do real code reviews whereas a mechanical or civil engineer will have her work reviewed ten ways to Sunday before anything happens.
posted by GuyZero at 5:17 PM on December 3, 2014 [12 favorites]


Surely the most efficient thing to do is unroll the loop and just keep incrementing "i" while outputting i, i, "fizz", i, "buzz" ... "fizzbuzz". Then you repeat. No comparisons necessary.

It wouldn't parallelise well, mind.
posted by Joe in Australia at 5:21 PM on December 3, 2014 [3 favorites]


print "1"
print "2"
print "fizz"
print "4"
print "buzz"
print "fizz"
print "7"
print "8"
print "fizz"
print "buzz"
print "11"
print "fizz"
print "13"
print "14"
print "fizzbuzz"
...

Am I hired?
posted by 256 at 5:24 PM on December 3, 2014 [5 favorites]


Psh. That doesn't follow any of the GoF patterns.
posted by LoopyG at 5:27 PM on December 3, 2014


Yes, but you need a program to generate those lines and keep adding them to a file, while another process reads the file and executes each line. The best bit is that if you find an error you can go back at any time and check the statement that produced the incorrect result.
posted by Joe in Australia at 5:27 PM on December 3, 2014


Sure, except the thing yerfatma was talking about was just a simple problem that didn't involve parsing HTML — just looking for a phone-number-type pattern within a bunch of HTML files. Sometimes a regular expression is actually the answer.

I agree - regular expressions are a useful, powerful tool. The danger relies on leaning on them too heavily. What happens when you need to find more than one format of phone number? It can become a very slippery slope that one day ends in crushing the soul of some developer tasked with adding a new format/new feature to something that is... less than readable. The same can be said about databases and embedded SQL logic (it starts with a view here and there, then a bit of script, and then 9/10ths of the application logic is somehow buried deep in a database). The trick is in knowing when to stop. Which, I suppose, is true of many software projects.
posted by combinatorial explosion at 5:34 PM on December 3, 2014 [4 favorites]


I started using a subset of Steve Yegge's interview questions. One of them literally only required you to say, "I'd use a regular expression". It seemed like the easiest question in the world, but by the 4th or 5th time I asked it I was ready to make love to anyone who came near the syllables.

Oh man, I once had a phone interview with someone applying for a developer role, but whose entire professional experience must have been loading files to SQL server. I asked the phone number question and as with everything else I asked, the answer was:
"I would use an ETL process to load the files to SQL server and do an UPDATE to change the phone numbers!"

"...er, OK, but suppose there were a million separate and totally unstructured text files scattered throughout a directory hierarchy? They're not necessarily CSV or XML files or anything like that."

"I would use an ETL process..."
posted by Blue Jello Elf at 5:40 PM on December 3, 2014 [3 favorites]


The sad thing is the static solution is better than what a lot of people interviewing for programmer work will give you. There are people interviewing who for real cannot listen to a description of a one-line program and then write it.

My favourite resume I had to read was from the person who was 'skilled in assassin requirements'. It could have been a spell-check failure for assessing, but who knows, maybe they were an actual hitwoman.
posted by xiw at 5:41 PM on December 3, 2014 [5 favorites]


Joe in Australia's solution is mine too. Resist the inclination to add layers of indirection!
posted by Sportswriters at 5:52 PM on December 3, 2014 [1 favorite]


Surely the most efficient thing to do is unroll the loop and just keep incrementing "i" while outputting i, i, "fizz", i, "buzz" ... "fizzbuzz". Then you repeat. No comparisons necessary.

This is a solution which occurs to people who understand "least common multiples", which is like a fraction of 1% of people.
posted by Wolfdog at 6:10 PM on December 3, 2014 [1 favorite]


The most self assured applicants always exclaim the answer as if it was wizardry.

"I would T-SQL the Interface into the SCSI!"
posted by benzenedream at 6:12 PM on December 3, 2014 [1 favorite]


Not a big fraction, by the way.
posted by Wolfdog at 6:14 PM on December 3, 2014


benzenedream: The most self assured applicants always exclaim the answer as if it was wizardry.

"I would T-SQL the Interface into the SCSI!"


Truth be told, who here among us hasn't T-SQLed the Interface into the SCSI?

Be honest. ;^)
posted by surazal at 6:14 PM on December 3, 2014 [3 favorites]


I once had a student in Introduction to Computer Science who mostly did his homework on LSD (yes, he told me this).

One exam had him write a function in Python.

He drew an extremely vivid, full-page picture of a python.

I wonder where he is now.
posted by miyabo at 6:19 PM on December 3, 2014 [29 favorites]


I worked through this exercise once on the advice of a friend who's a recruiter, when I was briefly flirting with the idea of looking for a gig in a healthier market. It was really silly easy--especially if you've ever used the modulus function before--so much so I couldn't believe there wasn't some hidden catch. In real life, there almost always is... Anyway, easy as it was, might have been harder if I'd had to sit with someone watching me work, as I can go painfully self-conscious now and then, but it's not exactly bleeding edge CS or anything.

(People really don't know how to use For loops? Unless you mean they don't know the syntax by heart in five different languages, I find that really hard to believe. But then, it's sometimes a bit of a luxury to get to work with technologies you actually have previous experience with in the wild these days. Whatever you do, don't get a reputation for being able to learn new technologies quickly under pressure. It's not worth the psychological toll, because once you're that guy, you never get a break.)
posted by saulgoodman at 6:37 PM on December 3, 2014 [1 favorite]


My personal favourite variation on fizzbuzz for shell scripting (particularly for candidates who may have seen it before) is to implement it using bash without using if, while, or case
posted by namewithoutwords at 6:43 PM on December 3, 2014 [1 favorite]


dd if=/dev/fizzbuzz count=100 bs=...

...um, wait, it'll come to me
posted by George_Spiggott at 6:45 PM on December 3, 2014 [3 favorites]


I have had co-workers attempt to parse HTML with regular expressions. They were not on my project, so I said nothing (I was in an evil mood).

DO NOT PARSE HTML WITH REGULAR EXPRESSIONS
posted by Itaxpica at 7:00 PM on December 3, 2014 [18 favorites]


My first whiteboard Java question for interviewees is "Write a method that prints every element of a List to standard output on its own line." I even give them the method signature:
public static void printListElements(List<String> list) {
  // code here
}
What's more, I'll tell them about System.out.println(...), if they don't know about it. I'll accept array syntax (e.g. referencing "list[i]" despite the fact that list is not an array, or using "list.length" instead of "list.size()").

I'm really very tolerant of their code. I tell them I don't care about semantically meaningless mistakes that the compiler would have caught, and I mean it.

This is a far, far easier problem than FizzBuzz. And so yeah, almost every interviewee comes up with a more-or-less correct solution.¹ So why ask it?

Here's the problem with FizzBuzz: most programmers never, or almost never, use the modulo operator. Those that do almost always use it to check if a number is even (mod 2). Other than that case, most programming jobs just don't have occasion to measure indices in a sequence to see if they're multiples of n.

I genuinely forgive candidates if they don't understand the function of the modulo operator. They don't need it, they might need the brain real estate for something else, so evict it! That's an admirable trait.

That's why I ask a question simpler than FizzBuzz. I don't want to know if they understand the modulo operator. And I don't want them to solve a trivial problem on a whiteboard. Whiteboard coding sucks and is a terrible measure of actual coding skill (and fancier methods using laptops or collaborative coding sites are only slightly better).

So their simple, "gimme" implementation is just the starting point. It gets some code on the board, then we can start talking the real shit. I ask them questions about real-world situations (often framed as bug reports):
"You get a bug report that users are seeing a NullPointerException, and it references this method. What might be the problem?
Most candidates will suggest that one of the list elements might be null. This isn't correct (System.out.println is null-tolerant), but it's at least along the right lines. I can eventually convince most candidates that the list parameter itself may be null, and then I ask them what they're going to do about it.

Of the candidates that know how to check whether a variable is null, most will try to do something like this:
public static void printListElements(List<String> list) {
  if (list == null) {
    System.out.println("List was null!");
  }
  // ...
}
This is frustrating, because then I have to pose a scenario: what if the list consists of a single String, "List was null!"? How useful is the error, if it can't be distinguished from the correct output?

What I really want is some precondition checking, to rethrow an IllegalArgumentException or (yes) a NullPointerException if the argument is null. Better to identify it at the source.

Moving on... now that they have some error checking, and I've fixed the meaningless syntax issues, I talk to them about performance. At this point, most implementations look like this:
public static void printListElements(List<String> list) {
  if (list == null) {
    throw new IllegalArgumentException();
  }
  for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
  }
}
I don't expect everyone to know big-O notation, but if they have a CS degree I'll ask if they're familiar with it. I ask them what the performance characteristics of their implementation are. Most people will say that it's O(N), or a layman-equivalent description of that. Then I ask them what happens if list is actually a java.util.LinkedList, where the get(...) method is itself O(N). A lot of people can't figure out the implications, and still think the whole thing is O(N).

Honestly, I wish I didn't have to ask this. The "foreach" syntax has been in Java for over a decade, and even if they were unfortunate enough to be on JDK < 1.4 for their projects they should at least understand the concept. Replacing the above with the following:
public static void printListElements(List<String> list) {
  if (list == null) {
    throw new IllegalArgumentException();
  }
  for (String str : list) {
    System.out.println(str);
  }
}
...is much more readable and is O(N) for any non-absurd List implementations.

I hope you get what I'm getting at, here. I honestly don't care about some things that are ostensibly fundamental to software development (e.g. modulo, or bitwise operators). But I do need to be able to talk to you about what is good practice, what is bad practice, and why one is distinct from the other. That discussion relies on a common vocabulary that's even more rudimentary than what's tested by FizzBuzz, and so I try to keep it to that simpler level.

And most of all, I need to be able to see how you react to the ugliness of real-world software development, where you get bug reports that (if you're lucky) are only as specific as "your method returns a NullPointerException".



¹ Appallingly, some candidates still fucking fail the "print everything in the list" problem. I actually have some perverse sympathy for that level of incompetence, because I've been at consulting jobs where there wasn't any coding work for me despite me having been contracted for coding work and my active, repeated requests for something to do.

This is why I'm permanently poisoned against using outside consulting firms; their incentive is to keep getting paid, not to solve your problem.

However, even if your current programming job doesn't require you to know programming, you should at least have enough respect to refresh yourself about the basics when you're seeking a new job.

posted by Riki tiki at 7:31 PM on December 3, 2014 [25 favorites]


in bash without if? - the easiest way I can think of is to make it some other program's problem, then..
x=0		# loop starts at 1 due to increment placement
stop=100

until [ "${x}" -eq "${stop}" ] ; do
  ((++x))
  let n=${x}%5 ; let z=${x}%3 ; nz="${n}${z}"
  echo $nz | grep -q 0 || echo -n "${x}"
  echo $nz | grep -qv 0 || nz=${nz/#0/buzz} ; nz=${nz/%0/fizz} ; nz=${nz//[0-9]} ; echo -n "${nz}" 
  echo ""
done
posted by arrjay at 7:35 PM on December 3, 2014 [1 favorite]


Goofy no-mod python version
threes = [x*3 for x in range(34)]
fives = [x*5 for x in range(21)]

for i in range(1, 101):
	if i in threes and i in fives:
		print 'fizzbuzz'
	elif i in threes:
		print 'fizz'
	elif i in fives:
		print 'buzz'
	else:
		print i
posted by a dangerous ruin at 7:39 PM on December 3, 2014 [4 favorites]


arrjay: "in bash without if? - the easiest way I can think of is to make it some other program's problem,"

thanks for that, I'll need to remember to include "no pipes or external programs allowed" the next time I'm trying to stump someone on this.</derail> :-)
posted by namewithoutwords at 7:56 PM on December 3, 2014 [1 favorite]


Yeah, Riki tiki's right: I've only ever needed modulo professionally to test for evens over 12+ years of professional coding. By the way, Im thinking of suggesting something like your test in my office, Riki tiki, for our candidate technical evaluation process. We seem to struggle with that exercise a little, like everybody these days, though to be fair, we're usually a little stretched for time.
posted by saulgoodman at 8:02 PM on December 3, 2014


For bash you could use "seq" to make lists incrementing by 3s and 5s and do something somewhat like the goofy python version above
posted by RustyBrooks at 8:03 PM on December 3, 2014


I just spent a week cleaning up perl code left by a former employee and far worse than people who can't code at all is people who can, but don't comment, test, use source control or do anything else that differentiates professionals from hackers.

It would have been easier to re-write the thing from scratch, but I basically had get it mostly working before I could even figure out what the hell it was supposed to be doing.
posted by empath at 8:12 PM on December 3, 2014 [2 favorites]


During the time when everybody was talking Design Patterns - if it was on their resume I would ask the candidate for a whiteboard sketch of singleton - that was always pretty enlightening. It's a good discussion topic - you can talk about static variables, classes vs. objects, private vs. public, inheritance, thread safety, use of globals, etc.
posted by parki at 8:14 PM on December 3, 2014 [1 favorite]


Riki tiki: that's a fantastic interview question.

I do think you're being a little hard on FizzBuzz though. If a candidate doesn't know or remember the modulo operator, that's fine. If they can't come up with another way of determining whether x is a multiple of y, that's a big red flag.
posted by ripley_ at 8:28 PM on December 3, 2014 [5 favorites]


There's really no need for the strings "fizz" or "buzz" to appear more than once in the source for any valid solution.
posted by invitapriore at 8:43 PM on December 3, 2014 [2 favorites]


Also, as an interviewer, I would want a testable implementation of fizzbuzz. To that extent, any IO performed should be abstracted behind a helper function or class that we receive via dependency injection so that we could pass in a mock that verifies that it's been called with the appropriate output strings.

I miss Ad hominem...
posted by invitapriore at 8:46 PM on December 3, 2014


threes = [x*3 for x in range(34)]

You probably want

threes = range(3,101,3)

Etc. It spares you coming up with the magic number up front and the interpreted calculation.
posted by George_Spiggott at 9:09 PM on December 3, 2014


If they can't come up with another way of determining whether x is a multiple of y, that's a big red flag.

Definitely. A set of "FizzBuzz" questions with increasingly weird restrictions like "no modulo allowed" or "no iterative loops", etc, would actually be a fun little set of problems.

Well, to work on at home, anyway. I am a not-terrible programmer, but whiteboarding makes me freeze up and become useless. I think a really good in-person whiteboard-interview tutor could probably do pretty well for themselves coaching currently employed programmers who suck at it and need to move jobs!
posted by Jon Mitchell at 9:10 PM on December 3, 2014 [3 favorites]


I do hate the fashionable interview practices, but given the apparent number of charlatans out there trying to pass themselves off as programmers I guess most outfits have no choice.

My advice for people who get jammed up on whiteboard tests is that the old-fashioned "the simplest thing that could possibly work" is almost always the best bet. That's what people who've seen the elephant, to borrow a phrase, will want to see. Fancy "just take the bitwise-or of the logarithm of the hypotenuse" code rarely belongs in production systems.
posted by ob1quixote at 9:41 PM on December 3, 2014 [1 favorite]


this thread makes me feel like I should get paid more.
posted by scose at 10:04 PM on December 3, 2014 [9 favorites]


Riki tiki: it's funny, I wind up doing something extremely similar for prospective Scala candidates-- ask them to write an iterator function in Java, talk them through the null check, talk them through an empty list, I even ask them about thread safety-- what happens if their list is changed by another thread, etc:
public List<Person> voters(List<Person> people) {
  ArrayList<Person> voters = new ArrayList<Person>();
  if (people != null) {
    synchronized(people) {
      for (Person p: people) {
        if (p.age >= 18) {
          voters.add(p);
        }
      }
    }
  }
  return voters;
}
then I show them the equivalent function in Scala:

def voters(people: List[Person]) = people.filter(_.age >= 18)

Judging their reaction is at least 50% of whether or not they get hired.
posted by mark242 at 10:09 PM on December 3, 2014 [5 favorites]


My personal favourite variation on fizzbuzz for shell scripting (particularly for candidates who may have seen it before) is to implement it using bash without using if, while, or case
for x in {1..100}
do
  ([ $(($x%15)) -eq 0 ] && echo FizzBuzz ) || \
  ([ $(($x%3)) -eq 0 ] && echo Fizz ) || \
  ([ $(($x%5)) -eq 0 ] && echo Buzz ) || \
  echo $x
done
(note, Bash3/KSH93 compliant, otherwise, use jot or seq instead of the {1.100})

Basically, it's using the Command And (&&) and Command Or (||) construct. Command And says "If this command returns zero, run the next command" and Command Or says "If the first command returns anything but 0, run the next command"

While using the || repeatedly is really building a case with a break after each statement and a fall through of echoing the number, it never actually uses the "case" command.

Having done that, don't do that sort of thing in the real world, because "if-then" is a vastly clearer construct. :-) Remember: Write like a stupider person has to work on your code after you are dead.
posted by eriko at 10:12 PM on December 3, 2014 [3 favorites]


Watching the approach someone takes to solve The Velociraptor Problem may or may not be any better than FizzBuzz as a screening tool, but it's a lot more entertaining.

A fair number of people will basically reinvent polar coordinates from first principles in the course of figuring it out.
posted by Kadin2048 at 11:22 PM on December 3, 2014 [2 favorites]



for i in {1..100}; do
  f=$((!($i%3)))
  b=$((!($i%5)))
  [[ $f -eq 1 ]] && echo -n fizz
  [[ $b -eq 1 ]] && echo -n buzz
  [[ $((!($f|$b))) -eq 1 ]] && echo -n $i
  echo
done

# mostly tranlated from the Perl
for(1..100){$f=!($_%3);$b=!($_%5);$f&&print"fizz";$b&&print"buzz";!($f|$b)&&print;print"\n"}
posted by zengargoyle at 12:16 AM on December 4, 2014


I bet you this is faster than most of your solutions:

10 X=0
20 X = X+1; PRINT X
30 X = X+1; PRINT X
40 X = X+1; PRINT "FIZZ"
50 X = X+1; PRINT X
60 X = X+1; PRINT "BUZZ"
70 X = X+1; PRINT "FIZZ"
80 X = X+1; PRINT X
90 X = X+1; PRINT X
100 X = X+1; PRINT "FIZZ"
110 X = X+1; PRINT "BUZZ"
120 X = X+1; PRINT X
130 X = X+1; PRINT "FIZZ"
140 X = X+1; PRINT X
150 X = X+1; PRINT X
160 X = X+1; PRINT "FIZZBUZZ"
170 GOTO 20
180 REM APPLE ][ 4EVA
posted by Joe in Australia at 1:20 AM on December 4, 2014 [16 favorites]


I have sinned: I once wrote a large(ish) perl script which parsed HTML (well, HTMLish SGML I think it was) with perl regular expressions.

My only defence is that the client had decided it would be a great idea to mix in their own custom data markup with the SGML. Ordinarily, this would have been no problem - parse the SGML with a proper parser, then parse the custom markup by walking the SGML AST. Unfortunately, their markup spanned SGML tokens in apparently arbitrary & inconsistent ways and just to complicate matters the data was full of errors, which were mostly not fixable at source, so had to be handled by my code. After a lot of hair pulling, a custom parser written in perl regular expressions with a pile of backtracking just about did the job.

I'm still not quite sure whether it would have been easier to write a custom flex/bison parser for the thing, but the total lack of any consistency meant that an ad-hoc perl parser was probably the only way to get something that solved the client's problem in a reasonable amount of time.
posted by pharm at 3:14 AM on December 4, 2014


Parse HTML with regexes? Nah, mate; you wanna smack it through lynx -dump then use regexes on the output …
posted by scruss at 5:04 AM on December 4, 2014


are schools these days just teaching "programming" in place of real-CS?

I fear that I am getting into the grumpy-old-man-stories era of my life, but my (liberal-arts, lol) undergrad in CS did not teach any language. not one, not any at all. I learned C++ because we were assigned to write a compiler for it (language of your choice.) I learned SQL because we had to write a compatible database server for it (language of your choice.) I had to take required sister-college-of-engineering courses - program a LEO satellite (language of your choice.)

this is not snow-up-the-hill-both-ways old-man-exaggeration, we literally had to do this ****. other required courses more or less migrated into getting additional degrees in Number Theory, Foundations of Mathematics (now there's the true-CS.)

but this seems to be some sort of historical problem - my time with much-older-than-me colleagues at the non-mefi-big-blue, and pretty much everywhere else since, has shown, people of either:
a. Grace-Hopper-level-awesomeness-brilliance
2. plodding, just WTF are you sure you are sapient?!

this fizzbuzz thing and V-- is pretty sweet. and I have been asked some unbelievably moronic questions on occasion by google interviewers, I swear they must have gotten their degree in "programming".
posted by dorian at 5:20 AM on December 4, 2014 [1 favorite]


Yeah, it's amazing how many supposedly competent programmers you can weed out with something like "write a function that counts the number of occurrences of the lowercase letter e in a string".

With that said, embarrassingly enough, I would have failed this test: I solved the Fizz Bizz problem, but it wasn't until after reading both links and half the comments in this thread that I suddenly realized it was "Buzz".
posted by Flunkie at 5:41 AM on December 4, 2014 [1 favorite]


Are schools these days just teaching "programming" in place of real-CS?

At my university, there was a mandatory first year course that taught you Java and then every course after that was about theory, with assignments you could complete in the language of your choice. One course though, had five assignments and you had to use a different language for each one.
posted by 256 at 6:02 AM on December 4, 2014 [3 favorites]


One thing to take into account during an interview: When I interviewed at Microsoft many years ago and was recently out of college, I was thrown when I was asked a question that anyone who graduated from a Computer Science program should be able to answer. I thought, "he must be asking something more complicated that I'm just not getting." It didn't occur to me that they get a bunch of people who lie on their resume. (I'm not so naive now!) So prefacing a simple interview question with, "This is just a question to find out if you (can code|understand object oriented programming|know (C|C++|Java|C#)|understand big O notation) because sometimes people fluff their resume" would have gone a long way to make me comfortable in the interview.

Oh, and V-- reminds me of INTERCAL, the Compiler Language With No Pronounceable Acronym. Here is a little INTERCAL code:

DO :5 <- "'?":1~'#65535$#0'"$":2~'#65535$#0'"'
~'#0$#65535'"$"'?":1~'#0$#65535'"$":2~'#0$
#65535'"'~'#0$#65535'"
DO .5 <- '?"'&"':2~:5'~'"'?"'?":5~:5"~"#65535~
#65535"'~'#65535$#0'"$#32768'~'#0$#65535'"
$"'?":5~:5"~"#65535$#65535"'~'#0$#65535'"'
"$"':5~:5'~#1"'~#1"$#2'~#3
posted by Xoc at 6:32 AM on December 4, 2014 [2 favorites]


I feel kind of bad for the guy whose code they put on the internet. Interviews are a stressful time when, if the questions are good, a lot of who you are as a person gets revealed, maybe more than you want. Many engineers are introverts and so when I ask a technical question many candidates will just shut down and start thinking. I've learned to ask them to tell me what solution they're thinking of, even if it's obviously a naive one, just to get them used to the interview more as a dialog and less as a stress test. But a few candidates go the other way and just spout whatever their brains come up with. It sounds like this guy was more the latter, and I empathize with him. I mean, the code was out of control, but I would just recycle the paper, maybe tell one or two trusted coworkers about the crazy interview I just had, and move on.

Oh, and I've definitely had some interviews where the candidate didn't make a lot of sense, and this one seems well within the realm of possibility.
posted by A dead Quaker at 6:52 AM on December 4, 2014


DO NOT PARSE HTML WITH REGULAR EXPRESSIONS

I hate to jump in here when someone has already defended the point, but this kind of mindless, cargo cult BS is part of the problem in programming. The two responses here where posters saw "HTML" and "regular expression" in the same paragraph and that tripped a switch in their brain that caused them to not only think of Jamie Zawinski's quotation and the most popular answer on Stack Overflow are perfect examples of people I would not hire: the point of interview questions (to me) is to see how you think not what rote memory you possess. The question isn't asking about parsing HTML, it's asking how to find patterns in text to see how the candidate would do it. Regular expressions are not easy to understand, especially once you get past the simplest pattern matching. I honestly don't care if you can handle a negative lookahead while standing on cracking ice in the middle of the Arctic, but I'd like to know you've done enough programming to know they exist and/ or are curious about what tools are available to you.

"Now you have two problems" isn't a koan or life lesson, it's a sigh about the trade-off regexes require: lots of power and expressiveness in exchange for having to write in what might as well be cuneiform for the first decade or so you work with them. If you're going to avoid a tool entirely because it can be dangerous, don't apply for a job doing construction demolition.
posted by yerfatma at 6:55 AM on December 4, 2014 [4 favorites]




Here's a puzzle I posed to my programming friends the other day.

Can you write a script that generates all rational numbers with no repeats and without any equivalent fractions (ie: 1/2 should be there, but not 2/4).

Hint.

I wrote a version in perl, but it will eventually run out of memory.
posted by empath at 7:14 AM on December 4, 2014 [1 favorite]


Whiteboard coding sucks and is a terrible measure of actual coding skill

That's funny to me because I agree with everything else you wrote, but I suppose I'm used to it plus I tend to think in Python which lends itself to pseudo-code.

This is just a question . . . because sometimes people fluff their resume

Yup, a lot of the problem is that interviewing is a skill and just like team leadership, isn't one that's necessarily a gift your best coder has, so forcing them to do the interviewing can be counter-productive. Bad interviewers come in all sorts; the most common I've seen are:
  • the combative interviewer - doesn't like your approach and is a dick about it
  • total introvert - asks the questions on the piece of paper he brought in and stares at the whole time, never gives you an open-ended question
  • the complete incompetent - a lot like Mr. Combative except he's threatened by your solution and worries hiring you would reveal his dark secret
I can say the best interviewing experience I ever had was at Yahoo! (back when they were still, y'know, hiring): the guy introduced himself as "Scotch", we made off-color jokes about the conference room names* on our way to our assigned room and then he presented me with a problem in electrical circuit design. When I said I knew nothing about it he replied, "Good, otherwise I'd have to ask you my backup question." However long our allotted time was, we spent the last half of it improving on his original design and extending the whole concept and refactoring because we were clearly simpatico.

My favorite white board question when I was interviewing, which I only got to ask twice (and both people were out of our budget) was to give me an object-oriented design for a parking garage. What I liked about the question was that I didn't have a perfect answer in my head, so there was always grey area the candidate could fill in as they saw fit. That led to good back-and-forth which should be one of the main goals of an interview IMO.

* All of which was made possible by us both being white guys around the same age which is another problem with technical interviewing. There's a pretty thin line between "good fit personality-wise" and "Who cares if she's brilliant? If we have a girl in here I have to start wearing pants."
posted by yerfatma at 7:16 AM on December 4, 2014 [5 favorites]


The question isn't asking about parsing HTML, it's asking how to find patterns in text to see how the candidate would do it. Regular expressions are not easy to understand, especially once you get past the simplest pattern matching.

Absolutely true. I think the point of the question was that. It was trying to see if you understood this was a simple pattern match problem on text files, not an HTML parsing problem. If all you could see was the HTML and wanted a parser, then, well, you're not understanding the problem *or* what the data you are looking at actually is.

This means you're likely to have problems in the real world. To find a solution, you need to understand what the problem really is.

Can you write a script that generates all rational numbers

Of course not, I've neither infinite memory nor storage. :-)
posted by eriko at 7:16 AM on December 4, 2014 [3 favorites]


Yeah obviously memory restrictions are going to be a problem when generating infinite lists :)
posted by empath at 7:20 AM on December 4, 2014


Yeah, it's amazing how many supposedly competent programmers you can weed out with something like "write a function that counts the number of occurrences of the lowercase letter e in a string".

I love when a candidate responds to questions like this with "what language can I use?" In Java or C++, this can be a little painful, but in scala it's as simple as def countE(st: String): Int = st.count(_ == 'e'), and in Clojure it's (defn count-e [st] (count (filter (partial = \e) st))). Quietly using Java or C++ without even asking whether other options are on the table is a bad sign.
posted by sonic meat machine at 7:36 AM on December 4, 2014 [3 favorites]


To find a solution, you need to understand what the problem really is.

This is what I always try to figure out in an interview. I don't care if someone can reverse a string or do a bubble sort (if I were to ask either of those questions, "I'd Google it" is a perfectly fine answer). I want to know if a person can understand the actual problem they are trying to solve.

When people ask me if programming is hard, I tell them no. Programming is easy. Asking the right question is hard.
posted by ryoshu at 7:37 AM on December 4, 2014 [4 favorites]


Quietly using Java or C++ without even asking whether other options are on the table is a bad sign.

Back in the day someone asked me to reverse a string in an interview. I was allowed to use any language I wanted, so I picked Ruby.

puts "Reverse this string".reverse

I was more amused than the interviewer was.
posted by ryoshu at 7:41 AM on December 4, 2014 [5 favorites]


So these parsing-HTML-with-regexp comments are funny because of one interview I had...

This was a phone interview so I didn't even have a whiteboard, I just had to verbally describe my system design. The interviewer asked about designing a system to do monitoring of webpages remotely. So I said you'd fetch i, store it, do alerts, etc. Then they asked about making sure specific elements were present in the pages. OK, so I'd fetch the page, parse it, traverse the DOM until I get to the bit I'm looking for... and the interviewer says "isn't there an easier way?" My reply is "uuuuhhhh... maybe?"

So the interviewer suggests simply using a regexp to find the one thing I want in the page as it's a lot simpler than a full dom parsing & traversal.

So... apparently parsing HTML with a regexp is the right answer sometimes.
posted by GuyZero at 7:44 AM on December 4, 2014 [1 favorite]


Back in the day someone asked me to reverse a string in an interview. I was allowed to use any language I wanted, so I picked Ruby.

Between when I learned Java and when I started doing interviews some smartass at Sun added StringBuilder.reverse() to the standard library.
posted by GuyZero at 7:46 AM on December 4, 2014 [2 favorites]


Can you write a script that generates all rational numbers

Of course not, I've neither infinite memory nor storage. :-)


He didn't ask to have the script actually run, just to write the script.

Assuming infinite heap and output to a TTY, sure.
posted by GuyZero at 7:47 AM on December 4, 2014


hermaneubis asked: "Why do we only hear these stories about software engineers?"

Have you been following the tales of the new eastern span of the Oakland-San Francisco Bay Bridge? Or seen the reports of buckets catching leaks yesterday in the San Jose City Hall (or, hell, if you've lived in Marin County and been to jury duty you've heard the staff at the Marin County Civic Center go off on Frank Lloyd Wright). Follow the GM ignition recall at all?

Hell, looked at traffic engineering or urban planning disciplines in the United States?

We hear these stories about software engineers because they're easily distilled down into anecdotes that anyone with a little interest in the field can understand.

We don't here about these stories in other disciplines because those who'd tell them are taken as arrogant, and everyone else is standing around embarrassed, looking at their shoes.
posted by straw at 8:10 AM on December 4, 2014 [1 favorite]


As mentioned, quite a few skilled folks have their brain freeze or at least slow down when put in an interview situation. At my current position (SW architect) there were three interviews before I got an offer, and the last was with the head of R&D here. He had a few of these kind of questions and I badly flunked one of them due to my malfunctioning brain. I don't remember exactly what the question was, but the answer was supposed to be something fundamental like "best solved by polymorphism", and I think I was saved by my obvious honest facepalm moment when he had to hint quite heavily for the solution.
posted by Harald74 at 8:13 AM on December 4, 2014


I don't care if someone can reverse a string or do a bubble sort

I tend to think that if someone can't come up with any way to reverse a string or sort a list, even if it's very inefficient, then I need to be worried about their ability to solve more complicated problems.

Assuming infinite heap

Adapted from an example in the Pure manual — no infinite allocation required!
  using system;

  gcd x y = x if y == 0;
          = gcd y (x mod y) otherwise;

  do (printf "%d/%d\n") [m,n-m | n=2..inf; m=1..n-1; gcd m (n-m) == 1];
posted by mubba at 8:59 AM on December 4, 2014


Assuming infinite heap and output to a TTY, sure.

Infinite heap on what? :-)

I know what you're saying, but as a sysadmin, system resources, mathematics, and physics are the arbiters of reality. Indeed, I still maintain it's impossible to write that script, because you also don't have infinite time to run it in. Even if you dump the results to a TTY and they disappear forever once they scroll off, you cannot generate the set of all rational numbers.

You can describe such a set, but you can never create the actual set, thus, the script cannot possibly create that set. Thus is impossible to write a script that will create the set of rational numbers. You can create a large subset of them, but not the entire set.

That's how infinity rolls, and if, as a developer, you are assuming infinite time, heap, storage, or anything, you are doing it wrong.

Another argument: Any script capable of trying has an infinite loop error.
posted by eriko at 9:28 AM on December 4, 2014 [3 favorites]


I tend to think that if someone can't come up with any way to reverse a string or sort a list, even if it's very inefficient, then I need to be worried about their ability to solve more complicated problems.

If a candidate happens to know the answer off the top of her head that's fine. If she implements bubble sort ab initio, I'm going to worry that she doesn't know how to use Google or Stack Overflow.

The best programmers I've worked with are really lazy. If someone has already figured out the problem, use that solution. It's very rare that someone needs to implement an algorithm from first principles in a professional environment.
posted by ryoshu at 9:42 AM on December 4, 2014 [4 favorites]


it's impossible to write that script, because you also don't have infinite time to run it in.

I have to assume that the hypothetical interviewer here is rational. Anyone who asks a question that includes the phrase "all rational numbers" (heck, even "all whole numbers") knows that there are more of them than there are particles in the universe ergo it's nonsensical to ask for anything other than abstract set operations across all of them.

If the interviewer asks about "all rational numbers" and doesn't know what set cardinality is, well, one of you is definitely screwed.
posted by GuyZero at 9:47 AM on December 4, 2014 [2 favorites]


vogon_poet: While the criticism is misplaced, that's kind of a roundabout solution anyway, and I'm pretty sure it doesn't compile cleanly. I don't think I would have hired him.
vogon_poet: suspiciously eponysterical... Surely it's a $5 throwaway... "Joined: December 6, 2009". I'll be damned.
posted by IAmBroom at 9:55 AM on December 4, 2014 [2 favorites]


You can describe such a set, but you can never create the actual set, thus, the script cannot possibly create that set

You don't know for sure the script doesn't have infinite time, so can't I use a generator expression and leave it as an exercise for you to see if it works out?

If she implements bubble sort ab initio, I'm going to worry that she doesn't know how to use Google or Stack Overflow.

Agree completely, but that's a hard lesson to teach because you need enough experience to know when you're looking at a reasonable bit of code versus something some clown posted because bits are cheap and they don't know better.
posted by yerfatma at 10:12 AM on December 4, 2014 [1 favorite]


But a few candidates go the other way and just spout whatever their brains come up with. It sounds like this guy was more the latter, and I empathize with him.

Maybe - I've been through the grueling 5-hour interviews that big software companies like to do these days and god knows what was coming out of my mouth by the end. This reads more like a guy who rode in on complete bullshit and had to make up how to "code" on the spot.
posted by atoxyl at 10:26 AM on December 4, 2014


GuyZero: OK, so I'd fetch the page, parse it, traverse the DOM until I get to the bit I'm looking for... and the interviewer says "isn't there an easier way?" My reply is "uuuuhhhh... maybe?"

So the interviewer suggests simply using a regexp to find the one thing I want in the page as it's a lot simpler than a full dom parsing & traversal.
THIS is an example of a terrible interviewer. "Better" was not part of the solution description. "Better" requires time and investigation.

"Jump!" does not imply the interviewer cares how high. (Which is why the classic drill-instructor cliche is so damn dumb.)
posted by IAmBroom at 10:37 AM on December 4, 2014 [1 favorite]


So, regarding infinity, the solution is infinite sequences. Consider, in Haskell:

Prelude> take 200 [1..]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200]


This is a truly infinite sequence; if you take a million numbers from it, you get a million numbers. If you try to evaluate it directly, it will crash your program. Most functional languages have idioms for this; in Clojure it's lazy-seq, while Haskell can generate them pretty naively because it's inherently lazy. (Although, as with the infinite list above, evaluating the entire thing will crash you.) Even Python can do it with generators.
posted by sonic meat machine at 10:38 AM on December 4, 2014 [1 favorite]


GuyZero: Can you write a script that generates all rational numbers

Of course not, I've neither infinite memory nor storage. :-)


He didn't ask to have the script actually run, just to write the script.
He didn't ask you to write the script, either. He asked if it could be written. In this universe, as functional code, no.
posted by IAmBroom at 10:38 AM on December 4, 2014 [2 favorites]


Some of the comments here are reminding me of an interview question sequence that I kind of like, although I can see how it would be stressful for some. It goes like this:

First, write a function that takes an integer parameter, and returns 1 if it's passed 2 and 2 if it's passed 1. We don't care what happens if it's passed anything other than 1 or 2; it can return anything or throw an error. (This step should be provided with assurances that this is just the first step and it's supposed to be as ridiculously easy as it sounds.)

The applicant will probably write something like: if (n == 1) { return 2; } else { return 1; }. If they do, the next step is "OK. We implemented this, but it turns out that conditionals are prohibitively expensive on our target hardware. Can you do it without conditionals?"

Let's say that in reply to this the applicant does something like: int results[3] = {0, 2, 1}; return results[n];. Now you say "This has to work correctly under a compiler that has a known bug in how it handles arrays. Can you do it without conditionals or arrays?"

And you keep iterating like that, cheeseshop-style, until the applicant runs out of ideas.

The crucial thing you're looking for with this question isn't just how many different ways they can solve the problem, it's how they react to the increasing constraints. Do they sigh and complain, or do they treat it as a challenge? People who are happier solving the problem will be happier working in software development. That's because the whole exercise is a small-scale simulation of how software development frequently goes.
posted by baf at 10:57 AM on December 4, 2014 [6 favorites]


namewithoutwords: arrjay: "in bash without if? - the easiest way I can think of is to make it some other program's problem,"

thanks for that, I'll need to remember to include "no pipes or external programs allowed" the next time I'm trying to stump someone on this.</derail> :-)
Then you are screening against hiring:
ryoshu: The best programmers I've worked with are really lazy.
posted by IAmBroom at 11:00 AM on December 4, 2014 [1 favorite]


THIS is an example of a terrible interviewer. "Better" was not part of the solution description. "Better" requires time and investigation.

I don't follow? I mean, I don't think they were the best interviewer of all time, but I think the interviewer was explicitly looking for something that one person could realistically both implement and use and not something gold-plated or that would take a team to maintain. I think their comment was specifically about time/cost of implementation.
posted by GuyZero at 11:01 AM on December 4, 2014


I think the only time I've ever actually pitted out a shirt was during a live coding interview (for my current Javascript job). It was straight fizzbuzz (which I'd somehow never encountered before), but the interviewer added the pretty useful twist of incrementally adding requirements once I finished each version (do fizzbuzz; ok, now clean it up to show you can do a basic refactoring of off-the-cuff code; now do it with a random list of numbers instead of a range; now add a simple test suite). The final requirement was to load a list of numbers from somewhere else using JSONP. I realized I had no idea how to do that and froze for a second, but fortunately my answer was "uh, that sounds familiar, can I look that up real quick?" I took 5 minutes to quickly scan the jQuery docs and a few stackoverflow threads about it and fortunately it was about a straightforward as I assumed it would be. Pretty sure that being honest about not knowing and showing a desire to figure it out (even if it took a little bit longer that I'd hoped) is what got me hired.
posted by OverlappingElvis at 11:06 AM on December 4, 2014 [3 favorites]


GuyZero: I don't follow? I mean, I don't think they were the best interviewer of all time, but I think the interviewer was explicitly looking for something that one person could realistically both implement and use and not something gold-plated or that would take a team to maintain. I think their comment was specifically about time/cost of implementation.
I'm saying that if someone asked me, on the fly in an interview setting, how to do X, I won't be thinking in terms of, "What is the most efficient way to do it?", but simply "How?".

Most ideas can be honed, refined, or rejected in favor of improved ideas. I think if the interviewer is looking for some goodness criterion ("using this compiler", "using Mac hardware", "in the least time", "with minimal memory overhead"), they should say so.

If the interviewer wants to say, "OK, but that's inefficient... how can you improve on it?" or "Would doing Y instead be faster?", that's the next-level of question.
posted by IAmBroom at 12:05 PM on December 4, 2014 [1 favorite]


The script i posted, given infinite memory and time, will generate all positive rational numbers. (well, mine terminates after N iterations, but you get the idea). Yes in the real world you don't have infinite time or memory, but if you can't separate the theoretical from the practical, you're going to have a hard time in CS.
posted by empath at 12:12 PM on December 4, 2014


If the interviewer wants to say, "OK, but that's inefficient... how can you improve on it?" or "Would doing Y instead be faster?", that's the next-level of question.

Not to beat a dead horse, but I think that's kind of what they were going for although perhaps I didn't get that across. I think they just wanted to verify I knew what regexps were. Although I do know what you mean - "That's not how I'd have done it" is not a particularly good interviewing style.
posted by GuyZero at 12:24 PM on December 4, 2014 [1 favorite]


Yeah, as empath said, you can't actually print an infinite number of things, but "write a program that prints all rational numbers" can be reasonably understood as meaning "write a program that will eventually print any given rational number exactly once in finite time." (You don't need infinite memory.)

And if you're being interviewed, it's usually a good idea to try to understand what the interviewer is asking for without letting pedantry get in the way.

If she implements bubble sort ab initio, I'm going to worry that she doesn't know how to use Google or Stack Overflow.

Maybe she remembers it from CS class? I don't get why this says anything about her ability to search the web.
posted by mubba at 12:33 PM on December 4, 2014


"write a program that will eventually print any given rational number exactly once in finite time." (You don't need infinite memory.)

The memory need explodes pretty quickly because you're pushing two numbers into the array every iteration and you can only drop 1 number per iteration (which i didn't actually do in mine).
posted by empath at 12:38 PM on December 4, 2014


You can also do it as above without allocating anything, where the algorithm is basically, loop over the sum of the numerator and denominator, then for all numerator/denominator pairs with that sum, print them if their greatest common divisor is 1.
posted by mubba at 12:42 PM on December 4, 2014 [1 favorite]


Maybe she remembers it from CS class? I don't get why this says anything about her ability to search the web.

My original statement:

If a candidate happens to know the answer off the top of her head that's fine. If she implements bubble sort ab initio, I'm going to worry that she doesn't know how to use Google or Stack Overflow.
posted by ryoshu at 1:31 PM on December 4, 2014


> "write a function that counts the number of occurrences of the lowercase letter e in a string".

That's just the Hamming Distance from the string of the same length as the input that consists entirely of lowercase letter e. It's In the Literature(tm).
posted by sourcequench at 2:01 PM on December 4, 2014 [2 favorites]


> "write a function that counts the number of occurrences of the lowercase letter e in a string".

This is another case where it matters whether they specify the language, since this is a built-in in a lot of them. If they won't accept

s.count('e')

in Python, then what will they accept?
posted by George_Spiggott at 2:35 PM on December 4, 2014


A good interviewer will ask a real question that can't be reduced to a single line of code in some language. If what you want to see is pointer math, ask for it. But I expect there's a non-trivial amount of judging that goes on about what language the candidate chooses. I tend to eventually revert to C since that's what I grew up on which is mostly OK although to some Python die-hard probably looks at my code like I'm brain-damaged and trying to write assembly code and oddly ignorant of array slices.
posted by GuyZero at 2:42 PM on December 4, 2014


In fairness, architects aren't supposed to know how to code. Their job is bullshitting non-technical managers into thinking they're essential. That Fizzbuzz scrawl would have done the job handily in plenty of workplaces.
posted by Zed at 4:46 PM on December 4, 2014 [2 favorites]


In this universe, as functional code, no.

On the contrary! The code definitely can be written. You don't even need to assume an infinite heap. You just need to assume that certain classes of reasons for the script not having finished successfully don't count. Which is a completely reasonable thing to do. Suppose, for instance, that you're given the task of printing out the first 1000 natural numbers (including zero), on per line. Ok, you say:
for x in range(1000):
    print x
"Ah!", says your interviewer. "What if, nanoseconds after your script is invoked, a nuclear bomb sitting next to the server goes off and utterly destroys it?"

Well, it won't print all the numbers, obviously. Equally obviously, that is not your script's problem. (If you want make objections about fault-tolerance increase the number of numbers your script has to print, so it takes longer, and say that many, many nuclear bombs destroy the entire earth.) Or, more mundanely, what if the memory is corrupted, or whatever. It's not YOUR problem. The script won't run successfully, but there's no error in the script.

Similarly, of course your script, lacking infinite space and time, won't actually print all the rational numbers. But you can do this: pick a rational number, and ask, if the script doesn't print this rational number, why not? What will have gone wrong? If your script is written properly, the answer will always be "some external assumption was violated"—either there wasn't as much memory as necessary, or the server slid into the Pacific Ocean in an earthquake, or some other time-related mishap occurred. It wasn't a logic error in your script.

Think, for instance, about the distinction between these two ways of generating all pairs of integers:
pairs1 = [(x, y) | x <- [0..], y <- [0..]]
pairs2 = [(x, y) | x <- [0..], y <- [0..x]
Obviously, in neither case will you be able to iterate through the variable and print out all pairs in such a way that you could ever "finish". But if I ask "what about (54, 100), will that ever be printed?" the answer is "no, under no circumstances" for the first one. There's a logic error; you never get to (1,0) because first you need to "finish" with (0,0), (0,1), (0,2) ..., which will never happen. Whereas you will eventually get to any arbitrary pair with the second one, provided, again, the script actually keeps running. So it's the correct answer.
posted by kenko at 4:56 PM on December 4, 2014 [6 favorites]


Well, in the second example, you're never going to get to (0, 1). Unless (1, 0) is equivalent, the second option will never print all possible pairs, either. Thus the first is correct, even though it will never finish iterating the first portion of the pairs.
posted by sonic meat machine at 6:06 PM on December 4, 2014


Ha oh right, I knew I'd messed that up!
posted by kenko at 6:44 PM on December 4, 2014


I'm sure kenko meant the "triangular" mapping
  [(x, n-x) | n <- [0..], x <- [0..n]]
(The same trick lets you iterate over the rationals, and is a constructive proof that the cardinality of the set of pairs of integers is the same as the integers.)
posted by mubba at 6:48 PM on December 4, 2014


(It should be pairs2 = [(y, x-y) | x <- [0..], y <- [0..x]].)
posted by kenko at 6:49 PM on December 4, 2014


Calkin and Wilf (2008)"Recounting the Rationals" [PDF link] describes a computable sequence of natural numbers beginning 1,1,2,1,3,2,3,1,4,3,5,... such that taking successive pairs from the sequence (i.e. 1/1, 1/2, 2/1, 1/3, 3/2, ...) gives an enumeration of the rationals in lowest terms without duplication. Given any rational it's easy to work out where in the sequence it occurs, and thus to show that every rational does indeed occur in the sequence. The sequence is given by a function defined as
f(0) = 1
f(2n+1) = f(n)
f(2n+2) = f(n)+f(n+1)

Brent Yorgey wrote a nice series of posts exploring this paper, starting here. (The rest of the posts are most easily found from this index.)
posted by logopetria at 8:33 AM on December 5, 2014 [2 favorites]


logopetria, my perl script above implements that. It was on numberphile this week, that's how I knew about it.
posted by empath at 8:47 AM on December 5, 2014 [1 favorite]


A Haskell implementation is available in the appendix of the paper Recounting the Rationals: Twice!
posted by sonic meat machine at 9:44 AM on December 5, 2014 [1 favorite]


I found the second link first and I found that humorous. Then I read the link it was based on. While I, too, have been on both sides of a rapidly devolving technical interview [A.F.R./O.N.A.N. joke reference here], I actually started wondering if the interviewee had decided that the job was going to suck and would have turned it down if offered. I think this would be a hilarious way to tank an interview for a job that I'd already decided I didn't want.

Metafilter is a funny place though. When I decided to make a quick FPP I expected a few short riffs on V-- and Hitchhiker's Guide foo and instead am treated to
  1. a pretty decent colloquium on how to properly conduct a technical interview
  2. various code snippets and solutions to related interview questions
  3. a discussion on the feasibility of describing all rational numbers in code and the limitations on getting that to run on today's hardware
  4. various Software Tall Tales
  5. and, of course, our resident Vogon poet as well as Mefi's Own vogon_poet posting nearly simultaneously.
posted by Fezboy! at 10:38 AM on December 5, 2014 [6 favorites]


I think, based on what I've learned from reading forum threads on problems I've solved at Project Euler, if I were ever hard up in an interview I would just mash some punctuation keys and claim it's a valid J program that solves the problem. Here, for example, is a program that apparently solves a problem about comparing numbers written in exponential form.
   1+ I.*./ ({:@[ <: {:@] * ^.&{.) "1/~ T
But I mean really if I put that down and claimed it solved fizzbuzz, I think the burden would be on you to prove that it doesn't.
posted by Wolfdog at 1:34 PM on December 5, 2014 [3 favorites]


By the way I played fizzbuzz with some third grade students yesterday (who needed to practice recognizing multiples of things so it was apropos). One girl almost died from laughing. Yes. This thread almost killed a third grader. I hope you're happy, MetaFilter.
posted by Wolfdog at 1:39 PM on December 5, 2014 [4 favorites]


If someone put Wolfdog's code in front of me and told me it was APL or J or something like that, I would believe them. (And ask for verification. But I'd believe them.)
posted by kenko at 2:04 PM on December 5, 2014


well, it has ascii characters, so that pretty much rules out APL.
posted by invitapriore at 4:38 PM on December 5, 2014 [1 favorite]


I don't care if someone can reverse a string or do a bubble sort (if I were to ask either of those questions, "I'd Google it" is a perfectly fine answer). I want to know if a person can understand the actual problem they are trying to solve.

When people ask me if programming is hard, I tell them no. Programming is easy. Asking the right question is hard.
This seems pretty ridiculous to me. I mean, sure, "implement quicksort" or something like that is "google it", but "reverse a string"? You genuinely don't care whether or not your programmer is capable of writing pseudocode to reverse a string? "I'd google for an algorithm to reverse a string" is a totally absurd answer.

Obviously you don't specifically care about reversing strings, and obviously many high level languages these days have a ".reverse" function that might make for the necessity of a "yeah, hah hah, real clever, but seriously, do I really have to be explicit about what I'm looking for here" response from the interviewer. But if someone genuinely cannot write pseudocode to reverse a string, I don't care what wonderful thought provoking heart-of-the-matter questions they come up with: You're unwise to hire them as a programmer.

And you might be surprised how many people who interview for these positions - and even how many get these positions - cannot accomplish extremely simple programming tasks like this. Questions like this are not stupid little misguided formalities - they really do weed people out quickly and easily.
posted by Flunkie at 5:16 PM on December 5, 2014 [1 favorite]


obviously many high level languages these days have a ".reverse" function

I think there's probably a "generation gap" (for lack of a better name) here: I came up working in "scripting" languages and still do 99% of my work in them so having someone who can provide a function to reverse a string and then optimize it never feels important to me. I'd be more interested in their ability to find performance gains across the stack: how knowledgeable are they about EXPLAIN queries, what tools do they use for profiling (which is just a polite way to see if they even know what that is), etc. Being able to optimize a single function obviously still matters once you find a bottleneck, but reversing a string or sorting feel like boilerplate "Make 'em nervous" questions along the lines of why manhole covers are round.
posted by yerfatma at 10:17 AM on December 6, 2014 [1 favorite]


No, there's no generation gap in the sense that old school programmers don't realize that there are now a lot more high level functions to various things. This is missing the point of such questions entirely.

The point of questions like that is not "in this job, reversing strings is an extremely important task, so I have to find out if they can they reverse a string". The point is "can they accomplish an extremely simple task in an algorithmic manner". Many candidates cannot.
posted by Flunkie at 10:41 AM on December 6, 2014


I hate to jump in here when someone has already defended the point, but this kind of mindless, cargo cult BS is part of the problem in programming.

Um... what? I mostly just posted that SO link because it's funny, but ok, let's do this: nobody is saying that you shouldn't parse HTML wih a regex for the hell of it; they say it because HTML isn't a regular language. It's the wrong tool for the wrong job, and your post reads like saying "all those people saying you shouldn't try to use a hammer to screw in screws are part of the problem!"

Anyone who would see HTML and think "let me use a regex" instead of "let me use one of the hundred HTML parsing libraries that are inevitably available in my language" isn't anyone I would hire, or ever want to work with. Hell, if you really must write your own parsing logic, at least do it right - HTML is a fairly simple CFL, so you can write your own parser with a stack and a minimum of effort. Anyone who wants to use regular expressions on HTML outside of very limited subsets either doesn't understand HTML, doesn't understand regular expressions, or both; and there's little more frustrating than trying to work with (or, more likely, around) someone who is trying to solve a problem they don't understand with a tool they don't understand.
posted by Itaxpica at 10:45 AM on December 6, 2014 [1 favorite]


That is true if you are actually parsing HTML.

Extracting phone numbers from an ASCII (or UTF-8) text file which may or may not, in addition to containing some phone numbers, also be HTML, in many situations may not actually require you to parse HTML. In fact, depending on the exact structure of the file, the fact that it's even an "HTML file" might be a total red herring.

You could pretty easily, if you were so inclined, make up a file that purported to be HTML and maybe even on casual inspection looked like it, but was so broken as to not parse using any normal HTML-parsing library. If the task is "extract the phone numbers from this file", someone who goes down the primrose path of using an HTML parsing library is going to waste a lot of time versus the person who just uses the brutalist regexp method.

That would be a crappy interview question since it's basically a trick, but it wouldn't be unrealistic.
posted by Kadin2048 at 1:43 PM on December 6, 2014 [1 favorite]


The point of questions like that is not "in this job, reversing strings is an extremely important task, so I have to find out if they can they reverse a string". The point is "can they accomplish an extremely simple task in an algorithmic manner". Many candidates cannot.

Part of the problem is, though, is that it's not a very interesting question, i.e., you haven't learned very much about the relevant capabilities of a candidate for whom the answer to that question is "yes." One of my favorite interview questions to ask is to ask the candidate to devise a wrapper function around another call that makes a request to some external service over HTTP that we want to rate-limit to at most X calls in any given one-second window. It's a problem that also requires basic algorithmic thinking to solve, but it's also embedded in a problem domain in a way that gives you insight into the candidate's actual practical engineering experience: do they ask whether the network call is made asynchronously? Are they concerned about the wrapper function blocking? Do they jump to a threaded solution immediately? Can they come up with a solution whose space complexity has a constant bound? It seems to me that asking questions like "write a function that reverses a string," that amount to merely ruling out that the person is totally helpless, is a waste of everyone's time.
posted by invitapriore at 5:14 PM on December 6, 2014 [2 favorites]


Questions like that are not intended as a sole solitary question to ask, and hire the person if they can do it and don't if they can't. They're intended to quickly weed out those who cannot do it, and that's all.

It's not a "helpless waste of everyone's time". In the case of someone who can do it, it takes mere moments; in the case of someone who cannot, the interviewer saves time by easily discarding the candidate from further serious consideration, without needing to worry about judgment call things like "Well, maybe I didn't understand exactly what he was going for in the answer to the more difficult question" or "Well, he didn't answer the difficult question correctly, but maybe it was close enough that he would be able to do it given more time to reflect" or "Well, his solution wasn't good, but it was correct, strictly speaking".

I've said this multiple times, but I'll say it one more time and then shut up about it: There are a lot of interviewees for programming jobs who cannot do this sort of thing. I'm not kidding and I'm not exaggerating.
posted by Flunkie at 5:26 PM on December 6, 2014


My honest answer for how I solve most programming problems is 'google it'.

But most of the programming I do at work is really basic linux shell scripting/perl.
posted by empath at 6:32 PM on December 6, 2014


I've said this multiple times, but I'll say it one more time and then shut up about it: There are a lot of interviewees for programming jobs who cannot do this sort of thing. I'm not kidding and I'm not exaggerating.

You're right, of course, but let me lay out some of my assumptions here:

1. You can't end an interview early just because the candidate is hopeless. That time is sunk the second you walk in the room.
2. Once you've determined that a candidate is hopeless, no further elaboration of the nature of their hopelessness is required. It's a done deal, free of ambiguity.
3. In the case of a promising candidate, the marginal return on each new datum concerning their capabilities actually increases with the number of data revealed.
4. It's not worth making excuses on behalf of the candidate -- if I didn't understand what she was going for, or if he might have nailed it given more time, or if she gave a correct but sloppy solution, it's totally rational for me to adopt a pessimistic policy and assume that all of those statements are false. I've administered enough interviews at this point to know that someone will come along who will unambiguously nail it, and even though it is certainly possible that some very great candidates fall through the cracks with that approach, I think, given my epistemologically compromised position as a human being, that that policy maximizes E[hire capability level]. That's really the best I can hope for.
posted by invitapriore at 9:04 PM on December 6, 2014


That's fair, Kadin, but it's also not what people were talking about. When I posted that SO link, it wasn't in response to people grabbing phone numbers from web pages, or anything about phone numbers (or even interviews) at all. It was a response to someone who said that they had worked with a group that had "tried to parse HTML with regular expressions", full stop, and that's a giant red flag. I said in my post that every rule has exceptions, and numbers in a web page like that is a huge one here since, like you say, you're not actually parsing the HTML.

But I also think that any of these are terrible interview questions - personally I prefer system design-type questions myself when I interview candidates. An engineer can go years without needing to know the difference between a depth-first search and a breadth-first search, but he or she is gonna be designing stuff, at least on a small scale, on a pretty much daily basis.
posted by Itaxpica at 9:15 PM on December 6, 2014 [1 favorite]


You don't even need infinite cardinality to break computers. Just ask for something finite but arbitrarily large.
posted by grog at 2:15 PM on December 8, 2014




It was a response to someone who said that they had worked with a group that had "tried to parse HTML with regular expressions", full stop, and that's a giant red flag

Well, you're arguing with me and as far as I can tell I posted what you responded to. The stuff you have in quotes doesn't appear elsewhere in the thread, so I'm not sure if it was in response to me or not, but if it was then you're still missing the point: you responded to something I wasn't asking without bothering to parse the question. The SO link isn't relevant to the Steve Yegge question I was talking about.
posted by yerfatma at 4:23 PM on December 8, 2014


So on the "regexes to parse HTML" discussion, I've been dealing with a lot of XML recently, and it seems to me that there are three stages of programming:
  1. The inexperienced coder, who says "why do I need to deal with all of this parser overhead when I can just use regexes?"
  2. The CS grad who's had "correctness" drilled into them in an academic environmet who says "It's either XML or it isn't, so we should definitely use a conforming parser."
  3. The grizzled old coder who knows that nobody actually generates valid XML, and the only people using XML are assembly line coders at big companies who don't actually understand the tools they're using, at the very least they're going to screw up character encoding, and entity encoding, and you're going to have to do a hell of a lot of automated cleaning up of all the crap that's coming out of the system anyway using regexes, so why not just parse it with regexes to begin with?
So whenever I hear "just parse it with regexes", I try to figure out whether it's #1 or #3, because #3 is the person you want to hire.
posted by straw at 8:52 AM on December 10, 2014 [4 favorites]


#3 is an admirably pragmatic sort but they're still wrong to be calling that activity "parsing XML."
posted by invitapriore at 10:34 AM on December 10, 2014 [1 favorite]


The grizzled old coder who knows that nobody actually generates valid XML, and the only people using XML are assembly line coders at big companies who don't actually understand the tools they're using, at the very least they're going to screw up character encoding, and entity encoding, and you're going to have to do a hell of a lot of automated cleaning up of all the crap that's coming out of the system anyway using regexes, so why not just parse it with regexes to begin with?

Because if you use a proper xml library on xml that's good enough, you get to do nice things like:

$xml = $result->XMLin($result->content);
$username = $xml->{'field'}->{'username'}->{'value'};
---
or something similar, rather than whatever dark sorcery you'd need to do with a regex, which nobody will be able to untangle later. If you need to clean up the xml, clean it up, then run it through a standard xml library, like a sane person.
posted by empath at 10:38 AM on December 10, 2014 [1 favorite]


Because if you use a proper xml library on xml that's good enough

Except what you'd get in the given example is an exception for malformed XML.
posted by yerfatma at 10:22 AM on December 12, 2014 [1 favorite]


So whenever I hear "just parse it with regexes", I try to figure out whether it's #1 or #3, because #3 is the person you want to hire.

Seems like you could figure that out pretty easily by asking "why?".
posted by kenko at 10:57 AM on December 12, 2014


Except what you'd get in the given example is an exception for malformed XML.

Depends on how malformed, I guess. I've never run into a problem with it, really.
posted by empath at 12:11 PM on December 12, 2014


On "how malformed": some actual transformations from production code done on output from a widely deployed piece of telecommunications infrastructure that purports to output XML:

s/(<[^ >;=?*+#]+)[;=?*+#]/$1-/g
Attempt to clean up invalid punctuation that sometimes shows up in element names
s/(<\!\[CDATA\[.*?)(?!\]\])\>\/(\w+)\>/$1\]\]\>\<\/$2\>/g
Close CDATA regions with malformed close tags
s/(\<\/?[\w\-]+)\=(.*?\>)/$1\-$2/g
Try to do the right thing with attributes with malformed equals signs
s/(\<\/?[\w\-]+)\/(.*?\>)/$1\-$2/g
Slash signs in elements

Of course my notes here on what these regular expressions are allegedly doing are probably wrong because they're pulled from the comments written by someone who was trying to get this into the parser. Looking at this system (and I do), it's mostly really just flat key value pairs, it'd be much easier if reading this were more of the form:
$value = $1 if (/\<elementwecareabout.*?>\>\s+(.*?)\s+\</elementwecareabout\>/s);
(Or some table driven loop to try to extract that and ignore the rest of the crap)

And don't even get me started on people who don't understand character set encoding issues, SOAP WSDL files that explicitly preclude values that huge vendor insists on being sent, and on and on and on...

But to get back to the original "Parsing HTML with regexes" bit of this: I have an HTML parser I wrote for user facing input that I wrote back in the days of my first blog comment system, so circa 2000. It uses regexes. I have ported it from Perl to Python to C++. I have kept it for around a decade and a half because all of those parsers which people extol on those various platforms do the wrong thing with some substantial portion of my tens of thousands records of user input HTML, and mine interprets what users have wanted fairly well, and has thus far kept out the malicious stuff as I've read about exploit after exploit in other systems.

I've also recently had to dive in and fix core code on widely distributed modules, and frankly the quality of that code was horrendous (a recent "OMG this is sooo gross": Perl's IO::Scalar module). "Use regexes to parse it" and "write it from scratch" are either an indication of immaturity, or maturity, and are responses worth pursuing further. "Just use a parser" or "just use module X" are fine for junior level coders, but be super careful with that person and make sure they get some good mentorship.
posted by straw at 2:11 PM on December 12, 2014 [1 favorite]


>> "write a function that counts the number of occurrences of the
>> lowercase letter e in a string".
>
>That's just the Hamming Distance from the string of the same length
>as the input that consists entirely of lowercase letter e. It's In the Literature(tm).

I'm an idiot. That's actually the length of the input minus the Hamming distance from the input to the string of the same length as the input that consists entirely of lowercase 'e'.

I award myself no points.
posted by sourcequench at 5:21 PM on December 17, 2014


« Older If Klein had even just read the entry on Wikipedia   |   'Ecological differentiation is the necessary... Newer »


This thread has been archived and is closed to new comments