Amazon Interview Question Software Engineer / Developers


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

- carol on August 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesnt nlogn sorting algorithm take extra space?

- Anonymous on September 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on September 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Add to that heap-sort etc.

- Anonymous on September 25, 2012 | Flag
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).

- Naveen Reddy Mandadi on August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SimplyMe on August 17, 2014 | Flag
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;
}

- Psycho on August 30, 2012 | Flag Reply
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 }

- Cerberuz on August 11, 2012 | Flag Reply
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));
	}

}

- namehere on August 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oops this is dead wrong

- namehere on August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- namehere on August 12, 2012 | Flag
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))

- pjane on August 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Cerberuz on August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- maxim on August 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will it minimize probability of collision ?

- Anonymous on August 16, 2012 | Flag
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))

- pjane on August 13, 2012 | Flag Reply
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).

- Jack on August 17, 2012 | Flag Reply
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);

}
}

- noobProg on October 09, 2012 | Flag Reply
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.

- Aashish on August 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- algos on August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Psycho on August 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

counting sort

- kk on August 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jeetu.mfp on August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ryan on August 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- TheWolfe on August 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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!

- StrictMath on August 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It would be correct, iff MAX <= N

- Razor on August 17, 2014 | Flag


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

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