## student Interview Question for Students

Country: India

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

The following algo may help
1.)Take a hash map with key as array element and value as its count.
2.)as u traverse the array update the map.
3.)the size of map should not exceed k.
4.)once the size of map is k and we encounter a new element which is not yet in the map, decrement the count of all the existing keys by 1.
5.) If there is a key with count 0, replace it with the new element, or replace the key with the lowest count with the new element.
6.)Repeat the above till all elements in array are done.
7.)Now what u have is a map with k elements, set count to 0. traverse the array again and update the count of the keys in map.
8.)check for count and if it exceeds k print it.

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

They are asking to do it in O(nk) time, which means you have to do it inplace...Any inplace algo u can think, will be heartily appreciated..:)

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

when you say we have to do it inplace.Do you mean that we can not use hashSet/HashTable?

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

Hi vimalk179,

Can you please explain a bit more on below statement.
"if it appears more than
n
k
times in A."
more than nk or n/k?

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

It's obvious. No number can exist nk times.
It is n/k

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

ya it's n/k .. can you post the pseudo code this programm in C langauge othrwise any

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

``````public static <T extends Comparable<T>> void findKMajority2(T[] array, int k) {
System.out.println("Finding " + k + " majority list: ");
if (k == 0) {
return;
}
if(k == 1) {
Set<T> s = new HashSet(Arrays.asList(array));
System.out.println(s);
return;
}
Map<T, Integer> map = new HashMap<T, Integer>();
for(int i = 0; i < array.length; i++) {
T key = array[i];
if(map.containsKey(key)) {
Integer count = map.get(key);
if(++count == k) {
System.out.print("	" + key);
}
map.put(key, count++);
}else {
map.put(key, 1);
}
}
System.out.println();
}``````

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

The algo is O(nk). In the first pass u generate the map.
Now if ur map has k elements then u scan the array k times to make sure that the keys are repeated n/k times.
So the net time complexity is O(nk).

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

sort the array ...time complexity nlogn for sorting
then traverse the array to find if any number exist which appears more than (n/k) times in array. can be done in O(n) time.
so total time complexity nlogn + O(n)
correct me if i'm wrong.

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.