Hacker News Reader

Comment by tptacek | Hacker News Reader

This is a fun puzzle, but it's not clear to me how this selects for people with the aptitude to perform well in any particular software development job, as the number of times I've been asked to determine is a string is/contains the concatenation of two dictionary words is I think zero.

Instead of doing stuff like this, you can just give candidates realistic programming challenges and have them write code. You don't even need to be in the room with them; after all, you won't be when they're actually doing the work.

View on HN

"work sample test"

I've given this same advice for _years_ for designing technical interviews. Take a problem that you or your team has actually faced in the last n months. Distill it down to remove tribal knowledge and get it to something you or a capable colleague can hammer out in m minutes. Give the candidate 3m minutes to solve it. Typically this means it should take you 15 minutes to solve and give them 45 minutes.

Our biggest hit for a question that followed this for an SRE type role: we had a cron job that was legacy and buggy and caused a couple of issues over 6 months. We went back and created a very similar script with very similar bugs, added some similar data and re-seeding scripts, and told the candidates "customers say that feature $x is not working, and that is ran by this script. Here is how to run it, here is the user's id that can be found in the data seed." We added some other data validation problems. After they fixed it, we asked them what they would do to make this more production safe and dig in on what they have and have not done for improving existing systems. We expected discussions on structured logging, metrics, alerting, testing, code layout, etc.

Over time, the roles that you are looking to fill and the weaknesses on the existing team that you want to shore up will change and you will need different interview questions. Maybe more towards distributed systems or more towards testing or observability.

3m -> 30m presumably?

> get it to something you or a capable colleague can hammer out in m minutes. Give the candidate 3m minutes to solve it

I think they're using "m" there as a variable, to frame that you should give the candidate 3 times however long it takes for an insider to solve it.

The usage seems inconsistent. I will check and report back to the Hive

> Typically this means it should take you 15 minutes to solve and give them 45 minutes

They mean 3 x m where m is how much time you think it would take for you to solve; so the example is: if it takes you 15mins, then give the interviewee 3 x 15 = 45mins

Sorry, missed this. Thanks

3m minutes is already shy of 6 years. I know that tech interviews are long but this is excessive.

This is the right answer. Questions of this type test for both experience (what you want from non-junior candidates - the fact that they have learned to program defensively, check edge cases, etc) and common sense (what you want from junior candidates - not making silly simplifying assumptions, thinking divergently about what could go wrong, etc).

Importantly, it also allows you to examine fluency. The candidate who can write a code/pseudocode solution as fast as they can type, and explain it verbally at the same time, is much more impressive than the candidate who pauses for a long time before starting haltingly and unconfidently. Fluency in solving leetcode problems just tests for having practiced leetcode, but fluency in writing real code tests for actual productivity.

If you have a question like this, you can drill down into performance characteristics just as the question in TFA does. Not necessarily using big-Oh notation, but "what if you have to do this millions of times? what if you have to provide results immediately? what if some of the files are too big to fit into RAM?". But you can also drill down into other aspects of the problem like changing specs, noisy input, constrained resources, observability.

FWIW, when I came up with a question like this (with the constraint that it had to represent a problem I had solved that morning), ChatGPT was not able to solve it correctly.

> Our biggest hit for a question that followed this for an SRE type role: we had a cron job that was legacy and buggy and caused a couple of issues over 6 months. We went back and created a very similar script with very similar bugs, added some similar data and re-seeding scripts, and told the candidates "customers say that feature $x is not working, and that is ran by this script. Here is how to run it, here is the user's id that can be found in the data seed." We added some other data validation problems. After they fixed it, we asked them what they would do to make this more production safe and dig in on what they have and have not done for improving existing systems. We expected discussions on structured logging, metrics, alerting, testing, code layout, etc.

No wonder it is a hit. It is an actual problem that makes me want to go for it - I want to take an interview like this, instead of the usual of dreading interviews! Keep it up.

One of the things I learned in the classical music world is that the things we ask people to do in auditions–play the hardest parts of all the most difficult orchestral music without any context–is really creating a new problem that doesn't need to exist.

And in my experience listening to auditions over the last several decades, what you have now is a bunch of musicians who can only do what's on the test. When you try to plug them into an orchestra, they are completely fucked.

My experience interviewing and hiring tech people is that this is one of the worst possible approaches. Anyone who needed to could figure this out. It's not relevant. What you need to figure out in an interview is if the person is curious enough to find the answer.

I don't ask for code or algos in my interviews. I ask about the person. What's your favorite programming language? Why is it your favorite? What do you not like about it?

What's the project you are most proud of? What was hard about it? What made you happy? What did you find challenging about that project?

These are 100% totally humane questions that tell you everything you could possibly need to know about a candidate in about a half hour. Maybe less.

If you can't figure out if this person is technically competent from this set of questions then you aren't competent to interview or hire.

