6 ms·

Retiring a Great Interview Problem

173 points by dtunkelang 15y ago

patio11 15y ago
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 our incompetencies are (marginally) harder to hide.
- arethuza 15y ago
  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 at the time.
  - nopassrecover 15y ago
    Iterating over a hashtable (at least in pseudocode if they didn't recall the API functions off-hand) hardly seems a trivia question...
  - StavrosK 15y ago
    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?
    - arethuza 15y ago
      No, it's really not - even with the java.util.Hashtable class that was all that Java had at the time. I think it was something that people from a C,C++ background didn't really expect to be able to do.
    - nitrogen 15y ago
      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); } }
      - arethuza 15y ago
        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....
        onemoreact 15y ago
        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.
        arethuza 15y ago
        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.
        kragen 15y ago
        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 wrong methods on an Enumeration or a Hashtable, how do you tell that they're the wrong methods? How does this work?
    - SoftwareMaven 15y ago
      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).
      - sur 15y ago
        He is using parentheses instead of square brackets, so the code is actually using a generator expression which will produce each value lazily.
        eru 15y ago
        Is mydict.items() also lazy?
        kragen 15y ago
        In Python 3 yes, in Python 2 no. In Python 2 you'd say mydict.iteritems() if you were concerned about it.
      - kragen 15y ago
        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 because you have a deep knowledge of the implementation of the Python standard library. The temporary list of temporary strings probably will use less memory than the original dict did, though, so it's only a very mild sort of "explosion". It will, however, be several times bigger than the final output string, which also has to be huge if the dictionary is huge. Python doesn't have anything like a StringBuffer. If it did, it would be reasonable for string_join to use it instead of generating a temporary list. The Python code above would look the same. But hey, if you just want to print the values, you could say sys.stdout.printlines("%s: %s\n" % (k, v) for k, v in mydict.items()) but frankly I think I would write instead for k, v in mydict.items(): print "%r: %r" % (k, v)
- access_denied 15y ago
  That's IMHO not beeing cynical, just realistic. In a world where the bar of what it means to be competent is constantly raised and where the amount of places where competence is needed is growing constantly, you would expect to observe incompetencies increasingly. Add to that the fact that your own abilties to spot incompetencies grow over time too.
- dxbydt 15y ago
  >sometimes I think the world is awash in incompetence. We see so much of it in tech because our incompetencies are (marginally) harder to hide. A very candid Philip Greenspun in Founders@Work( p341-2) : "In aviation, by the time someone's your employee, their perceived skill and actual skill are reasonably in line. JFK Jr is not working at a charter operation because he's dead. In IT,you have people who think 'I am a great programmer'. But where are the metrics that prove them wrong ? Traffic accidents are very infrequent, so they don't get the feedback that they are a terrible driver. Programmers walk around with a huge overestimate of their capabilities. That's why a lot of them are very bitter. They sit around stewing at their desks. That's why I don't miss IT, because programmers are very unlikable people. They are not pleasant to manage."
  - nasmorn 15y ago
    I second that. For musicians it is hard to hide their incompetence, for programmers it is just a matter of picking the right succession of jobs.
  - deleted 15y ago
    [deleted]
- onemoreact 15y ago
  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.
JL2010 15y ago
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 :)
tzs 15y ago
I 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.
- VinyleEm 15y ago
  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?
- dtunkelang 15y ago
  Actually, my original implementation used Dijkstra's algorithm. But I think the linear table of suffixes (or prefixes if you prefer) is a cleaner approach.
Havoc 15y ago
Its a great question. Pretty sure its not nearly as much of a secret as the author thinks though. I've seen a detailed write-up before somewhere (HN?) and I'm not even a programmer by profession.
- dtunkelang 15y ago
  Secret is a strong word -- I link to another post on the subject in the article. Still, seeing it on Glassdoor for my own employer crossed the line of disclosure.
wisty 15y ago
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.
- dtunkelang 15y ago
  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.
  - wisty 15y ago
    There's not too much difference between "people who get dynamic programming, after boning up for the interview", and "people who can answer your dynamic programming question because they read the answer to a similar one while boning up for the interview". Both are probably good candidates.
  - jswinghammer 15y ago
    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.
    - cema 15y ago
      I think Google etc are exceptions, people do prepare for technical interviews there.
