Hacker News Reader

Comment by glitchc | Hacker News Reader

It is indeed telling that experience does not help with this question. It's a toy problem with no real consequences.

The linked to article explains this is a real problem that the author needed to solve at scale.

(I still think the question is unfair, but my objection is more about the stressful interview situation where the real problem you're solving is "desperately trying to pass this or N other interviews you're currently doing").

The thing I hate about this kind of question is there seems to be no expectation that a candidate will try to dig into the requirements.

What's the function going to be used for? Are we talking about strings of length 32 or strings of length 32k? Is this going to be run a billion times a day or 12?

We're not competing at some contest, we're trying to solve real problems here. I'm not going to waste a couple hours hammering out some ultra-optimized code so the logAnalyzer4000 can run its hourly batch jobs 0.004% faster. If we need it to handle strings of length N with a dictionary of size M comprised of strings from length X to Y, tell me that, and we can plan (and benchmark) based on that.

> It's a toy problem with no real consequences.

It's an extremely simplified but recognizable version of a real problem: natural language input tokenization, which of course has real consequences.

Then this problem is solved by a gazillion of libraries already, no?

Ah yes, I whack out four or five natural language input tokenizers before lunch most days.

This problem was solved by medieval monks by introducing white spaces.

Many languages still don't put whitespace between some or all words (Chinese, Japanese). Many languages tend to use long compound words which are better represented as sequences of tokens rather than one token (German, Russian). Many inputs are dirty (coming from OCR, for example) so whitespace can be unreliable. And even in clean English text, inflected words may be better tokenized as sequences of tokens rather than a single token.

The problem there is that natural language processing is a highly specialized field, not something one can expect a generic SRE to know unless it's explicitly mentioned in the posting. I'm willing to bet the posting said nothing about NLP.

I could ask a detailed question on cryptography, robotics or reverse-engineering, and it would be just as (ir)relevant to the SRE. Computer science is a much broader field than your niche area. Arbitrary goal-posts are arbitrary.

Pretty much every good programmer I know, senior or not, will have no problem solving this unless they have a particularly bad day or brain fart; at worst, they may take slightly more time remembering/reinventing aspects of a trie to work out the optimal solution.

What folks need to remember is the employers who are primarily known for asking this generally have no problem hiring people who are good programmers and ALSO good at e.g. Dynamic Programming. And no, as much as some try to frame it, the two skills are not directly at odds with each other. Therefore, between a good programmer who can “Leetcode” and one who cannot, why wouldn’t they pick ones that are good at both?

And sure, if your company don’t have that luxury, don’t cargo cult. Hire a good enough domain expert for your specific needs.

While being good at Leetcode is not necessarily negatively correlated with being a good software engineer, is is also not positively correlated. Thus, by relying on it solely, you are still making a coin-toss decision about the software engineering skills of the candidate.

> it is also not positively correlated

Do you seriously think that claim is true? That coin toss predicts software engineering ability as well as leetcode? I don’t think any reasonable person can take this seriously.

Berkson's paradox suggests that even if they seem negatively correlated that may only be due to the selection process. For example, suppose that an interview has 2 components, a leetcode section and an engineering section. Both are scored out of 10, and a total score of 15 is needed to pass.

Among those who pass, the two components might seem negatively correlated. This is because you can score a 10 on one section and pass with only a 5 on the other. However, among the general population both sections might even be positively correlated.

As someone who actually uses algorithms and data-structures in their job, I disagree.

I think both things can be true. These are valuable skills in some situations/jobs and you're selecting for students with these concepts still fresh in their minds and/or people who enjoy algorithm competitions.

And that's fine! A specialized subset of engineers. Maybe that subset is exactly what you need.

I wonder how the stress of the interview process selects out people who understand O-notation and to whom a Trie would make sense if explained to them, vs people who have these concepts fresh in their minds and/or can handle themselves in stressful interview situations.

The author, everyone.

You did emphasize it was the best result, so it's hard to argue that you selected for it.

Back in 2015 Peter Norvig discussed an analysis at Google that suggested doing well at coding contests was a negative indicator of job performance: https://youtu.be/DdmyUZCl75s

Presumably they do well at these sorts of questions, but that doesn't imply the same actual effectiveness.

If you watch the Peter Norvig link you shared on YouTube he actually interprets the phenomenon quite clearly: the statistic reported is only true for the subsample of people who get hired and absolutely not true for the general candidate population.

(Personally I would add that human measures of “job performance” can also be quite subjective.)

You're imagining I didn't listen to an extremely short clip of a talk that I linked to?

Yes, implicitly Google can only measure the job performance of people they actually hire.

I did not mean to imply you in particular did not watch it. The way this observation often gets quoted is extremely misleading (often intentionally so, as the first piece without the second is much more sensationalistic) and needs an explicit clarification, as Norvig did immediately after reporting the curious observation.

I am sure this person has NO IDEA how well the candidates do after they are hired.

What algorithms and data-structures do you commonly use when shutting down useful services?

LRU Cache

Perhaps there is a sort of selection bias going on, where the people who work at Google have been chosen because they are good at leetcode type problems and think they are important, and so they tend to solve problems by implementing their own tries and similar data structures, rather than by using robust canned implementations.

> rather than by using robust canned implementations

And who is supposed to implement the robust canned implementation?

Probably not a UWaterloo recent grad who is good at programming competitions and has just been hired onto a random product team at Google.

I’d posit that a UWaterloo grad who landed a job at Google is close to maximally likely to end up working on something like that [acknowledging that in absolute terms relatively few college grads do so.]

Would you care to extend your reply, and tell us how you use them? Just like you expect a good candidate to do ;)

Reply on news.ycombinator.com