## Google Interview Question for Software Engineer / Developers

• 4

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
40
of 44 vote

I have a correct solution to it. I am gonna post a small piece of code. You need a compiler that support C++ 11 to run the code.
But don't worry if you don't have such one. I know that most of people would prefer English to code. I will explain the idea in English afterward, but, excuse me for I am not a native English speaker.
The algorithm here is actually not designed dedicatedly to solve this question but to handle a more general case:
Given an array of N numbers, finds all the elements that appear more than N/M times and report the their frequencies.
The time complexity is O(2*N*logM) and space complexity is O(M)
For this question, M = 3, so the time is O(2log3 N) = O(N), space is O(3) = O(1);

``````#include <iostream>
#include <map>
#include <algorithm>
typedef std::map<int, int> Map;
Map findOverNth(int arr[], int size, int n)
{
Map ret_map;
typedef Map::value_type Elem; //pair<CONST int, int>
int total = 0;
std::for_each(arr, arr + size, [&, n](int val)
{
auto ret_pair = ret_map.insert(Elem(val, 0));
++(*ret_pair.first).second; ++ total;
if (ret_map.size() == n)
for (auto iter = ret_map.begin(); iter != ret_map.end(); )
{
--(*iter).second; -- total;
if ((*iter).second == 0)
ret_map.erase(iter++);
else
iter++;
}
});
std::for_each(ret_map.begin(), ret_map.end(), [](Elem &elem) {elem.second = 0;});
std::for_each(arr, arr + size, [&ret_map](int val) {if (ret_map.find(val) != ret_map.end()) ret_map[val] ++;});
for (auto iter = ret_map.begin(); iter != ret_map.end(); )
{
if ((*iter).second <= size / n)
ret_map.erase(iter++);
else
iter++;
}
return ret_map;
}
using namespace std;
int main()
{
//int arr[] = {5,6,7,8, 10, 4,4, 4, 4,1, 1,1};
int arr[] = {5,6,7,8, 10, 10, 10,10,10,10, 4,4, 4, 4,4,1, 1,1,1};
auto a_map = findOverNth(arr, sizeof(arr)/sizeof(int), 4);
cout<<sizeof(arr)/sizeof(int)<<endl;
//cout<<a_map.size()<<endl;
for each(auto elem in a_map)
{
cout<<elem.first<<" "<<elem.second<<endl;
}
}``````

Comment hidden because of low score. Click to expand.
4

Well, here comes the English:
The idea of the problem is from the famous game: Tetris
Lets see how it works. Consider m = 5;
Given an array : 4 3 3 2 1 2 3 4 4 7, we treat each number as a piece in Tetris, which falls down from the ceil. Our task is to try to keep the same number stacked on the same column. Consider the moment that 7 is going to fall down. The snapshot of our game now is like :
7

4
4 3 2
4 3 2 1 _
Note that, the size of a row is designed as M, which is 5 here.
Just like Tetris, this game has a similar rule that:
if a row is full of numbers then it should be eliminated.
So when 7 goes down, it becomes:
4
4 3 2
4 3 2 1 7 //This row is full and to be eliminated
Then the bottom row is gone.
It becomes
4
4 3 2
As the numbers falls down, eventually, the game will end in a status that no row is full.
So we have at most M - 1 numbers left at the final stage.
But it is not over. We can easily prove that, if there is a solution, it must be in the number left at the final stage; but we can not guarantee all numbers left are the correct solution.
So we need to scan the array again, and count the numbers left to find the correct solutions and report their frequencies.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Now the idea is clear, but the implementation of this idea is more crucial. A bad implementation would result in a very bad complexity. In my code, I used std::map, which, more theoretically, is RB tree.
For each number, I inserted it into the map. I have the rule from the Tetris that the map size cannot reach M. If an existing number is inserted, the count of the number in map is increased by 1; if a new one comes, it is inserted with count = 1; if the map reaches the size limitation M, all the counts in map are forced to be decreased by 1. Of course, if it counts to 0, eliminate it! This is how it works like a Tetris.
You may ask why it is still O(NlogM) if I need to traverse the whole map to decrease each count by 1. That's because in total, every number is added once and erased once, so the amortized complexity is still O(N) for this part. So the total is still O(NlogM).

The remaining part of this algo is trivial then. I believe everyone here can figure it out.

Finally, btw, the variable "total" in my code plays no role but was for debugging, feel free to delete it: ）

Comment hidden because of low score. Click to expand.
0

I think that is the best and most vaild answer so far :).

Comment hidden because of low score. Click to expand.
0

True, you nailed it, great job. while going through other solutions i felt that yours is a generalization of majority voting algorithm (correct me if thats wrong).
However, on a curious note, you could have used 2 arrays, for std::map, and would have avoid that logM factor. (i know thats constant anyway). Thanks for posting great solution.

Comment hidden because of low score. Click to expand.
0

Hi abc1.picasa, could u explain more about how to use 2 arrays avoid the logM factor?

Comment hidden because of low score. Click to expand.
0

Fantastic

Comment hidden because of low score. Click to expand.
0

@Fentoyal

Superb Solution..I was thinking one possible tweak though..U scan for each element left in the tetris to check if its the desired answer..For this we can do this
1) Take a variable count.When ever u elimiate one row increment count by 1.
2) Now say 3 rows were deleted(count =3) and size is 15 and we need to find which element is present say 15/3 (N=15,M=3)=5 times . So we know each element has appeared 3 times so far (value of count) . Now scan the remaining elements in the map and check if any one's count is >=2. Thats the answer. So instead of scanning the whole array again for each remaining element we just scan the remaining elements.

Comment hidden because of low score. Click to expand.
0

What if there are N elements in input and M distinct numbers and each occurs exactly n/m times. For example:
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10
The question is to find all the elements that occur exactly 2 times.
Also you are using a hashtable, complexity of access is O(1). We are scanning the hashtable to decrease count when a row is full. This can happen N/M times in the worst case. So the complexity comes out to be O(n) + O(m*n/m) = O(n)

Comment hidden because of low score. Click to expand.
0

What if there are N elements in input and M distinct numbers and each occurs exactly n/m times. For example:
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10
The question is to find all the elements that occur exactly 2 times.
Also you are using a hashtable, complexity of access is O(1). We are scanning the hashtable to decrease count when a row is full. This can happen N/M times in the worst case. So the complexity comes out to be O(n) + O(m*n/m) = O(n)

Comment hidden because of low score. Click to expand.
0

Obviously, this algorithm can only find the element that occurs > N/M times not >=. But it is exactly what the original question asks.

Comment hidden because of low score. Click to expand.
0

How would you know at the start that there are M different numbers in the array. In my opinion all we can know about that at the start that if there will be at one number with the count more than n/3 then there can be at most n - n/3 distinct numbers in the array. And if in the case there are where there are more than one number in the array with the count more than n/3 then all we know that there can be at most 2 of these numbers and the maximum number of distinct numbers in the list are n - 2(n/3) distinct numbers in the array....

Comment hidden because of low score. Click to expand.
0

Hi, Abdul
Please make sure you fully understand the algorithm since I did explain a lot. I do not need the assumption that there are M different numbers for this algorithm. The task is only to find the ones that appear more than N/M times.
like:
1 2 3 4 4 4 4 5 5 5 5 6.
N = 12
M = 4
There are 6 different numbers.
The goal is to find ones occurring > 12/4 = 3 times.
4, occurs 4 times.
5, occurs 4 times.