nandemo 15y ago
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) <- find pairInDict pairs 　 Just (x ++ " " ++ y)
- ottbot 15y ago
  http://www.codinghorror.com/blog/2007/02/fizzbuzz-the-programmers-stairway-to-heaven.html http://www.codinghorror.com/blog/2007/02/fizzbuzz-the-progra...
  - nandemo 15y ago
    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.
- eru 15y ago
  Yes, doesn't strike me as idiomatic. But I can't come up with a better version on the spot.
- zohebv 15y ago
  How about this, this will compute more than pairs <pre><code> let dict = Data.Set.fromList["apple", "pie", "bread", "applepie", "piebread"] let fn q = concat.Data.List.map (\(x,y) -> if (member x dict) then if y == "" then [[x]] else Data.List.map (x:) (fn y) else [] ) $ tail $ zip (inits q) (tails q) fn "applepiebread" [["apple","pie","bread"],["apple","piebread"],["applepie","bread"]] </code></pre>
- shangaslammi 15y ago
  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) <- zip (inits s) (tails s) guard $ hasWord dct i (i:) <$> 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 <- [1..len-i] let w = take l $ drop i s guard $ hasWord dct w (w:) <$> a ! (i+l)
StavrosK 15y ago
Only slightly joking: re.findall("(your|dict|here)", "yourword") I like the idea of constructing a state machine to do all the matching.
- skrebbel 15y ago
  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.
  - someone13 15y ago
    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.
    - skrebbel 15y ago
      That's my point. At work, I'd prefer someone using String.Compare() over some nasty hand-crafted for-loop with switches and things for all kinds of collation issues. Why would I ask something else during the interview? I love the GGP's solution for the same reason. If the regex is compiled only once, it may be only marginally slower (if at all), and it significantly improves readability and maintainability, and tremendously reduces the chances for bugs. I'd hire the him. I have the impression most Google-interviewers (and similar dudes/dudettes) wouldn't. I wonder why.
      - StavrosK 15y ago
        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 backtracking example in the article (although with much less code, and no memoization). That said, I think that the reason interviewers ask about functions for which we have well-known implementations is to see whether or not you know how they work and/or could implement them yourself. Nobody will reasonably expect you to implement your own string comparison routine, but you could score points if, for example, you said Boyer-Moore for string searching rather than the naive iterative version.
NY_Entrepreneur 15y ago
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 would be each of i = 1, 2, ..., n for the given string of length n. But this definition of the stages does not yield a dynamic program because the solution at stage i needs more than just the solution at stage i + 1 and, indeed, potentially needs the solutions at each of stages i + 1, i + 2, ..., n. So, first-cut, there is no dynamic programming solution. For a second-cut, there might be a dynamic programming solution if the author would outline one! There is now some question if the Google interviewers really understand dynamic programming!
- rfurmani 15y ago
  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
  - NY_Entrepreneur 15y ago
    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 < p < j < q, is [p, q] a word. That is, even if [i,j) is a word, we can't conclude yet that it will be a word in the final, feasible 'segmentation' of the whole string. Indeed, even if [j, n] 'segments', we can't yet conclude that those segments will be in the final, feasible segmentation of the whole string [1, n]. 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 < j <= n and ask if [i, j) is a word AND at the same time if [j,n] can be 'segmented'. If so, then say that [i,n] can be segmented. So, in this, first we ask if [j,n] can be segmented since we have already addressed that issue and recorded the result, true or false. 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 <= j < i which is again a break with dynamic programming where we regard each i = 1, 2, ..., n as a stage. 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.
mynegation 15y ago
Quick heads up: page is not rendered properly in Mobile Safari on iPhone: fixed width font lines are cut off.
- dtunkelang 15y ago
  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.
  - pavel_lishin 15y ago
    It's not rendering well for me, either: http://i.imgur.com/Q89gP.png 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. :(
pkteison 15y ago
Bit of a tangent, but a real question: If a writer doesn't approve of a site's behavior (in this case, Glassdoor is desribed as "a site that does not seem to mind when interview candidates violate NDAs"), why does the writer still link to them? Inbound links (w/o a nofollow) help sites, why help sites you don't like?
- access_denied 15y ago
  Because on a conceptual level you are above that. Relevant links also improve the web. Also you may want to spare your inclined readers the fun of googleling the site for themselves.
