Knuth–Morris–Pratt algorithm • Hacker News Board

Re: Knuth–Morris–Pratt algorithm

#21

Post by gedrap » Sat, Jul 05, 2014, 5:49 PM UTC

volaski wrote: post #13

Why is KMP on the front page of HN? Not complaining, just confused. Is this related to some other news?

Because it takes just a few votes (4-7 in first ~45min, from my experience) to bring something up to the front page. Plus a cool name, I guess.

Re: Knuth–Morris–Pratt algorithm

#22

Post by gedrap » Sat, Jul 05, 2014, 5:51 PM UTC

noir_lord wrote: post #12

foobarian wrote: post #8

Earlier quoted context omitted.

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

Re: Knuth–Morris–Pratt algorithm

#23

Post by fengjingchao » Sat, Jul 05, 2014, 6:06 PM UTC

volaski wrote: post #13

Why is KMP on the front page of HN? Not complaining, just confused. Is this related to some other news?

Because people like you and me are bored enough to reply here..

Re: Knuth–Morris–Pratt algorithm

#24

Post by devcpp » Sat, Jul 05, 2014, 6:14 PM UTC

DanBC wrote: post #14

volaski wrote: post #13

Why is KMP on the front page of HN? Not complaining, just confused. Is this related to some other news?

It's a weekend and other material surfaces.

Yup welcome to the slow hours in the weekend on HN. Personally, I like the change.

Re: Knuth–Morris–Pratt algorithm

#25

Post by mightybyte » Sat, Jul 05, 2014, 6:29 PM UTC

kevingadd wrote: post #2

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 optim…

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.

Re: Knuth–Morris–Pratt algorithm

#26

Post by blencdr » Sat, Jul 05, 2014, 6:33 PM UTC

volaski wrote: post #13

Why is KMP on the front page of HN? Not complaining, just confused. Is this related to some other news?

reminds me that I implemented it 10 years ago... and forgot it in the meantime. It's nice to see a good old friend.

Re: Knuth–Morris–Pratt algorithm

#27

Post by Cieplak » Sat, Jul 05, 2014, 6:39 PM UTC

Here is the boost implementation: http://www.boost.org/doc/libs/1_55_0/libs/algorithm/doc/html...

Re: Knuth–Morris–Pratt algorithm

#28

Post by brudgers » Sat, Jul 05, 2014, 7:08 PM UTC

volaski wrote: post #13

Why is KMP on the front page of HN? Not complaining, just confused. Is this related to some other news?

Because it is of interest to hackers and rightly so. Some submittals are good because they are cutting edge, others because they touch on the fundamental - the magical - aspects of computing.

In terms is it being news, it's a bit of a feature story rather than on the scene reporting of a city council meeting or a cub's coverage of the police blotter or the Chamber of Commerce recent press release wrapped up as news.

If nothing else it's better than a blog post about the algorithm, and for me it's always helpful to be reminded what an amazing resource Wikipedia has become for computer science topics.