Interviews don't have to be only about how good you are at interviews. They could be about trying to understand if the person would be good at the job and fit in well with the team.

I think your approach is fine, but I should mention that it will, like any interview approach, misfire with some people.

Episodic recall and emotional recognition are both talents that vary across the population. If I want to do well at an interview like this, I will have to spend a bunch of time in advance refreshing my memory of various projects I have worked on so that I can simulate a neurotypical response to those questions. If I don't, I may just stare at you nervously and break out in a sweat when I realize I don't have anything filed under, "project I am most proud of". Or that pulling up the narratively engaging details of a project I haven't thought about in years is a process that will take me hours of specific effort. And it's not just me; I've hired great developers who were also terrible at "humane" interview questions but who did great when we just sat down and coded together.

Interviewing is a separate domain from programming, and everyone should brush up, be prepared, before interviewing.

I usually have a project or two that I can speak-to in depth, to give examples of decisions made, challenges handled.

I agree this is true, but I think that's in contradiction to the notion that one can just ask some breezy "totally humane questions" and then make optimal hiring decisions. The more separate the domain, and the more preparation helps, the more you're testing for something pretty different than the work.

You don't make "optimal" hiring decisions by just talking to someone. I would say whether your hiring decision was optimal can only be judged in hindsight. Hiring is getting a limited pool of people and filtering down to find the ones that fit the role most.

In the end all you could actually do is guesstimating who would do best at the job. And sometimes the answer is: "none of the ones who showed up".

If you are a good engineer or programmer yourself you can tell a lot about a person by talking to them for an hour. You can learn what is important to them in the craft, how they deal with criticism, what they aspire to, what kind of problems they tend to work on, if they are more autodidactic or more influenced by other's opinions and so on. This is all knowledge directly inpacting the question whether they are the right person for the job.

And who the right person is depends on the job, so there might not be "right" answers to the questions. For a very niche database job you might actually want someone who is very accurate, very in the detail and very focused. For other jobs maybe some entirely different traits are better.

Of course the problem here is that the people you hire could just be very good actors or liars who cannot do the things they say, so a little technical testing might also be needed.

I think the issue is that, and I'm paraphrasing something which someone else said but which I think reflects what I've seen, nobody (at least in larger companies) wants to be responsible for a bad hiring decision.

While yes, you can get someone who has a good track record of being a good judge of character to make hiring decisions. If that decision goes wrong and the blame game starts then you inevitably ask this person to explain their hiring decision. This person will then reply: well it was my opinion that X, Y and Z.

In the alternative case where you just get someone to follow a rigid process you can answer: Well he scored well on this exercise and the opinion of the team was in his favour and the work history ticked the right boxes. This effectively dilutes the responsibility. You can no longer blame one person for the bad hire.

Lastly there's also the diversity aspect. With companies increasingly being scrutinized for their hiring practices, "it was my opinion" just gets translated to "this person's internal biases guided the hiring process and as such it was not fair."

I agree this is all making hiring much harder than it needs to be. And certainly you can still find companies where the hiring decisions are made on highly experienced and well honed gut instinct (its the only kind of interview I have been a part of) but it also makes sense how in our increasingly overcomplicated world we are developing increasingly overcomplicated hiring processes.

My recommendation is if you want a sensible hiring process (with maybe a telephone screen followed up by one normal interview) you should stick to smaller and less corporate companies.

Unfortunately, "gut instinct" is just another phrase for "unconscious bias". Sometimes those biases are helpful, some less so. And some can result in hiring results that are unfair enough to invite lawsuits.

I know plenty of smaller, less corporate companies that still use careful hiring processes with thoughtful rubrics. They do that not because of risk avoidance; they are generally still ok firing people who don't work out. They do it because they want to run a fair process while maximizing ROI.

This very thing happened to me recently in an interview. This was my first interview after not having actively interviewed for a few years now, so I was quite rusty. I was asked what some issues were that I worked on at an initial phase of the project and I blanked the fuck out and then instantly went into self-scrutiny and sweating as I spiralled into "oh crap I should really know this" and "this is making me look stupid" and wondering how I was coming across to the interviewer. I have some anxiety problems, that's there too - but point is that if you're not really prepared with answers to questions like these, it can seriously throw you off mid-interview.

I'm sorry this happened to you.

And lots of good developers skew anxious! What in normal life counts as being overly careful or or overly sensitive is just good practice in coding.

That's why I think it's especially important to make interviews as low-anxiety as possible. They'll always be worse than the job, of course, but the closer you get them, the more you're likely to see how people will really perform on the job.

The curse of the engineer, always looking at the worst possible outcome :) I have to work hard not to bring this into my non-work life.

Out of curiousity, did your high school or college teach you much about interview prep?

