Amazon Interview Question for SDE1s


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

- Miguel Oliveira July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- User_Cup September 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes. weird question to ask on careercup though..

- Miguel Oliveira September 23, 2013 | Flag
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.

- oOZz July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anjali July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- algos July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- manojsankethi1 August 01, 2013 | Flag
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;
}

- Sakthivel Sethu ,Software Engineer ,Bangalore October 07, 2013 | Flag Reply
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);

}
}

- Mohammed.Alghzawi July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Upper limit is not given

- Kallu September 23, 2013 | Flag
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;
}

- ambu.sreedharan July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Miguel Oliveira July 25, 2013 | Flag
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);
}
}
}}

- Guillermo Londono July 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will work only elements range is given.

- Kallu September 23, 2013 | Flag
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
	}

- iammrigank July 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i dindn't read "C/C++".
My bad!

- iammrigank July 26, 2013 | Flag
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";
}

- bimleshsharma July 27, 2013 | Flag Reply
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);
			}	
	}
}

- manojsankethi1 August 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can use counting sort

- Anonymous August 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kallu September 23, 2013 | Flag
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.

- Kallu September 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Miguel Oliveira September 23, 2013 | Flag
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.

- Sunil October 07, 2013 | Flag Reply
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;
}

- student January 02, 2015 | Flag Reply
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;
}
}
}
}

- STUDENT January 02, 2015 | Flag Reply
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;
}
}
}
}

- STUDENT January 02, 2015 | Flag Reply
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)

- bimleshsharma July 25, 2013 | Flag Reply


Add a Comment
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.

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