1. 28

I can’t understand why tech interviews involve implementing some sort of tree, regular expression engine, sorting algorithm or parser


  2. 31

    Author here. To be clear, all the stories in this series are jokes, not endorsements. Engineering interviews are a complex problem and I won’t begin to discuss them here, except to say that there are people whose entire lives involve studying and improving teams of humans, they’re called organizational psychologists, and it might be worth hiring some.

    Since folks have expressed incredulity that these techniques are at all involved in modern programming jobs, I should note that I have had to implement trees, sorting algorithms, and parsers in my professional code. For instance, I wrote the clj-antlr parser bindings to support Riemann’s query parser, which is chock full of tree transforms, on account of it being a compiler for search predicates. Knossos includes a hand-rolled binary search over… what are essentially packed and bitmasked structs, masquerading as a JVM int array. There’s also some graph neighborhood stuff in there that allows us to memoize arbitrary function calls over objects into pointer-chasing through densely packed int arrays. Gretchen implements a number of simplification algorithms over trees of boolean expressions, as well as Tseitin-expansion to reduce predicates to conjunctive normal form, which are required to turn transaction dependency graphs into constraint- and SAT-solver-friendly expressions. This is, like, the third or fourth time I’ve tackled this problem.

    I don’t… think I’ve done a regex algorithm yet, but my former coworker Zach Tellman has done quite a few DFA and NFAs in his time; Automat comes to mind. I’m sure it’s only a matter of time before I wind up doing it too.

    My experience is, of course, not representative. :)

    1. 1

      Why is it not representative? Seems like problems any experienced person may encounter in their travels. Enjoyed the story BTW.

      1. 3

        That’s the hope, but I suspect not everyone gets the chance to venture out into the interesting waters of comp sci.

        1. 3

          I’d guess because the median programmer is writing business code and never writes library code in their entire career.

          1. 1

            Come on, that’s rock-star stuff.

            1. 1

              It’s true, it’s obviously great work. My point is that aphyr IS representative of experienced people. Experienced people … experience many variety of problems.

        2. 8

          I can’t understand why tech interviews involve implementing some sort of tree, regular expression engine, sorting algorithm or parser

          I don’t have the history to back it up, but I strongly suspect tree and linked-list questions are a holdover from a time where almost everything was done in C, and you had to know how to hand-roll data structures to get anything done. If that’s the case, then it would have been a “do you know how to use the language” question, not a “can you come up with new algorithms on the spot” question.

          1. 10

            Specifically, programming in C requires understanding pointers, and the difference between and object and a pointer to an object, and a pointer to a pointer. These distinctions are essential to solving any problem in C. Basic data structures are a simple self contained problem that involves pointers. The linked list question is not about linked lists. It’s about understanding why your append function takes a node star star.

            1. 2

              Basic data structures are a simple self contained problem

              (I agree with your whole assessment, but find this part particularly compelling.)

              If you interview for a position that involves programming, you are ultimately going to be forced to solve problems—sometimes brand new problems that have not been solved before. So how does one assess a person’s ability to do that? You can’t give someone a problem that’s never been solved before…

              I don’t know. The thing that I find most awful about data structures questions is that the distribution of those with knowledge is normal, so it’s either impossible, derive it from scratch, or memorized/almost rehearsed because the candidate just knows it.

              The best questions I’ve had have been generally open ended. There might be a data structure that solves it well that the interviewer has in mind, but there are also 10 other ways to solve the problem, with different levels of sophistication, that would probably be good, in practice, at least until hockey stick growth hits. The best interviewers are open minded, and good enough on their feet to adapt their understanding of the problem to a successful understanding of a potential solution that the candidate is crafting.

              Maybe the fact that algorithms, and data structures have but one answer is the actual drawback… hmmm.

              1. 3

                WRT the normal distribution, I think modern interviewing has forgotten that such questions aren’t supposed to be textbook tests and have drifted away from reasonable questions. Even if you’ve never heard of a binary tree, I can explain the concept in 30 seconds such that you should be able to implement search and insert. (Rebalance may be harder.) I can’t argue it won’t be easier if you’ve done it before, but it should never be impossible.

                1. 4

                  That’s probably true. But the concept isn’t useful without intuition about how to apply it, and I think that’s part of the problem, too. Often, criticism of these questions is that “libraries already have a binary tree, and I’ll just use that.” I think it’s likely that these types of interview questions poorly proxy the question of: “does this person know when to use a binary tree? They must if they know how to implement one!”

              2. 1

                They are asked such questions to differentiate between a flood of new programmers each without experience. Such aptitude type questions can be be automated as a way to cull the majority of applicants.

                Sad that they are being applied across the board regardless of experience, even though nearly all experienced programmers have never had to actually implement a CS/text book algorithm, preferring instead to use the tried, tested and optimized implementation in a language’s base class library, or those readily available elsewhere.

                1. 1

                  But trivia about algorithms and data structures says practically nothing about experience.

                  EDIT: Nevermind, I just read your post again.

                  Still, I feel like focusing on more realistic problems could be a much better predictor of aptitude.

            2. 3

              From the next one in the series:

              “If it were meant to be illegal,” you remind him sagely, “Sun Microsystems would have made it unrepresentable.”

              1. 3

                Nobody cares about the actual algorithm (I hope). As an interviewer I want something the applicant is not familiar with. Dumping a rehearsed blob of code provides no information. I want them to notice holes in the specification and ask for clarification. I want to see a balanced amount of safe guarding.

                I you hire C/C++ programmers it matters that they program defensively enough, because any junior programmer can introduce arbitrarily breaking stuff into your code base. Nearly as bad are scripting languages with monkey patching.

                There is less need for Java programmers because the impact of code snippets can be properly limited. Microservices are a higher level mechanism to limit impact for any language. No need to grill applicants so much in that context.

                I believe programming ability is overemphasized in interviews. Asking for experience and opinions on continuous integration gives me more information on overall developing ability.

                1. 3

                  I can’t understand why tech interviews involve implementing some sort of tree, regular expression engine, sorting algorithm or parser

                  It depends. If the candidate is told that they will be solving problems like this before the interview, then the interview is, in part, testing their ability to take an assignment (study these things) and execute on it and then use the things they learned. This is basically what they’ll be doing at work, so it’s appropriate. Note, this is not the only way to interview candidates, but it is a way that is not terrible.

                  However, if the interview is structured such that the candidate is expected to walk in off the street and answer any question, that just means the company hasn’t figured out how to interview people.

                  1. 0

                    I don’t see how asking you to implement trees/regex engines/sorting algorithms/parsers is really appropriate. You’re not going to be asked to do something you’ll never do at work.

                    1. 2

                      I’m not sure if you just didn’t read my comment, but as I said in the good version of these kinds of interviews, what’s being tested is not if you can implement a tree or sorting algorithm but it’s if you can be given an assignment that requires learning some things and then use that knowledge. That is the type of work one will be doing at a job.

                      1. -1

                        I read what you wrote. My point is that you don’t get assignments for things you will never do. It doesn’t even make sense. An assignment like rewriting a regex engine is totally pointless. You aren’t going to get something that is comparable to that at work that you’ll have to learn about. It’s just not going to happen.