21–30 of 250 posts
Earlier quoted context omitted.
I'm glad you do cool stuff day to day and not need this. But I would disagree that what you do is foundational, whereas string matching is absolutely foundational.
String matching, like == or string.compare? Anything more complicated than that and you're not building anything that isn't already available.
Earlier quoted context omitted.
The subsequences of a string X are any strings Y such that Y is X with zero or more characters dropped, with the condition that the original characters of X must remain in the same order. As an example, the string "help" has 16 subsequences: ["", "h", "e", "l", "p", "he", "hl", "hp", "el", "ep", "lp", "hel", "hep", "hlp", "elp", "help"]. Note that the set of subsequences are isomorphic to the power set (assuming repe…
Okay gotcha. So for each word in the length-sorted set, walk the string "picking up" characters as you go. If you complete the word, that's your answer. I'm sure there's a faster or more mathematical answer. But that would be my napkin python. (Edits made)
EDIT: You shouldn't sort the list beforehand. You should compile the list of matched candidates after walking through the whole string and pick the longest match. (Or just represent the matched candidates in a list of bools). It's possible that your answer only happens to match the last few characters of your haystack, so you must walk the entire length of the haystack.
EDIT2: This solution also makes a bunch of assumptions and you can find a better runtime in certain cases. For example, if you have many more candidates than the length of your haystack, it might be worthwhile to generate all O(2^n) subsequences and store them in a hashmap/bloom filter. Then you can do (almost) O(1) lookups for each word. This would also lend well to a distributed compute approach: you could have k machines sharded in this manner: the first machine computes and stores in your hashmap/bloom filter the first 2^n/k subsequences, the second the second 2^n/k, etc. Then you can either 1) in the case of hashmaps, fan out each request to each machine, succeeding if any machine succeeds or 2) merge the bloom filters on a central machine (assuming the same hash functions and modulus constants) and do O(1) lookups. (Copying hashmaps is O(data stored inside); merging bloom filters is O(bloom filter size).)
Earlier quoted context omitted.
Okay gotcha. So for each word in the length-sorted set, walk the string "picking up" characters as you go. If you complete the word, that's your answer. I'm sure there's a faster or more mathematical answer. But that would be my napkin python. (Edits made)
You probably don't need a dict; just a list of candidates. And you should clarify that you should sort your list by reversed word length and keep another list of indexes into each word. EDIT: You shouldn't sort the list beforehand. You should compile the list of matched candidates after walking through the whole string and pick the longest match. (Or just represent the matched candidates in a list of bools). It's pos…
Earlier quoted context omitted.
Honestly I don't care about the algorithms and data structures used for string search, or event sourcing for that matter. I use that code to build stuff. There's a vanishingly small portion of the population devoted to these problems, and indeed most of those people are probably working on search at Google or something similar. Calling them "foundational" is a joke. They're important, absolutely -- we all use them da…
What would you consider foundational?
I'd place a person's debugging skills, their ability to predict bugs, system design, knowledge of common (applicable) libraries (more so knowing when to use them, not method signatures), and perhaps even ethics above algorithms. Probably many more but there's a couple to start. Having never needed to build my own sorting algorithm in 14 years of coding, I'm pretty confident I don't need an engineer who can do that, either.
"Given a string S and a set of words D, find the longest word in D that is a subsequence of S." Found under "Foundations of programming" -- this is exactly the type of problem I'd expect as question one under this section. When it's made by Googlers, that is. I make a lot of cool stuff day to day, and usually that requires a lot of code and knowledge about programming and topics that are rather advanced (currently I'…
Seems like a pretty normal algorithms problem to me. Anyone that's taken a CS curriculum has done plenty of them.
Earlier quoted context omitted.
Okay gotcha. So for each word in the length-sorted set, walk the string "picking up" characters as you go. If you complete the word, that's your answer. I'm sure there's a faster or more mathematical answer. But that would be my napkin python. (Edits made)
You probably don't need a dict; just a list of candidates. And you should clarify that you should sort your list by reversed word length and keep another list of indexes into each word. EDIT: You shouldn't sort the list beforehand. You should compile the list of matched candidates after walking through the whole string and pick the longest match. (Or just represent the matched candidates in a list of bools). It's pos…
Yeah I'm convinced I wouldn't bother with something beyond my basic idea until I profile.
"Given a string S and a set of words D, find the longest word in D that is a subsequence of S." Found under "Foundations of programming" -- this is exactly the type of problem I'd expect as question one under this section. When it's made by Googlers, that is. I make a lot of cool stuff day to day, and usually that requires a lot of code and knowledge about programming and topics that are rather advanced (currently I'…
Huh. I was thinking it seemed like a fairly reasonable question. You sort D by length, and then iterate through it doing a kind of string matching. Both of those operations are pretty "foundational" in programming, right? I'd be curious what you think a better question would be. It's not for brand new programmers - it says the pre-req is a couple of previous computing courses.
While sorting might work out in the best case for a long String and a few words of different length so you can terminate early, you just made a problem that is solvable in average in O(|S| * |D|) to O(|S| * |D| * log(|D|)). If you don't realize this and the implications, I would assume you just failed your interview.
"Given a string S and a set of words D, find the longest word in D that is a subsequence of S." Found under "Foundations of programming" -- this is exactly the type of problem I'd expect as question one under this section. When it's made by Googlers, that is. I make a lot of cool stuff day to day, and usually that requires a lot of code and knowledge about programming and topics that are rather advanced (currently I'…
>currently I'm building a distributed collaboration system with event sourced data in Microsoft Orleans I know it's easy and fun to use frameworks that abstract all the gory low-level details (the equivalent of calling a built-in sort function on a list of numbers), but somebody has to write those frameworks at some point. Don't get me wrong, I'm certainly impressed with the work that the Orleans team did and it woul…
Earlier quoted context omitted.
You probably don't need a dict; just a list of candidates. And you should clarify that you should sort your list by reversed word length and keep another list of indexes into each word. EDIT: You shouldn't sort the list beforehand. You should compile the list of matched candidates after walking through the whole string and pick the longest match. (Or just represent the matched candidates in a list of bools). It's pos…
I guess it depends on profiling real world behaviour. If you walk the list only a few times because long words are present, that's better than walking the list once and for each character, walking your set of words. Or if most words aren't a match early on, you'll cull the candidate set pretty quickly. Yeah I'm convinced I wouldn't bother with something beyond my basic idea until I profile.
"Given a string S and a set of words D, find the longest word in D that is a subsequence of S." Found under "Foundations of programming" -- this is exactly the type of problem I'd expect as question one under this section. When it's made by Googlers, that is. I make a lot of cool stuff day to day, and usually that requires a lot of code and knowledge about programming and topics that are rather advanced (currently I'…
the site probably should have presented these puzzles from a different perspective, so that it is easier for people to recognize the message about what kind of programmer skills and mindset it is looking for.