The problems with live coding interviews

But the whole point of the "cute solution" is to solve with O(1) memory; if you're willing to allow O(n) then the linked list also admits more sane solutions.

I'm not sure what you mean by comparing "layers" of traversal. Tortoise and hare is about provide a termination condition in the case that a cycle exists. In the case that there's no cycle, every algorithm must inspect each node, so is O(n). In both the linked list and the DAG case, if there is at least one cycle, (a) both pointers will enter it in at most O(n) time, and they will match in at most O(n) additional time, so this stays big-oh optimal.

I'm pretty sure I heard the same point made 20 years ago against using IDEs, with their auto-complete and tool-tips and style feedback.

And 40 years ago in the debate over letting kids use a calculator in school instead of calculating by hand.

A footballer follows a very constrained set of rules. If the footballer were allowed to use a car then 1) it would be easy to score a point, 2) the field would be ruined, and 3) people wouldn't pay to watch or support the team.

If a programmer uses ChatGPT to get a handle on a task with a new API, and saves a day of futzing around, how is that NOT relevant to job performance? (For the sake of argument, let's say that experiment showed that API doesn't scale well enough, resulting in a decision to scrap that approach entirely and use a different API.)

I feel all discussions about the coding interview are missing two critical points: first, how we got here, and second, why are we still here.

First, how we got here. I didn't experience this first hand, so I'm just making a recount based on what I've heard and read from "old timers". My understanding is that before whiteboard, leetcode-style interviews became the norm, tech interviews were mostly unstructured and quite informal. In the really old times (pre 90s) you could get a job just by knowing how to use a computer. I believe this wasn't that unusual in the 90s and early 2000s. I still remember hearing a founder-CEO bragging that his interview process was a 30 min chat with each candidate, and if he liked them, he would hire them.

From what I could gather Microsoft is the first big company that started using these "coding challenges". Then they became wildly popular thanks to Joel Spolsky [1], the publishing of Cracking the Coding Interview [2], and Google made brain teasers world famous.

Second, why we are still here. First, I believe there is a huge cargo-cult factor. Companies want to copy big tech, and alumni from these companies go on to found their own. This kind of interview has been honed and polished over the years, landing in a local optimum. An entire industry of websites and products has been created, and there are many entrenched interests. People might hate it, but the process works well enough for tech companies that they don't need to worry too much about it. Another under-appreciated factor is scale. This kind of interview sort-of scales well, which is important when you hire at a massive scale. That's why things like "have the candidate come to work one day and pay them" won't work for companies that need to screen thousands of people a week. Lastly, a standardized and "well known" process introduces some guardrails that can avoid some obvious pitfalls. The book "Working Backwards" explain how the Bar Raiser program was created at Amazon when a bad senior leader hire used the unstructured approach to hiring to build an empire misaligned with the company. At a big enough company this is bound to happen sooner or later.

Third, where do we go from here? I find it extremely unlike existing big companies will change their methodology any time soon. It might not seem like it, but for a company like Google it would be a massive undertaking to overhaul their hiring process. It would take years to achieve the level of efficiency and effectiveness of the current system, and surely there would be tons of opposition.

I believe the only way forward is for new companies to experiment with other methods of hiring, particularly at the beginning when they are nimble and can experiment freely. As they grow they will face challenges scaling, polishing and standardizing their process. At some point they will become the next generation of Big Tech, and the cargo cult wheel might spin again.

In any event it seems we need some sort of structured approach to hiring where we assess the match between company and candidate.

[1] https://www.joelonsoftware.com/2006/10/25/the-guerrilla-guid...

[2] https://www.crackingthecodinginterview.com/

We’re not talking about whether you should use them at work; we’re talking about whether it makes sense to have an evaluation where you don’t use them. Closed-book exams are similar. There’s no real-world situation where you wouldn’t be allowed to refer to whatever materials you like, but the evaluation uses somewhat unnatural circumstances to gauge how well you’ve assimilated the material in a limited amount of time and with a consistent process that’s fair for everyone.

Actually, now that I spend more than ten seconds thinking about this, I think this requires O(1) space; you only need to remember the single most recent link behind you to avoid following it again. Remembering a single break is sufficient to get you to either the next cycle or (if no more) terminate the BFS; and once you detect the next cycle you can safely remember only /its/ break since BFS will never take you back to the first cycle. Assuming streaming output (e.g. print identification of each cycle as you detect it -- including e.g. printing each node until you see the break point, which will identify each node that is part of the cycle), this is O(n) time and O(1) space, which I believe is optimal.