Directi Interview Question Interns

• 0
of 0 votes

Given an array of Integers of size n, Find element appearing more than n/2 times

Country: India
Interview Type: Phone Interview

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

It shows three dots instead of question?

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

Yep ! this is a majority vote problem ... and the fastest known algorithum for this problem has been suggested by Prof Robert Boyer.

It goes like this [ writing for a C program ]

``void findMajorityElement( int Arr[] , int N){``

``int count=0; int guess=0;``

``for (int i=0; i<N ; i++ ){``

``if(count==0){``

``guess = Arr[i];``

``count++;``

``}//end of the count =0 if statement``

``else{``

``if(guess==Arr[i]){``

``count++;``

``}else{   count--;  }``

``}``

``}//end of the for loop``

``printf("The  element with the majority element is %d", guess);``

``}//end of the findME function``

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

I run the code against [1, 1, 1, 2, 2, 3, 3]. the result is 3. but isn't 1 the right answer?

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

I am able to see only 3 dots - what is the question. How did u infer that this is majorty vote problem

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

question said >n/2. In your input no. of 1 is 3 and as per conditions it should have been >(int)3.5 which means 4 instead of 3

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

Naive approach:
-Sort the array. Now run a scan and find the number with occurences > n/2
Complexity: O(nlogn)

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

Make pairs of elements, throw pairs with different elements, keep pairs with the same elements.
Then the pairs kept must less than n/2, and more than half pairs with the elements we are looking for.
Treat each pair as an new element, repeat the process until there is only one group.

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

What if the array only has 2 elements? It is possible you will throw out only a constant number each time.

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

take two buckets
first element in bucket1
second element if different from first one then in bucket 2
else in bucket 1
if 3 rd element is different from both buckets then pop both buckets and forget 3 rd element
continue this till array ends.
finally the elements in the buckets may be the elements so we have to lookup two scans for the elements in buckets finally.
So time=3n ie O(n)

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

import java.util.HashMap;

public class sortnbytwo {

public static void main(String args[]) {
int a[] = { 1, 2, 2, 4, 2, 2, 4, 233, 2, 4 };
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int cnt = 0;
for (int i = 0; i < a.length; i++) {
if (hm.containsKey(a[i])) {
cnt = hm.get(a[i]);
cnt++;
if(cnt==a.length/2){
System.out.println(a[i]);
break;
}
hm.put(a[i], cnt);
} else
hm.put(a[i], 1);
}
}
}

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

import java.util.HashMap;

public class sortnbytwo {

public static void main(String args[]) {
int a[] = { 1, 2, 2, 4, 2, 2, 4, 233, 2, 4 };
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int cnt = 0;
for (int i = 0; i < a.length; i++) {
if (hm.containsKey(a[i])) {
cnt = hm.get(a[i]);
cnt++;
if(cnt==a.length/2){
System.out.println(a[i]);
break;
}
hm.put(a[i], cnt);
} else
hm.put(a[i], 1);
}
}
}

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

Let the first element be required element(say result).Take a variable count initially initialized to 1.now start scanning the array from 2nd element.if element is same as result then increase the count else decrease the count.When count reaches to 0,make result as current element and initialize count to 1.At the end,result will contain the required element.

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

Here is the "single pass" O(N) solution:

``````function find_the_most_repeating(array)
declare traverser_pair[key:int, count:int]
traverser_pair.key = array[0]
traverser_pair.value = 1 //init
iterate "i" over array from 1 to array.length - 1
if (traverser_pair.key == array[i])
traverser_pair.value++
else
if (--traverser_pair.value == 1)
//here comes the new dominant value
traverser_pair.key = array[i]
traverser_pair.value = 1

return traverser_pair.key;``````

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

HashMap<Integer, Integer> occurence = new HashMap<Integer, Integer>();

for(int i:array){
if(occurence.contains(i))occurence.put(i,occurence.get(i)+1);
else occurence.put(i,1);
}

time: O(n)

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

for(int i:occurence.keyset()){
if(occurence.get(i)>N/2)return i;
}

return -1;

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

import java.util.HashMap;
int find(int[] array){
HashMap<Integer, Integer> occurence = new HashMap<Integer, Integer>();

for(int i:array){
if(occurence.containsKey(i))occurence.put(i,occurence.get(i)+1);
else occurence.put(i,1);
}
for(int i:occurence.keySet()){
if(occurence.get(i)>array.length/2)return i;
}

return -1;
}

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

this is a majority vote problem.

Add a Comment
Name:

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

Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More