Both of mine did. Much of their advice was irrelevant (nobody in tech gives a shit about your suit or how firm your handshake is) but they both stressed the importance of preparing in advance to show how good your skills are; and giving thought to cliche lines of discussion like 'what's your biggest weakness?'

I too have to prepare for such questions. I thought everyone else also did.

Not only do I not remember past successes very well, preparing for these questions is literally the first time I asked myself what I'm proud of. I didn't even consider doing this and reject it as irrelevant before. It just never came up.

I have arbitrarily terrible episodic memory, especially so for professional stuff. If I don't have the commit history to check, I have trouble describing what I did in the last month in anything like a lucid level of detail.

I've always had trouble with the kind of behavioral interviews that are "Tell me about a time when . . ." since I can often recognize that I've been in relevant situations but can't for the life of me remember the details (even with time to prepare).

This honestly makes me more nervous about interviews than leetcode shenanigans. At least with those, I know how to improve.

(At work I rely on a combination of having the code in front of me, written notes, and whatever project management tools we have so it's not much of an issue, but most of that isn't available to me in an interview setting.)

From what I've seen, getting a regular job in classical music is difficulty and pressure on a level few of us can imagine. Might be easier to get tenure at Harvard than a rostered spot in an orchestra.

You can be an excellent player with a likable personality and your chances of getting a spot in any high-profile orchestra are still less than 20%.

I think the odds of getting a high-profile orchestra slot are far lower than that.

Source: Multiple orchestra musicians and management speaking about the audition process and the now-defunct myauditions.com website

Process:

Show early talent

Get the right instruction

Get into a preparatory program

Make it into a conservatory

Do well once there

Get a spot in an ensemble, probably lesser-known (not easy) and establish a reputation

See an audition notice with repertoire to prepare, apply

Spend a few weeks or months intensively practicing (on top of other commitments)

Maybe get an audition, realizing the Music Director may be promoting his buddy past these rounds

Travel at your own expense to the audition

Play demanding repertoire behind a screen and respond to any directions

Most likely get rejected

Play in any following rounds

If not rejected, maybe you get a qualifying week rehearsing with your potential colleagues and playing a couple of concerts when the Music Director is in town

If you beat out the couple of stellar artists who've also gotten that far, you may get an offer

Or, the MD's buddy may get the offer

Or, there may be a no-hire

If you get and accept the offer, you are "on approval" for a couple of years at which point there's the Tenure Decision

Can you explain to a non-musician what playing with an orchestra entails? I'm unfamiliar with the challenge.

I love the comparison to music auditions, and I mostly agree with the advice.

I would still require the candidate however to write some code. Something rather simple, not leetcode, ok, not fizzbuzz either, and something that proves their familiarity with at least one language and platform.

I should be a GM by now simply watching chess analysis videos on Youtube, learning the names of some openings etc. I can talk about it all day long. But since I don't play at all (I'm not interested) when I actually do play on occasions I revert to 500 ELO...

You can easily tell a seasoned veteran from a rookie just by looking at them code for a few minutes, working on a simple task. If you can't, you have no business in interviewing others :)

Aesthetic judgements, and the ability to justify and defend them, are very important, but not the only important thing IMO.

Someone who can explain why they love Rust and hate Python (or vice versa) is a convincing candidate but I think you need to see a couple of other things from them. In addition, sometimes you just don't hit on the right question to get evidence of their aesthetic judgement. (Like the candidate who doesn't care about Rust vs Python, but who hates Postgres and loves MariaDB..)

I suspect it's less useful as a "this person will excel" test and more useful as a "this person won't fail miserably" test. Which for most hiring decisions is the more important factor. I would under no circumstances hire someone who couldn't at least get the brute-force level solutions and talk intelligently about performance concerns.

IMO, the disdain from LeetCode from developers vs. its continued use disconnect stems from the fact that we developers tend to assume that the goal of the hiring process is to find the very best possible candidate, whereas the goal in reality is to find somebody "good enough" as efficiently as possible.

The disdain is fueled by companies' behavior. Your approach makes sense, but if that were the case, then a DSA whiteboard interview should be a fail/pass -- a company shouldn't prefer a candidate that managed to cook up an O(n log n) solution over a candidate that only got a solution in O(n2). In my experience, no company doing whiteboard interviews works like that. As OP themselves said in another comment, "it's not a binary yes/no, but gives a range to score the candidate"

At the end of the day, you can't test for negatives and just pick a random person that doesn't fail anything. You need to have a defined set of values to look for in a candidate, and to design an interview that tests for those values. That's why I hate DSAs -- for most (all?) companies, they're treated as dogma rather than a pragmatic solution to a difficult problem.

I don't ask just one question in a DSA interview.

I ask multiple related questions, and if a candidate struggles with one of them, I probe for strengths in other areas.

No one answer to a question in that interview is a pass or fail. But the interview, holistically, is a pass or fail, or a conditional[1] pass.

