Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Retiring a Great Interview Problem

thenoisychannel.com

Post reply on HN
Print view View original

61–70 of 122 posts

Re: Retiring a Great Interview Problem

#61

Post by wisty »

dtunkelang wrote: post #43
wisty wrote: post #5

The problem he's having is that good interview questions are getting busted, as people post solutions on the web. If you have a lot of similar interview questions, then there's no way anyone other than a savant can memorize them without actually learning the theory.

Point taken. But it's hard to come up with good interview questions, as my colleagues here, at Google, and at Endeca can attest. In contrast, it's much easier to post solutions. That's why I'm working on an approach that assumes the candidate does of prior knowledge of the problem. But not there yet.

There's not too much difference between "people who get dynamic programming, after boning up for the interview", and "people who can answer your dynamic programming question because they read the answer to a similar one while boning up for the interview". Both are probably good candidates.

Re: Retiring a Great Interview Problem

#62

Post by georgemcbay »

Why retire the question just because you saw it on Glassdoor? The same question was posted to sureinterview last year, so anyone you hired since November is suspect! (If you believe that potential advance knowledge of the question is relevant).

Worse yet, even if you did come up with this problem on your own, this exact problem was a fairly common interview question back in the mid 90s, when string processing interview questions were all the rage for C/C++ programming jobs -- I must have seen it a dozen times in various interviews over the years. The problem is familiar enough that I'd bet a decent amount of money that it must be listed in one of those interview problem books that were popular before the websites for this stuff started showing up over the past couple years... If you really relied on the interviewee having no possible advance knowledge of this question prior to the interview you surely had a false sense of security prior to seeing it appear on glassdoor.

As long as you engage the interviewee to see that s/he really understands the answers they are giving, I don't really see why it matters if the question has appeared on one of these sites. If the interviewee is preparing for their interviews enough that they are actually looking at these sites and understanding the answers to the point where they can intelligently discuss them, that probably already puts them in the upper tier of people you'd want to seriously consider hiring, so retiring the question is probably counter-productive unless you have a non-disclosed alternative that you're sure is as good of a question.

Re: Retiring a Great Interview Problem

#63

Post by Daniel_Newby »

StavrosK wrote: post #34
skrebbel wrote: post #23

Earlier quoted context omitted.

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 treme…

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 backtra…

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

#64

Post by nasmorn »

dxbydt wrote: post #30
patio11 wrote: post #2

A spiritually similar question at a previous employer resulted in many candidates attempting to iterate over the dictionary rather than iterating over the string. We hired them. At least they could iterate over a dictionary. That's a surprisingly rare skill in the hiring pool. Maybe I'm just getting cynical in my old age, but sometimes I think the world is awash in incompetence. We see so much of it in tech because o…

>sometimes I think the world is awash in incompetence. We see so much of it in tech because our incompetencies are (marginally) harder to hide. A very candid Philip Greenspun in Founders@Work( p341-2) : "In aviation, by the time someone's your employee, their perceived skill and actual skill are reasonably in line. JFK Jr is not working at a charter operation because he's dead. In IT,you have people who think 'I am a…

I second that. For musicians it is hard to hide their incompetence, for programmers it is just a matter of picking the right succession of jobs.

Re: Retiring a Great Interview Problem

#65

Post by phillytom »

nitrogen wrote: post #16
StavrosK wrote: post #7

Earlier quoted context omitted.

I'm sorry, my Java is rusty; is this the equivalent of the Python print("\n".join("%s: %s" % (key, value) for key, value in mydict.items())) ? If so, is it hard to do in Java?

In 1997, before for-each and generics, it would've been very verbose. I learned Java in 2006 and haven't written much in a while, so I maybe slightly off, but I think you'd either get an Iterator for the Hashtable's keys and repeatedly call Iterator.next() and Hashtable.get(), or get the length of Hashtable.keys() and use a traditional C-style for loop. Okay, I couldn't resist looking up the old docs, so this looks a…

FYI - there's a potential defect there - keys are not required to be strings so you should lookup the value before you cast.

Re: Retiring a Great Interview Problem

#66

Post by free »

phillytom wrote: post #65
nitrogen wrote: post #16

Earlier quoted context omitted.

In 1997, before for-each and generics, it would've been very verbose. I learned Java in 2006 and haven't written much in a while, so I maybe slightly off, but I think you'd either get an Iterator for the Hashtable's keys and repeatedly call Iterator.next() and Hashtable.get(), or get the length of Hashtable.keys() and use a traditional C-style for loop. Okay, I couldn't resist looking up the old docs, so this looks a…

FYI - there's a potential defect there - keys are not required to be strings so you should lookup the value before you cast.

Ideally, whatever your key/value is would have the toString method over ridden to meaningfully represent it. Alternatively, I could write it as

for(Map.Entry entry : map.entrySet()){

     System.out.println(entry.getKey());

     System.out.println(entry.getValue());

}

Re: Retiring a Great Interview Problem

#67

Post by sur »

SoftwareMaven wrote: post #50
StavrosK wrote: post #7

Earlier quoted context omitted.

I'm sorry, my Java is rusty; is this the equivalent of the Python print("\n".join("%s: %s" % (key, value) for key, value in mydict.items())) ? If so, is it hard to do in Java?

Well, yours does iterate over the dictionary twice and generates a temporary list in the meantime. If you have a huge dictionary, this would explode. The equivalent Java code wouldn't do that (due to lack of list comprehensions).

He is using parentheses instead of square brackets, so the code is actually using a generator expression which will produce each value lazily.

Re: Retiring a Great Interview Problem

#68

Post by ohashi »

I read this and went, I had someone build this for me years ago!

So I looked at the code, it used the efficient solution. Now I am even more impressed with the programmer. I've always thought highly of him (better than me) but it's hard to evaluate someone better than you. His solution ran circles around mine (I had general simple case with 2 words) and now I know exactly how much more efficient his solution was. Very neat.

Re: Retiring a Great Interview Problem

#69

Post by rfurmani »

NY_Entrepreneur wrote: post #49
rfurmani wrote: post #14

Earlier quoted context omitted.

The "obvious" selection of stages does work. When you are at position j you check all i<j until you find one where there is a segmentation up to i, and the substring [i,j) is a word. Memoization is just syntactic (semantic?) sugar on top of this and he provides the code that basically implements the above. In programming competition circles it's common to just say "it's dynamic programming" when the stages are semi-o…

Yes, from a fast reading, your solution appears to be correct, and so does 'memoization', but, still, in spite of common practice in computing, it's not a dynamic programming algorithm because what 'dynamic programming' is goes back to R. Bellman and his student Dreyfus and the book Dreyfus and Law. There may be a problem with what you outline: That substring [i, j) is a word is not so impressive! In addition we need…

I'm confused. Are you saying that if you have a DP table A then to compute A[i+1] you are only allowed to use A[i]? This question is classic DP. A[i] stores the segmentation of the first i letters if it exists (or it can just store a boolean, depending on implementation). Then to compute A[i] you look at the j<i see if A[j] is non-empty and if the [j,i) substring is in the dictionary. If you find a valid j you set A[i] accordingly, otherwise leave it empty.

Re: Retiring a Great Interview Problem

#70

Post by pbh »

I hope readers aren't getting the impression from this article that the code examples provided are the correct way to do word segmentation in English. (Though I understand this is an article about interviewing and not about word segmentation. And this might be considered a preprocessing step for doing things correctly...)

Norvig gives a very approachable version of English word segmentation that uses a language model below.

http://norvig.com/ngrams/

Post reply on HN