Working on machines without understanding them ? Then you should be here..
Geographical location should not become a barrier to Share our knowledge.
Puzzles and Interview question are intended to be discussed here.
A majority element in an array A, of size N is an element that appears more than N/2 times (and hence there is atmost
one such element)
Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:
I/P : 3 3 4 2 4 4 2 4 4
O/P : 4
I/P : 3 3 4 2 4 4 2 4
O/P : NONE
Obvious answer is create a binary search tree. When you get one element insert it. If the element exists increase count by one in the node. After insertion traverse the tree for the required element!
But the real and smart answer is something else.
A Linear Time Majority Vote Algorithm (linear time)
Scan the array elements, while scanning elements maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.
When we move the pointer forward over an element e:
* If the counter is 0, we set the current candidate to e and we set the counter to 1.
* If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.
But if you must confirm that the chosen element is indeed the majority element, you must take one more linear pass through the data to do it.
one such element)
Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:
I/P : 3 3 4 2 4 4 2 4 4
O/P : 4
I/P : 3 3 4 2 4 4 2 4
O/P : NONE
Obvious answer is create a binary search tree. When you get one element insert it. If the element exists increase count by one in the node. After insertion traverse the tree for the required element!
But the real and smart answer is something else.
A Linear Time Majority Vote Algorithm (linear time)
Scan the array elements, while scanning elements maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.
When we move the pointer forward over an element e:
* If the counter is 0, we set the current candidate to e and we set the counter to 1.
* If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.
But if you must confirm that the chosen element is indeed the majority element, you must take one more linear pass through the data to do it.
0 comments:
Post a Comment