[1] I was impresssed by some aspects of the candidate, but there are notable, significant weaknesses. Please determine if other interviewers have detected similar weaknesses, or if the candidate just got unlucky with my particular question.

I suspect it's less useful as a "this person will excel" test and more useful as a "this person won't fail miserably" test.

Unfortunately the OP seems to be using it in the former sense (when applied to the tries solution that he things will separate the "good" candidates from the plodding lunkheads).

> ...[companies and interviewers] that the goal of the hiring process is to find the very best possible candidate, whereas the goal in reality is to find somebody "good enough" as efficiently as possible.

I suppose that's why mathematicians came up with the idea of "optimal stopping." There are literally tons of scenarios out there where the goal isn't to get "the very best possible candidate," but to get someone "good enough," or maybe even the best person you can get after putting a reasonable amount of time and effort into searching.

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

You appear to be shadowbanned.

New account.

Huh, well. That's no good. People upvoted me, so I'm assuming it's fixed now. Since you're the only one who's mentioned it, I'm guessing you made it happen, so, thanks. :)

"it's less useful as a "this person will excel" test and more useful as a "this person won't fail miserably" test."

This is also an unproven statement with dubious validity.

I come from the trading world where the leetcode equivalent is a brain teaser. After much deliberation, the only thing we could think of for why a brain teaser was useful was that it often proved someone wanted the job so badly that they memorized all the brain teasers. And that type of dedication and drive is what we really wanted.

To me, I don't understand why someone who develops with advanced IDEs, using complex tools and libraries, is in the least bit judged by putting them in front of what is essentially a text editor, and asking them to solve a problem that's of no relevance to their job, using no tools that they're comfortable with

You can use all the IDEs and tools and libraries you want, at the end of the day you still need to know how to read and write code. If you can't pound out a FizzBuzz-level without help, no amount of tooling, IDEs, or libraries is going to make you capable of developing software.

Period. If someone tells me they can develop software in a language, and they can't write ~10 lines of code, that tells me they lied. It's like when getting lifeguard certified they require you to dive down to the bottom and grab a brick. Nothing at all in the day-to-day job of lifeguard requires retrieving submerged bricks, but the set of people who possess the swimming skills to be a lifeguard is fully included within the set of people who dive to the bottom to grab a brick.

Thanks for the brick example. I'm going to use that a lot!

Lifeguard here. The brick is actually part of lifeguard training, at least where I'm from.

At least for Red Cross certification, the training is a mix of teaching and test. The basic swimming skills are basically a test, as it's incredibly unlikely that someone would develop those in the 2-3 days that the course runs.

When I was a young lad you had to pass basic, intermediate, and advanced swimming classes before signing up for the guard class. Each class took about two weeks of daily lessons at the local pond.

This qualified me to sit next to a pool in a condo complex where no one ever swam for eight hours a day. Best job I ever had.

It's just as easy to analogize it as picking up a brick is to lifeguard training as it is to say it's swimming in melted chocolate is relevant to lifeguard training.

Your question has no scientific justification. It just is a problem you can do, and you like yourself and think you're awesome. So you think it finds people like you. But even that isn't scientifically supported.

If you think trying to use machismo like declaring your opinion as fact with a "Period" emphasis is somehow a substitute for evidence, then you're talking to the wrong person.

I'll take someone whose Github repo shows talent, dedication and passion, but who misspelled an include header in their brain teaser over the inverse any day of the week. But you do you. Neither you nor I have a lot of evidence to support our preferences either way.

You are either deliberately misinterpreting what I'm saying, or are unaware of just how muddy the hiring pool is for software jobs. If you post a software role, you will get a significant number of applicants who will struggle to write FizzBuzz. Not on grounds of misspellings or missing semicolons: they genuinely have no idea how to code. If you have them code for you, it's really not hard to spot.

Digging through a couple GitHub repos is a good way to find good developers versus poor ones. The goal of a leetcode question is to separate the developers from the non-developers. And you can do that pretty adequately with 2 questions: "Tell me about something you've worked on" and "Hack together a solution to this trivial question".

Anyone who hasn’t sat in the interviewer’s chair would be shocked at how many “Senior Software Engineers At BigCo” can’t even write a program that “displays a countdown of all even numbers from 100 to 2, each on a different line.” There is literally no baseline level of knowledge that is a given, like there is for, say, a doctor.

Sure but then why do people do leetcode hards coding brain teasers? This is like asking a journalist to write a sentence that is reversible when you just want to know he speaks English.

It strikes me as counter productive to select for memorization for a job based on research and collaboration. It's easy, but then the whole "software development is costly and error prone" problem looks self inflicted.

This is a decade old story, but I was asked FizzBuzz for the first time without knowing what it was, and got it fundamentally wrong. This was three years into a career in which I alone had written a full equity arbitrage trading system in C++ that was making millions per year. I had written PDE solvers running in production for 50 traders doing $1bn worth of trades a day. I was not a liar.

