Amazon Interview Question Software Engineer in Tests




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?

- Raj on October 13, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Correct! but not optimize

- Anonymous on October 13, 2009 | Flag Reply
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.

- Ashutosh on October 14, 2009 | Flag Reply
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

- Anonymous on October 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

largest and second largest

- anu on November 02, 2009 | Flag
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]).

- anon on October 14, 2009 | Flag Reply
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))

- Anonymous on October 14, 2009 | Flag Reply
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).

- Anonymous on October 15, 2009 | Flag Reply
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).

- Hari on October 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nix on October 17, 2009 | Flag
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.

- Aditya on October 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could u please give sample code for this algorithm

- new.learner67 on October 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please see these two documents

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

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

- Harish Surana on November 06, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- clrs on March 25, 2010 | Flag
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.

- kulang on October 17, 2009 | Flag Reply
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.

- kulang on October 17, 2009 | Flag Reply
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;

- kulang on October 17, 2009 | Flag Reply
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
}

- simplifier on October 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- kulang on October 19, 2009 | Flag
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

- Vijay on October 22, 2009 | Flag Reply
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);
	
}

- Sudipta on November 07, 2009 | Flag Reply
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)

- magadheera on November 10, 2009 | Flag Reply
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;
}
}

- srujan on November 10, 2009 | Flag Reply
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 .

- Anonymous on November 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the sequence using BST sort o(nlogn)descending order
Put it in linked list
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.

- sriram on January 15, 2010 | Flag Reply
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);
}
}

- ani on January 30, 2010 | Flag Reply
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

- neo on March 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- KK on July 29, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Prateek on September 30, 2010 | Flag Reply
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

- Anonymous on October 16, 2009 | Flag Reply


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