The fact that the sequence A, A, A, B, B, C output C as the leader is a bit underwhelming.
I find the (n/2 + 1) majority limitation a little harsh, but indeed it's an elegant solution to a very common problem.
People will sometimes get stuck on that point and disregard the algorithm. I love that someone out there posted this as a puzzle which is solvable in linear time BUT has this perfect unique solution.
Lead Developer: Adobe Experience Manager.
Father of one.
Minnesota.
Occasionally write here: ahmedmusallam.com and there: https://blogs.perficientdigital.com/author/amusallam/
Could not help but rewrite it in javascript to help me understand it better. It's not the syntax, but me trying to wrap my head around it. here is what I have:
functionfindLeader(votes){// after one vote, we have a leaderletleader=votes[0];letcount=1;for(i=1;i<votes.length;i++){letvote=votes[i]if(vote===leader)// the lead may growcount++;else// or shrinkcount--;// and they may be replacedif(count==0){leader=vote;count=1;}}returnleader;}console.log(findLeader(['a','b','a','c','b','c','a','a']));// "a"console.log(findLeader([0,1,1,0,1,0,1,1]));// "1"
Lead Developer: Adobe Experience Manager.
Father of one.
Minnesota.
Occasionally write here: ahmedmusallam.com and there: https://blogs.perficientdigital.com/author/amusallam/
Bachelor's and Master's in CS from MIT. Previously, worked @ Microsoft & Zynga. Currently Co-Founder of Moesif (moesif.com), the most advanced API analytics platform.
The leader election algorithms, who knew that have computers making seemingly simple decisions in a distributed setting could be so hard and fascinating.
The fact that the sequence A, A, A, B, B, C output C as the leader is a bit underwhelming.
I find the (n/2 + 1) majority limitation a little harsh, but indeed it's an elegant solution to a very common problem.
It seems pretty rare that you'd have a large data set and know that there is a majority without knowing what that majority is. But if that was the case, then this would be the optimal algorithm.
It was more important when older computers had different restrictions:
Note that the algorithm fetches the elements of A in linear order. Thus, the algorithm can be used efficiently when the number of votes is so large that they must be read from magnetic tape.
"Even when the input sequence has no majority, the algorithm will report one of the sequence elements as its result....This second pass is needed, as it is not possible for a sublinear-space algorithm to determine whether there exists a majority element in a single pass through the input."
The fact that the sequence
A, A, A, B, B, Coutput C as the leader is a bit underwhelming.I find the
(n/2 + 1)majority limitation a little harsh, but indeed it's an elegant solution to a very common problem.People will sometimes get stuck on that point and disregard the algorithm. I love that someone out there posted this as a puzzle which is solvable in linear time BUT has this perfect unique solution.
If you enjoy perfs related algo puzzles, I really liked solving this one: codingame.com/training/medium/stoc...
Overall, codingame is a great website.
This looks neat! Thanks for sharing.
This is awesome!!
Could not help but rewrite it in javascript to help me understand it better. It's not the syntax, but me trying to wrap my head around it. here is what I have:
Looks great! Watch out for
unshift()which could have an O(n) runtime.ah, good point, updated!
The leader election algorithms, who knew that have computers making seemingly simple decisions in a distributed setting could be so hard and fascinating.
en.wikipedia.org/wiki/Leader_election
Wow! Really fascinating stuff. I’m interested in some of the code behind this.
Your naive solution needs a bit of updating. You never update the max_votes and as such such will only remain 0. Should be
You’re correct! I must have typoed when I copied it over. Thanks, updated.
Took me quite some time to comprehend. Good one though!
But I have a couple genuine questions.
Is this algorithm practically applicable? If we needed to implement a voting system, would we use this algorithm?
And, will this behavior reflect in real life where we have huge number of elements?
The fact that the sequence
A, A, A, B, B, Coutput C as the leader is a bit underwhelming.I find the
(n/2 + 1)majority limitation a little harsh, but indeed it's an elegant solution to a very common problem.It seems pretty rare that you'd have a large data set and know that there is a majority without knowing what that majority is. But if that was the case, then this would be the optimal algorithm.
It was more important when older computers had different restrictions:
Your code is missing an important element:
Otherwise, [A, B, C] => C
Hi Valentin, a majority element cannot be confirmed with one-pass but if there is a majority element (as per the problem statement) it will be found 🔍