Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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).
void getSMax(int arr[])
{
map<int, int> mymap;
int max=0, maxcnt=0, smax=0, smaxcnt=0;
for(int i=0; i<=N; i++)
{
if ( (++mymap[arr[i]]) > maxcnt )
{
if (max != arr[i])
{
smax = max;
smaxcnt = maxcnt;
}
max = arr[i];
maxcnt = mymap[arr[i]];
}
else if ( mymap[arr[i]] > smaxcnt)
{
smax = arr[i];
smaxcnt = mymap[arr[i]];
}
}
cout << smax << " " << smaxcnt << endl;
}
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;
}
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 }
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));
}
}
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));
}
}
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))
What is the most appropriate hash function to use if array elements are 32 bit signed integers ??
according to knuth's multiplicative hashing method, we could multiply some number and mod 2^32 to get the hash value.
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))
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);
}
}
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.
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
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.
Well, the O(nlogn) solution is not optimal. There is in fact a solution which takes O(n):
Assumptions:
1) (N+1) * max(arr[0..N]) can fit in an 32 or 64-bit integer.
Here is how:
1) Iterate through the array and fix the maximum element in the array: MAX = max(arr[0..N])
2) Iterate through the array again, and for each 'i' : arr[arr[i]%MAX] += MAX
3) Iterate through the array again, and find the second maximum element.
4) If required to restore the array back, iterate again and arr[i] = arr[i]%K for each 'i'.
The above takes O(n) time with O(1) space.
Cheers!
1. Sorting using any nlogn algorithm.
- carol August 12, 20122. 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).