+ 4

Majority vote efficient implementation

election time ! Each candidate is represented by a letter a..z. You need to tell if one candidate get the majority of the votes and wins, or not. Make a program taking a string as input and displays the letter of the winning candidate or "" if nobody wins a majority. Bonus: do it in one pass, dont use builtin find/count functions and limited memory use in the main loop. aaaeecacffggaa => a iibcidieei => "" (i gets just 50% of the votes, you need at least 50%+1 vote to have a majority) abcde => ""

26th Dec 2017, 11:39 AM
VcC
VcC - avatar
12 Respuestas
+ 3
Here is a Java solution I think it's very efficient. This solution uses a map for counting all votes while iterating ones through the given Input String. Then it iterates through the map to analize it and return a result. If you have an input String of length n and m different candidates, this solution needs n+m steps to return a solution. The memory used is the used map with m entries. Solution: https://code.sololearn.com/cHu3H6de9t99/?ref=app Btw, your example is wrong: aaaeecacffgga --> 5x 'a', 2x 'c', 2x 'e', 2x 'f', 2x 'g' so 'a' has 38.5 % and it's not an absolute majority which you want to get as a result. Which is implied by your second example about the 'i'. Here is a working example: aaabbac --> returns 'a'
26th Dec 2017, 5:05 PM
Andreas K
Andreas K - avatar
27th Dec 2017, 1:10 PM
LukArToDo
LukArToDo - avatar
+ 8
Thank you Andreas. It has now been modified for the winner with non-absolute majority. In case we have an equal score - there is no winner. In one pass 😊
27th Dec 2017, 2:53 PM
LukArToDo
LukArToDo - avatar
+ 1
Nice modification to my solution. An integration of the analysis into the counter phase. Well done. Didn't see it while programming my one. But this is just possible for absolute majority. So for a special case. So it's great for this challenge.
27th Dec 2017, 2:09 PM
Andreas K
Andreas K - avatar
+ 1
well done. @Luka
27th Dec 2017, 2:56 PM
Andreas K
Andreas K - avatar
0
I would like to see a solution with n steps // For others, n represents the length of the input String// And thanks for your quick view on the code.
26th Dec 2017, 5:13 PM
Andreas K
Andreas K - avatar
0
Oh I would appreciate to see the code to this. It seems like a type of predictive algorithm by analysing while counting through the String, isn't it?
26th Dec 2017, 5:58 PM
Andreas K
Andreas K - avatar
0
Nice solution.
26th Dec 2017, 6:26 PM
Andreas K
Andreas K - avatar
- 1
good one. note that n is possible though.
26th Dec 2017, 5:10 PM
VcC
VcC - avatar
- 1
@andreas the n steps, 2 variables no array solution only works when there is a winner (if there is not, it returns a letter without telling there no winner)
26th Dec 2017, 5:54 PM
VcC
VcC - avatar
- 1
If you want to be sure you are a real winner you need a second pass. Since the code is very simple this should be faster than any other solution
26th Dec 2017, 6:29 PM
VcC
VcC - avatar