Comment by pflats | Hacker News Reader

Comment by pflats | Hacker News Reader

> Asking someone who hasn’t been recently exposed to computing theory to write a balanced parentheses recognizer is asking them to reinvent the basic research of people like Kleene and von Dyck, extemporaneously. And then write code under the interviewer’s watching eye. That is unlikely to show these candidates in their best light, and the results become very uneven.
> Outside of a special-case like certain CS students, this question is likely to give very inconsistent results, and those results are going to be dominated by a candidate’s recent familiarity with the underlying problem, rather than their coding skills.

> In most cases, that makes for a bad interview question.

This only makes it a bad interview question if the goal of the question is to only hire the candidates that can code the solution.

Otherwise, it can be a very good interview question. How do they go about "reinvent[ing] the basic research of people like Kleene and von Dyck, extemporaneously"? What questions do they ask? What ideas do they come up with? What resources do they say they would consult? Under pressure, how do they behave? If they make a mistake, are they coachable? Do they lash out or double-down on mistakes? If they mention using a language's regex, do they understand the performance tradeoffs of various different features?

There is a lot to see by asking the question beyond just "whether or not candidate X can code a solution".

Beyond that, I have taught theory of computation in the past, and I think the rest of the article is a solid writeup. The DPA section might need another pass; that felt the most uneven. Things that jumped out at me:

- If the audience if programmers unfamiliar with automata theory, I am not sure how many would know what a Turing machine, von Neumann machine, or even a program counter is.

- Clarifying what is meant by "internal" and "external" state.

Thank you, that's excellent feedback.

There is no program counter. Computers don't normally need to count programs. ("let's see, I have calc.exe, that's one, and notepad.exe makes two...")

There is an instruction pointer. Note that it doesn't count. It frequently is incremented, but it can jump forward and even backward. It points at an instruction.

https://en.wikipedia.org/wiki/Program_counter

There's a lot of literature that states otherwise. Of the assembly languages I've studied (and within reach of me I have references to the Motorola 6809, 680x0, VAX, MIPS, Z80, 6502, and x86) it's only the x86 line that used the name `IP` (Instruction Pointer [1])---the rest all use `PC` (Program Counter). And (to be even more pedantic) that register (`IP` or `PC`) always points to the next instruction to be executed, never the current instruction being executed. And just to note, on the VAX, the `PC` register is also `R15`, so it can participate in any instruction as either a source or destination; whether that's a good idea is another matter.

[1] Technically, until you get to the 64-bit version, it's `CS:IP` (Code Segment, Instruction Pointer).

There's a lot of literature that repeats a harmful misnomer.

The register is always an instruction pointer, even if the hardware incorrectly calls it a program counter.

The processor that matters most, by far, is x86. At one point PowerPC wasn't too far behind, and PowerPC still dominates in high-end network gear. Both of these processors are correctly documented. For x86 the name is ip, eip, or rip. For PowerPC the name is usually nip, meaning "next instruction pointer". Sometimes the PowerPC documentation will use "current" instead of "next", or "address" instead of "pointer". All of these are correct.

And the processor that matters the most after the x86 is the ARM, which uses `PC`. I suppose all ARM documentation is incorrect then.

Also, in electrical engineering, the direction of electricity is taught backwards from what it really does. In all sources I've read, electricity flows from positive to ground, whereas in reality, it's the opposite. Good luck in changing that.

That's certainly an interesting approach, but in that case I would want to budget a fair bit of time, and not be attached to coding a solution at all.

And again, you want to be aware that you are going to have sharply different experiences depending upon the candidate's familiarity with the basic research.

It would be very interesting to walk through a candidate's thinking about this problem "raw," but it would be grossly unfair to ask the same question of an intern who had studied the problem in the last semester.

I have seen interview questions along the lines of "reinvent basic research," but they typically pick something obscure-ish to reduce the likelihood that the candidate has seen it before, and such things are usually more of the dreaded "whiteboard your thinking," rather than judging you based on the code produced.

Reply on news.ycombinator.com