The question did not "weed out someone who couldn't code." It weeded out someone who couldn't use a totally unfamilliar dev environment while being stared at and asked to "walk me through your thoughts" instead of letting me think. It left me distracted, thinking both "this is easy, what's the catch" and "wtf is the point of this?"

"Tell me about something you've worked on" is a totally fine question. I'm not arguing with that. But anything leetcode is not, IME. This becomes increasingly true as people's careers develop. If you've spent your last two years writing hyper low latency deserialization engines and packet processing, then you'd know that's what the job is about. In the macro, trading engines and game engines are one medium leetcode problem from an algorithms point of view, but they require teams of people and years of optimization and customization to make truly effective. I don't want to test for the person who can make a really basic solution in 30 minutes. I want to test for the person who can optimize a tiny fraction of it in 2 days.

That’s a disingenuous argument enabling somebody with a massive ego problem.

1) most people here, I believe, don’t have a problem testing a developer’s code writing acumen.

2) People weigh something. Bricks weigh something. It’s the same exercise. The analogy in software would be the difference between asking someone to write _an_ function that can do x vs write _the_ function your company uses to do x.

3) the lions share of counterarguments here propose using real world exercises vs toy problems

I think you're missing the point of the comment about tools.

Programmers skew anxious. In theory there's no difference between writing basic code on a whiteboard and writing it in an IDE. But in practice, an interview is a novel, high-stakes environment with a bunch of judgy strangers. So if you then have people do the interview using tools that are unfamiliar, a notable percentage of them will be thrown off.

Once I switched to encouraging people to bring their own tools (own laptop, own editor, preferred language), I saw a marked decrease in people bombing interviews. Some of the people you might have put in the "they lied" bucket were, at least for me, just ones who got really nervous and so were unable to grab the brick.

To me, that's a bad interview, because the job isn't going to be high-stakes whiteboard coding. It's going to be sitting quietly in a comfortable and safe place and gradually improving things. The more an interview can be like that, the better.

Isn't the brick test pretty close to a work-sample test?

I've always assumed the brick was meant to simulate a drowning swimmer, whose rescue is pretty clearly part of the lifeguard's job. I guess a mannequin would be more realistic, but it still seems pretty close.

It selects for people who prefer solving puzzles to doing work. Source: I am one.

I prefer solving puzzles -as- my work. If I’m not doing work that gives me the opportunity to take a Problem Solved Victory Lap every once in a while, I don’t want the job.

I can tell you the reason for the continued use of leetcode (or similar) at my company. We started giving junior candidates a leetcode-ish test with a low bar for passing to screen out really weak programmers. Everyone who passed went on to on-site interviews. Interviewers complained about having too many interviews to do. So the recruitment team just cranked up the score required to pass. Bingo, less work for interviewers.

Sadly everyone who makes it to an on-site is now a competitive programming enthusiast who is probably a really poor fit to actually working in software development.

Many people are vaguely aware of this problem, but nobody has a strong incentive to put in the work to come up with anything better.

I agree that leetcode questions are great for quickly eliminating bad candidates, but this question has the classic problem of being way too hard. Like 50% of leetcode questions are difficult dynamic programming problems (why the obsession with dynamic programming?). Even in the most algorithm heavy job I've had which actually did involve coming up with novel algorithms there was 0 dynamic programming.

And most programming jobs involve no complex algorithms at all. At most you have to be a little careful to avoid N^2 occasionally.

Leetcode is great for filtering out bad candidates but if your solution involves dynamic programming it is too hard for an interview.

At least in my experience dynamic programming only comes up when I'm studying for interviews. Of all algorithms common in interview questions, I think DP has the highest ratio for occurrence on whiteboards vs occurrence in most software development jobs. I understand it's fun when you spot the solution but I think it only really proves your candidate did their homework

You are correct in that. A few points though:

- While DP might be rare, memoize is quite common alternative. Sticking a @functools.cache in Python for example. They are functionally equivalent in many cases,

- I believe knowing their data-structures and algorithms is the difference between an okay programmer and a good one,

- When interviewing entry-level software-engineers, there's not much else you can ask them except for what they learned in class, which is these kinds of questions.

> I believe knowing their data-structures and algorithms is the difference between an okay programmer and a good one

For me, the difference between and okay programmer and a good one is: how much Linux/Unix they know (processes, core system calls, networking, sockets, awk/sed/bash). Whether you are writing apis for ecommerce platforms or writing custom k8s providers, Linux knowledge is a must. Knowing how to implement a trie? I bet most of us have never been in that situation.

That depends on what kind of system you are developing. For example if you're writing APIs for e-commerce platforms you may need to know how to tune a container's CPU and memory limits but not the difference between cgroups v1 and v2.

