Skill Subsist Impulse Ltd Interview Question
Data ScientistsCountry: India
Interview Type: Written Test
import java.util.Arrays;
/*
* Find the highest frequency number in an array
* That is in a number the highest repeating number
*/
public class HighestFrequencyNumber {
int[] a = {1, 2, 1, 0, 5, 3, 4, 2, 3, 0, 1, 3, 2, 4,3};
public void sortArray(){
Arrays.sort(a);
}
public void printArray(){
for(int i: a){
System.out.print(i+" ");
}
System.out.println();
}
public void findHigestFreqNumebr(){
int size = a.length;
int freq1=0;
int freq2 = 0;
int i=0;
int num=0;
printArray();
while(i<size-1){
if(a[i]==a[i+1]){
freq1++;
}
else
{
if(freq1>freq2){
freq2 = freq1;
num = a[i];
}
freq1=0;
}
i++;
}
System.out.println("number "+num+" freq "+(freq2+1));
}
public static void main(String[] args){
HighestFrequencyNumber highfreq = new HighestFrequencyNumber();
highfreq.sortArray();
highfreq.findHigestFreqNumebr();
}
}
The total time complexity is O(nLogn) for Arrays.sort and for traversing through the array calculating the highest is O(n) so total being O(n)+O(nLogn)
/* It works*/
#include<stdio.h>
#include<conio.h>
main()
{
int num[100], count[100], arr[100];
int i, j, k, l = 0, n, a = 0, b, d;
int c = 0;
clrscr();
printf("enter number of elements");
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
for (i = 0; i < 100; i++)
num[i] = NULL;
for (i = 0; i < n; i++)
{
b = arr[i];
a = 0;
for (k = 0; k < l; k++)//check whether the number is already scanned or not
{
d = 0;
c = num[k];
d = check(b, c);
if (d != 0)
{
a++;
}
}
if (a == 0)//if number is not already scanned
{
c = 0;
for (j = 0; j < n; j++)//check the array with same numbers
{
if (arr[i] == arr[j])
c++;
}
num[l] = arr[i];
count[l] = c;
++l;
}
}
for (i = 0; i < l; i++)
{
for (j = i + 1; j < l; j++)
{
if (count[i] < count[j])
{
a = count[i];
count[i] = count[j];
count[j] = a;
a = num[i];
num[i] = num[j];
num[j] = a;
}
}
}
printf("\n");
for (i = 0; i < l; i++)
printf("%d\t", num[i]);
getch();
}
check(int b, int c)
{
int k, a = 0;
if (b == c)
return 1;
else
return 0;
}
The question is to print the number in descending order based on frequency(number of occurrence) .
1- Create an hashmap with key as number and value as the occurrence. O(1)
2- Traverse the array, Increase the count(value in hash) if the number is repeated. else put value = 1 if number came first time. O(n)
3- Sort the hashMap based on value and print it. O(nlogn)
Total time complexity O(n) + O(nlogn) => O(nlogn)
/*It works*/
#include<stdio.h>
#include<conio.h>
main()
{
int num[100], count[100], arr[100];
int i, j, k, l = 0, n, a = 0, b, d;
int c = 0;
clrscr();
printf("enter number of elements");
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
for (i = 0; i < 100; i++)
num[i] = NULL;
for (i = 0; i < n; i++)
{
b = arr[i];
a = 0;
for (k = 0; k < l; k++)//check whether the number is already scanned or not
{
d = 0;
c = num[k];
d = check(b, c);
if (d != 0)
{
a++;
}
}
if (a == 0)//if number is not already scanned
{
c = 0;
for (j = 0; j < n; j++)//check the array with same numbers
{
if (arr[i] == arr[j])
c++;
}
num[l] = arr[i];
count[l] = c;
++l;
}
}
for (i = 0; i < l; i++)
{
for (j = i + 1; j < l; j++)
{
if (count[i] < count[j])
{
a = count[i];
count[i] = count[j];
count[j] = a;
a = num[i];
num[i] = num[j];
num[j] = a;
}
}
}
printf("\n");
for (i = 0; i < l; i++)
printf("%d\t", num[i]);
getch();
}
check(int b, int c)
{
int k, a = 0;
if (b == c)
return 1;
else
return 0;
}
/*it works*/
#include<stdio.h>
#include<conio.h>
main()
{
int num[100], count[100], arr[100];
int i, j, k, l = 0, n, a = 0, b, d;
int c = 0;
clrscr();
printf("enter number of elements");
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
for (i = 0; i < 100; i++)
num[i] = NULL;
for (i = 0; i < n; i++)
{
b = arr[i];
a = 0;
for (k = 0; k < l; k++)//check whether the number is already scanned or not
{
d = 0;
c = num[k];
d = check(b, c);
if (d != 0)
{
a++;
}
}
if (a == 0)//if number is not already scanned
{
c = 0;
for (j = 0; j < n; j++)//check the array with same numbers
{
if (arr[i] == arr[j])
c++;
}
num[l] = arr[i];
count[l] = c;
++l;
}
}
for (i = 0; i < l; i++)
{
for (j = i + 1; j < l; j++)
{
if (count[i] < count[j])
{
a = count[i];
count[i] = count[j];
count[j] = a;
a = num[i];
num[i] = num[j];
num[j] = a;
}
}
}
printf("\n");
for (i = 0; i < l; i++)
printf("%d\t", num[i]);
getch();
}
check(int b, int c)
{
int k, a = 0;
if (b == c)
return 1;
else
return 0;
}
#include<stdio.h>
#include<conio.h>
main()
{
int num[100], count[100], arr[100];
int i, j, k, l = 0, n, a = 0, b, d;
int c = 0;
clrscr();
printf("enter number of elements");
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);
for (i = 0; i < 100; i++)
num[i] = NULL;
for (i = 0; i < n; i++)
{
b = arr[i];
a = 0;
for (k = 0; k < l; k++)//check whether the number is already scanned or not
{
d = 0;
c = num[k];
d = check(b, c);
if (d != 0)
{
a++;
}
}
if (a == 0)//if number is not already scanned
{
c = 0;
for (j = 0; j < n; j++)//check the array with same numbers
{
if (arr[i] == arr[j])
c++;
}
num[l] = arr[i];
count[l] = c;
++l;
}
}
for (i = 0; i < l; i++)
{
for (j = i + 1; j < l; j++)
{
if (count[i] < count[j])
{
a = count[i];
count[i] = count[j];
count[j] = a;
a = num[i];
num[i] = num[j];
num[j] = a;
}
}
}
printf("\n");
for (i = 0; i < l; i++)
printf("%d\t", num[i]);
getch();
}
check(int b, int c)
{
int k, a = 0;
if (b == c)
return 1;
else
return 0;
}
import java.util.Map;
import java.util.HashMap;
public class GetMaxFrequencyNumber {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {1, 2, 1, 0, 5, 3, 4, 2, 3, 0, 1, 3, 2, 4,3};
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < a.length; i++) {
if(!map.containsKey(a[i])){
map.put(a[i], 1);
}
else {
System.out.println("value==="+map.get(a[i]));
map.put(a[i], map.get(a[i])+1);
}
}
System.out.println(map);
int maxFrequency =0;
int number = 0;
for (Map.Entry<Integer,Integer> x : map.entrySet()) {
if(x.getValue()>maxFrequency){
maxFrequency = x.getValue();
number = x.getKey();
}
}
System.out.println("Frequency==="+maxFrequency);
System.out.println("Number==="+number);
}
}
- Dhenu April 11, 2017