- dtunkelang 15y ago
  Point taken. I thought of not linking to them, or even not mentioning them. But they do play an important part in the story of the post, and I don't think I'm helping them so much as I'm raising employees' and employers' awareness of their existence. At least now a few more interviewers might check to see if their questions are posted there. From my limited data, interviewees are already more aware of Glassdoor than interviewers. As for feeding them page rank, I don't think I have so much to offer that it helps them materially.
  - logic 15y ago
    > interviewees are already more aware of Glassdoor than interviewers My first amusing thought when reading this was to assume a correlation; ie. that interviewees who lean heavily on Glassdoor prior to interviewing do not eventually become intervewers.
deleted 15y ago
[deleted]
wensing 15y ago
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.
- SoftwareMaven 15y ago
  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.)
  - mason55 15y ago
    The advanced answers to this question require spending a lot of time understanding string processing. Really? Seems like a standard DP question to me
    - btilly 15y ago
      Indeed. The only detail that surprised me was that you could only do exact lookups in the dictionary. That makes it O(n*n). If you had the dictionary stored in a trie it would be O(n) on long strings. (With a maximum constant whose size depends on the length of the longest word in the dictionary.)
      - kragen 15y ago
        You could store the dictionary in a trie in O(m) time before you start. But I don't think it's true that it makes it O(n); being able to tell that the prefix you're considering is the prefix of some word doesn't help you, because you still don't know if the suffix of the string after that word is segmentable. (Or even whether the string contains the entire word.)
Shenglong 15y ago
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.
- dtunkelang 15y ago
  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. :-)
  - Shenglong 15y ago
    You have my sympathy :)
  - cema 15y ago
    Yes, it's basic. But many people who are not fresh out of college may have spent recent years solving a completely different set of programming tasks, and do not have it loaded in their brains. When applicants prepare for an interview, they do not often know what kind of knowledge to load in their heads. For example, just a couple of weeks ago I was asked to figure out a simple bit-flipping scheme, and bit string manipulations are something that I have not thought about in many years. So it took me about 10 minutes for a problem that I would have done in less than a minute when I was spending time thinking about similar things and my mind was full with them. Being prepared for a technical interview does not mean to have memorized a few solutions to a few problems, but it means to have played with them sufficiently to have the brain loaded with the material. This helps with intuition as well as specific technical skills.
pavel_lishin 15y ago
Quick note to the author - holy god, this is annoying: http://i.imgur.com/0cNx4.png http://i.imgur.com/0cNx4.png
- dtunkelang 15y ago
  Sorry. The post renders well in Chrome on my Mac and on my Nexus One. But apparently not so well in other browser / platform combinations.
georgemcbay 15y ago
Why retire the question just because you saw it on Glassdoor? The same question was posted to sureinterview last year, so anyone you hired since November is suspect! (If you believe that potential advance knowledge of the question is relevant). Worse yet, even if you did come up with this problem on your own, this exact problem was a fairly common interview question back in the mid 90s, when string processing interview questions were all the rage for C/C++ programming jobs -- I must have seen it a dozen times in various interviews over the years. The problem is familiar enough that I'd bet a decent amount of money that it must be listed in one of those interview problem books that were popular before the websites for this stuff started showing up over the past couple years... If you really relied on the interviewee having no possible advance knowledge of this question prior to the interview you surely had a false sense of security prior to seeing it appear on glassdoor. As long as you engage the interviewee to see that s/he really understands the answers they are giving, I don't really see why it matters if the question has appeared on one of these sites. If the interviewee is preparing for their interviews enough that they are actually looking at these sites and understanding the answers to the point where they can intelligently discuss them, that probably already puts them in the upper tier of people you'd want to seriously consider hiring, so retiring the question is probably counter-productive unless you have a non-disclosed alternative that you're sure is as good of a question.
ohashi 15y ago
I read this and went, I had someone build this for me years ago! So I looked at the code, it used the efficient solution. Now I am even more impressed with the programmer. I've always thought highly of him (better than me) but it's hard to evaluate someone better than you. His solution ran circles around mine (I had general simple case with 2 words) and now I know exactly how much more efficient his solution was. Very neat.
pbh 15y ago
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 below. http://norvig.com/ngrams/ http://norvig.com/ngrams/
- dtunkelang 15y ago
  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.
