## Amazon Interview Question for Software Engineer in Tests

• 0

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

My gut feeling tells me that: Do a bubble sort and then traverse it.
Is this correct?

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

Correct! but not optimize

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

Its good to use merger/heap sort rather then bubbel sort.
Improvement:
O(n*n) ===>> O(n*log(n))

But still there is a scope of improvement.

SUGGESTION-1
Use the red-black tree.
By this the retreval complexity get reduced to log(n).

SUGGESTION-2
We can try hashing to optimize the retreval complexity.
Inesrt the values in hash table in sorted order.
Use the key as sorted position and values as their actual value.

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

-There is a algorithm with running time O(n+klogn)
-However, there is also algo with O(n) time

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

largest and second largest

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

Im missing why you would use a RB tree. What is the cost of populating a RB tree of size n? Since insertion takes 0(log(n)), wouldn't the cost of populating the tree be 0(nlog(n))? After you have the tree populated, how would you retrieve the xth largest value? I believe you would have to traverse the RB tree to find this value, which would be a worst case of 0(n). RB trees are great for searching for particular values, not for finding the xth largest value.

My gut tells me to sort using merge sort and then retrieve the xth value (IE array[x-1]).

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

How about using quick sort, which performs in the order of nlg(n). We can choose the median element to be the partition element and then perform quick sort recursively. Finding median from the array takes O(n) and quick sort O(nlg(n)). Now the ith largest number will be at the (n-i) position in the array.
Complexity id O(nlg(n))

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

Don't do sort. Sorting is too slow in this case. You don't need to sort everything to get the nth maximum. Use "Partition" algorithm, you will get theta(n).

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

1). Construct a heap with k elements. (Can be done in O(k).
2). For each of the remaining (n-k) elements,
a). If it's smaller than the root, discard it.
b). Otherwise, insert into the heap. ( O(logk) ).
3). When all the elements are finished, the root node is the kth largest.

Running time: O(k+(n-k)logk).

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

In b), when you insert into the heap of size k, the size is no longer k, but k+1. So, the root is not k-th largest but largest among a bunch of numbers..

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

Use Median of Medians algorithm to find the k-th largest number.
O(n) time complexity.

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

Could u please give sample code for this algorithm

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

http://crystal.uta.edu/~gdas/Courses/Courses/Spring2008/Algo2/L4.ppt

http://www.soe.ucsc.edu/classes/cmps102/Spring05/selectAnalysis.pdf

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

SELECT algorithm can be used.. its run time is logarithmic i believe..

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

The question should be:
Given a array of n integers we need to find the second largest number in it. And generalized to find kth largest number, where k << n.

As simple as it is, we can just keep scaning the array, storing the largest number and the second largest number and their indice.