Comment hidden because of low score. Click to expand.
0

1 1 1 2 2 2 3 3 3
Size: 9
M: 2
Your algorithm seems to output only 3 in this case. Please correct if I'm wrong here.

Comment hidden because of low score. Click to expand.
0

Sorry, ignore above comment, I got it now :)

Comment hidden because of low score. Click to expand.
0

So how do you explain that in array
1,2,3,4,5,6,7,8,9,11,11,11 and M=3
we still will get 11 as our answer, while we have 3 repetitions, not 4.

Comment hidden because of low score. Click to expand.
0

But seems that it said no excessive space can be used, and no hash. Using a map violated both requirements...

Comment hidden because of low score. Click to expand.
0

But seems that it said no excessive space can be used, and no hash. Using a map violated both requirements...

Comment hidden because of low score. Click to expand.
0

bellow is the java implementation

``````public ArrayList<Integer> findRepetedElements(int[] arr, int M) {
ArrayList<Integer> result = new ArrayList<Integer>();
TreeMap<Integer, Integer> tm = new TreeMap<Integer, Integer>();
int minCount = (int) Math.ceil(((double) arr.length) / M);

for (int i = 0; i < arr.length; i++)

// find count of elements left in the tree
Iterator<Entry<Integer, Integer>> iter = tm.entrySet().iterator();
Entry<Integer, Integer> e;
int value;
int currCount;
while (iter.hasNext()) {
currCount = 0;
e = iter.next();
value = e.getValue();

for (int i = 0; i < arr.length; i++)
if (arr[i] == value)
currCount++;

if (currCount >= minCount)
}

return result;
}

private void add(TreeMap<Integer, Integer> tm, Integer key, int maxSize) {
Integer mpValue = tm.get(key);

if (mpValue == null)
tm.put(key, 1);
else
tm.put(key, mpValue + 1);

if (tm.size() == maxSize)
clearRow(tm);
}

private void clearRow(TreeMap<Integer, Integer> tm) {
Iterator<Entry<Integer, Integer>> iter = tm.entrySet().iterator();

Entry<Integer, Integer> e;
int value;
while (iter.hasNext()) {
e = iter.next();
value = e.getValue();
if (value == 1)
iter.remove();
else
e.setValue(value - 1);
}
}``````

Comment hidden because of low score. Click to expand.
0

U use the std:map to store the count..which seems to violate the requirement of no excessive storage

Comment hidden because of low score. Click to expand.
0

Hi, Anonymous on February 26, 2012 ,

Plz try your input 1,2,3,4,5,6,7,8,9,11,11,11 to this algorithm. It outputs nothing, because there is no solution.

Comment hidden because of low score. Click to expand.
0

Hi, liangzhongliang on March 01, 2012 & Anonymous on April 19, 2012

As I have explained in the very beginning, the algorithm requires O(M) space. Since M for this original question is 3. so it requires O(3) space. It is technically O(1) space. In my implementation, the map has a size limit : M. So it cannot ever grow larger than 3. That is, the map i used has only 3 elements! This is not a excessive storage. It consumes just like you did in every program: int i, j, k; <--- this uses O(3) too, and people do not call constant space storage excessive storage because it is not.

Comment hidden because of low score. Click to expand.
0

@fentoyal just curious..Are you a Microsoft employee?

Comment hidden because of low score. Click to expand.
0

Man, the tetris explanation is beautiful. Thank you @fentoyal

Comment hidden because of low score. Click to expand.
0

@bashrc, no, I am not. But I have several friends who got its offer. Someone did go there and someone rejected the offer. I have not even interviewed with MS. Why are you asking?

Comment hidden because of low score. Click to expand.
0

The solution is good. But its space complexity is O(n) in worst case(when no element is repeated).

In this case what if you go for solution using hash? (hash function is going to be critical)

Comment hidden because of low score. Click to expand.
0

for example 111123456789 or 123123123 , this would fail as there would be no element left in any row finaly, but answer is sure, here m = 3 .

Comment hidden because of low score. Click to expand.
0

Misra-Gries Algorithm

Comment hidden because of low score. Click to expand.
0

@Paidi @Navaneet, @etc,
After read these comments and suspects on this algorithm, I'd like to highlight some points to make it clear. So anyone questioning the complexity or correctness could firstly double check the algorithm with these points:
0. It is meant to find those that occur more than N/M times
1. not those that duplicate more than "M" times
2. Neither are those that appear "exactly" N/M times. It can only find those that repeat "more than" N/M times, which is exactly the interview question asked. And, in fact, to report those that appear "exactly" N/M times will turn this problem to a completely different one.
3. The space complexity is O(M), in any case. There is no such "worst case" thing, because for any input, I always allocate a M sized BST structure(in my implementation, it was std::map).
4. We do call O(M) space complexity as "constant storage" or "no excessive storage required"if M = O(1) i.e. M is a constant number, which holds in this interview question where M = 3, always.
Given that so many people are interesting this solution, I leave my email here:
the.easiest.name.to.remember@gmail.com
if you have any questions, you may contact me directly

Comment hidden because of low score. Click to expand.
0

@fentoyal,

Very good solution. Anyone up for C# implementation? Or I will try to implement this in C# this weekend.

Comment hidden because of low score. Click to expand.
0

Hey Fentoyal, I think your explanation is good, especially when equating to Tetris. But, I have difficulty believing that this is O(1) space or that it will find the correct answer.

Consider that you have N = 300 and M = 3. And the first 101 elements are 1 and the rest are 2 and 3. In this case, the first column goes to size 101 as there are no complete rows to delete. So, the space complexity is N/3 or O(N). Or if the numbers 1 and 2 keep repeating till 298. Then your space complexity becomes O(2n).

You can certainly make this better is if you keep the count of the numbers rather than keep a list of them in your columns, as Ankur suggested. Then this is essentially a map of the positions and their count.

Am I missing something here?

Consider the following:
N = 10
M = 4 (which is greater that 10/3)
Sequence = 1 2 3 5 1 4 1 4 1 4
Answer is 1 (as it is the only number that repeats 4 times)

Based on my understanding, which could be wrong, the states will be:

1
1 2
1 2 3
1 2 3 5
clear
1 4
1 4
1 4

And you are left with 2 elements, 1 and 4. So, how do you distinguish which one is the right answer?

PS: I really want to like and understand your solution and I hope I missed something in understanding your solution. I hate to be the messenger of bad news here :)

Comment hidden because of low score. Click to expand.
0

Yes, you did misunderstood it.
As I said " but the implementation of this idea is more crucial".
If you implemented it that way, you'll end up in a O(N) solution.
Check my third posts on how to implement it.
I did a counting.
So, for your first column, why should I bother storing all 101 same numbers? I just need to store (1, 101). That's enough.
So I need only M space, each representing a column. And each space only storing a single integer representing how high the column is.
I hope it is clear now.
Again, because I can't check this thread all the time, if anyone got any new questions, write to my email:
.
the.easiest.name.to.remember@gmail.com

Comment hidden because of low score. Click to expand.
0

"No hashing/excessive space" means you cannot use a map.

Comment hidden because of low score. Click to expand.
0

@GKalchev You'd have to sort your solution before executing it, otherwise for input like findRepeatedElements(new int[]{1,2,3,4,1,1,1}, 3) 1 will not be found because you would have cleared that from the map before finding that it is there the requisite number of times.

