6 ms·

I've always liked the elegance of this algorithm, fun little example of how you can make things incredibly fast by thinking about your problem. And a related a

I've always liked the elegance of this algorithm, fun little example of how you can make things incredibly fast by thinking about your problem. And a related anecdote: I was interviewing at Apple for a systems development related role (graphics drivers, I think?) and one of the senior-level folks asked me to write strstr on the whiteboard. I started with a naive, working implementation, then he asked me how I'd optimize it. I said 'knuth morris pratt' and gave a basic overview of the algorithm and explained how it's faster. He insisted the algorithm couldn't possibly work. I spent a few more minutes trying to explain it, but I couldn't convince him. The dark magic of efficient string searches evades us all sometimes, I suppose. I always like coming away from an interview feeling like I learned something, so I hope he googled the algorithm later. :-)

jiggy2011 12y ago
That's the risk with interview questions, that the candidate suggests a better solution that the interviewer anticipated. Leaving the interviewer with the task of ascertaining whether the solution is correct.
- foobarian 12y ago
  I love to be surprised like that in interviews, let me tell you. Makes my decision much easier.
  - noir_lord 12y ago
    > Makes my decision much easier. You didn't say which way, I've worked with and for people who wouldn't hire someone smarter than them, the human psyche is a dark place.
    - gedrap 12y ago
      That's true. On other hand, it's just for the interviewees own good - you don't want to work with people like that ;) except from megacorps with hundreds and thousands of devs
- taeric 12y ago
  This story is borderline baffling, though. If you flat out named the algorithm and it contains a famous name like Knuth, that should be good enough to go. That you may not have all of the points of it memorized is irrelevant. Now, if you name a very obscurely named algorithm, that is one thing. But seriously, Knuth!? Is anyone involved with optimizations and serious algorithm design not aware of that name?
mightybyte 12y ago
IMO the Boyer-Moore string searching algorithm is way more elegant. Average case performance of O(n/m)?!? That means that the longer the string you're searching for the faster you can find it! It obviously makes perfect logical sense once you think about it, but when I first heard about the algorithm it seemed magical.
- pedrocr 12y ago
  Wikipedia says Boyer Moore is O(n+m) which is the same as this algorithm. https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm#Performance https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algo...
  - mightybyte 12y ago
    That's worst case complexity. It's the average case where Boyer Moore wins over KMP.
bitdiddle 12y ago
There's some interesting theoretical work that was done by Srinivas in the 90s[1], that takes a geometric view of pattern matching, based on sheaves, and uses it to derive a generalized version of KMP that can be applied in other domains. I'm not sure what happened to this research program, and forget most of the details, but I heard a talk by Srinivas and recall thinking it was a very practical and real application of category theory. [1] http://www.sciencedirect.com/science/article/pii/030439759390239P http://www.sciencedirect.com/science/article/pii/03043975939...

jiggy2011 12y ago

That's the risk with interview questions, that the candidate suggests a better solution that the interviewer anticipated. Leaving the interviewer with the task of ascertaining whether the solution is correct.

foobarian 12y ago
I love to be surprised like that in interviews, let me tell you. Makes my decision much easier.
- noir_lord 12y ago
  > Makes my decision much easier. You didn't say which way, I've worked with and for people who wouldn't hire someone smarter than them, the human psyche is a dark place.
  - gedrap 12y ago
    That's true. On other hand, it's just for the interviewees own good - you don't want to work with people like that ;) except from megacorps with hundreds and thousands of devs
taeric 12y ago
This story is borderline baffling, though. If you flat out named the algorithm and it contains a famous name like Knuth, that should be good enough to go. That you may not have all of the points of it memorized is irrelevant. Now, if you name a very obscurely named algorithm, that is one thing. But seriously, Knuth!? Is anyone involved with optimizations and serious algorithm design not aware of that name?

mightybyte 12y ago

IMO the Boyer-Moore string searching algorithm is way more elegant. Average case performance of O(n/m)?!? That means that the longer the string you're searching for the faster you can find it! It obviously makes perfect logical sense once you think about it, but when I first heard about the algorithm it seemed magical.

pedrocr 12y ago
Wikipedia says Boyer Moore is O(n+m) which is the same as this algorithm. https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm#Performance https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algo...
- mightybyte 12y ago
  That's worst case complexity. It's the average case where Boyer Moore wins over KMP.

bitdiddle 12y ago

There's some interesting theoretical work that was done by Srinivas in the 90s[1], that takes a geometric view of pattern matching, based on sheaves, and uses it to derive a generalized version of KMP that can be applied in other domains. I'm not sure what happened to this research program, and forget most of the details, but I heard a talk by Srinivas and recall thinking it was a very practical and real application of category theory. [1] http://www.sciencedirect.com/science/article/pii/030439759390239P http://www.sciencedirect.com/science/article/pii/03043975939...