## Amazon Interview Question Software Engineer / Developers

• 0

Given an array of integer as an input. write a function to return the second most occurring element in the array.

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 5 vote

1. Sorting using any nlogn algorithm.
2. maintain 2 variables max ans s_max.
3. count the frequency of the first value and store it in max.
4. when another value is encountered , count it's frequency and compare it with max.
5. if the frequency is greater than max then s_max= max, and max= frequency of the new value.
6 if the frequency is less than max then compare it with s_max..if s_max is lesser then s_max=new frequency.
7. repeat step 4 till all the elements in the array are covered.
this algorithm has the time complexity of O(nlogn) and space complexity of O(1).

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

doesnt nlogn sorting algorithm take extra space?

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

Quicksort does not. in-place merge sort does not.

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

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

Have maxNum, maxNumCount, secondMaxNum, secondMaxNumCount and hash table{num=>count}.
Update the values as we scan each element in the array.
Finally you will remain with secondMaxNum.
Complexity is just O(n).

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

Same as @carol says

``````#include <cstdio>
#include <algorithm>
using namespace std ;

void swap (int *a, int *b) {
int temp = *a ;
*a = *b ;
*b = temp ;
}

int main () {
int arr[] = {9,0,3,2,4,1,3,4,0,4,4,0} ;
int max, s_max, mCount = 1, smCount = 0, temp, count = 0;
int size = sizeof(arr)/sizeof(arr[0]) ;
sort (arr,arr+size) ;

for ( int i = 1, max = arr[0], temp = arr[0] ; i < size ; i ++ ) {
if ( temp == arr[i] )
count ++ ;
else {
/* New element with max occurance found out */
if ( count > mCount ) {
/*assign it to second max */
swap (&max, &s_max);
swap (&mCount, &smCount) ;
mCount = count ;
max = temp ;
count = 0 ;
} else if ( count > smCount ) {
/* Second max found */
smCount = count ;
s_max = temp ;
count = 0 ;
}
}
temp = arr[i] ;
}
if ( smCount != 0 )
printf ( "\nSecond ocurring number = %d", s_max ) ;
return 0;
}``````

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

Sorting can solve it in O(nlogn).

If array elements are in definite range ( small enough ), we can store count of each element and traverse the count array to get its second minimum element whose index will be the answer. { O(range of elements) }

Else, we can use appropriate hash table( taking care of collisions ). { O(n) + collision avoidance overhead }

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

``````import java.util.HashMap;

public class SecondMostCommonInt {

public static int secondMostCommon(int [] input){

HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(input.length);
for(int i = 0; i < input.length; i++){
if(hash.get(input[i]) == null){
hash.put(input[i], 1);
}
else
hash.put(input[i], hash.get(input[i]).intValue() + 1);
}

int max = Integer.MIN_VALUE;
int secondMax = Integer.MIN_VALUE;

Object [] keys = hash.keySet().toArray();

for(int i = 0; i < keys.length; i++){
if(hash.get(keys[i]) != null)
if(((Integer)hash.get(keys[i]).intValue()> max))
max = (Integer)(keys[i]);

}

for(int i = 0; i < keys.length; i++){
if(hash.get(keys[i]) != null && hash.get(keys[i]) <= max)
if(((Integer)hash.get(keys[i]).intValue()> secondMax))
secondMax = (Integer)(keys[i]);
}

return secondMax;
}

public static void main(String [] args) {
int [] input ={1,1,2,5,6,6,6,5,9000,3,4};
System.out.println(secondMostCommon(input));
}``````

}

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

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

Is this linear?