Comment hidden because of low score. Click to expand.
11
of 13 vote

There can be atmost 2 elements that appear more than n/3 times.
Suppose given array is A. Use a 2d array of size 2 ( or u can use 4 variables ) -> RES which stores the two possible values in R and R
RES -> count of RES in array
RES -> count of RES in array

The trick is if we keep cancelling 3 distinct elements then the remaining one/two final values will be the possible answer ( like for majority element, we keep cancelling two distinct elements )

``````for each A[i] in A:
if RES == 0:
RES = A[i]
RES = 1
else if RES == A[i]:
RES++
else if RES == 0:
RES = A[i]
RES = 1
else if RES == A[i]:
RES++
else
RES--
RES--

count1 = count2 = 0

for each A[i] in A:
if A[i] == RES:
count1++
else if A[i] == RES:
count2++

if count1 > size(A)/3:
RES is first desired no.
if count2 > size(A)/3:
RES is second desired no.``````

Complexity : O(n)

Comment hidden because of low score. Click to expand.
0

Hey first thing which I wanna tell you is that there can b atmost 3 elements. Secondly you are not supposed to use additional memory. :)

Comment hidden because of low score. Click to expand.
0

@CodeCracker : The idea is correct... and there will be only 2 such elements..
lets say the number of elements is 99.. Then more by than by n/3 means, (n/3 + 1), which is 34...
So there 34 + 34 = 68.. the count of the third one is going to be 31.
So that leaves the possibility of just 2 numbers.

And there is no additional memory used here.

Comment hidden because of low score. Click to expand.
0

@erberuz The idea looks fine based on the majority element algo,had a confusion though
For sequence like 12312
When we encounter 3, are we not reducing count1 to 0 and count2 to 0 as well making a[maximum1]=3 and a[maximum2]=3 as well.
Are you sure its working perfectly, an example would help.Thanks

Comment hidden because of low score. Click to expand.
1
of 1 vote

Yes, this question was posted before and that solution is correct.
This is a variation of linear time majority voting algo.

The key idea behind this method is that such n/3 majority numbers
will still remain n/3 majority if you remove three different numbers
from the set if exist. This algo keeps doing so until you have only
less than three elements left. And you need to check if any of them
are really n/3 majority numbers.

Comment hidden because of low score. Click to expand.
1
of 1 vote

I think it should iterate twice to find two majority elements. but still achievable in O(n).

Comment hidden because of low score. Click to expand.
0

I think the idea is correct, but the code should be modified. I use the same idea, but use 3 parameters to remember the number and 3 parameters for counting. Here is my solution:

``````for each A[i] in A:
if A[i] == Num:
Count+=2;
Count--;
Count--;
else if A[i] == Num:
Count--;
Count+=2;
Count--;
else if A[i] == Num:
Count--;
Count--;
Count+=2;
else
Count--;
Count--;
Count--;
if Count == 0:
Num = A[i];
Count = 2;
else if Count == 0:
Num = A[i];
Count = 2;
else if Count == 0:
Num = A[i];
Count = 2;``````

As far as number X is more than n/3, it will has count as m*2 - (n-m) > 0, m is the appear time of X. So X will stay in the parameter when the algorithm finished.

This should works for the scenario that when there is 2 majority elements.

Comment hidden because of low score. Click to expand.
0

Made little change, it should be fine now.
@GS, only one more array iteration will do it ( store count of RES and RES )

Comment hidden because of low score. Click to expand.
0

Have you even tried the solution. Does not work and does not make sense. The idea is not majority voting. The idea is more than that.
PS: I am trying your solution for array sizes 6,7,8,9 and it keeps failing

Comment hidden because of low score. Click to expand.
0

can u give an example for which my algo doesn't work.

Comment hidden because of low score. Click to expand.
0

Hi Cerberuz:
1. which 2 initial values should be filled in res and res?
2. Are they examining the same A[i] in each iteration?
3. As per Ashar's example 123123, if using your way, it will both have 2 as a result, while 1 will be missed.

Can you explain? Thanks

Comment hidden because of low score. Click to expand.
0

@Cerberuz ur method is right, i previously missed the "else" key word.

Comment hidden because of low score. Click to expand.
0

@Cerberuz, try 1,1,1,2,2,2,3,3.
1 will not survive.

Comment hidden because of low score. Click to expand.
0

@G yeah the 2 if statements should probably be swapped

Comment hidden because of low score. Click to expand.
0

What if the array size 'n' is a multiple of 3? Would the maximum number of elements be repeated n/3 times is 2? I don't think so: n=3, A[a, b, c]. 3 elements. Please let me know.

Comment hidden because of low score. Click to expand.
0

Question says : more than n/3 times

Comment hidden because of low score. Click to expand.
0

@Cerberuz, I am really not sure how this will work for something like 1, 1, 2, 2, 3, 3, 1, 1

Comment hidden because of low score. Click to expand.
0

I have modified the code to make it more clear.

Comment hidden because of low score. Click to expand.
0

Sorry but in the question is not clear if the numbers are only 1, 2 and 3 or can be any other number (or comparable element). Es: [2,3,4,1,7,5,3,4,5,8,8,8,3,4,5]. In this case the solution has no sense. What's the difference of using 3 pairs of variables or a Map with 3 possible keys??? The constraints is don't use hashing or more (eccessive) space.

Comment hidden because of low score. Click to expand.
0

@Max, solution works for all cases ( including the one you mentioned ).

Comment hidden because of low score. Click to expand.
0

Best solution, Main idea is what anonyguru said.
here I use an array B of length 3 to maintain the disjoint set we need to delete every time.
when A[i] == B[j],count[j]++,when both B B B !=0, we find a disjoint set which can delete. so we do for j in range(0,3):
count[j]--

Comment hidden because of low score. Click to expand.
7
of 9 vote

careercup.com/question?id=11879708

Comment hidden because of low score. Click to expand.
3
of 3 vote

``````#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

void find(vector<int> data)
{
int one, two;
int num1 = 0;
int num2 = 0;
vector<int>::iterator it;
for (it = data.begin(); it != data.end(); ++it)
{
if (num1 == 0)
{
one = *it;
num1 = 1;
}
else if (one == *it)
{
++num1;
}
else if (num2 == 0)
{
two = *it;
num2 = 1;
}
else if (two == *it)
{
++num2;
}
else
{
--num1;
--num2;
if (num1 == 0 && num2 != 0)
{
one = two;
num1 = num2;
num2 = 0;
}
}
}
if (num1 > 0)
{
num1 = 0;
for (it = data.begin(); it != data.end(); ++it)
{
if (*it == one)
{
++num1;
}
}
if (num1 > data.size() / 3)
{
cout << one << endl;
}
}
if (num2 > 0)
{
num2 = 0;
for (it = data.begin(); it != data.end(); ++it)
{
if (*it == two)
{
++num2;
}
}
if (num2 > data.size() / 3)
{
cout << two << endl;
}
}
}

