[noobermin]

As someone who might apply once I get my PhD, what does basic CS knowledge mean for you? Like what a tree is or fizzbuzz? Hopefully it isn't that terrible...how someone can make it through any amount of CS related schooling and not know the basics?

Somewhat related anecdote, I do computational physics. I once attended "training seminar[0]" put on by the funders for using DOD supercomputers, and there was this soon-to-be-minted computer science PhD student who was also an intern. Most of the systems have pbs[1], a batch system that prioritizes jobs from users based by amount of requested time, number of nodes, etc. The seminar leader (and I have before) referred to it loosely as a queue, because it sort of is, and the CS guy kept interrupting the talk (may be two or so times) to point out that PBS really wasn't a "queue" because it didn't respect FIFO in a strict sense... I mean, sure, he did know what a queue was, but I'm pretty sure that isn't the most interesting problem you could have.

[0] there was one fact I found useful, which was where to find their docs online. Other than that, it was the sort of stuff you can find by just reading man pages and such. Waste of time but checked off a box for the internship which made the funders happy, I suppose.

[1] https://en.wikipedia.org/wiki/Portable_Batch_System

[skybrian]

Well, for example, I have an interview question where it's not just about knowing what a stack or a tree is, but rather realizing that a stack or a tree might be useful to solve a particular problem. (You could use either one.) And then writing out code to do it.

So, no esoteric data structures, but you really do have to know how to use the standard ones. It tends to trip up people who might have some book knowledge of CS but don't know how to apply what they learned. There's also a difference between knowing that a tree might be useful and being able to actually write some code to build a tree.

But the thing is, the next interviewer will have different preferences - there's no standardization here.

[Retric]

I have had many people with 3-5 years of 'experience' developing not know how to find the smallest element in an array. Initially I was thinking it would be a quick check to see if people thought about null values, but apparently this is a hard problem...

Now they might have been useful for something, but I suspect they are just playing the numbers game and showing up to a lot of interviews until they get in. So even if say 5% of coders are useless that 5% is vastly over inflated in the interview process.

[arghnoname]

I think it is interview paralysis. They can't believe an interview answer is ever supposed to be O(n). I've had it happen to me where I get tripped up on relatively easy problems because the initial easy solution I came up with wasn't sufficiently clever and magically log n or some such thing.

[new299]

I can't believe it's just interview paralysis to be honest. I've had people try and solve problems like that with 3 nested loops. Completely failing to come up with a working solution after 20 minutes.

I've been in situations where those kind of people have been hired too. Their code tends to be quite bad...

[Retric]

Any suggestions for dealing with this? I try and keep things as relaxed as possible to start with and make it clear that trivia and syntax is not what I am going after.

I would walk out of the room, but I am happy to walk someone though most of a problem they are not getting. The goal is going from an understood problem to actual code.

[cwilkes]

In addition to the obvious have the person walk you through what they are going to do try rewording it slightly. In this case ask for the max value.

Maybe they are nervous and focused too much on the minimum part of this that they lose sight of what they are trying to solve for. But be careful not to spoon feed it to them.

[lawnchair_larry]

It could also be that you only ever have to do this between 0 and 0.00001% of the time in the real world, and many people who could do it just fine if they are given space to think about it or refresh their memory, which usually results in freezing up during a stressful interview. They probably haven't exercised that knowledge because they have been too busy building real things.

[xiaoma]

How would you filter those "many people who could do it just fine if they are given space to think about it or refresh their memory" down to the number you need to hire?

This is a serious question. I hate the way interviewing works at tech companies. Though I've generally done well and it helped me break into the industry as an outsider, it's a really time-consuming and wasteful process on both sides. So far, I'm leaning strongly towards Reid Hoffman's suggestion of weighting references much more strongly than interviews but it's hard to say how far one can safely go with that approach.

[microcolonel]

That seems like a lousy excuse to me. As a web developer, my entire job revolves around computing trees; and that is (as of now) the most common development environment in the world. My side projects (graphics demos/toys, a multiprocess text editor, various twilio SMS utilities, a high-performance pastebin server) end up using stacks, trees, hashmaps, and bloom hashes as logical responses to the problem descriptions.

Only somebody who doesn't write software for a living would claim that "between 0 and 0.00001% of the time in the real world" should these techniques be readily accessible in working memory.

