81–90 of 122 posts
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)
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).
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())
for k, v in mydict.items():
print "%r: %r" % (k, v)Earlier quoted context omitted.
He is using parentheses instead of square brackets, so the code is actually using a generator expression which will produce each value lazily.
Is mydict.items() also lazy?
Earlier quoted context omitted.
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.
Earlier quoted context omitted.
The advanced answers to this question require spending a lot of time understanding string processing. Really? Seems like a standard DP question to me
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.)
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.
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…
Perhaps that was rhetorical, but I'll answer anyway:
Being able to wire up existing libraries to accomplish a goal is a pretty low bar to set as far as proficiency goes. Google doesn't want code monkeys. The solution above is perfectly good from a software engineering perspective, but it doesn't show the depth of the candidates knowledge nor how strong their grasp of CS techniques is.
Google's interviews are more like IQ tests than software engineering tests, using CS as the measuring tool. When you're Google you can afford to be that selective.
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.
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…
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 memoization but not dynamic programming, you might invent dynamic programming in response to this question.)
I think this is at the opposite end of the spectrum from your CSS example. Dynamic programming has nothing to do with string processing or with any other particular domain. There's a list of 29 significant algorithms that apply it at http://en.wikipedia.org/wiki/Dynamic_programming#Algorithms_.... It might qualify as "deep knowledge", but it's not deep domain knowledge; it's the kind of deep knowledge that would make you want to hire someone from a different domain.
Earlier quoted context omitted.
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.)
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.)
Once you've scanned the string, only then do you discover whether the whole string is segmentable.
Put another way, while you're processing you don't immediately know whether or not the whole string is segmentable. But having a trie can let you discard possibilities early. Discarding work early means doing less work means being more efficient.
Only slightly joking: re.findall("(your|dict|here)", "yourword") I like the idea of constructing a state machine to do all the matching.
>>> re.compile('|'.join(open('/usr/share/dict/words').read().split()), re.I)
OverflowError: regular expression code size limit exceeded
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…
The trouble with the question is that proper code to compare strings is almost certainly going to be a call to some existing library function. There are only rare cases (e.g. when you're one of the 50 people in the world who implement libc) that it makes sense to write it yourself. It's not clear from "code a string compare" exactly which set of wheels the interviewer wants reinvented: if strcmp is out of bounds, can you use strlen and memcmp? Because if strcmp was somehow buggy, that might be a reasonable thing to do. If the problem is that strcmp is too slow, should we maybe drop to assembly? Or change to a counted-string representation to avoid byte-by-byte operations? Or calculate hashes when strings are mutated, or intern them?
(Maybe in C strcmp is a bad example, since
while (*s && *s == *t) {
s++;
t++;
}
return *t - *s;
> If I was the interviewer I'd create a new data structure Foo and then ask the candidate to implement Foo.compare().
I think that's a better approach.