Likewise, there are jobs where being able to reason on complexity and data structures is important.

We have developers writing APIs for e-commerce platforms that don't know a lick of Linux, thus proving it's possible to write code without knowing how to deploy it.

But then how are you gonna have a one-person IT department if your developer doesn't know Linux?

Ecommerce? Linux? Wtf?

Those are fair points and you also said you didn’t expect them to implement DP. I’m curious what your minimum expectations are for the candidate to solve. When I ask these questions it’s usually about the journey more than the destination (which I believe you mentioned in the beginning) but I’m guessing you’d at least expect the candidate to come up with the brute force solution.

I think the difference between a good front end developer and an ok one is how they understand about what goes on under the hood of React.

Your broad strokes don’t account for the domain knowledge of a job. If all you’re doing is interviewing college grads, then I guess you have no choice, but this interview question sucks in just about any other context.

> While DP might be rare, memoize is quite common alternative. Sticking a @functools.cache in Python for example. They are functionally equivalent in many cases

They're not just functionally equivalent. They are the same thing. There are two things you need for a dynamic programming solution:

1. You remember the answer every time your function is called. ("Memoization".)

2. You structure your function calls so that they will ask for a lot of answers that have already been computed.

What you don't want is: say you're computing the sums of contiguous subsections of an array. You've already figured out that indices [2:5] sum to 3 and indices [5:8] sum to 8. When you need the sum of indices [2:8], you need to make sure you get it by asking for sum(2,5)+sum(5,8), and not by asking for sum(2,6)+sum(6,8).

> They're not just functionally equivalent. They are the same thing. There are two things you need for a dynamic programming solution

At a high level they are the same, but it makes sense to distinguish between the techniques based on whether you need random access to the already-computed data.

For example, if you are computing the nth fibonacci number f(n), a DP solution needs only the state f(n-1) and f(n), but a typical memoized solution keeps around all the state f(1) through f(n-1). For tougher problems, you can't always convert between them trivially while keeping performance the same.

> if you are computing the nth fibonacci number f(n), a DP solution needs only the state f(n-1) and f(n), but a typical memoized solution keeps around all the state f(1) through f(n-1)

That's all true, but is it comparing like with like?

The "generic DP" solution to the problem is to allocate an array of n elements and fill it in from f(1) to f(n). That's the same amount of storage the "typical" memoized solution uses; cutting it down to an array of 2 elements plus an (implicit) offset between the part of the array that's in use and the full array seems to be an optimization on top of the DP solution.

You could apply the same optimization to a memoized form of the solution. I certainly agree that you most likely wouldn't do that, but you could.

What do we learn by comparing a tightly optimized DP solution against a "typical" memoized solution? Why do we give the DP solution credit for not using what it "doesn't need" while penalizing the memoized solution for what the programmer probably added unnecessarily?