As for "freezing up during a stressful interview": is that not some indication of what normal workplace stresses will do to your ability to complete technical work? I certainly wouldn't want to work with somebody who is knowledgeable but will wimp out the moment you ask them a tough question on the spot.

[vonmoltke]

> As for "freezing up during a stressful interview": is that not some indication of what normal workplace stresses will do to your ability to complete technical work?

To add to roganartu's very good point about what filtering for that says about your company, you seem to be buying into the pervasive myth that "stress" is some universal and fungible thing. The stress of an interview is not of the same nature as the stress of, say, having a key server go down and take your company down with it. It's a fool's errand to think you can manufacture stressful situations in an interview and get a read on how the candidate would perform in a real situation.

[roganartu]

> As for "freezing up during a stressful interview": is that not some indication of what normal workplace stresses will do to your ability to complete technical work? I certainly wouldn't want to work with somebody who is knowledgeable but will wimp out the moment you ask them a tough question on the spot.

I would argue that a workplace that is continuously stressful is not healthy, and optimising your interview process to filter for this is probably not a great idea.

Additionally, I would expect that when asked a "tough question" at work that you would have both the time and resources available to find or determine the answer, things that one likely doesn't have in an interview (and certainly not to the same extent).

[ivanhoe]

Not sure what do you mean by computing trees in this context, but I personally as a web dev for 15+ years have never-ever had to e.g balance a binary tree or do any other low level operation of that kind. It's important to learn it at some point to be able to understand how it all works, but afterwords you just don't write the low level stuff yourself, ever. If given enough time I'm pretty sure I could come up with some solution for reversing a linked-list, probably even the optimal one, the same way I could probably also figure out how to fix my car when broken... but that doesn't make me a mechanic

[microcolonel]

The solution to reversing a linked list should be self-evident to anyone who makes an attempt.

    #include <stdio.h>
    
    typedef struct Node Node;
    struct Node {
      int data;
      Node * next;
    };
        
    Node * reverse_linked_list (Node * node) {
      Node * prev = NULL;
      Node * next;
      do {
        next = node->next;  
        node->next = prev;   
        prev = node;
      } while ((node = next));
      return prev;
    }
    
    int main () {
      Node * node;
      Node nodes[3];
      nodes[0].data = 0;
      nodes[0].next = &nodes[1];
      nodes[1].data = 1;
      nodes[1].next = &nodes[2];
      nodes[2].data = 2;
      nodes[2].next = NULL;
    
      node = nodes;
      do {
        printf("%d", node->data);
      } while ((node = node->next));
    
      node = reverse_linked_list(nodes);
      do {
        printf("%d", node->data);
      } while ((node = node->next));
    
      return 0;
    }

Or something thereabouts.

[skybrian]

I've never had to balance a tree either. But typically it's because the tree represents something essentially tree-shaped and preserving the structure is important. (For example, what would it mean to balance a DOM tree? Nobody would do that.)

On the other hand, I hope you're not saying that the DOM is the only tree you ever use and in 15 years you've never needed to build your own. If so, consider that companies might be interviewing people for programming jobs that aren't like that.

[lawnchair_larry]

Are you not aware that most languages provide that for free? Note that the question was about implementing, not using. People use them all the time, but they don't reinvent the wheel to do so when it is in the standard library and has nice abstractions already.

Why is a web developer implementing a DFS by hand every day? I would not hire that person.

[skybrian]

I'm not sure what you mean. I don't know any languages where you don't have to define your own node if you want to implement a new kind of tree, and write a bit of code to recurse over it. (In JavaScript the most common tree is the DOM, but you should still be able to build another one if you need it.)