mak120 15y ago
Its a nice Dynamic programming problem. The beauty of DP is that simply memorizing one application of it does not guarantee you a solution to an entirely different problem that might have a similar Dynamic Programming solution. Look over the TopCoder SRM archives if you don't believe me. So even though you are retiring this one, coming up with something similar that tests for basically the same things shouldn't be impossible.
svdad 15y ago
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.

173 points by dtunkelang 15y ago

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 our incompetencies are (marginally) harder to hide.

arethuza 15y ago
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 at the time.
- nopassrecover 15y ago
  Iterating over a hashtable (at least in pseudocode if they didn't recall the API functions off-hand) hardly seems a trivia question...
- StavrosK 15y ago
  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?
  - arethuza 15y ago
    No, it's really not - even with the java.util.Hashtable class that was all that Java had at the time. I think it was something that people from a C,C++ background didn't really expect to be able to do.
  - nitrogen 15y ago
    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); } }
    - arethuza 15y ago
      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....
      - onemoreact 15y ago
        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.
        arethuza 15y ago
        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.
        kragen 15y ago
        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 wrong methods on an Enumeration or a Hashtable, how do you tell that they're the wrong methods? How does this work?
  - SoftwareMaven 15y ago
    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).
    - sur 15y ago
      He is using parentheses instead of square brackets, so the code is actually using a generator expression which will produce each value lazily.
      - eru 15y ago
        Is mydict.items() also lazy?
        kragen 15y ago
        In Python 3 yes, in Python 2 no. In Python 2 you'd say mydict.iteritems() if you were concerned about it.
    - kragen 15y ago
      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 because you have a deep knowledge of the implementation of the Python standard library. The temporary list of temporary strings probably will use less memory than the original dict did, though, so it's only a very mild sort of "explosion". It will, however, be several times bigger than the final output string, which also has to be huge if the dictionary is huge. Python doesn't have anything like a StringBuffer. If it did, it would be reasonable for string_join to use it instead of generating a temporary list. The Python code above would look the same. But hey, if you just want to print the values, you could say sys.stdout.printlines("%s: %s\n" % (k, v) for k, v in mydict.items()) but frankly I think I would write instead for k, v in mydict.items(): print "%r: %r" % (k, v)
access_denied 15y ago
That's IMHO not beeing cynical, just realistic. In a world where the bar of what it means to be competent is constantly raised and where the amount of places where competence is needed is growing constantly, you would expect to observe incompetencies increasingly. Add to that the fact that your own abilties to spot incompetencies grow over time too.
dxbydt 15y ago
>sometimes I think the world is awash in incompetence. We see so much of it in tech because our incompetencies are (marginally) harder to hide. A very candid Philip Greenspun in Founders@Work( p341-2) : "In aviation, by the time someone's your employee, their perceived skill and actual skill are reasonably in line. JFK Jr is not working at a charter operation because he's dead. In IT,you have people who think 'I am a great programmer'. But where are the metrics that prove them wrong ? Traffic accidents are very infrequent, so they don't get the feedback that they are a terrible driver. Programmers walk around with a huge overestimate of their capabilities. That's why a lot of them are very bitter. They sit around stewing at their desks. That's why I don't miss IT, because programmers are very unlikable people. They are not pleasant to manage."
- nasmorn 15y ago
  I second that. For musicians it is hard to hide their incompetence, for programmers it is just a matter of picking the right succession of jobs.
- deleted 15y ago
  [deleted]
onemoreact 15y ago
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.

JL2010 15y ago

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

tzs 15y ago

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

VinyleEm 15y ago
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?
dtunkelang 15y ago
Actually, my original implementation used Dijkstra's algorithm. But I think the linear table of suffixes (or prefixes if you prefer) is a cleaner approach.

Havoc 15y ago

Its a great question. Pretty sure its not nearly as much of a secret as the author thinks though. I've seen a detailed write-up before somewhere (HN?) and I'm not even a programmer by profession.

dtunkelang 15y ago
Secret is a strong word -- I link to another post on the subject in the article. Still, seeing it on Glassdoor for my own employer crossed the line of disclosure.

wisty 15y ago

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.

dtunkelang 15y ago
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.
- wisty 15y ago
  There's not too much difference between "people who get dynamic programming, after boning up for the interview", and "people who can answer your dynamic programming question because they read the answer to a similar one while boning up for the interview". Both are probably good candidates.
- jswinghammer 15y ago
  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.
  - cema 15y ago
    I think Google etc are exceptions, people do prepare for technical interviews there.

