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

51–60 of 122 posts

Re: Retiring a Great Interview Problem

#51

Post by dtunkelang »

Shenglong wrote: post #47

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.

I don't have stats I can share, but I assure you that this problem has confounded many interview candidates with strong resumes. I agree with you that it's all basic material -- that's deliberate. I'm glad you think it's too easy. :-)

Re: Retiring a Great Interview Problem

#52

Post by SoftwareMaven »

wensing wrote: post #31

Humbling way to start the work week. I could produce the fizzbuzz solution and in my sharper days the recursive backtracing one, but definitely no further.

I wouldn't feel bad. The advanced answers to this question require spending a lot of time understanding string processing. It's like having a CSS question that can be implemented multiple ways: a simple, obvious, slow way and a complicated, "deep knowledge required", fast way. If you have lots of experience with CSS, you might get the fast way, but it doesn't really say how good a programmer you are.

(Yes, not a perfect analogy, but it hopefully gives the idea.)

Re: Retiring a Great Interview Problem

#54

Post by NY_Entrepreneur »

anonymoushn wrote: post #24
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 article actually includes a solution that uses memoization, which is equivalent to DP.

Yes, I can go along with the claim that the article uses memoization. But that 'memoization' is "equivalent to DP" is not correct, not even close to correct, really is just nonsense. What dynamic programming is has been solid, clear, and fixed all the way back to Bellman, and memoization just is not the same thing at all.

Yes, a memoization solution to the segmentation problem might work in a loop on i for i = n, n - 1, ..., 1, and the usual backward recurrence in dynamic programming does also, but that similarity does not mean that the loop is dynamic programming.

For more, dynamic programming has stages, states, state transition functions, and a basic recurrence relationship. The recurrence does the work at stage i just from the work at stage i + 1; the string problem does NOT do this. In the case of uncertainty, we also need essentially a Markov assumption,

Again, the string problem is cute, and there is at least one cute solution, but it's not dynamic programming.

Re: Retiring a Great Interview Problem

#55

Post by pavel_lishin »

dtunkelang wrote: post #42
mynegation wrote: post #18

Quick heads up: page is not rendered properly in Mobile Safari on iPhone: fixed width font lines are cut off.

Sorry about that. Advice on how to fix it while maintaining good rendering elsewhere? Looks good in Chrome on my MacBook and my Nexus One.

It's not rendering well for me, either: http://i.imgur.com/Q89gP.png

My suggested solution: don't wrap it in PRE tags with manual line-breaks. It's not code, so why preserve the exact breaks? Try BLOCKQUOTE - I don't know if it's widely supported anymore - or just italicize the whole thing.

I don't really have a good solution for what to do about the actual code, though. :(

Re: Retiring a Great Interview Problem

#56

Post by mason55 »

SoftwareMaven wrote: post #52
wensing wrote: post #31

Humbling way to start the work week. I could produce the fizzbuzz solution and in my sharper days the recursive backtracing one, but definitely no further.

I wouldn't feel bad. The advanced answers to this question require spending a lot of time understanding string processing. It's like having a CSS question that can be implemented multiple ways: a simple, obvious, slow way and a complicated, "deep knowledge required", fast way. If you have lots of experience with CSS, you might get the fast way, but it doesn't really say how good a programmer you are. (Yes, not a perf…

The advanced answers to this question require spending a lot of time understanding string processing.

Really? Seems like a standard DP question to me

Re: Retiring a Great Interview Problem

#57

Post by jswinghammer »

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.

One thing that I've noticed over the years is that almost no one prepares for an interview in any way so you'll still keep out the worst candidates with this question.

Re: Retiring a Great Interview Problem

#58

Post by qntm »

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.

Interestingly, the article explicitly states that our dictionary supports only the exact string lookup command, dict.contains(string). Strictly speaking, the full content of the dictionary isn't available to us, and we can't create the regular expression.

Re: Retiring a Great Interview Problem

#59

Post by Shenglong »

dtunkelang wrote: post #51
Shenglong wrote: post #47

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.

I don't have stats I can share, but I assure you that this problem has confounded many interview candidates with strong resumes. I agree with you that it's all basic material -- that's deliberate. I'm glad you think it's too easy. :-)

You have my sympathy :)

Re: Retiring a Great Interview Problem

#60

Post by JL2010 »

I had a similar question with a twist asked of me during an interview. It went something like this:

Given a list of all the short strings in the periodic table of elements (e.g. Na, F, Al, etc) and a list of all the words in the English language: 1) write a method that finds the longest possible English word you can spell given any combination of the strings in the periodic table of elements. Re-usage of elements in the same string are allowed. 2) Describe what kind of data types you would want for the two lists and describe anything special about them. 3) Give a big O estimation.

I thought it was a great question :)

Post reply on HN