Also, in an interview it's perfectly fine to say you'd use a library, if you know one that applies. (They might ask you next how you'd do it without a library, but you still get points for knowing about it.)

The other thing to remember is that everyone is effectively grading on a curve, and with practice you get better at interviews.

[berntb]

On one hand -- sure, I've sadly forgotten most of the math I ever learned.

But on the other hand, no. I can bounce around modelling with basic data structures (hashes, arrays, structs/objects etc) in my head like a good juggler can treat 3 balls.

I think that is normal for quite a large subset of developer work. I assume there will be some jobs that won't need those data structures, but can't think of any. (Graphics and game developers would remember more math, of course.)

The description in the GP sounds more like the (probably false) stories about the Japanese English education: People with a vocabulary of 40K words that are unable to order coffee or talk about the weather.

[ng12]

Anecdotally, I've learned to expect nothing. I used to ask a graph-based question -- I had to adjust it so that the first step was doing a dead-simple DFS. This tended to weed out a good sixth of candidates and save us both a lot of time. And this was pretty constant against education level and background.

[somedangedname]

DFS == Depth First Search?

[ng12]

Yeah, given an acyclic graph print out each node's value. Passing candidates generally got it in five minutes.

[jnordwick]

Sometimes I get these questions in interviews and I really don't know if I should be offended. My resume is pretty good, and I wonder who T.F. applies to these places that they have to have such simple weeder questions. Then I get all paranoid that there is some hidden complication and soon I'm producing FizzBuzz in TensorFlow:

http://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/

[vacri]

I think you shouldn't be offended at interview questions around skill unless you've been on the other side of the table. It's eye-opening, the range of people that apply for these positions.

[kirab]

Should every node's value be printed out exactly once and if so, are there nodes which have two parents?

If so, I would keep the pointers in a set to mark nodes as processed but is there a more elegant solution?

[ng12]

I would explicitly tell them that you should revisit nodes, and give them a few examples illustrating that point -- so all they needed to do was traverse edges.

[drakonandor]

Each node is an object and has a "checked" variable.

[dastbe]

Do you give them a graph data structure or something that is explicitly a tree?

[dnautics]

A acyclic graph is isomorphic to a tree, but the way you access the vertices and edges is completely different.

[palunon]

Depends on your memory representation of the graph. If you simply use the obvious one (a node have a list of pointers to its successors), I don't see the difference except for successors[]/children[]

[sheeshkebab]

was writing DFS from scratch ever needed to perform dev job or was it a thing that stumped 95% of applicants (and let you read some hacker news/email on your phone/laptop in the mean time)?

[morgante]

If you ignore the terminology, DFS is basically just recursively walking a graph, something which actually happens all the time in most dev jobs. I'm sure I wrote a DFS long before I had heard the term.

I hate brain teaser interviews as much as the next guy, but being able to do basic operations on basic data structures is pretty much the minimum to be a developer.

[vonmoltke]

> If you ignore the terminology, DFS is basically just recursively walking a graph, something which actually happens all the time in most dev jobs.

In ten years of full-time professional development I have never needed to recursively walk a graph. Hell, the only data structures in the software I worked on for the first six (real-time signal processing code) didn't use any data structures other than lists, arrays, and C structs. I would not be able to answer the interview question that started this subthread, despite my track record of efficient and well-designed code.

[ng12]

It only stumped the candidates that clearly wouldn't make it through the rest of the problem. One sixth was a probably a high estimate.

DFS for an acyclic graph is about five lines of code and shows me that you A. know a programming language B. can figure out a data structure. I would argue both are needed to perform a dev job.

[ap22213]

I've written DFS about 1-2 times a year, on average, for the last 15 years. Why do I need to? Usually, because I need to modify or create a data structure that is kind of graph-like but not quite. If someone didn't know how to write one or at least derive it, they would confuse a lot of people, so yeah it's kind of important.

[lawnchair_larry]

No, they'd probably look it up, skim a blog for a few minutes, then figure it out and promptly forget. This is no different than forgetting the order of the arguments to socket() and accusing that person of being incapable of writing networking code.

[DontGiveTwoFlux]

Eh, I had to write a DFS the other day at work.

[arcanus]

Weird. No one else would want a scheduler to be FIFO, either. Rather, the actual optimization that is performed by slurm, pbs, etc. under the hood is pretty interesting.

The point of schedulers is much more complicated than a straightforward queue, as they seek to project how best to utilize system resources into the future.

Strange he would be so pedantic. Everyone in HPC certainly does call it a queue, as you noted.

[dekhn]

Common problem with programmers: when they learn a term means something, they associate that term absolutely with that meaning (common in other fields with people who are highly analytical, IME).

The HPC people are referring to a "job queue", rather than a "ADT queue". Those are distinct things, the ADT queue is a much more restrictive defintion, but it's not an exclusive one. HPC queues are more like priority queues with complex ranking functions (and queues of queues), just like real-life queues where people can cut by paying more money (first class airline ticket).

[conjectures]

Yeah, because it is a queue in the ordinary English sense.

[nolok]

> Like what a tree is or fizzbuzz? Hopefully it isn't that terrible...how someone can make it through any amount of CS related schooling and not know the basics?

Ah! You're in for some surprise down the line. Fizzbuzz almost always clear out large amount of applicants.

[basseq]

I was a CS major, but my career took a different direction, and I haven't programmed "professionally" for 8+ years. I looked up the FizzBuzz question and wrote some psuedocode in about 5m.

It's sad that FizzBuzz is such a "weeding out" tool, but I guess good to know that I can still pass the first round of an entry-level technical interview!

[nolok]

FizzBuzz (from the point of view of me as an interviewer) is not so much about knowing how to code, but understanding the thought process about basic problem solving. Read the instruction, provide a solution, don't over engineer. It also provides the basics, loop and conditional.

Once you're set on that, you at least know you have a person in front of you who, on the basic level, thinks like a programmer.

So I would say 8+ years doesn't matter so much and you shouldn't worry about that, as long as your mind can still "tick" the right way.

[vacri]

We had another applicant just last week with a shiny spiral-bound resume that looked good, but couldn't do FizzBuzz.

[ap22213]

In the last two weeks I interviewed three candidates with masters of science C.S. None of the three knew the memory size in bytes of a double precision floating point variable. None of the three could explain scenarios in which they would use an array over a linked list.

[probably_wrong]

I don't think that first question proves what you think it proves.

Learning implementation details about a specific programming language is not what CS is supposed to be about (see the quote about astronomers and telescopes). In fact, if you use several programming languages at the time, I'd go as far as to call it a waste of my time - if I'm worried about overflow for a specific problem, I can get the range of data (in which programming language? which architecture?) in 30 seconds online.

I can see it being a valid question if you are working in a problem down to the bit level. But those are getting rarer, and ultimately it's what an Engineer excels at.

The second question does seem fair, though.

[scatters]

sizeof(double) is not specific to any one programming language or architecture; it's determined by IEEE 754, an international, cross-language, cross-platform standard. Non-IEEE floating-point implementations are exceedingly rare nowadays (although they do exist).

You're right about it being engineering, not computer science, but IMO it's reasonable to expect someone applying to a programming job (assuming this is what it was) to have at least some software engineering experience.

[kirab]

Well..

  C and C++ offer a wide variety of arithmetic types.
  Double precision is not required by the standards
  (except by the optional annex F of C99, covering
  IEEE 754 arithmetic), but on most systems, the
  double type corresponds to double precision.
  However, on 32-bit x86 with extended precision
  by default, some compilers may not conform to
  the C standard and/or the arithmetic may suffer
  from double-rounding issues.

[daemin]

So a reasonable answer could say - usually 8 bytes - but sometimes with extended precision it could be 10 bytes, etc...

I am actually kind of sick of the people that say these details are not important to being a good programmer. They absolutely are, knowing fundamentals of the machine, language, and environment that you are developing in is essential.

[scatters]

ap22213 (OP for this thread) was more precise than I was; they actually wrote "a double precision floating point variable" rather than writing "double", which could either be a shorthand for "double precision floating point" or be referring to a platform/language type (where that exists by that name).

[ap22213]

The particular positions that I'm hiring for require certain kinds of knowledge, unfortunately. When one is dealing with Petabytes of structured signal data, it's helpful (but not required) that someone know memory layout. But, it's not the first question I ask.

Usually, I start off with some behavioral, get-to-know-them type questions. One of these is to ask them to recall the 'best software developer' that they've ever worked with. The great majority of candidates actually say themselves which is unexpected (and a little arrogant to me - weren't we all 'junior' developers once? - didn't we all once look up to someone?). But, surely one of the best would know when to use an array and when not to or know the memory and precision impacts of the variable types that they use.

[CJefferson]

The floating point I think comes from C bias.

In C you kind of have to know the size of a double -- you'll call "sizeof(double)" fairly often, you'll notice the number in your code.

In most languages, you don't have a way of knowing the size of a double -- and furthermore the size a double takes in your code won't be sizeof(double) anyway, it will be much more.