## Amazon Interview Question for SDE1s

• 0

Country: India
Interview Type: Written Test

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

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.

``````int v[], size; // input
int count[MAX_VAL], best, best_count = 0;
for (int i = 0 ; i < size; ++i)
if (++count[v[i]] > best_count) {
best_count = count[v[i]];
best = v[i];
}
printf("%d\n", best);

// Or
#include <unordered_map> // new C++11 standard
std::unordered_map<int,int> hash_map;
int v[], size; // input
for (int i = 0 ; i < size; ++i) {
int cnt = ++hash_map[v[i]];  // inserts if it does not exist
if (cnt > best_count) {
best_count = cnt;
best = v[i];
}
}
printf("%d\n", best);``````

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

Hey are you the guy with the username 'mogers' on topcoder ?

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

Yes. weird question to ask on careercup though..

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

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.

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

will this algo work for 3 5 3 7 3 1 1 3 plz reply

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

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)

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

I suppose Moore’s Voting Algorithm will assume at least half the number of elements are the same.

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

#include<stdio.h>
int main()
{
int a[] = {6,7,1,2,3,4,5,6,7,7,7,78,8,8,2,3,4,5,8};
int digit[10] = {0};
int i;
int max = a[0];
for(i=0;i<(sizeof(a)/sizeof(a[0]));i++)
{
digit[a[i]]++;
if(digit[max] < digit[a[i]])
max = a[i];
}
printf("Max :%d",max);
return 0;
}

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

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);

}
}

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

Upper limit is not given

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

``````#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;
}``````

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

map operations work in O(log n) so your algorithm works in O(n log n).
To make it O(n), use a hash map instead (now available in the new standard c++11 as unordered_map)

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

{{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);
}
}
}}

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

This will work only elements range is given.

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

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
}``````

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

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

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";
}``````

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

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);
}
}
}``````

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

we can use counting sort

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

Could you give more details how count sort helps here? Thank you.

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

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.

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

you can take advantage of default values and write it like this

``````for(int i =0; i < size; i++) {
cnt = ++m[a[i]];
if(cnt > NoOfOccurences) {
MajorityElement = a[i];
NoOfOccurences = cnt;
}
}``````

likewise with a hash map

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

If additional space is allowed, then i think hashmap is the right solution.
If not allowed to use additional space, i think we can go with 3 way quick sort as well which is inplace algorithm with no extra space and we can get the longest duplicate sequence in O(n log n) time.

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

#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;
}

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

{
{
{
#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;
}
}
}
}

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

{
{
{
#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;
}
}
}
}

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

I am Pythonic so i can answer in Python only:

``````from collections import Counter  #module import
L=[6,7,7,8,8,2,3,8,8,11,23,8,8,1,3,3,4,4,4]
most_common,num_most_common =Counter(L).most_common(1)[0]
print most_common,num_most_common  # output  (8, 6)``````

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.