Amazon Interview Question
SDE1sCountry: India
Interview Type: Written Test
It's not clear from the question, but if this is the majority find problem, then you can use Moore’s Voting Algorithm, which is O(N) time and O(1) space. (see w w w.geeksforgeeks.org/majority-element/)
If the problem is finding the most frequent element in the array, then the given hashtable solutions will work.
in first iteration algorithm finds the probable majority element. during second iteration it verifies probable majority element appears more than n/2 times or not. if it appears more than n/2 times then it will return that number else it returns -1 (no such majority element exists)
3 5 3 7 3 1 1 3
in this example 3 appears 4 times but it is not >n/2... so it returns -1 (not found)
I Will answer it in java only .
public static void main(String[] args) {
int[] a = {6, 7, 7, 8, 8, 2, 3, 8, 8, 11, 23, 8, 8, 3, 3, 4, 4, 4};
findMajorElement(a, 50);
}
public static void findMajorElement(final int[] a, final int upperLimit) {
int b[] = new int[upperLimit];
int max = 1;
for (int i = 0; i < a.length; i++ ) {
b[a[i]] = b[a[i]] + 1;
}
for (int k = 0; k < upperLimit; k++ ) {
if (b[k] > max) {
max = k;
}
}
System.out.println(max);
}
}
#include<map>
#include<iostream>
using namespace std;
int main(){
int arr[] = {6,7,7,8,8,2,3,8,8,11,23,8,8,7,3,3,4,4,4};
int size = 18;
map<int, int> mymap;
for(int i = 0; i<size; i++){
if(mymap.count(arr[i])>0) mymap[arr[i]]++;
else mymap[arr[i]] = 1;
}
int largest = 0;
for(map<int, int>::iterator it = mymap.begin(); it!=mymap.end(); ++it){
if((*it).second > mymap[largest]) largest = (*it).first;
}
cout<<largest;
}
{{class Program
{
static void Main(string[] args)
{
int[] a = { 6, 7, 7, 8, 8, 2, 3, 8, 8, 11, 23, 8, 8, 7, 3, 3, 4, 4, 4 };
int[] b = new int[24];
int max = -1;
int num = -1;
for (int i = 0; i < a.Length; i++)
{
b[a[i]] += 1;
if (b[a[i]] > max) {
max = b[a[i]];
num = a[i];
}
}
System.Console.WriteLine("Max occurences {0} for number {1}", max, num);
}
}
}}
A HashMap solution...
public static int findMostFrequent(int ar[]) {
int freq = -1;
int freqNum = ar[0];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0; i<ar.length; i++) {
if(map.get(ar[i]) == null)
map.put(ar[i], 1);
else
map.put(ar[i], map.get(ar[i]) + 1);
}
for(int i : map.keySet()) {
if(map.get(i) > freq) {
freq = map.get(i);
freqNum = i;
}
}
System.out.printf("%d %d", freq, freqNum); //prints frequency and the number.
return freqNum; //returns the most freqent number
}
Here is perl....
sub finding_highest
{
my @list=(6,7,7,8,8,2,3,8,8,11,23,8,8,2,3,3,4,4,4);
my %val;
foreach my $x (@list)
{
if(exists $val{$x})
{
$val{$x}=$val{$x}+1;
}
else
{
$val{$x}=1;
}
}
my ($lk,$lv)= %val;
foreach my $k (keys %val)
{
if($lv<$val{$k})
{
$lv=$val{$k};
$lk=$k;
}
}
print "\nLargest value is $lk and count is $lv";
}
Java Solution
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
public class MaxOccuranceElement {
public static void main (String[] args){
int[] a = {6,7,7,8,8,2,3,8,8,11,23,8,8,3,3,4,4,4};
HashMap<Integer, Integer> maxOcc = new HashMap<Integer, Integer> ();
Integer value = 0;
for (int i = 0; i < a.length - 1; i++){
Integer key = new Integer(a[i]);
if (maxOcc.containsKey(a[i])){
value = maxOcc.get(key);
maxOcc.put(key, value + 1);
}
else {
maxOcc.put(key, 1);
}
}
java.util.Iterator<Entry<Integer, Integer>> entry = maxOcc.entrySet().iterator();
while (entry.hasNext()) {
Map.Entry<Integer, Integer> thisEntry = (Map.Entry)entry.next();
Object key = thisEntry.getKey();
Object values = thisEntry.getValue();
System.out.println ("Key = " + key + "Value = " + values);
}
}
}
The best solution I can think of is we should go with hash/map to get it done in O(n). But, people are doing it in two steps (1. prepare map with elements frequencies, 2. Iterate through map to find max frequency number). Actually, we can avoid second step, if we maintain (and update) num of frequencies/majority elements in first iteration itself, then no need to go over map again. Below is working code in C++:
int MajorityFindProblem(int * a, uint size) {
if(size < 1)
return -1;
ulong MajorityElement = a[0];
uint NoOfOccurences = 0;
map<int, uint> m;
map<int, uint>::iterator itr;
pair<int, uint> p;
// loop through the array and prepare a mao (Key is element and value is num of occurences)
// At the same time, maintain MajorityElement also, so that NO NEED to traverse map again for largest element
for(int i =0; i < size; i++) {
itr = m.find(a[i]);
if(itr != m.end()) { // increase num of occurences and also update MajorityElement (if required)
itr->second++;
if(itr->second > NoOfOccurences) {
MajorityElement = itr->first;
NoOfOccurences++;
}
} else { // this is new element
m[a[i]] = 1;
}
}
return MajorityElement;
}
-ve comments (if any) are most welcome.
#include<stdio.h>
#include<stdlib.h>
int main()
{
int a[100],j,i,cnt=0,n,maj=0,temp=0;
printf("ENTRE THE NUMBER OF ELEMENTS \n");
scanf("%d",&n);
printf("ENTRE THE ELEMENTS \n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
j=0;
while(j<n)
{
temp = a[j];
cnt = 0;
for(i=0;i<n;i++)
{
if(temp == a[i])
cnt++;
if(cnt>=n/2)
{
printf("THE MAJORITY ELEMENT IS %d\n",a[i]);
exit(0);
}
}
j++;
}
if(cnt<n/2)
{
printf("THE MAJORITY ELEMENT IS %d\n",a[i]);
exit(0);
}
return 0;
}
{
{
{
#include<stdio.h>
#include<stdlib.h>
int main()
{
int a[100],j,i,cnt=0,n,maj=0,temp=0;
printf("ENTRE THE NUMBER OF ELEMENTS \n");
scanf("%d",&n);
printf("ENTRE THE ELEMENTS \n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
j=0;
while(j<n)
{
temp = a[j];
cnt = 0;
for(i=0;i<n;i++)
{
if(temp == a[i])
cnt++;
if(cnt>=n/2)
{
printf("THE MAJORITY ELEMENT IS %d\n",a[i]);
exit(0);
}
}
j++;
}
if(cnt<n/2)
{
printf("THE MAJORITY ELEMENT IS NOT PRESENT");
exit(0);
}
return 0;
}
}
}
}
{
{
{
#include<stdio.h>
#include<stdlib.h>
int main()
{
int a[100],j,i,cnt=0,n,maj=0,temp=0;
printf("ENTRE THE NUMBER OF ELEMENTS \n");
scanf("%d",&n);
printf("ENTRE THE ELEMENTS \n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
j=0;
while(j<n)
{
temp = a[j];
cnt = 0;
for(i=0;i<n;i++)
{
if(temp == a[i])
cnt++;
if(cnt>=n/2)
{
printf("THE MAJORITY ELEMENT IS %d\n",a[i]);
exit(0);
}
}
j++;
}
if(cnt<n/2)
{
printf("THE MAJORITY ELEMENT IS NOT PRESENT");
exit(0);
}
return 0;
}
}
}
}
If the values on the array are reasonably small, use an array as a hashmap, otherwise use the unordered_map available in C++11 standard.
- Miguel Oliveira July 25, 2013