Comment by sverona | Hacker News Reader

Top New Best Ask Show Jobs

Comment by sverona | Hacker News Reader

> I then push them on this until they realize that any implementation of the dictionary lookup function of a string would be o(n) at best, and as such the total runtime of the solution is O(n²).

Is n the length of the word or the length of the dictionary? And if it's the length of the word (<< the length of the dictionary), why does it matter if it's linear or quadratic?

n is the length of the string. As for why it matters whether it's linear or quadratic, we are assessing the candidates ability to analyze a problem and possibly improve an algorithm. It might not matter in the problem at hand.

Okay, yeah, that's fair.

Surely there is a longest word in the dictionary, so you can short circuit for any string longer than twice that. So an asymptotic analysis in the length of the string doesn't really make sense.

We're assessing the candidates ability to do work that doesn't matter?

This is a negative hiring signal you're looking for, right?

Reply on news.ycombinator.com