if a[0] > a[1
1stLGNo = a[0]; 1stLGInd= 0; 2ndLGNo = a[1]; 1stLGInd= 1;
else
1stLGNo = a[1]; 1stLGInd= 1; 2ndLGNo = a[0]; 1stLGInd= 0;

for (i-2, i< n; i++)
{
Update(a[2], 1stLGNo,1stLGInd, 2ndLGNo,1stLGInd);
}
out put 2ndLGNo and 2ndLGInd.

This is a plain and simple O(n) algorithm. It is good for k < lg(n).
If k is close to n, we can use l = n - k << n to find the lth smallest number.
However, when k is close to lg(n), sorting algorithm becomes attractive.

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

The question should be:
Given a array of n integers we need to find the second largest number in it. And generalized to find kth largest number, where k << n.

As simple as it is, we can just keep scaning the array, storing the largest number and the second largest number and their indice.

if a[0] > a[1
1stLGNo = a[0]; 1stLGInd= 0; 2ndLGNo = a[1]; 1stLGInd= 1;
else
1stLGNo = a[1]; 1stLGInd= 1; 2ndLGNo = a[0]; 1stLGInd= 0;

for (i-2, i< n; i++)
{
Update(a[2], 1stLGNo,1stLGInd, 2ndLGNo,1stLGInd);
}
out put 2ndLGNo and 2ndLGInd.

This is a plain and simple O(n) algorithm. It is good for k < lg(n).
If k is close to n, we can use l = n - k << n to find the lth smallest number.
However, when k is close to lg(n), sorting algorithm becomes attractive.

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

Sorry for the errors:

if a[0] > a[1
1stLGNo = a[0]; 1stLGInd= 0; 2ndLGNo = a[1]; 2ndLGInd= 1;
else
1stLGNo = a[1]; 1stLGInd= 1; 2ndLGNo = a[0]; 2ndLGInd= 0;

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

int Bubble_Sort(input[], target_position)
{
int iterations = target_position - input.length + 1;
return bubble_sort_scan(input, iterations);
/* each bubble sort scan places 1 element to its final position in the array.
starting from the largest element. complexity will be O(n) for largest element.
O(2n) for 2nd largest
}

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

There is no reason to do the second scan.
O(2n) is O(n).
If we need to know the index i, where a[i] is the second largest, the reqular bubble won't do it.

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

Use a loser tree. Extra space O(n) and time for initialization is O(n). Any subsequent retrieval is O(log n).

This way, for the second largest element, the complexity will be n + 2 log n which is of order O(n). Again, for the kth smallest element, the complexity is O(n + k * log n).

Correct me if I am wrong!!

-VJ

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

Using C++

``````int findKthLargest(vector<int> v,int k)
{
partial_sort(v.begin(),v.begin() + k, v.end());
return v.at(v.size () - k-1);

}
int findKthSmallest(vector<int> v,int k)
{

partial_sort(v.begin(),v.begin()+k ,v.end ());

return v.at(k-1);

}``````

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

Find the largest number of the array in one pass -> O(n)
in the next pass of the array find the number which is just less than largest -> O(n)
Total time: O(n)+O(n)=O(n)

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

public void FindSec()
{
int[] arr = { 1,2,0,-1,8,26,1,26};
int high, secHigh, temp, i;

high = secHigh = arr[0];

for (i = 1; i < arr.Length; ++i)
{
temp = arr[i];
if(temp > high)
{
secHigh = high;
high = temp;
}
else if(temp >secHigh && temp != high)
{
secHigh = temp;
}
}

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

Question belongs to Order statistics Coreman 9th or 8th Chapter.
Finding the k th rank in array User Randomize-select average case complexity theta(n).
Use linear select guaranteed O(n)

Randomize-select(a,p,r,k)
{
if p==r
return a[p]
q=randomize-partition(a,p,r) //quick sort partition which gives pivot index
i = q-p+1
if(k==i)
return a[i]
else if(k<i)
return Randomize-select(a,p,r,k)
else
return Randomize-select(a,p,r,k-i)
}
randomize-partition(a,p,r)
{
n = rand(1...sizeof(a))
swap(a[n] <-> a[r])
partition(a,p,r)
}
partition(a,p,r)
{
x=a[r]
i=p-1;
for j=p to r-1 j++
{
if(a[j]<=x)
{
i++
a[i]<->a[j] //swap
}
}
a[i+1]<->a[r] //swap
}

call Randomize-select(a,1,10,k)

Recurrence Equation = T(n) = T(9n/10) + o(n) // say each time it divide in 9/10 and 1/10 and we are unlucky and each time we have to solve 9/10 problem.
solve using mater theorem case 3.. T(n) = o(n)

you can make guanteed o(n) by linear select .

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

Sort the sequence using BST sort o(nlogn)descending order
now run a loop n-1 times to remove the first element and add it to last of the linked list
now get the first element from the linked list.

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

How abt this one

Int getLarge(int[] a, int n){
int max = 0;
for(int i = 0; i< a.length; i++){
if(a[i]>max) max = a[i];
}

if(n == 1)return max;
else {
for(int i = 0; i< a.length; i++){
if(a[i]==max) a[i] = -65535;
}
return getLarge(a,n-1);
}
}

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

use a part of quick sort. Select the pivot element which is at position of K ( we have to find kth largest element) now swap all the elements smaller than k on left side to all the elements larger than k on right side till both pointers meet.
at the end of first iteration, kth position would have the correct element placed

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

Can U plz Explain it again clearly........

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

Its the standard selection algorithm... O(n)

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

-Quick sort and hash elements as they are being sorted to remove multiples
-Pull (n-1)th element from your sorted array

There might be a cleaner or faster solution, but this works fairly neatly, I believe

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.