Amazon Interview Question for Front-end Software Engineers


Country: United States
Interview Type: Phone Interview




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

Why we have to use tree for 2nd largest.. it can be done in jus 0(n).Just with help of two variables we can do space : O(2) time :O(n) Even in this we can reduce number of comparisions by taking pair of elements every time.

- Ram June 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

inputs : 1 - int type array of numbers
2 - size of array

output : Second Largest number in array

assumption : There are no two or more times occurance of largest number
int find2ndLarge(int array[],int size)
{
int max[2];
int i; /* for array indexing */

if(array[0]>array[1])
{
max[0]=array[0];
max[1]=array[0];
}
else
{
max[0]=array[1];
max[1]=array[0];
}

for(i=2;i < size; i++)
{
if(array[i]> max[1])
{
if(array[i] > max[0])
{
max[1]=max[0];
max[0]=array[i];
}
else
{
max[1]=array[i];
}
}
}

return max[1]; /*second largest number */
}


/* here time complexity is O(n) */

- prateek June 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

See my implementation that properly handles all the stuff that you make assumptions for.

- ashot madatyan June 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ashot madatyan;

Can you please tell me how your code has O(1) space efficiency? I don't understand this time and space complexity w.r.t your code

- Boobal June 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@boobal
NP, look. I am using a two element scratch array where I store two greatest elements at the moment, and since this scratch array size does not grow with the original input array, it is O(1) space efficient. Every time a new element is inserted into the scratch array, I do at most three comparisons, so the total of comparisons is 3*N, which is linear time. As soon as the input array scan is over, you get two largest values in the scratch array. Hope that clarified the algorithm that I have implemented.

- Anonymous June 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

surely ur solution will work........

but the point is for getting the third max again you need to maintain three variables....same for four.....and so on and for each complexity is of o(n)....but once you have structure like as explained in the previous solution after getting first max...all you will need is 0(log n) ...

- coder0708 June 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem statement is just "find the second largest", and this does not imply that we are to create an effective query structure, for which the solution with BST's would be one of the ways to go with. So, given the statement itself (for one time query) the use of an additional O(N) storage is not that what I think was expected by the interviewer.

- ashot madatyan June 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if(array[0]>array[1])
{
max[0]=array[0];
max[1]=array[0];
}
else
{
max[0]=array[1];
max[1]=array[0];
}

Did you mean 'max[0]=array[1];' for the first assignment?

- Anonymous June 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oops. I meant 'max[1]=array[1];' for the second assignment.

- Anonymous June 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static int secondLargestInt(){

int firstMax = 0;
int secondMax = 0;

for(int i=0;i<arr2.length;i++){
if(arr2[i] > firstMax){
secondMax = firstMax;
firstMax = arr2[i];

}
}


return secondMax;
}

- Achuth R June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

private int getSecondLargest(int[] array)
{
int max=0;
int secMax=0;
for (int i : array) {

if(i>max)
{
secMax=max;
max=i;
}

}
return secMax;
}

- Anonymous June 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't work. Consider the array:
[1, 2, 13, 4, 5, 6],
when the loop process 13:
secMax = 2
max = 13
and secMax will never be updated again. So the result will be 2 even though the right solution is 6

- Anonymous May 10, 2021 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't give the correct answer. Consider the following example
[1, 2, 13, 4, 5, 6]
After processing 13 we have:
secMax = 2 and max = 13. Then secMax won't be ever updated and the result will be 2 even though the correct answer is 6

- oshiro.hugo May 10, 2021 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int FindsecondMax(int[] m)
        {
            //Check for empty array
            if (m.Length == 0)
            {
                throw new Exception("Input array is empty");
            }
            int max = m[0];
            int sMax = int.MinValue;

            for (int i = 1; i < m.Length; i++)
            {
                if (m[i] > max)
                {
                    sMax = max;
                    max = m[i];
                }
                else if (m[i] > sMax && m[i] != max)
                {
                    sMax = m[i];
                }
            }

            if (sMax == int.MinValue)
                throw new Exception("There is no second max");

            return sMax;
        }

- Anitha November 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A JavaScript solution, but the algorithm is quite clear:
{{var input = [0, 1, 2, 2, 3, 9, 5, 7, 5, 6];
var max = 0,
secondMax = 0;
for (var i = 0; i < input.length; i += 1) {
if (input[i] > max) {
max = input[i];
}
if (input[i] < max && input[i] > secondMax) {
secondMax = input[i];
}
}
alert(secondMax);}}

- PS October 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] ArrayOfNums = new int[] { 1, 5, 7, 3, 6, 8, 2 };

        // O(N) Time O(2) Space.
        public int GetSecondBiggestInNTime()
        {
            if (ArrayOfNums.Length == 0)
            {
                throw new Exception("Array is empty");
            }

            int FirstBigNum = 0;
            int SecndBigNum = 0;

            for (int arrayIndx = 0; arrayIndx < ArrayOfNums.Length; arrayIndx++)
            {
                //When we find current element is bigger than earlier elements, then obviously the previous big element is the 2nd biggest.
                if (ArrayOfNums[arrayIndx] > FirstBigNum)
                {
                    SecndBigNum = FirstBigNum;
                    FirstBigNum = ArrayOfNums[arrayIndx];
                }
            }
            return SecndBigNum;
        }

