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

111–120 of 122 posts

Re: Retiring a Great Interview Problem

#111

Post by onemoreact »

kragen wrote: post #87
SoftwareMaven wrote: post #52

Earlier quoted context omitted.

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. No, the advanced answers are a simple application of dynamic programming. If you've never heard of dynamic programming before, you're unlikely to invent it in response to an interview question, of course; but if you have heard of it, it might occur to you to try it on this problem. (Actually, if you've heard of mem…

Counterpoint: @Retric congratulations, you’ve reinvented dynamic programming with your O(n) solution That’d be a perfect solution.

And yes, I had zero idea what memorization or dynamic programming meant in that context. After looking it up on wikipedia it seems to mean caching intermediate steps to avoid recalculating them which seems obvious enough.

Re: Retiring a Great Interview Problem

#112

Post by eru »

NY_Entrepreneur wrote: post #102
eru wrote: post #79

Earlier quoted context omitted.

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.

As far as I know Dijkstra's algorithm is the fastest path finding algorithm in general directed graphs without cycles of negative length. But you have to employ fibonacci heaps (or so) to get the best run-time.

If you have some heuristics to guide your path finding, e.g. if you are trying to find paths on a map, then you can do better than Dijkstra's algorithm. See A*.

Re: Retiring a Great Interview Problem

#113

Post by NY_Entrepreneur »

anonymoushn wrote: post #104
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…

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?"

CLRS can write what they want, but they can't rewrite what R. Bellman wrote.

Part of the problem of 'what is dynamic programming' is that if permit the 'states' to keep growing in 'complexity' with the stages, then nearly anything can be called dynamic programming. A big example is stochastic optimal control with an arbitrary exogenous stochastic process. In that case, at each stage, the state is just the whole past history of the process, and then for estimates of the future we take the conditional expectation given the history. So, to make stochastic optimal control, and discrete time stochastic dynamic programming, 'meaningful' we ask for a Markov assumption -- the past and future are conditionally independent given the present -- on the exogenous stochastic process.

The key, central point about dynamic programming is the computational savings we can get, when there is good news, from the basic recurrence relation. There at state i, get to do all the work using just the work did at state i + 1 for backward recurrence and state i - 1 for forward recurrence. If can't do this, and if the 'complexity' of the states keeps growing along with the stages, then are into essentially just arbitrary problems with nothing special, and little hope of gains, from dynamic programming.

How general? There is a big AI theme that the problem is solved: Just use dynamic programming! Alas, the state variables at each stage are the past history of the universe and, thus, a bit much to handle on Windows XP for now!

Again, once again, still again, for, what, a dozen times on this thread, the algorithm of the word segmentation problem is not really dynamic programming because at each stage need to use the results of the work not just at the last stage but at all the previous stages. Yes, can patch up the situation by saying that all the work of all the previous stages is now part of the current state, but if do that then the AI problem is also solved by dynamic programming because can just say that the current state has all the past history of the universe and then we don't have much for dynamic programming being anything different from everything.

For CLRS and "matrix chain multiplication", etc., to know if a solution algorithm is DP, the burden is on the proposer, not me. If someone describes the problem and writes out a clean description of why their solution is DP, then we can consider it.

But clearly what has happened is that essentially every algorithm in computer science with an outer loop from i = 1 to n is called DP, and that's not helpful.

Re: Retiring a Great Interview Problem

#114

Post by StavrosK »

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).

Aside from the fact that I'm using a generator, where does it iterate twice? I don't see it.

Re: Retiring a Great Interview Problem

#115

Post by dtunkelang »

pbh wrote: post #70

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…

Peter actually emailed me directly, though I was already very familiar with his work on this and similar problems. But yes, I make it very clear in the post (and to candidates) that they should not assume an English -- or even a natural language -- dictionary.

Re: Retiring a Great Interview Problem

#116

Post by nyellin »

kragen wrote: post #82
SoftwareMaven wrote: post #50

Earlier quoted context omitted.

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).

At first glance, your statement is incorrect: there is no Python code to create a list here, and no list comprehensions. On further examination, though, string_join in stringobject.c invokes PySequence_Fast to convert its iterable argument into a sequence --- a temporary list, in this case --- so your statement that this code generates a temporary list is correct, although I suspect that this is more by accident than…

Why doesn't StringIO count as a string buffer?

Re: Retiring a Great Interview Problem

#117

Post by StavrosK »

Daniel_Newby wrote: post #63
StavrosK wrote: post #34

Earlier quoted context omitted.

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.

Insecure how?

Re: Retiring a Great Interview Problem

#118

Post by Daniel_Newby »

StavrosK wrote: post #117
Daniel_Newby wrote: post #63

Earlier quoted context omitted.

Nobody will reasonably expect you to implement your own string comparison routine, ... Standard string comparisons exit on the first mismatched character, which is insecure.

Insecure how?

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

#119

Post by StavrosK »

Daniel_Newby wrote: post #118
StavrosK wrote: post #117

Earlier quoted context omitted.

Insecure how?

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.

Interesting, thanks.

Re: Retiring a Great Interview Problem

#120

Post by dtunkelang »

btilly wrote: post #106
kragen wrote: post #100

Earlier quoted context omitted.

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.

Am curious to see having the dictionary in a trie allows you to build an implementation that is O(n). Will add it to the blog post if it works.
Post reply on HN