Hacker News Reader

Comment by kevingadd | Hacker News Reader

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

View on HN

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/03043975939...

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.

I love to be surprised like that in interviews, let me tell you. Makes my decision much easier.

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

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

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?

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.

Wikipedia says Boyer Moore is O(n+m) which is the same as this algorithm.

https://en.wikipedia.org/wiki/Boyer-Moore_string_search_algo...

That's worst case complexity. It's the average case where Boyer Moore wins over KMP.

Reply on news.ycombinator.com