I came to the field from a slightly different direction; I never studied DP in classes (I was a bio major) but used them extensively in my undergraduate research and later when implementing a few toy bioinformatics algorithms (it's a real joy when it works for the first time!). Even though I've written them a number of times, I really doubt I'd ever be able to spot a DP problem and solve it with that, without some hinting. I do not think it provides useful signal unless you're looking for people who will be writing algorithms.

> dynamic programming only comes up when I'm studying for interviews

I worked a SWE job years ago which was heavily reliant on dynamic programming and string search/alignment/etc. It really depends.

It always depends, but I think we can safely say that it doesn’t come up in the _majority_ of jobs.

But even if the job actually requires solving puzzles like that one, what's the point of asking the candidate to solve it in 45 min? Without googling? That's what it's actually totally unrealistic.

Give me any problem related to algorithms+ds to be solved in 45mins without internet access and someone looking over my shoulder and I will give you a poor solution. But give me a day and internet connection and I will solve the problem in the most efficient/readable/maintainable way possible.

It's especially ironic that this puzzle structure selects away from candidates whose ordinary method would be to look up available algorithms, rather than just going with the best answer they came up with off the top of their head.

That actually explains a lot of Google.

To be honest the first solution is literally one line of code. The data structures are those included in Python, there's nothing to look up. It's an important skill to take some code written by others and understand precisely it's performance characteristics.

The interview question is not just about knowing data structures and is not about Behdad showing off either. It's the starting point for a Socratic discussion.

> To be honest the first solution is literally one line of code.

OK, but every program is literally one line of code. We only put line breaks in to make them easier to read.

The author makes this terrible comment about his "one-liner":

> Most candidates though write a for loop, which is equally acceptable.

He has also written a for loop. Specifically, he's written this for loop:

    for i in range(1, len(s)):
        if inDict(s[:i]) and inDict(s[i:]):
            return True
    return False

Yeah, that's the part that tripped me up. Looking down on for-loops immediately after showcasing their for-loop solution!

It was not uncommon for speech synthesis systems to have an algorithm much like the one in the interview question to pronounce e.g. words in URLs ("ycombinator"), brand names ("Bitcoin"), or words in languages that like to agglomerate ("Donaudampfschiff"). Admittedly, though, this task is increasingly being delegated to machine learning models.

I actually have had to solve a version of this problem on the job. There was a database of tagged photos; for some reason all the tag strings had had their spaces stripped. So you had to efficiently find a probable chunking into words. (Of course the original text wasn't always all dictionary words.)

OTOH re the concern for O(n^2) time when n is bounded by word lengths, and when the inner loop was in already-optimized string comparisons in your language's hashtable library -- I think that part is very artificial.

> OTOH re the concern for O(n^2) time when n is bounded by word lengths, and when the inner loop was in already-optimized string comparisons in your language's hashtable library -- I think that part is very artificial.

Yes! The candidate already optimized for the important thing (which the author forgot about and added in a footnote), which is that the list of words could be very long, and that the words in an English dictionary are relatively short.

Optimising for the important factors based on an assessment of the problem domain is actually a more important skill than regurgitating the best algorithm from the book. If the author wanted to suggest a solution suitable for very long needles, he should have used a different domain like, say, gene sequencing.

It was an ok question until around 2015 when i started noticing junior-ish candidates blurted out “trie” immediately and proceeded to write very crappy code for it. In short, it got gamed by the lc types into oblivion. I changed my strategy then to ask very simple algo problem (i would explain the algorithm) with ~20 lines of code solution then aggressively rejected candidates who weren’t fluent in their choice of language. Pros were it was immediately obvious in first two minutes if they coded day to day or just copypastad SO, cons were that it probably was biased against the nervous type. Not my fault though the latter group got shafted by the leetcoders

I am not sure about this particular puzzle but I have noticed that I can learn a lot from observing how to approach such a problem. Even some senior people seem to have no ability to think about solutions. Other people seem to only be able to look up things on Google. I like people who at least try to attack the problem and think it through. I don't care so much if they succeed but I am happy if they are able and willing to think about something they haven't done before. From my experience this bodes well for working with them and them being able to adapt to new things.

I agree. One of the best interviews I ever had was for an iOS position at a company. The interviewer himself had a little bit of experience with iOS development and he lent me his laptop and asked me to write a simple app.

It was great because he was testing the very thing I was going to be hired for. Additionally, he asked how I would design X or Y and I explained the pros and cons of certain designs and I could show him right there on the screen how I'd do it. This wasn't a whiteboard where I'd have to slowly write out code in a medium I'm not used to. I literally was typing on a keyboard, using intellisense, etc.

As someone who does iOS development day to day, it was a very easy way for me to show that I knew what I was doing and the guy was quite pleased when I plowed through all the requests he had.

> just give candidates realistic programming challenges

Not precisely a SWE, but every single piece of code I write at work is more about knowing how the immense codebases are laid out and where to insert my change which is typically simple.

Given this, any "write self contained thing" is unrealistic. The only thing a coding question tells me is whether someone is happy writing simple code to solve a vaguely fun problem.

That still feels useful?

I don’t think it’s super relevant for the challenge to be similar to the day job challenges. Maybe it’s even unclear what those are at the point of interviewing.

What is important is that the candidate’s skills generalize well to both the challenge in the interview as well as the day job. A question like this might be a good indicator or not depending on the job.

If people completely fail at this question it can reveal a lot of relevant information.

We got exactly this problem on my previous job: split #thispopularhastag into words it combined from.

Yeah, once you get the job after the grueling interview you realize that your actual responsibility will be for the "More" button in Gmail. You need to make sure that it sticks to the "Refresh" button at all times, because it apparently likes to drift.

To be fair, if you are dealing a lot with indexes and word tokenization/lemmatization, as Google engineers presumably are, then this seems to be a relatively "real world" problem.

That might have worked before ChatGPT. :)

Unfortunately, I just checked and ChatGPT gives the correct (slow) answer to your question:

    def is_concatenation_of_two_dict_words(word, dict_words):
        """
        Returns True if the input word is a concatenation of two words in the input list of dictionary words,
        and False otherwise.
        
        Args:
        - word (str): The input string to check.
        - dict_words (list[str]): A list of dictionary words to check against.
        
        Returns:
        - (bool): True if the input word is a concatenation of two words in the input list of dictionary words,
        and False otherwise.
        """
        for i in range(1, len(word)):
            prefix = word[:i]
            suffix = word[i:]
            if prefix in dict_words and suffix in dict_words:
                return True
        return False

In general, I don't think that LeetCode questions have any particular advantage over work sample tests when LLMs are involved. Your questions will end up on LeetCode, where LLMs will index them and will be able to recite the answers.

> I don't think that LeetCode questions have any particular advantage over work sample tests when LLMs are involved.

I agree. We do work sample tests, and in addition to the code and docs the candidates hand in, what really matters is the walkthroughs we do with them. Why did they do it that way? What alternatives did they consider? What are the pros and cons? What past projects did they draw on? How did they research this?

Candidates usually enjoy this - most programmers enjoy talking about a just-finished project, especially when they feel good about the result - and you get to learn a lot about them.

If someone turned in an LLM-assisted work and lied about it, I doubt they'd fare well. And if they did use LLM assist - could be an interesting conversation all the same. What did you reject? What did you correct? Why?

You're writing "work sample tests," and I'm hearing "take home assignments." Is that right?

If so, how do you solve the problem of the assignment just taking way too much time compared to a more typical process, where you do a phone screen and 3-5 hours of technical interviews with a behavioral or 2 thrown in there? I know that if you send me a take home that's any like most of the ones I've gotten in the past, and your competitor says I can do a recruiter chat and technical phone screen to qualify for a 4-5 hour onsite, I'm going with them just on the sheer amount of time and effort needed from me for each process.

How do you get around the fact that if you give such a test to enough people, some of them will eventually put it up on Github for the world to see and crib from? Even for those willing to accept the time commitment, how do you account for the bias involved in giving the same assignment to working candidates and people just out of school? There's a good bit of implicit age discrimination going on there, since folks who have been working a while are far more likely to have families than those just out of school. And then there's the old "fraudulent candidate hires someone else who's actually good to do the assignment." Granted, that person won't succeed at the job, but it'll take at least some weeks before most companies will give up on someone they hired, even if they're completely hopeless at the actual job.

I could go on and on, but I think you get the idea.

A) you have developers you already have hired take the tests regularly and make sure they are properly calibrated for time

