CppCon 2017: Nicholas Ormrod “Fantastic Algorithms and Where To Find Them”
Why Stack Overflow recommends it
Stack Overflow users link it when explaining Morris tree traversal or the heavy hitters (majority element) algorithm.
Recommended by 1 people across 1 different months, 2020 to 2021.
What it is
A CppCon 2017 talk by Facebook engineer Nicholas Ormrod on lesser-known but practical algorithms. Topics include heavy hitters for spotting abusive traffic, Morris traversal for destroying trees without blowing the stack, and war stories of using them in production.
What people said
Recommends n314159 · 2020-02 · Stack Overflow · on “Why use morris traversal not recursion in binary tree or binary search tree?”
That is only true if you are able to do tail recursion. This talk [this video] (right before the 12 minute-mark) has a in my opinion very good explanation on the algorithm and what its advantages are
Cites Surt · 2021-07 · Stack Overflow · on “Find the frequency of number repeates (r-l+1)/2 times in range [l:r]”
Appear more than half the time, sounds like one of the algorithms from "fantastic algorithms and where to find them" [this video] see the part heavy hitters.
Cites Ander · 2021-08 · Stack Overflow · on “Find the frequency of number repeates (r-l+1)/2 times in range [l:r]”
I have no idea about such data structure, but I find an solution for this problem. If Ri - Li + 1 is odd, there may have two elements appear (Ri - Li + 1) / 2 times. Which one do you want to get? We can use the algorithm beblow to get one of them and the algorithm can get all of these two if you want. If there are just few queries satisfy \sum (Ri - Li) are small enough, get the answer for each [Li, Ri] separately. For each [Li, Ri] ,we can use a O(Ri - Li) time, O(1) auxiliary memory algorithm to get the answer. If there is a x appears exactly (Ri - Li + 1) / 2 times , at least one of three case below must happend (suppose Ri > Li ). x appears (Ri - Li + 1) / 2 times in [Li, Ri - 1] . x app