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)
Retiring a Great Interview Problem
11–20 of 122 posts
Re: Retiring a Great Interview Problem
#12I would have thought of dynamic programming when asked if I could solve it more efficiently, but I've somehow just not had much occasion to use dynamic programming, so would have had to admit it would take an evening of reviewing my algorithms books to actually solve it that way.
However, I would have been able to come up with an alternative O(n^2) solution, involving building a directed graph with vertices representing each position in the string and the end of the string, with edges connecting two vertices if there is a dictionary word starting at the position corresponding to one vertex and ending just before the position corresponding to the second vertex. This can be done in O(n^2), and then you can find the shortest path from the vertex for 0 to the end vertex on this graph in O(n^2) (e.g., by Dijkstra's algorithm), and that gives you an exact covering of the string using the minimal number of dictionary words.
Re: Retiring a Great Interview Problem
#13A 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…
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…
Iterating over a hashtable (at least in pseudocode if they didn't recall the API functions off-hand) hardly seems a trivia question...
Re: Retiring a Great Interview Problem
#14The 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-obvious, and given that he uses memoization I'd say there's a strong chance he's been involved in Topcoder
Re: Retiring a Great Interview Problem
#15Just 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)
http://www.codinghorror.com/blog/2007/02/fizzbuzz-the-progra...
So what? This problem (the full version) is more complex than FizzBuzz. Besides, I'm not pasting code here to prove that I can program, but to show how the solution looks like in Haskell.
Re: Retiring a Great Interview Problem
#16Earlier 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?
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 about right (Enumeration instead of Iterator -- two interfaces that do basically the same thing):
void printTable(Hashtable table)
{
Enumeration e = table.keys();
while(e.hasMoreElements()) {
String key = (String)e.nextElement();
String value = (String)table.get(key);
System.out.println(key + ": " + value);
}
}Re: Retiring a Great Interview Problem
#17I would have thought of dynamic programming when asked if I could solve it more efficiently, but I've somehow just not had much occasion to use dynamic programming, so would have had to admit it would take an evening of reviewing my algorithms books to actually solve it that way. However, I would have been able to come up with an alternative O(n^2) solution, involving building a directed graph with vertices represent…
Your approach is correct. The graph that you've built is a DAG. This means that, you can solve for the lower vertices before solving for the upper ones. This is exactly how a typical Dynamic Programming solution works. If for solving a problem, we can see the relationship b/w this problem and other similar but smaller ones, we solve the smaller problems first and use these solutions to build up a solution for the larger case.
EDIT: A naive implementation of your idea can take upto O(n3m) time where m is the no. of words in dictionary. Using a fancy data structure like a trie or suffix tree or an automaton can speed it upto O(n^2). Can we better that?
Re: Retiring a Great Interview Problem
#18Quick heads up: page is not rendered properly in Mobile Safari on iPhone: fixed width font lines are cut off.
Re: Retiring a Great Interview Problem
#19Earlier 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…
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....
Re: Retiring a Great Interview Problem
#20Only slightly joking: re.findall("(your|dict|here)", "yourword") I like the idea of constructing a state machine to do all the matching.
I love it. You spark an (imho) much more interesting debate: that of raw smartness vs pragmatic productivity.
A colleague of mine (now hired) was asked to code a string compare during her interview for a .NET function. She said "String.Compare()". This puzzled the interviewers for a while. They asked her whether she could write it out, she said she didn't see the point.
They ended up hiring her for other reasons (notably, references from trusted colleagues who had worked with her), but I still wonder whether that attitude worked for her or against her.