Amazon Interview Question for Software Engineer / Developers






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

This might help!
geeksforgeeks.org/?p=3968

- Anonymous June 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Copy the given array in new array.
Sort the new array.
search for the index of each element of given array,say i, into new sorted array,say j.
if j < i then num_of_inv += 1

- Googler May 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Googler, can u plz check this logic for
2,4,3,1
here the number of inversions are 4 ((2,1), (4,3), (4,1), (3,1)).
But as per ur logic, we get 1 as the number of inversions.

- Apritha May 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks, u r right. i'll correct it soon.

- Googler May 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Enhanced Merge Sort O(nlogn)
cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf

- R May 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//basically merge sort, but count the inverse when merge the array
int CountInversion(vector<int>& a, vector<int>& b, int left, int right)
{
if( left >= right) return 0;
int count = 0;
int mid = left + (right - left)/2;
count += CountInversion(a,b,left,mid);
count += CountInversion(a,b,mid+1,right);
for(int i=left; i<=right; i++)
b[i] = a[i];
int i1 = left, i2 = mid+1;
for(int i=left; i<=right; i++)
{
if(i1>=mid) {a[i] = b[i2]; i2++;}
else if(i2>=right) {a[i] = b[i1]; i1++; count += (right - mid);}
else if(b[i1] > b[i2]) {a[i] = b[i2]; i2++;}
else if(b[i1] <= b[i2]) {count += (i2 - mid); a[i] = b[i1]; i1++;}
}
return count;
}

- Anonymous May 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

best solution by thomas cormen book. very nicely written!

- m12 July 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

give one example what exactly you are looking for

- swathi May 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Google it :)

- Apritha May 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do it by Quick Sort also...
Count the no of places particular value passes when a pivot is swapped with it.
The total no of values of swaps will be the total no of inversions

- Gaurav Garg May 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please check my code

#include<stdio.h>

int mergeandcountinversion(int a[],int begin,int middle,int end,int z)
{
	int length=end-begin+1;
	int tmp[length];
	int i1=begin,i2=middle+1,it=0,i=0;
		

	for(i=0;i<length;i++)
	{
		if(i1>middle)
		{
			for(;i2<=end;i2++)
			{
				tmp[it]=a[i2];
				it++;
			}
			break;
		}
		if(i2>end)
		{
			for(;i1<=middle;i1++)
			{
				tmp[it]=a[i1];
				it++;
			}
			break;
		}
		if(a[i1]<=a[i2])
		{
			tmp[it]=a[i1];
			it++;
			i1++;
		}
		else if(a[i2]<a[i1])
		{
			tmp[it]=a[i2];
			it++;
			i2++;	
			z+=middle-i1+1;
		}
	}
	i1=begin;
	for(i=0;i<length;i++)
	{
		a[i1++]=tmp[i];
	}
	return z;
}

int m_sort(int a[],int begin,int end)
{
	int middle=(begin+end)/2,x=0,y=0;
	if(begin==end)
		return 0;
	x=m_sort(a,begin,middle);
	y=m_sort(a,middle+1,end);
	return x+y+mergeandcountinversion(a,begin,middle,end,0);
}

int mergesort(int a[],int n)
{
	return m_sort(a,0,n-1);
}

int main()
{
	int a[]={4,5,3,1,2};
	int n=5,i=0;
	
	printf("%d\n",mergesort(a,n));

}

Feedbacks are welcome

- ananthakrishnan.s.r June 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe the simplest approach is to count the number of swaps that occur in bubble sort.
That'll suffice !

O(n^2)

- TheGhost February 22, 2012 | Flag Reply


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