nandemo 15y ago

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) <- find pairInDict pairs 　 Just (x ++ " " ++ y)

ottbot 15y ago
http://www.codinghorror.com/blog/2007/02/fizzbuzz-the-programmers-stairway-to-heaven.html http://www.codinghorror.com/blog/2007/02/fizzbuzz-the-progra...
- nandemo 15y ago
  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.
eru 15y ago
Yes, doesn't strike me as idiomatic. But I can't come up with a better version on the spot.
zohebv 15y ago
How about this, this will compute more than pairs <pre><code> let dict = Data.Set.fromList["apple", "pie", "bread", "applepie", "piebread"] let fn q = concat.Data.List.map (\(x,y) -> if (member x dict) then if y == "" then [[x]] else Data.List.map (x:) (fn y) else [] ) $ tail $ zip (inits q) (tails q) fn "applepiebread" [["apple","pie","bread"],["apple","piebread"],["applepie","bread"]] </code></pre>
shangaslammi 15y ago
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) <- zip (inits s) (tails s) guard $ hasWord dct i (i:) <$> 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 <- [1..len-i] let w = take l $ drop i s guard $ hasWord dct w (w:) <$> a ! (i+l)

StavrosK 15y ago

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

skrebbel 15y ago
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.
- someone13 15y ago
  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.
  - skrebbel 15y ago
    That's my point. At work, I'd prefer someone using String.Compare() over some nasty hand-crafted for-loop with switches and things for all kinds of collation issues. Why would I ask something else during the interview? I love the GGP's solution for the same reason. If the regex is compiled only once, it may be only marginally slower (if at all), and it significantly improves readability and maintainability, and tremendously reduces the chances for bugs. I'd hire the him. I have the impression most Google-interviewers (and similar dudes/dudettes) wouldn't. I wonder why.
    - StavrosK 15y ago
      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 backtracking example in the article (although with much less code, and no memoization). That said, I think that the reason interviewers ask about functions for which we have well-known implementations is to see whether or not you know how they work and/or could implement them yourself. Nobody will reasonably expect you to implement your own string comparison routine, but you could score points if, for example, you said Boyer-Moore for string searching rather than the naive iterative version.

NY_Entrepreneur 15y ago

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 would be each of i = 1, 2, ..., n for the given string of length n. But this definition of the stages does not yield a dynamic program because the solution at stage i needs more than just the solution at stage i + 1 and, indeed, potentially needs the solutions at each of stages i + 1, i + 2, ..., n. So, first-cut, there is no dynamic programming solution. For a second-cut, there might be a dynamic programming solution if the author would outline one! There is now some question if the Google interviewers really understand dynamic programming!

rfurmani 15y ago
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
- NY_Entrepreneur 15y ago
  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 < p < j < q, is [p, q] a word. That is, even if [i,j) is a word, we can't conclude yet that it will be a word in the final, feasible 'segmentation' of the whole string. Indeed, even if [j, n] 'segments', we can't yet conclude that those segments will be in the final, feasible segmentation of the whole string [1, n]. 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 < j <= n and ask if [i, j) is a word AND at the same time if [j,n] can be 'segmented'. If so, then say that [i,n] can be segmented. So, in this, first we ask if [j,n] can be segmented since we have already addressed that issue and recorded the result, true or false. 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 <= j < i which is again a break with dynamic programming where we regard each i = 1, 2, ..., n as a stage. 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.

mynegation 15y ago

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

dtunkelang 15y ago
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.
- pavel_lishin 15y ago
  It's not rendering well for me, either: http://i.imgur.com/Q89gP.png 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. :(

pkteison 15y ago

Bit of a tangent, but a real question: If a writer doesn't approve of a site's behavior (in this case, Glassdoor is desribed as "a site that does not seem to mind when interview candidates violate NDAs"), why does the writer still link to them? Inbound links (w/o a nofollow) help sites, why help sites you don't like?

access_denied 15y ago
Because on a conceptual level you are above that. Relevant links also improve the web. Also you may want to spare your inclined readers the fun of googleling the site for themselves.
dtunkelang 15y ago
Point taken. I thought of not linking to them, or even not mentioning them. But they do play an important part in the story of the post, and I don't think I'm helping them so much as I'm raising employees' and employers' awareness of their existence. At least now a few more interviewers might check to see if their questions are posted there. From my limited data, interviewees are already more aware of Glassdoor than interviewers. As for feeding them page rank, I don't think I have so much to offer that it helps them materially.
- logic 15y ago
  > interviewees are already more aware of Glassdoor than interviewers My first amusing thought when reading this was to assume a correlation; ie. that interviewees who lean heavily on Glassdoor prior to interviewing do not eventually become intervewers.

