News for hackers. Stuff that matters.
Re:Retiring a Great Interview Problem by skrebbel on Monday August 08, 2011 @08:39AM (#2859827)
That's my point. At work, I'd prefer someone using String.Compare() over some nasty hand-crafted for-loop with switches and things for all kinds of collation issues. Why would I ask something else during the interview?

I love the GGP's solution for the same reason. If the regex is compiled only once, it may be only marginally slower (if at all), and it significantly improves readability and maintainability, and tremendously reduces the chances for bugs.

I'd hire the him. I have the impression most Google-interviewers (and similar dudes/dudettes) wouldn't. I wonder why.

Re:Retiring a Great Interview Problem by hackinthebochs on Monday August 08, 2011 @06:21PM (#2861815)
>I have the impression most Google-interviewers (and similar dudes/dudettes) wouldn't. I wonder why

Perhaps that was rhetorical, but I'll answer anyway:

Being able to wire up existing libraries to accomplish a goal is a pretty low bar to set as far as proficiency goes. Google doesn't want code monkeys. The solution above is perfectly good from a software engineering perspective, but it doesn't show the depth of the candidates knowledge nor how strong their grasp of CS techniques is.

Google's interviews are more like IQ tests than software engineering tests, using CS as the measuring tool. When you're Google you can afford to be that selective.

Re:Retiring a Great Interview Problem by StavrosK on Monday August 08, 2011 @09:47AM (#2860042)
I'm glad that you like my solution, but please note that, as another commenter said, it's a buggier version of the original regex I thought of ("^(dict|here)+$"), which I think should work but doesn't, at least not in Python.

I suspect it's because the match group is being replaced with the last match rather than added as another group, but it will work as a state machine, and is pretty much equivalent to the backtracking example in the article (although with much less code, and no memoization).

That said, I think that the reason interviewers ask about functions for which we have well-known implementations is to see whether or not you know how they work and/or could implement them yourself. Nobody will reasonably expect you to implement your own string comparison routine, but you could score points if, for example, you said Boyer-Moore for string searching rather than the naive iterative version.

Re:Retiring a Great Interview Problem by Daniel_Newby on Monday August 08, 2011 @12:18PM (#2860571)
Nobody will reasonably expect you to implement your own string comparison routine, ...

Standard string comparisons exit on the first mismatched character, which is insecure.

Re:Retiring a Great Interview Problem by StavrosK on Tuesday August 09, 2011 @06:30PM (#2865800)
Insecure how?
Re:Retiring a Great Interview Problem by Daniel_Newby on Wednesday August 10, 2011 @12:16PM (#2868901)
Timing attacks. If one of the strings is supplied by the client and the other string is a secret, a comparison that exits at the first mismatch is faster. The client can try every value of the first character until it finds one that takes longer, and it knows that that one is the first character of the secret. It can repeat this with the second character, and so on until the entire secret is known.
Re:Retiring a Great Interview Problem by StavrosK on Wednesday August 10, 2011 @12:41PM (#2869038)
Interesting, thanks.