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

41–50 of 122 posts

Re: Retiring a Great Interview Problem

#41

Post by arethuza »

onemoreact wrote: post #36
arethuza wrote: post #19

Earlier quoted context omitted.

Yeah - that's pretty much it. Except that being lazy I'd have probably not bothered casting the keys and values to Strings and just called toString() on them directly....

Did you expect people to be able to do this by hand? I mean infront of an IDE I could do this in 5-10 minutes. But on a blackboard or pen and paper there is little chance I would get anywhere close to a correct answer.

This was the last question out of 15 or so that we used to give to people as part of an interview if they claimed they had done Java before - it was a written test. Some people had only done C or C++ before and had only had a quick look at Java and still did pretty well in it.

Re: Retiring a Great Interview Problem

#43

Post by dtunkelang »

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.

Re: Retiring a Great Interview Problem

#44

Post by onemoreact »

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…

I like that you accepted new approaches as valid even if a candidate did not finish them. Reading this I can’t help but think how this person falls into the java trap of trying to make a ridiculously generic solution which I would consider a danger sign but plenty of people love to see.

So, assuming a real world input and real world dictionary you can try plenty of things that break down for a dictionary that includes four hundred A’s but are actually valid solutions. Also, if you want a fast real world solution then sticking with a pure lookup dictionary would slow things down. Being able to toss 5 letters into a lookup table that says the longest and shortest words that start with those letters would save a lot of time. Basically, ‘xxyzy’ = null, null saves you from looking up x to the maximum word length in your dictionary. Secondly sanitizing inputs is going to be both safer and faster. And anything you are coding in 45 minutes is going to be a long way from production ready code.

PS: Even with backtracking you can code an O(n) solution for vary large input sets. Just keep track of the K best output sequences that are aka N, N-1,N-2,…N-K.

Re: Retiring a Great Interview Problem

#45

Post by reidrac »

rfurmani wrote: post #29
StavrosK wrote: post #8

Only slightly joking: re.findall("(your|dict|here)", "yourword") I like the idea of constructing a state machine to do all the matching.

bzzt wrong. >>> re.findall('(a|aa|aaa|ab)', 'aaab') ['a', 'a', 'a'] The correct answer would be ['aa', 'ab'] but unfortunately findall works greedily and so will not find the optimal solution. It is possible to specify it as a regex, but common implementations might take too much time to come up with the good solution.

I think ['a', 'a', 'ab'] is also valid, isn't it? So ['aa', 'ab'] would be one of the correct answers.

(of course ['a', 'a', 'a'] it's not because the 'b' is not a valid word and it's not in the solutions)

Re: Retiring a Great Interview Problem

#46

Post by kevinastock »

rfurmani wrote: post #29
StavrosK wrote: post #8

Only slightly joking: re.findall("(your|dict|here)", "yourword") I like the idea of constructing a state machine to do all the matching.

bzzt wrong. >>> re.findall('(a|aa|aaa|ab)', 'aaab') ['a', 'a', 'a'] The correct answer would be ['aa', 'ab'] but unfortunately findall works greedily and so will not find the optimal solution. It is possible to specify it as a regex, but common implementations might take too much time to come up with the good solution.

From the problem definition:

Q: What if there are multiple valid segmentations? A: Just return any valid segmentation if there is one.

Re: Retiring a Great Interview Problem

#47

Post by Shenglong »

With the exception of the last part of the question, you learn everything there in your first year of CS at university. Do people who can't write this really put the language on their resume?

Can I get some stats? I really don't (want to) believe it. What percentage of people get this question wrong? Are they all some sort of eng/cs graduate? I'm not even a coder and I can solve this in a few minutes.

Re: Retiring a Great Interview Problem

#48

Post by rfurmani »

reidrac wrote: post #45
rfurmani wrote: post #29

Earlier quoted context omitted.

bzzt wrong. >>> re.findall('(a|aa|aaa|ab)', 'aaab') ['a', 'a', 'a'] The correct answer would be ['aa', 'ab'] but unfortunately findall works greedily and so will not find the optimal solution. It is possible to specify it as a regex, but common implementations might take too much time to come up with the good solution.

I think ['a', 'a', 'ab'] is also valid, isn't it? So ['aa', 'ab'] would be one of the correct answers. (of course ['a', 'a', 'a'] it's not because the 'b' is not a valid word and it's not in the solutions)

Ah right, I was a bit too quick to challenge. Dictionary: aa, aaa, aaaa, ab Word: aaaab

Re: Retiring a Great Interview Problem

#49

Post by NY_Entrepreneur »

rfurmani wrote: post #14
NY_Entrepreneur wrote: post #9

The author just mentioned dynamic programming. Usually in dynamic programming, e.g., as in Dreyfus and Law, to say that a problem has a dynamic programming solution we outline the solution. But the author did not outline such a solution. An outline usually includes at least the definition of the 'stages' of the dynamic programming solution. For the problem of 'string segmentation', the obvious selection of stages wou…

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 to know, for i Maybe in the core of the work what we want to know is, for each i = n, n - 1, ..., 1, is there a 'segmentation' of [i,n]. To tell this, at i, consider j so that i So, the break with dynamic programming is that at stage i, we have to look at the results of not just stage i + 1 but at the results of each j for j = i + 1, i + 2, ..., n, which breaks the basic 'recursion' that is at the core of dynamic programming. That is, a key feature of dynamic programming is that at stage i, to find what to do, need only the 'state' at stage i and, for each possible state at stage i + 1, what to do at stage i + 1. That is, at stage i, do not have to look at stages i + 2, i + 3, etc.

Also for your approach, you are not working just at stage i but also with [j, i) for 1 No matter what some common practice is, just saying dynamic programming without being explicit about the stages, states, state transition functions, and the recurrence is sloppy to the point of risking often being wrong. This is not nearly the first time that computing took something solid and precise from applied math and made a mess. Messes, even if common, are not good. You will see a lot of care and discipline in Dreyfus and Law along with essentially all the applied math literature on dynamic programming, back to Nemhauser, Bellman, and others.

It's a cute string exercise with some cute solutions, but it's just not dynamic programming.

Re: Retiring a Great Interview Problem

#50

Post by SoftwareMaven »

StavrosK wrote: post #7
arethuza wrote: post #3

Earlier quoted context omitted.

Many years ago ('97) we had a Java programming test for new hires that included a question that involved iterating over a Hashtable containing String keys and values and printing them all out. Nobody ever answered that question correctly and I used to joke that if anyone ever did we'd hire them immediately. NB I've long since stopped using those kind of trivia questions in interviewing, but I didn't know any better a…

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).
Post reply on HN