deleted 15y ago

[deleted]

wensing 15y ago

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.

SoftwareMaven 15y ago
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.)
- mason55 15y ago
  The advanced answers to this question require spending a lot of time understanding string processing. Really? Seems like a standard DP question to me
  - btilly 15y ago
    Indeed. The only detail that surprised me was that you could only do exact lookups in the dictionary. That makes it O(n*n). If you had the dictionary stored in a trie it would be O(n) on long strings. (With a maximum constant whose size depends on the length of the longest word in the dictionary.)
    - kragen 15y ago
      You could store the dictionary in a trie in O(m) time before you start. But I don't think it's true that it makes it O(n); being able to tell that the prefix you're considering is the prefix of some word doesn't help you, because you still don't know if the suffix of the string after that word is segmentable. (Or even whether the string contains the entire word.)

Shenglong 15y ago

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.

dtunkelang 15y ago
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. :-)
- Shenglong 15y ago
  You have my sympathy :)
- cema 15y ago
  Yes, it's basic. But many people who are not fresh out of college may have spent recent years solving a completely different set of programming tasks, and do not have it loaded in their brains. When applicants prepare for an interview, they do not often know what kind of knowledge to load in their heads. For example, just a couple of weeks ago I was asked to figure out a simple bit-flipping scheme, and bit string manipulations are something that I have not thought about in many years. So it took me about 10 minutes for a problem that I would have done in less than a minute when I was spending time thinking about similar things and my mind was full with them. Being prepared for a technical interview does not mean to have memorized a few solutions to a few problems, but it means to have played with them sufficiently to have the brain loaded with the material. This helps with intuition as well as specific technical skills.

pavel_lishin 15y ago

Quick note to the author - holy god, this is annoying: http://i.imgur.com/0cNx4.png http://i.imgur.com/0cNx4.png

dtunkelang 15y ago
Sorry. The post renders well in Chrome on my Mac and on my Nexus One. But apparently not so well in other browser / platform combinations.

georgemcbay 15y ago

Why retire the question just because you saw it on Glassdoor? The same question was posted to sureinterview last year, so anyone you hired since November is suspect! (If you believe that potential advance knowledge of the question is relevant). Worse yet, even if you did come up with this problem on your own, this exact problem was a fairly common interview question back in the mid 90s, when string processing interview questions were all the rage for C/C++ programming jobs -- I must have seen it a dozen times in various interviews over the years. The problem is familiar enough that I'd bet a decent amount of money that it must be listed in one of those interview problem books that were popular before the websites for this stuff started showing up over the past couple years... If you really relied on the interviewee having no possible advance knowledge of this question prior to the interview you surely had a false sense of security prior to seeing it appear on glassdoor. As long as you engage the interviewee to see that s/he really understands the answers they are giving, I don't really see why it matters if the question has appeared on one of these sites. If the interviewee is preparing for their interviews enough that they are actually looking at these sites and understanding the answers to the point where they can intelligently discuss them, that probably already puts them in the upper tier of people you'd want to seriously consider hiring, so retiring the question is probably counter-productive unless you have a non-disclosed alternative that you're sure is as good of a question.

ohashi 15y ago

I read this and went, I had someone build this for me years ago! So I looked at the code, it used the efficient solution. Now I am even more impressed with the programmer. I've always thought highly of him (better than me) but it's hard to evaluate someone better than you. His solution ran circles around mine (I had general simple case with 2 words) and now I know exactly how much more efficient his solution was. Very neat.

pbh 15y ago

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 below. http://norvig.com/ngrams/ http://norvig.com/ngrams/

dtunkelang 15y ago
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.

mak120 15y ago

Its a nice Dynamic programming problem. The beauty of DP is that simply memorizing one application of it does not guarantee you a solution to an entirely different problem that might have a similar Dynamic Programming solution. Look over the TopCoder SRM archives if you don't believe me. So even though you are retiring this one, coming up with something similar that tests for basically the same things shouldn't be impossible.

svdad 15y ago

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.