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.
Retiring a Great Interview Problem
31–40 of 122 posts
Re: Retiring a Great Interview Problem
#32Earlier 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…
I see, thanks. It's more complicated than the Python version, which does the iteration implicitly, but I'm still surprised that nobody was able to do it.
Re: Retiring a Great Interview Problem
#33Only slightly joking: re.findall("(your|dict|here)", "yourword") I like the idea of constructing a state machine to do all the matching.
bzzt wrong. >>> re.findall('(a|aa|aaa|ab)', 'aaab') ['a', 'a', 'a'] The correct answer would be ['aa', 'ab'] but unfortunately findall works greedily and so will not find the optimal solution. It is possible to specify it as a regex, but common implementations might take too much time to come up with the good solution.
The mistake arises from the different semantics of findall versus what I initially wanted to do. I initially tried "^(dict|here)+$", which should return all the subwords, but doesn't (it only returns the last one).
I'm missing something, clearly, but my initial idea was a state machine that contained all the words (sorted by length, perhaps, but that's not necessary if we don't care about the solution with the "most words") and linked back to itself. It's essentially the same as the backtracking example, from a cursory glance.
Of course, findall is a dumb version that only finds disjoint substrings.
EDIT: It turns out that the group count in regexps is fixed, so it's not possible to return all matches of a single group, even if it's repeated. All my solution above does is show you whether there's a match or not, but not what it is (unless it's the single word).
Re: Retiring a Great Interview Problem
#34Earlier 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.
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 treme…
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.
Re: Retiring a Great Interview Problem
#35Only slightly joking: re.findall("(your|dict|here)", "yourword") I like the idea of constructing a state machine to do all the matching.
This was actually going to be my solution as well. Regex engines are optimised for exactly this sort of problem, why duplicate the work manually?
rfumani gave one reason: it won't produce the right answer. Here's another: your regex engine will probably fall over dead if you ask it apply a million-word alternation.
Re: Retiring a Great Interview Problem
#36Earlier quoted context omitted.
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....
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.
Re: Retiring a Great Interview Problem
#37The author just mentioned dynamic programming. Usually in dynamic programming, e.g., as in Dreyfus and Law, to say that a problem has a dynamic programming solution we outline the solution. But the author did not outline such a solution. An outline usually includes at least the definition of the 'stages' of the dynamic programming solution. For the problem of 'string segmentation', the obvious selection of stages wou…
The article actually includes a solution that uses memoization, which is equivalent to DP.
I wouldn't say "is equivalent to"; rather "is a form of". While it is a dynamic programming technique, unless it's specified people tend to think of the bottom-up approach to be what's implied by "dynamic", with memoization being a special case. Yes, it's semantics, but I think that where the GP was coming from.
Re: Retiring a Great Interview Problem
#38I 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…
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.
Re: Retiring a Great Interview Problem
#39Bit 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?
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.
Re: Retiring a Great Interview Problem
#40Its 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.
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.