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

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) */

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

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

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

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

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

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

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

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

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

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.

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

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?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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.

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

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

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

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

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

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)

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

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

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

Use randomized quick sort

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

For just 2 numbers?

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

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

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)

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

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.

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.

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

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

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

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

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

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

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

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.

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

Tree is too much of an over kill

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

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.

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

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

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

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

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

Agree tournament algorithm is the way to go

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

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.

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

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.

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

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

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.

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