``````public class SecondMostCommonInt {

public static int secondMostCommon(int [] input){

HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(input.length);
for(int i = 0; i < input.length; i++){
if(hash.get(input[i]) == null){
hash.put(input[i], 1);
}
else
hash.put(input[i], hash.get(input[i]).intValue() + 1);
}

;

Object [] keys = hash.keySet().toArray();

Integer max = Integer.MIN_VALUE;
Integer secondMax = Integer.MIN_VALUE;

int maxKey = 0;
int secondMaxKey = 0;

for(int i = 0; i < keys.length; i++){
if(hash.get(keys[i]) != null)
if(      (Integer)hash.get(keys[i]).intValue() >= max){
maxKey = (Integer)(keys[i]);
max =  (Integer)hash.get(keys[i]).intValue();
}

}

secondMaxKey = maxKey;
for(int i = 0; i < keys.length; i++){
if(hash.get(keys[i]) != null && !keys[i].equals(maxKey))
if((Integer)hash.get(keys[i]).intValue()>= secondMax){
secondMaxKey = (Integer)(keys[i]);
secondMax =  (Integer)hash.get(keys[i]).intValue();
}
}

return secondMaxKey;
}

public static void main(String [] args) {
int [] input ={1,1,1,1,2,5,6,6,6,5,9000,3,4};
System.out.println(secondMostCommon(input));
}
}``````

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

Two ways to do it:
1. Sorting and calc second max (nlogn)
2. Use hashtable, using the number as key and no. of occurrences of that number as the value. Each time the number is encountered again, increment the value for said number. Finally, get the second highest value amongst all keys (Should take O(n))

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

What is the most appropriate hash function to use if array elements are 32 bit signed integers ??

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

according to knuth's multiplicative hashing method, we could multiply some number and mod 2^32 to get the hash value.

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

Will it minimize probability of collision ?

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

Two ways to do it:
1. Sorting and calc second max (nlogn)
2. Use hashtable, using the number as key and no. of occurrences of that number as the value. Each time the number is encountered again, increment the value for said number. Finally, get the second highest value amongst all keys (Should take O(n))

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

Can b done without hashtable, but O(n^2) running time. If the array is small, this will suffice...
First loop to find the most occurring element.
Second loop to find the second-most occurring element. Both loops will take O(n^2).

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

``````import java.util.*;
public class kLargest{
public static void main(String args[])
{
//int []arr={5,5,5,23,23,23,23,1,2,5,6,7,7,7,7,7,7,3,2,1,34,54,23,5,5,5};
int []arr={1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,4,4,5};
findkLarge(arr);
}
public static void findkLarge(int []a)
{
HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
int i;
for(i=0;i<a.length;i++)
{
if(hm.get(a[i])==null)
hm.put(a[i],1);
else
hm.put(a[i],hm.get(a[i]).intValue()+1);
}
System.out.println(" "+hm);
Object [] keys = hm.keySet().toArray();
Integer max1val=Integer.MIN_VALUE;
Integer max2val=Integer.MIN_VALUE;
Integer max1key=0,max2key=0;
for(i=0;i<keys.length;i++)
{
if((Integer)hm.get(keys[i])>=max1val)
{
max2val=max1val;
max2key=max1key;

max1val=(Integer)hm.get(keys[i]);
max1key=(Integer)keys[i];
}
else if((Integer)hm.get(keys[i])>=max2val)
{
max2val=(Integer)hm.get(keys[i]).intValue();
max2key=(Integer)keys[i];
}
}
System.out.println("The Second Highest key: "+max2key+" value: "+max2val);

}
}``````

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

1. Take a BST with extra field count of occurrence.
2. Maintain a min heap of size 2 dealing with the frequency. Whenever any item occurrence is more than the frequency of the head, replace it & update heap.
3. At the last, the top of the heap gives the required item.

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

BST will take O(nlogn) time, instead you can use hash table and store the count as well... it just need O(n) time and space

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

BST can force the algo to run in o(n^2) Because structure of BST highly dependent on numbers to be inserted. If the array size is large and the numbers which occur max and second most number are at extreme right or left, then algo will run in O(n^2) time.

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

counting sort

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

the range of the numbers is not given so we cannot use counting sort...

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

jeetu.mfp, finding the range is easy. It just takes one pass through the list. You keep a record of Max and Min. If the range turns out to be small and the number of elements is large then counting sort is the best. However, if the range is big and the list is small we'd need another option. This is where the hash table solutions will work much better. I suggest to everyone not to be quick to discount counting as an option.

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

This can be done in n + logn comparisons. Read cormen carefully

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through 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.