- Srigopal Chitrapu December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

See my implementation of this problem with O(N) time and O(1) space efficiency at the following link codepad.org/5kpsGjK6

- ashot madatyan June 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think it is O(1) space. Also the code requires some loop optimization like loop invariant, Strength Reduction.

- Srigopal Chitrapu December 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

If you want to find nth largest also we can do in worst case linear time algo : Just by modifying quick sort algo.Pivot should be median(refer Median of median algorithm)

- Ram June 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Eugene..could you pls share a better solution in case you happen to know one. I could think of having a tournament tree for this one.

- Pavan Dittakavi June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just keep track of the 2 largest. Compare elements to the smaller of the two, and if elements are bigger, check whether they should become the new second largest or the new largest. Some of the solutions on this page implement this approach.

- eugene.yarovoi June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Tournament Sort is best DS to find out nth largest number.....

- joker_123 June 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@joker : whats the worst case time complexity for that approach ?

- Ram June 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@jan : Sorting will take O(n logn) - merge sort or O(n) if you are doin linear sorting..

- Ram June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use championship method to find the largest number, then find the 2nd largest number from the numbers which are defeated by the largest number. Space is O(2n) and time is O(n+log n)

- poxzlm June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The space required would be O(n^2) since for every element we have to store the list of no. it has defeated in the competition, since we don't know which no is the largest from the start

- Anon June 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use randomized quick sort

- Arya June 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For just 2 numbers?

- eugene.yarovoi June 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

bubble sort would give the second largest number in o(n) time complexity..

- Sathish_master June 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

As we know the number of elements we need to sort, we just need to sort the first 2 elements which can be done in first 2 passes. So the order will be O(2*n) = O(n)

- Anonymous July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

use quickselect to find the required element . like if u have to find kth largest element from a set of n elements find the n-k th smallest element using quickselect algorithm

- Anonymous June 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Finding an i th maximum can be done in log n time using Augmented Red Black Tree.
In red black tree, in each node add one more data, that is size

Size is calculated as (size of left subtree) + (size of right subtree) + 1.

Now once the tree is build, question is how to find i th maximum.

We'll start checking from root.

r = size[left[node]]+1

There are 3 cases:
1. if i == r, then root is the answer
2. if i < r, then search for i th maximun in left subtreee
3. if i > r, then search for (i - r) the maximum in right subtree.

In the worst case, you have to travel from root to leaf node, therefore worst case running time is log n.
1.

- Coder June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Solution is Median of medians algorithm. Guaranteed O(n) in worst case, regardless of whether its is the largest, second-largest or nth largest element we're looking for.

- ACoder July 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That has a very high constant factor compared to other approaches.

- eugene.yarovoi July 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 vote

A tree approach would be appropriate!!!
eg. 10 , 3, 4 ,17 , 12 31 ,5

like
                    (31)
          (17)               (31)
     (10)    (17 )     (31)   (5)
(10 ,3 ) (4, 17) (12, 31) (5)      find max element from bottom to top.

here 31 is the largest element.
noe replace the 31 with the some other value i.e. very small value says -INF
                   (17)
          (17)               (12)
     (10)    (17 )     (12)   (5)
(10 ,3 ) (4, 17) (12, -INF) (5)

This time watever you get will be the second maximum.

- coder0708 June 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i dont understand.how do you get the tree in the 1st place?

- Anonymous June 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Read about ,Tournament Tree approach .......

- coder0708 June 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I presume the using tree is an overkill here, because it can be done with more effective time and space complexities - see the implementation at the link provided in my post. The solution with a tree assumes O(N*logN) time and O(N) space complexities. Moreover, the time complexity will be even worse with unbalanced trees.

- ashot madatyan June 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tree is too much of an over kill

- Randomness June 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess this solution is much like using a heap.. u first build a max heap with numbers as the keys.. now remove first k-1 numbers from the heap to get the kth largest number [O(nlogn)]..
but i dont see any need of this.. finding second largest element can easily be done in O(n) time.

- bam bhole June 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Coder0708: Dude this is THE correct answer. LOL that 2 idiots have voted you down. This approach does minimum comparisons - [n+log(n) -2]. Normal approach would make 2*n-3 comparisons.

- Apurva June 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Apurva thanks atleast you understood the thing what I wanted to explain..:-)

- coder0708 June 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agree tournament algorithm is the way to go

- Bommel June 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the best technique to find out the first and second max or min in an array. TC is n+logn-2 , fully agreed.

- Aavesh September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The potential issue here is that you need O(n) extra space, and you also need to make memory writes, instead of just reads. The fact that you're writing a bunch of stuff to memory can slow you down because those writes are being made to memory instead of much faster registers. I wouldn't necessarily expect this technique to be faster than the naive technique of just keeping two variables with the top two numbers as you traverse the array, as there you don't spend any time doing memory writes.

- eugene.yarovoi October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

There are no sorting approaches that require only O(log n) time.

- eugene.yarovoi June 19, 2012 | Flag


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