Amazon Interview Question
Front-end Software EngineersCountry: United States
Interview Type: Phone Interview
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) */
See my implementation that properly handles all the stuff that you make assumptions for.
@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
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.
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) ...
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.
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?
private int getSecondLargest(int[] array)
{
int max=0;
int secMax=0;
for (int i : array) {
if(i>max)
{
secMax=max;
max=i;
}
}
return secMax;
}
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
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;
}
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);}}
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;
}
See my implementation of this problem with O(N) time and O(1) space efficiency at the following link codepad.org/5kpsGjK6
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)
@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.
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)
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.
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.
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.
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.
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.
@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.
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.
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.
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