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

101–110 of 122 posts

Re: Retiring a Great Interview Problem

#101

Post by svdad »

I think the concern about whether or not candidates have seen this, or any, programming question before is missing the point. Think about what we want in the ideal candidate -- we want them to come up with a good (elegant, efficient) solution to the problem, and implement it. We (judging by all the other responses) expect them to do that because they've had a solid CS education (formal or informal) as well as significant experience.

But people with that background will give good answers, even if they haven't seen _this specific problem_, because they have seen lots of problems like it and recognize the pattern. And even in that case, we evaluate them based on how well they can implement the pattern they saw, not just on whether they recognized the correct algorithm. So what if they've seen this problem already? Coding it up efficiently and elegantly in an interview context is still non-trivial, and you can still push them to discuss edge cases and performance tradeoffs.

The person who really has _never_ seen anything like this in his life, and still can give a good answer, I have yet to meet.

Re: Retiring a Great Interview Problem

#102

Post by NY_Entrepreneur »

eru wrote: post #79
NY_Entrepreneur wrote: post #49

Earlier quoted context omitted.

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…

At university we defined dynamic programming as reducing a problem to finding paths in directed acyclic grahp. By that definition, there's a simple way to map the problem to dynamic programming. And yes, it's sloppy, if you don't mention the `stages' or equivalently, how you'd (lazily) construct the graph.

One famous application of dynamic programming is finding shortest paths in directed acyclic graphs. Maybe should credit E. Dijkstra. As I recall, that is not regarded as the most efficient such algorithm, but I haven't considered that problem for years.

Re: Retiring a Great Interview Problem

#103

Post by NY_Entrepreneur »

kragen wrote: post #99
NY_Entrepreneur wrote: post #49

Earlier quoted context omitted.

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 just put a bottom-up reformulation of the dynamic-programming solution at http://canonical.org/~kragen/sw/inexorable-misc/wordseg.c , in the function "segment". The stages are the prefixes of s: the substrings s[0:0], s[0:1], s[0:2],... s[0:n], where n is the length of s. The state of some stage s[0:i] is a finite map from all of its segmentable prefixes s[0:j] {j∈[0,i)} to segmentations of those prefixes. (Only on…

You may have a sufficiently tricky formulation to have a dynamic programming solution. But your states and stages are a bit strange!

Much of why we use dynamic programming is that the work at stage i needs only the work at stage i + 1 (for the backward iterations), and here in some problems we can get some huge savings in computing. Also this 'framework' does well handling uncertainty.

Yes, the usual way is to do find the solution from the end and then use it starting at the beginning. In the code I posted on this thread, I found the solution starting at the beginning and then used it by starting at the end and then printed out the words in the reverse order in which I found them.

Re: Retiring a Great Interview Problem

#104

Post by anonymoushn »

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…

Just to clarify, would you say that you cannot solve optimal matrix chain multiplication using dynamic programming, because each state depends on a non-constant number of other states? If so, what is the proper name for the commonly known algorithm used to solve optimal matrix chain multiplication, which is described in CLRS as "dynamic programming?"

Re: Retiring a Great Interview Problem

#106

Post by btilly »

kragen wrote: post #100
btilly wrote: post #94

Earlier quoted context omitted.

The trie check contains the maximum-dictionary-word-length check as an obvious special case and therefore its worst case is the same order of magnitude efficiency as the other check. You do have the cost of descending a level in the trie. But that can be made constant (with a jump table) or else the log of the size of the alphabet (which is a constant for all intents and purposes).

I suppose that depends on what you store in your trie. If every node contains a field for the length of the longest path below it, then yes. But that's not a normal thing to store in a trie, and it wasn't at all obvious to me that that was what you meant.

Not true.

If you keep on following the trie, you'll fall out of the trie at the point that there are no words that have that sequence at the start. Which will happen by the time you exceed the longest word in the dictionary, but will probably happen substantially before that.

Re: Retiring a Great Interview Problem

#107

Post by shangaslammi »

nandemo wrote: post #6

Just for fun I decided to rewrite his first version in Haskell. This is probably not idiomatic, though. segment_string :: String -> Set String -> Maybe String segment_string [] _ = Nothing segment_string str dict = if str `member` dict then Just str else let pairs = zip (inits str) (tails str) pairInDict (x, y) = x `member` dict && y `member` dict in do (x, y)

Here's my Haskell attempt (both naive recursive backtrack and dynamic programming version):

    type Dict = Set String

    hasWord :: Dict -> String -> Bool
    hasWord = flip Set.member

    fmtWords :: [[String]] -> Maybe String
    fmtWords = fmap (intercalate " ") . listToMaybe 

    splitWordsSimple :: Dict -> String -> Maybe String
    splitWordsSimple dct = fmtWords . go where
        go [] = return []
        go s = do
            (i,t)  go t

    splitWordsDP :: Dict -> String -> Maybe String
    splitWordsDP dct s = fmtWords $ a ! 0 where
        a = listArray (0, len) $ map f [0..len-1] ++ [[[]]]
        len = length s
        f i = do
            l  a ! (i+l)

Re: Retiring a Great Interview Problem

#108

Post by epaga »

nandemo wrote: post #72
someone13 wrote: post #22

Earlier quoted context omitted.

There's something to be said for NOT reinventing the wheel. Standard libraries are standard for a reason - the "String.Compare()" function is likely faster for just about every case, in addition to being already there.

I keep seeing this argument on threads about interview questions. The principle of not reinventing the wheel has nothing to do with interview questions. Sure, if you're actually working on solving an actual problem at your job, then most of the time you'll be better off using a standard library function instead of rolling your own. In the context of the job interview, however, it doesn't matter if the solution to the…

They would say Foo.ToString().Compare()... ;)

Re: Retiring a Great Interview Problem

#109

Post by skrebbel »

epaga wrote: post #108
nandemo wrote: post #72

Earlier quoted context omitted.

I keep seeing this argument on threads about interview questions. The principle of not reinventing the wheel has nothing to do with interview questions. Sure, if you're actually working on solving an actual problem at your job, then most of the time you'll be better off using a standard library function instead of rolling your own. In the context of the job interview, however, it doesn't matter if the solution to the…

They would say Foo.ToString().Compare()... ;)

And not get the job, because it's likely wrong.

Re: Retiring a Great Interview Problem

#110

Post by onemoreact »

kragen wrote: post #84
onemoreact wrote: post #36

Earlier quoted context omitted.

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.

I don't understand how that's possible. I mean, I'm going to assume that you're telling the truth, but I don't understand how it's possible for that knowledge to reside so entirely in your IDE rather than in your head. Do you mean you know that you would use an Enumeration, but not the names of the Enumeration and Hashtable methods that you would use? If you're trying to debug a piece of code and it's calling the wro…

I have use a lot of diffrent programming languages. I have trouble seperating what you can in theory do with a hashmap from what a given implementaiton let's you do with a hashmap. I have also engraned typing code out to the point where a lot of basic syntax features quickly become automatic I might think EOL but I type ;

The best way I can discribe it is like singing. You can have trouble speaking the words to something that you can sing without difficulty.

Post reply on HN