int main()
{
int t;
vector<int> v;
/*while (scanf("%d", &t) != EOF)
{
v.push_back(t);
}*/
while (cin >> t)
{
v.push_back(t);
}
find(v);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

The idea of the algorithms seems to be the same as in the previous post (by nio, who simply provides link to the solution by fentoyal), and the code is quite clean, I like it. However, the complete lack of comments makes it unreadable, unless you are aware of the idea (which fentoyal calls 'tetris rules').

EDIT: deleted incorrect paragraph.

Comment hidden because of low score. Click to expand.
0

The last paragraph in the previous comment is wrong: counting decrements would not provide useful info. Oops.

Comment hidden because of low score. Click to expand.
0

@ wenlei.zhouwl
your program is not giving write output . it is alwz giving 1st element

Comment hidden because of low score. Click to expand.
2
of 4 vote

1. Find the n * 1/3 and n * 2/3 largest element using QuickSelect. In order for an element to occur more than 1/3 of the time in the array, it must be one of these two elements.
2. Do a linear pass through the array to see if the array contains these two elements.

Comment hidden because of low score. Click to expand.
0

@Dr. Andrew: What you are saying is not applicable for the array: 1,1,1,3,4,5
The value of n is 6. Hence the n/3(or 2nd) largest element is 3 and 2n/3(or 4th) largest element is4. And neither of them is repeated more than n/3 times. Instead, 1 is repeated more than n/3 times!
Correct me if I am wrong.

Comment hidden because of low score. Click to expand.
0

@alex: I haven't implemented it myself yet, but the QuickSelect algorithm (see Wikipedia), as I understand it, would give you the nth smallest element in an unordered list. So in your list of 6, I'm saying it would pick the 2nd and 4th largest elements, counting duplicate elements, so the 2nd largest is 1 and the 4th largest is 3. Any list longer than 1/3 of the list has to touch one or both of those ranks.

Comment hidden because of low score. Click to expand.
0

@Dr. Andrew: If you count the duplicates, it might be valid, provided you take the ceiling of n/3 and 2n/3. Thanks!

Comment hidden because of low score. Click to expand.
0

Of course it is correct. The sequence is larger then n/3 of the size of the vector and it has to occupy the (n/3)th or (2n/3)th position in vector. This is the correct answer.

Comment hidden because of low score. Click to expand.
0

@Dr. Andrew: An interesting solution.

@fanymanea: I wouldn't say it's *the* correct answer, but it's *a* correct answer.

Comment hidden because of low score. Click to expand.
1
of 1 vote

The algorithm is called misra-gries

Comment hidden because of low score. Click to expand.
1
of 1 vote

Divya,
It is said in the question that you can not use excessive space. Does it mean that we can not use any additional array ??

Comment hidden because of low score. Click to expand.
1
of 1 vote

by definition, you can only have 2 values that are in the set for more than 1/3.

therefore, if sorted (which we wont do), the 2 values would have to be visible at n/3 and/or 2n/3 (and/or because 1 or 2 can be more than 1/3)

so selection/rank (should be expected O(n)) those 2 positions.

then iterate over the the entire array counting those that match those 2 positions.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Algorithm

similar as the linear majority voting algorithm, we maintains two numbers having top two votes

if it's the number having the top votes, increment the top votes by 1
if it's the number having the second top votes, increment the second votes by 1 and swap it with the top votes number if it has more votes
if the number having the top votes is not defined, make the number top votes with vote 1
if the number having the second top votes is not defined, make the number second top votes with vote 1

when the votes become zero, the number of the top or the second top are undefined

Time: O(n)
Space: O(1)

ideone.com/8yNNIW

``````public void find(int[] a)
{
int first = Integer.MIN_VALUE; // the number with the top votes
int firstVote = 0; // the top votes
int second = Integer.MIN_VALUE; // the number with the second top votes
int secondVote = 0; // the second top votes
for(int i: a) {
if(firstVote > 0 && i == first) {
firstVote++;
} else if(secondVote > 0 && i == second) {
secondVote++;
if(secondVote > firstVote) {
int t = first;
first = second;
second = t;
t = firstVote;
firstVote = secondVote;
secondVote = t;
}
} else if(firstVote == 0) {
first = i;
firstVote++;
} else if(secondVote == 0) {
second = i;
secondVote++;
}  else {
firstVote--;
secondVote--;
}
}
// confirm if the number with top 2 votes occurs more than 3/n times
int firstCount = 0;
int secondCount = 0;
//System.out.println(first + "," + second);
for(int i: a) {
if(firstVote > 0 && i == first) firstCount++;
if(secondVote > 0 && i == second) secondCount++;
}
if(firstCount > a.length / 3) System.out.println(first);
if(secondCount > a.length / 3) System.out.println(second);
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````Algorithm:
The idea of the problem is from the famous game: Tetris
Lets see how it works. Consider m = 5;
Given an array : 4 3 3 2 1 2 3 4 4 7, we treat each number as a piece in Tetris,
which falls down from the ceil. Our task is to try to keep the same number stacked on the same column.
Consider the moment that 7 is going to fall down. The snapshot of our game now is like :

7

4
4 3 2
4 3 2 1 _

Note that, the size of a row is designed as M, which is 5 here.
Just like Tetris, this game has a similar rule that:
if a row is full of numbers then it should be eliminated.
So when 7 goes down, it becomes:

4
4 3 2
4 3 2 1 7 //This row is full and to be eliminated

Then the bottom row is gone.
It becomes

4
4 3 2

As the numbers falls down, eventually, the game will end in a status that no row is full.
So we have at most M - 1 numbers left at the final stage.
But it is not over. We can easily prove that, if there is a solution, it must be in the number
left at the final stage; but we can not guarantee all numbers left are the correct solution.
So we need to scan the array again, and count the numbers left to find the correct solutions and report their frequencies.

Implementation:

struct node
{
int val;
int count;
};

Create following var for keeping track

struct node tracker;

for each node in input array arr
{

if(tracker.val == arr[i])
{
tracker.count++;
}
else if(tracker.val == arr[i])
{
tracker.count++;
}
else if(tracker.val != 0)
{
tracker.count--;
tracker.count--;
tracker.count--;
}

if(tracker.val == 0)
{
tracker.val = arr[i];
tracker.count++;
}
else if(tracker.val == 0)
{
tracker.val = arr[i];
tracker.count++;
}
else if(tracker.val == 0)
{
tracker.val = arr[i];
tracker.count++;
}

}// for end

// reset the counters

tracker.count = 0;
tracker.count = 0;
tracker.count = 0;

for each node in input array
{
if(tracker.val == arr[i])
tracker.count++;
else if(tracker.val == arr[i])
tracker.count++;
else if(tracker.val == arr[i])
tracker.count++;
} // for end``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````void max_num(int *A, int l){
int n1 = -1, n2 = -1, c1 = 0, c2 = 0, i;
for(i=0; i<l; i++){
if(-1 == n1){ n1 = A[i]; c1++; }
else if(-1 == n2){ n2 = A[i]; c2++; }
else if(A[i] == n1) {c1++;}
else if(A[i] == n2) {c2++;}
else{
c1--;
c2--;
if(c1 == 0) n1 = -1;
if(c2 == 0) n2 = -1;
}
}//for()
c1 = 0; c2 = 0;
for(i=0; i<l ; i++){
if(n1 == A[i]) c1++;
else if(n2 == A[i]) c2++;
}
if(c1>(l/3)) cout << n1;
if(c2>(l/3)) cout << n2;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

I think the best solution uses a map. You could return the map or just dump out the freqs like this does.

``````template <class Ty>
void ElementCounter(std::vector<Ty> inArray)
{
// Map key, value
std::map<Ty,int> tempMap;
std::vector<Ty>::iterator vecIter;

// O(n) iteration
for (vecIter = inArray.begin(); vecIter != inArray.end(); ++vecIter)
{
std::pair<std::map<Ty,int>::iterator, bool> pr = tempMap.insert(std::pair<Ty, int>(*vecIter, 1));
if (pr.second == false)
{
(pr.first)->second++;
}
}

// Print results
std::map<Ty,int>::iterator tempIter;
for (tempIter = tempMap.begin(); tempIter != tempMap.end(); ++tempIter)
{
if (tempIter->second >= (int)(inArray.size() / 3))
std::cout << "Item " << tempIter->first << " appears " << tempIter->second << " times." << std::endl;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````vector<int> FindAtLeastOneThirdFreq(vector<int> sample)
{
vector<int> result;

if (sample.size() == 0)
{
return result;
}

int mostFrequent = -1;
int count = 0;

for (vector<int>::const_iterator it = sample.begin(); it != sample.end(); it++)
{
if (count == 0 || *it == mostFrequent)
{
++count;
mostFrequent = *it;
}
else
{
--count;
}
}

int secondFreq = -1;
count = 0;
for (vector<int>::const_iterator it = sample.begin(); it != sample.end(); it++)
{
if (*it != mostFrequent)
{
if (count == 0 || *it == secondFreq)
{
++count;
secondFreq = *it;
}
else
{
--count;
}
}
}

int mostFreqCount = 0;
int seondFreqCount = 0;

for (vector<int>::const_iterator it = sample.begin(); it != sample.end(); it++)
{
if (*it == mostFrequent)
{
++mostFreqCount;
}
else if (*it == secondFreq)
{
++seondFreqCount;
}
}

int threshold = sample.size();

if (threshold % 3 == 0)
{
threshold /= 3;
++threshold;
}
else
{
threshold = (threshold + 2) / 3;
}

if (mostFreqCount >= threshold)
{
result.push_back(mostFrequent);

if (seondFreqCount >= threshold)
{
result.push_back(secondFreq);
}
}

return result;
}``````

Comment hidden because of low score. Click to expand.
0

This works, when an element occurs more than n/2 times, and not n/3.

Consider this: 2 2 5 4 2 6 8

Here in the end, mostFrequent comes out to be: 6, and not 2.

Comment hidden because of low score. Click to expand.
0

Sorry, COnsider the input: 2 2 5 4 6 2 8

Comment hidden because of low score. Click to expand.
0

Sorry, COnsider the input: 2 2 5 4 6 2 8

Comment hidden because of low score. Click to expand.
0

it says more than n/3 so the answer is {}.

Comment hidden because of low score. Click to expand.
0
of 0 vote

construct a treap , instead of random number use frequency, but will it be linear.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm not sure if a solution exist in O(n) and constant space

Comment hidden because of low score. Click to expand.
0

I too believe that because if we keep track we need extra memory and can be done in linear time if not i.e., with out extra memory it cannot be done in linear time.

Comment hidden because of low score. Click to expand.
0

Probabilistic algos exist in constant space and linear time. Consider the following. Pick 1000 entries at random. Sort them and find any entries that occur at least (for instance) 200 times. It is now very unlikely that any entry that occurs more than n/3 has less than 200 entries in this representative sample of 1000. You will find at most 5 (O(1)) values that have at least 200 occurrences in the sample. Do a pass through the full array counting the number of occurrences of each of these values. Return the ones that occur at least n/3 times.

This is correct with incredibly high probability (for large n) and is linear time. But a deterministic algo...I definitely think it's possible, but I'm not sure right now.

Also, no one said "constant space". Only "no excessive space" was mentioned. Hashing is apparently "excessive" for purposes of this problem. But I think a log-space solution or something like that would be fine...

Comment hidden because of low score. Click to expand.
0
of 0 vote

If we assume it's an array of integers then maybe we can accomplish this by counting bits.

Note that there can be at most 2 numbers that occur more than n/3 times. So we make 2 passes through the array.

Maintain a 32 element BIT-TRACKER array. Examine each number and for any 1 bits in the number, and increment the corresponding element int the BIT-TRACKER array.

So, for example, if we encounter 25 (11001), do BIT-TRACKER++, BIT-TRACKER++, BIT-TRACKER++.

Then check all the bits that have occurred more than n/3 times. If those bits match the current number, then that number must occur more than n/3 times.

So now we have 1 number. So we repeat the process again but only consider the remaining numbers. As we go through the array we simply skip the number we found already. Call the remaining count m. So for the 2nd pass we look for the number that occurs more than m/2 times. There can only be 1 of these.

If it's strings instead of integers then we have to map the strings to integers and do the same thing. However, the integers (and hence the number of bits) could get really large. So maybe this doesn't make sense for strings.

And then of course this whole idea could be complete nonsense.

I'll try to write it out this weekend.

Later!

Comment hidden because of low score. Click to expand.
0

I don't think your algorithm works correctly. Assume we have 9 numbers in binary as below:
1. 1001100
2. 1010011
3. 1010011
4. 1010011
5. 1000011
6. 1111111
7. 1111111
8. 1111111
9. 1111111

According to your algorithm, after we check the 5th number, the bit tracker is like . The 5th number has bits , all of those with 1 now have 4 counts in the bit tracker. However, this number only has one copy in the whole array.

Comment hidden because of low score. Click to expand.
0

Bummer! You're right. Thanks for writing that out.

Comment hidden because of low score. Click to expand.
0

Hmmm... Maybe if we count 0 bits as well?

Comment hidden because of low score. Click to expand.
0
of 0 vote

A suggestion

First Pass: Pick each element one by one. When you pick the first element increase the counter by 2. Get the next element if it is the same element increase counter by 2 otherwise decrease by 1. Get the next element and so on. If the counter hits 0 set the current character as the comparison element and increment by 2. Keep the last comparison element.

Second Pass: Counter the number of occurences of the element found from first pass. If it is bigger than n/3 than store this as one of the elements.

Third pass: If the element found has occurred more than 2n/3-1 times dont need this other wise Repeat first pass with incrementing by one and ignoring the element found from first pass. And then repeat the second pass.

Comment hidden because of low score. Click to expand.
0

consider: 3 2 2 4

in your first pass. comparision element in the end will be 4, whereas it is expected to be 2.

Comment hidden because of low score. Click to expand.
0
of 0 vote

int findMostFrequentNumber(int *a, int size) {
int i;
int cand1; int count=0;
int cand2; int ncount=0;
for(i=0;i<size;i++) {
if(count==0) {
if(ncount!=0){
if(cand2!=a[i]) {
cand1=a[i];
count++;
} else {
ncount++;
}
} else {
cand1=a[i];
count++;
}
} else {
if(cand1==a[i]) {
count++;
} else {
if(ncount==0) {
cand2=a[i];
ncount++;
} else {
if(cand2==a[i])
ncount++;
else {
--count;
--ncount;
}
}
}
}
}
if(count!=0)
printf("candidate:%d\n",cand1);
if(ncount!=0)
printf("candidate:%d\n",cand2);
return cand1;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

well, we understand english better

Comment hidden because of low score. Click to expand.
0
of 0 vote

@all Seems Extension's of Moore Voting Theorem ?

Comment hidden because of low score. Click to expand.
0

Yes, see my comment above.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I thought of a solution , I can neither prove it right nor prove it wrong. The solution is on the similar lines as it were for the problem where you have to find a number occuring more than n/2 number of times.

lets say we take 4 numebrs at a time. each time shifting the window by one bit.
1st to 4th , 2nd to 5th, 3rd to 6th etc...
Now we see the majority in these four numbrs, if the majority is the same as last majority, we increase a variable frequency, if it is different thn we decrease the freq. If not majority do
nothing

//edge cases not counted, jsut the sudo code
for(i = 1 to n)
{
maj = getMajority(i,i+3);
if(maj==null)
//nothing
else if(maj==last_majority)
freq++
else frq --
if(freq< 0)
{
last_majority = maj;
freq = 1 ;
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it is a variation of voting problem. If you add 3 when a number is encountered and subtract 1 if not and only change a number if count hits 0 then you will get your answer.

Lets prove it. If you have 4 numbers 1 2 3 then clearly this holds. For an arbitrary case if the count is x then it can only go to 0 if following 3x numbers are different. Hence if a number is more than n/3 times then it will yield a positive count.

Comment hidden because of low score. Click to expand.
0

I didn/t understand. could you pls take an example and give step by step explanation?

--> If you add 3 when a number is encountered and subtract 1 if not and only change a number if count hits 0 then you will get your answer.

What is this for> I dont think it'l help.

Comment hidden because of low score. Click to expand.
0

It doesn't work for:
1 2 2

Comment hidden because of low score. Click to expand.
0

@Anonymous
You are right... We should be adding 2 and not 3...

Comment hidden because of low score. Click to expand.
0

If you add 2, it doesn't work for
2 2 5 6 7 8 4 2

length = 8. a no shud occur more than 8/3 = 3 times.

if you check for the above input, last no. comes out to be 4 and not 2 as expected.

Comment hidden because of low score. Click to expand.
0

I think Ashish is right about :

If you add 3 when a number is encountered and subtract 1 if not and only change a number if count hits 0 then you will get your answer.

But the only thing that we have to modify in here is we'll have to traverse the array two times because there will be atmost 2 elements with more than n/3 occurence.

So in first attempt we'll find our first number and in second attempt we'll cross out the found number as dummy and will search for another number, and print both the numbers found.

Thanks.

Comment hidden because of low score. Click to expand.
0

doesn't work for 6,1,2,6,3,4,5,6

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ Note: You can have at-most 2 such numbers. Step1: O(n) Find the 2/3rd order statistic (say x) in the array using heuristic to pick pivot. Step2: O(n) Check if x occurs more than n/3 times. Step3: O(n) Check for element other than x occurring more than n/3 times in first 2/3rd of array using Moore's voting algo.
Comment hidden because of low score. Click to expand.
0

What exactly "2/3rd order statistic" means ?
What is it for 1 2 1 2 1 2 ?

Comment hidden because of low score. Click to expand.
0

dude ... it is mentioned that you should not be using any linear selection algorithm...

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this problem is simply an extention to the class majority voting algorithm.
Instead of incrementing the counter by 1, you should increment by 2.
Code in Python:
def FindThird(A):
Num = A
count = 1
for i <- 2 to n:
if A[i] == Num
count += 2
else if count > 0
count -= 1
else:
Num = A[i]
count = 1

return Num

Comment hidden because of low score. Click to expand.
0

doesnt work for: 6,1,2,6,3,4,5,6

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the algorithm. Maintain up to two elements and a positive counter for each. Scan through the array. If the next element x is the same as either stored element, increment the counter for that stored element. Otherwise, if there are fewer than two stored elements, store x and set its counter to 1. In the third case, if there are two stored elements and x is different from both, decrement the counter for each stored element, unstoring it if the counter would become zero (since we require the counter to be positive).

After the scan, any special element will be one of the stored elements. Then you just need to verify them.

Comment hidden because of low score. Click to expand.
0

Can u provide an example Implementation. I tried what u said with N=14,and M=3
with array
5,1,7,1,10,4,1,1,4,8,4,1,8,6
8 and 6 remains in the end while the answer is 1 . Probably, I implemented it in a wrong manner

Comment hidden because of low score. Click to expand.
0
of 2 vote

I'm not sure whether this would work.

``````Type candidate1,candidate2;

void Find(Type* ID,int N)
{
int nTimes1 = 0 ;
int nTimes2 = 0 ;
int i;

for( i = 0; i < N; i++)
{
if (nTimes1 == 0)
{
candidate1 = ID[i], nTimes1 = 1;
}
else
{
if (candidate1 == ID[i])
{
nTimes1++;
}
else
{
if (nTimes2 == 0)
{
candidate2 = ID[i], nTimes2 = 1;
}
else
{
if (candidate2 == ID[i])
{
nTimes2++;
}
else
{
nTimes1--;
nTimes2--;
}
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

if it is sorted array

``````public static void main(String ar[]){
int arr[]		= {1,2,3,3,3,5};
int size 		= arr.length;
int interval	= size/3;

int i2			= interval;
for( int i1=0;i1<size-interval;i1++,i2++ ){
if( arr[i1]==arr[i2] ){
System.out.println( arr[i1] );
i1+=interval;
i2+=interval;
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

But the question doesnt say anything about array being sorted.

Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
int *arr,count;
int n,i,size,u;
float notzero;
printf(" enter the value of n \n");
scanf("\n%d",&n);
arr=(int *)malloc(sizeof(int)*n);
printf(" enter values in array \n");
for(i=0;i<n;i++)
scanf("\n %d",&arr[i]);
if(n<0)
exit(0);
for(i=0;i<128;i++)
{
*(count+i)=0;
}
printf("\n values is ->> ");
for(i=0;i<n;i++)
{
u=*(arr+i);
*(count+u)= *(count+u)+1;
size=n/3;
if(*(count+u)>=size)
printf("\n %d ",*(arr+i));
}
getch();

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````for(int i = 0; i < sizeof(arr) - 2; i++)
{
if(arr[i] == arr[i+1] || arr[i] == arr[i+2])
{
printf("%d\n", arr[i]);
}

}

for(;i<sizeof(arr);i++)
{
if(arr[i] == arr[(i+1)%sizeof(arr)] || arr[i] == arr[(i+2)%sizeof(arr)]
{
printf("%d\n",arr[i]);
}
}``````

Comment hidden because of low score. Click to expand.
0

Can someone explain the above code?

Comment hidden because of low score. Click to expand.
0

Don't think that will work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I didnt understand how to do it for unsorted arr without using extra space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

For a given list of element of length n, Take an array a, now iterate the list and for every element i , increment the value a[i]++.
At the end you have array a with only count of the respective no (I.e. Index is the actual number and value is there count)

Comment hidden because of low score. Click to expand.
0

we're expected to use comparison . and also you've used extra space i.e. an array a .

Comment hidden because of low score. Click to expand.
0

yeah that's right. without using extra space we cann't count.

Comment hidden because of low score. Click to expand.
0

We can't use hashing.......

Comment hidden because of low score. Click to expand.
0
of 0 vote

1.use radix sort with 0(n) complexity ,and no use of extra space ..
1.1 find lowest unit digits of all the elements,and with the help of lowest unit digit swap elements ,and repeat again for 2nd lowest digit and at the find a sorted array list .

2. after sorting like elements 1,1,1,1,2,2,3,4,5 ,(n=9)
size=n/3 and in this size =3
3. check 1st and n/3th+1 element if both are same so print this element.
and over all complexity is 0(n).

Comment hidden because of low score. Click to expand.
0

Radix Sort is a non comparative sorting algo . We're expected to use comparisons .

Comment hidden because of low score. Click to expand.
0
of 0 vote

The hint is linear selection problem. Application of quicksort.

Comment hidden because of low score. Click to expand.
0

but in quicksort ,complexity is 0(n logn)

Comment hidden because of low score. Click to expand.
0

@Divya, What he/she must have meant is Quick select(and not exactly Quicksort) which works in linear time.

@Anonymous, It is mentioned in the problem to not use linear deterministic selection algo

Comment hidden because of low score. Click to expand.
0
of 0 vote

The best way is to go by radix sort which is a linear time sorting alogrithm and check every length(n/3-1) if n is divisible by 3 or (n/3+1) if n is not divisible by 3

Comment hidden because of low score. Click to expand.
0
of 0 vote

a) most three elements can appear N/3 times in an array of size N.

b) Take a structure consisting of two integers to store an element value and its count in the array. Let there be 4 instances of this structure (or an array of size 4) initialized to 0.
e.g. struct { int element, int count } counter;

c) Iterate over the array and place each element into the counter array at index having the smallest count if the element does not exist in the array. If the element already exist, increment its count.

d) At the end of iteration, print out the elements with count >= N/3

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create 3 equal partition. If the 3 partitions were sorted , then one of the partition would contain the integer which occurs more than n/3.
2. On each of the partition, do the process of figuring out the minimum integer out the integers in the partition. One of these 3 numbers is a potential candidate we are looking for.
3. Create 3 separate variables, which count the number of times each of these candidate occurs in the entire array and figure out the number for which count > n/3

Comment hidden because of low score. Click to expand.
0
of 0 vote

Heapify - O(n)

Remove max and store it... while(removeMax.equals(max) increment counter, if counter > n/3 return max.

Remove max takes at most log(n) so SUM(logn + log(n-1) + ... + 2 + 1) = O(n)

Comment hidden because of low score. Click to expand.
0

How do you heapify? I tried to search Heapify solution a lot but couldn't find. Can you please post the implementation and picture of Heapify?

Comment hidden because of low score. Click to expand.
0
of 0 vote

1.USE BST where duplication is allowed.
2.In order traverse of Tree.(gives sorted array such as 111 2 344455)
3.traverse the array and if count goes to 3 or above print the number.

Comment hidden because of low score. Click to expand.
0

BST creation alone will take O(nlogn) time...

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can not have more than 2 such elements. Here we start with first two unique elements and keep track of their count. we update the values when required. Implementation is self intuitive. Its a O(n) time complex algorithm and with O(1) i.e. constant memory requirement

public class FindTheElementWhichIsRepeatedMoreThanNBy3Times {

/**
* Problem Statement :- Find the element which is repeated for more than n/3 times in a given array of ints
*/
public static void main(String[] args) {
int[] input = {1, 2, 3, 2, 2, 3, 3};
int probableValue1 = input;
int probableVaulue1Count = 1;
int i = 1;

if(i == input.length){
System.out.println("Element : " + probableValue1 + " Count Of The Element : " + probableVaulue1Count);
return;
}
while(probableValue1 == input[i]){
i++;
probableVaulue1Count++;
continue;
}
int probableVlaue2 = input[i];
int probableValue2Count = 1;
boolean probableValue1Turn = true;
for(; i < input.length; i++){
if(input[i] == probableValue1){
probableVaulue1Count++;
}else if(input[i] == probableVlaue2){
probableValue2Count++;
}else{
if(probableValue1Turn){
probableVaulue1Count--;
if(probableVaulue1Count == 0){
probableValue1 = input[i];
probableVaulue1Count++;
probableValue1Turn = !probableValue1Turn;
}
}else{
probableValue2Count--;
if(probableValue2Count == 0){
probableVlaue2 = input[i];
probableValue2Count++;
probableValue1Turn = !probableValue1Turn;
}
}
}
}

probableVaulue1Count = 0;
probableValue2Count = 0;

for(i = 0; i< input.length; i++){
if(probableValue1 == input[i]){
probableVaulue1Count++;
}else if(probableVlaue2 == input[i]){
probableValue2Count++;
}
}

if(probableVaulue1Count > input.length/3){
System.out.println("Element : " + probableValue1 + " Count Of The Element : " + probableVaulue1Count);
}

if(probableValue2Count > input.length/3){
System.out.println("Element : " + probableVlaue2 + " Count Of The Element : " + probableValue2Count);
}

if(!(probableVaulue1Count > input.length/3) && !(probableValue2Count > input.length/3)){
System.out.println("No Such Element found");
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another approach would be to construct a trie with all the numbers. At each node of the trie, including non-leaf nodes, store the count of that particular number. This will need a constant space as the height of the trie is the number of digits in the largest number. Moreover, traversing a trie of constant height is linear - O(1).

When trying to find the numbers that occur at least N/M times among N numbers, this implies that there can be, at the most, N/3 - 1 such numbers. For instance, there can be only 3 numbers that repeat more than 4 times in a list of N numbers.

Along with the trie, have M separate variables that keeps track of the numbers with the highest count so far. In this case, have 2 variables that keep track of the top 2 counts.

For example:
Consider N = 10 => M = 4 (>10/3)
Sequence = 24 56 38 38 51 56 56 56 80 8

Then the trie will be

``````----2(0)     3(0)      5(0)       8(1)
/        /         /   \          \
/        /         /     \          \
4(1)     38(2)     51(1)   56(4)   80(1)``````

And max count is 4 for 56. The second max is 2, which is < 10/3 and hence, can be ignored.

Comment hidden because of low score. Click to expand.
0
of 0 vote

using selection algorithm
1. quickselect (amorized cost is O(n))
or 2. median of median algorithmO(n))

pesudo code:
input: Array
Element elements=new Element;
elements=selectKthElement(Array,0);
elements=selectKthElement(Array,Array.size/3);
elements=selectKthElement(Array,Array.size/3*2);
// each Element in elements is a candidate for appearing more than n/3 times.

for(int i=0;i<elements.size;i++)
{
if(appearMoreThanNOver3Times(elements[i]))
print(elements[i]);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Sort the array using quicksort - O(nlogn)
2) Iterate through the array once
3) if (a[i]=a[i-1] ) then cnt ++ ;
4) if (a[i]!=a[i-1] ) then if cnt > a.length/3 then print a[i-1]; // if cnt is more than third of the array, then print it as one of the elemnts that is more than 1/3rd
5) Reset cnt = 1;
6) go to step 3

Comment hidden because of low score. Click to expand.
0
of 0 vote

We do not need std::map for the original question. Just six int's shall be enough. See the code below.

``````#include <stdio.h>

main() {
int elements;
int counters;
int sum;
int a[] = {5,6,7,8,10,10,10,10,10,10,4,4,4,4,4,1,1};
int size = sizeof(a)/sizeof(int);
int i;

counters = counters = sum = sum = 0;
for (i = 0; i < size; ++i) {
if (counters == 0) {
elements = a[i];
++counters;
sum = 1;
} else if (counters == 0) {
elements = a[i];
++counters;
sum = 1;
} else if (elements == a[i]) {
++counters;
++sum;
} else if (elements == a[i]) {
++counters;
++sum;
} else {
--counters;
--counters;
}
//printf("%d %d(%d) %d(%d)\n", a[i], elements, counters, elements, counters);
}

if (counters > 0 && sum > size/3)
printf("%d\n", elements);
if (counters > 0 && sum > size/3)
printf("%d\n", elements);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the quicksort partition method (randomized) to find the n/3 largest and 2n/3 largest element. Then partition the array based on 2n/3 element. If all the elements after index 2n/3 are same then you have found the number. If not then partition the first 2n/3 elements based on n/3 largest element. Check whether all elements in first partition is same or 2nd parition is same. If one of them is same then we have found it. This is O(n) algo with no extra space.

Comment hidden because of low score. Click to expand.
0

same code at pastebin: a4FzvjDC

Comment hidden because of low score. Click to expand.
0

sorry, wrong branch

Comment hidden because of low score. Click to expand.
0
of 0 vote

hi guys ,
i suggest one could sort the array using merge sort which takes O(nlogn) [worst-case].
then scan the sorted array for all elements that appear more than n/3 times , this would take O(n)
thus we achieve what we want in O(nlogn) + O(n).

let me know if this solution is efficient or not ...
thank you..

Comment hidden because of low score. Click to expand.
0

It's not terribly inefficient. Still, I imagine we're trying to do better than O(NlogN) here because it's just too easy to do what you did.

Comment hidden because of low score. Click to expand.
0

okay eugene

Comment hidden because of low score. Click to expand.
0

What I mean is the problem is rendered uninteresting if we admit this kind of O(NlogN) solution. However, in a practical setting it wouldn't necessarily be a bad idea.

Comment hidden because of low score. Click to expand.
0

yes ,
and i think this algo is risk free..
even if all the n elements are distinct(no duplicates) this algo will give correct answer.

and one improvement while scanning the sorted array can be : scanning (n-((n/3)-1)) elements only .
suppose if there are 20 elements ; n=20 and n/3 = 6 then scanning only till 15 elements , if in case 14th and 15th element are same then we can scan further elements (16th 17th ...) in the hope that elements 14-20 will be the same and can appear in our answer. if we find any element with different values in between 16 - 20 we stop processing further elements.

saving could be large for larger values of n

Comment hidden because of low score. Click to expand.
0
of 0 vote

it can be done like this..array size Max 9
lets say elements are 123 262 482
we have to take array[MAX-1] extra space

scan the the given no
1st no i got 1 so a 1
2nd no i got 2 so a 2
after scanning all the no we end up getting
a 1 a 4 a 1 a 1 a 0 a 1 a 0 a 1 a 0
print that index in which value is > n/3 (4 in this case)
so ans is 2

Comment hidden because of low score. Click to expand.
0

10000000000 10000000000 10000000001
Too much memory requirement isn't it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void printMajorElements(int[] a) {
int e1, c1, e2, c2;

foreach (var x in a) {
if (c1 == 0) {
e1 = x;
c1++;
continue;
}
if (c2 == 0 && x != e1) {
e2 = x;
c2++;
continue;
}

if (x == e1) {
c1++; continue;
}
if (x == e2) {
c2++; continue;
}
c1--; c2--;
}

// second pass to verify
int cA, cB;
foreach (int x in a) {
if (x == e1) cA++;
if (x == e2) cB++;
}

if (cA > a.length / 3)
print(e1);

if (cB > a.length / 3)
print(e2);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import random
import time
import collections
import sys

def solve(A):
INT_MAX = sys.maxint

MAX_TABLE = 3
HASHTABLE = collections.defaultdict(int)

N = len(A)
min_element = None
min_count = INT_MAX

for i in range(0, N):
if len(HASHTABLE) >= MAX_TABLE:
break
HASHTABLE[A[i]] += 1

for i in range(i, N):
if A[i] in HASHTABLE:
HASHTABLE[A[i]]+=1
if min_element == A[i]:
min_count += 1

elif len(HASHTABLE) < MAX_TABLE:
HASHTABLE[A[i]] = 1

if min_count != 1:
min_count = 1
min_element = A[i]

else:
# make some room for new element

# first, find the least frequent
if min_count == 1:
else:

min_element = None
min_count = INT_MAX
for element,count in HASHTABLE.iteritems():
if count < min_count:
min_element, min_count = element, count

HASHTABLE[min_element] -= 1
if HASHTABLE[min_element] <= 1:
del HASHTABLE[min_element]
HASHTABLE[A[i]] = 1

#print HASHTABLE, N, N/3

ret = {}
for element, count in HASHTABLE.iteritems():
ret[element] = "%.2f%%" % (float(count)/ N)

return ret

def main(N):

N3 = N / 3 + 1

A =  * N3
#A.extend( * N3)
#A.extend( * (N - len(A))) # int(N3 * 0.5)

L = len(A)
garbage_size = N - L
A.extend([random.randint(3,4) for i in range(garbage_size)])

S = solve(A)
print S

random.shuffle(A)
S = solve(A)
print S

if __name__=='__main__':

MAX_TESTS = 6 if len(sys.argv) == 1 else int(sys.argv)

SCALE = 10e6

N = 10
for t in range(0, MAX_TESTS):
begin = time.clock()
main(N)
end = time.clock()
T = end - begin
print "test#%d: array_size: %d speed factor:%f" % (t, N, SCALE * (end - begin)/N )
N *= 10``````

Comment hidden because of low score. Click to expand.
0

same code at pastebin: a4FzvjDC

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0

Why it works - this is not a trivial question. In his original post, near the bottom, @fentoyal says: "We can easily prove that, if there is a solution, it must be in the number left at the final stage; but we can not guarantee all numbers left are the correct solution. "

Well, maybe not *easily*, but this thing requires proof, it is not obvious. The idea of the proof would be, that every time you remove 3 different numbers. If some number occurs more than 1/3 of time, it should survive all the removals. The less frequent numbers not necessarily would survive it. (But if a number occurs exactly 1/3 of the times, it may not survive either, BTW).

I think, one can formulate an accurate proof along these lines.

Comment hidden because of low score. Click to expand.
0

Why it works - this is not a trivial question. In his original post, near the bottom, @fentoyal says: "We can easily prove that, if there is a solution, it must be in the number left at the final stage; but we can not guarantee all numbers left are the correct solution. "

Well, maybe not *easily*, but this thing requires proof, it is not obvious. The idea of the proof would be, that every time you remove 3 different numbers. If some number occurs more than 1/3 of time, it should survive all the removals. The less frequent numbers not necessarily would survive it. (But if a number occurs exactly 1/3 of the times, it may not survive either, BTW). I think, one can formulate an accurate proof along these lines.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done using an Augmented AVL tree.

1. create an AVL tree with an additional field as count;
2. Treat numbers in an array as stream of intergers
3. start creating the AVL tree , and keep on updating the count field for each node.
4. Once the array is complete, do a traversal of tree and print nodes whose count > N/3

Comment hidden because of low score. Click to expand.
-1
of 3 vote

check out
cs.utexas.edu/users/moore/best-ideas/mjrty/index.html
a slight modification to this will work.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Step 1: Get the min value of an array (N complexity), say it min
Step 2: Get the max value of an array (N complexity), say it max
Step 3: const = max - min; loop from min to max and checks the frequency of each number and see if it is more than N/3. Complexity : const*N

Comment hidden because of low score. Click to expand.
-2
of 2 vote

@bobby.arora how can u run loop form min to max and count each frequency in o(n).

Comment hidden because of low score. Click to expand.
0

surely worst case would be n^2

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.