Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: What are your favorite algorithms?

news.ycombinator.com

Post reply on HN
Print view View original

81–90 of 93 posts

Re: Ask HN: What are your favorite algorithms?

#81

Post by bfors »

sherincall wrote: post #67
huhtenberg wrote: post #63

Earlier quoted context omitted.

Hacky, trashes CPU cache, the code itself is on a sloppy side and, most importantly, it lacks the elegance of the original solution. So I beg to differ, it's not really "better" by any metric.

It was tongue-in-cheek (see the smiley face), your critiques are all spot on, but there is one thing where it is objectively better: Tortoise and hare can only detect that a cycle exists. This hack will tell you exactly which node the cycle starts on. That means that if you want to e.g. repair a list, you can just cut that last link and set it to either null or root. Granted, this wasn't the original problem.

Tortoise and hare can actually tell you which node the cycle starts on.

  1 -> 2 -> 3 -> 4 -> 5 -> 6
            ^              |
            |______________|

  Step:       0 1 2 3 4
  Tortoise:   1 2 3 4 5 
  Hare:       1 3 5 3 5
Then create another tortoise pointer at the head, iterate until both tortoises point to the same node.

  Step:       0 1 2
  Tortoise:   5 6 3
  Tortoise2:  1 2 3

Re: Ask HN: What are your favorite algorithms?

#83

Post by theemathas »

palashkulsh wrote: post #64
zelah wrote: post #32

Earlier quoted context omitted.

I vote twice for this one!

Any laymen explanation ? Not able to grasp the concept.

It does two things concurrently: (1) search for an algorithm along with proofs for its correctness and time upper bound (2) run the fastest algorithm found so far, possibly aborting an slower algorithm when a faster one is found.

Everything is scheduled so it's asymptotically optimal. However, there's an added cost to search for algorithms. This cost is exponential in the proof length, but constant for each problem since it is independent from the inputs. Of course, this constant is ridiculously huge.

Re: Ask HN: What are your favorite algorithms?

#85

Post by haidrali »

sameera_sy wrote: post #44
haidrali wrote: post #43

I really like majority voting algorithm to get majority number in array which appears more then half of the elements, Its the most simplest and elegant algorithm i have studied http://www.geeksforgeeks.org/majority-element/

I'm surprised how the solution doesn't have the hashmap implementation of it, which gives out o(n) and is much more simple. But the algorithm is interesting though!

@sameera_sy thats the point hash map solution will take O(n) space complexity as well consider a situation where you need memory efficient solution

Re: Ask HN: What are your favorite algorithms?

#88

Post by jones1618 »

Cuckoo Hashing: http://www.lkozma.net/cuckoo_hashing_visualization/

"An elegant method for resolving collisions in hash tables... It has the rare distinction of being easy to implement and efficient both in theory and practice."

It does an amazing job of packing values into N hash tables so there's very little dead space but lookups are very fast.

Re: Ask HN: What are your favorite algorithms?

#89

Post by jones1618 »

jnpatel wrote: post #9

Bloom filters: https://en.wikipedia.org/wiki/Bloom_filter

Agreed. Bloom filters are amazingly useful for checking membership in a set while taking much less space than a database or hash table. They achieve this by being crazily "probabilistic", sacrificing a small amount of accuracy for speed and compactness. Still, this sort of broken, degenerate hash table has found a ton of uses in everything from spell checkers to distributed content networks.
Post reply on HN