B) you replace time in interviews with the test you don’t just add it on as another thing.

C) you change the test regularly and implement basic plagiarism filters on the tests you do have.

As a person who has been in the industry a fair bit I think the flexibility of take home work samples gives me a leg up over day long in person interviews (and the last time I interviewed it was multi day not 4 or 5 hours).

I don’t have to take time off of work or not pick up my kid from school or anything. Just do it in my free time.

Yeahhh, I'm gonna need you to fuck right off with all this reasonable attitude you've got about this... lol, (kidding of course.)

Seriously though, you've basically outlined the only reasonable way to go about it. The problem is really that that's a lot of fucking work you're opting into with 3 little sentences, and after all that, you actually end up with a non-repeatable process, which is not really ideal. I'm still highly skeptical that it's not biased toward people without families, either.

But my real issue here is that at least 75-80% of companies that do this crap obviously don't implement any of that stuff, and most of the rest don't do all 3. You really need all 3 in order to maintain any integrity to the process, and that's, unfortunately, one of the strengths of whiteboard hazing from the employer side. I know I'm never doing another 2+ hour take-home again, and the fact that employers generally don't do any of that stuff are more or less my reasons.

I agree that most companies don’t do work sample hiring well. But most companies don’t do any technical filters well. They’ll waste your time with dumb whiteboarding, or leet code or god forbid personality tests.

To me it’s a strong signal if a company has a work sample test because it shows they have at least one part of their process that has a chance to be a good filter. It’s an even stronger signal if they’ve replaced the majority of their pipeline with it.

I won’t say I won’t accept a job that didn’t do a work sample component but it would definitely jade my thinking against the firm. And I’ve certainly told companies I wouldn’t continue with their hiring process after hearing what it entails.

Bing Chat also gave this answer to part 2:

    def is_concatenation_of_dictionary_words(s, words):
        if not s or not words:
            return False
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break
        return dp[n]

It doesn't find the trie (or regex) solutions to parts 1 and 2, though. It also finds the right complexity for its solution for part 1, but when asked for an O(n) solution, it first repeats an equivalent algorithm, and suddenly claims it is O(n) because the hash is O(1).

That said, I believe an engineer with the answers it gave, would easily figure out from its output what the right complexity is. (Figuring out the trie, may not be so easy.)

That said, meanwhile, ChatGPT is not yet at a point where it can write out a full working repository solving a nontrivial problem. It can help, but it is not autonomous; and realistically, if someone can get that help to reach a good solution for a test, they can do so for a salary.

Trie is not important at all.

With O(n) memory, precomputing the rolling hash in O(n) time, you can get a hash of a prefix/suffix (or any substring) in constant time.

https://cp-algorithms.com/string/string-hashing.html#calcula...

When I asked, it first gave the for loop answer. I asked it the complexity, it answered, then I asked it if it could find an algorithm with lower complexity and it came up with an answer using a trie, although not the reversed words trie trick.

Better than the candidates I interview would do, and probably better than I would do, I would probably need a hint to use a trie and I haven't analyzed algorithmic complexity in a quarter of a century.

Reply on news.ycombinator.com