Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

If we need to find all k points, then it can be done in O(nlogk).

We can store only k points in a min-heap of size k.
The value for inserting the element in heap is distance from origin which is (x^2+y^2)
Since the heap size is logk.
Hence, for insertion of n elements, total TC :- O(nlogk)

- navin.nitjsr May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but the the initial size of the heap we need is n right? so wont it make the complexity nlogn

- madav May 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You would want to use max heap and not min heap

- Bloodhawk May 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Min heap won't work!
It should be max heap!

- words&lyrics July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And again klogk is not possible. It should be nlogk. One clear reason , you can't take n out as it is not possible to say about which are k smallest if you have not seen all the element!

- words&lyrics July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Did you mean O(n log(n))? If not, then what's ur algo?

- sethia May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

He probably meant N log(K). Of course it has to be at least O(N) because if you haven't looked at all the points, you don't know that there's not a closer one.

- Anonymous May 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can u plz give the solution??

- pd May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

yeah, I think the tc would have to be a function of N. if I try finding the nearest 3 points out of total 5 or total 500, the times required will be a lot different.

as for the algo, how about using a min heap of size k to store the points arranged by their distances from the origin.

- Anonymous May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can u plz give the solution??

- pd May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can store the distances of all N points from origin in an array.
And then we can use selection algorithm to find kth minimum in array and partition the array according to that point in O(n).
So the overall complexity will be O(N);

- Ajax May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When you use selection sort, the overall time complexity becomes O(kn) not O(n) ?

- Brian May 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Brian, that is not selection sort. It is just the Quick select algorithm.


Ajax, that is good too.

- Pavan Dittakavi May 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1st solution: build a min heap of N points in O(N) time and retrieve K points from the top, complexity: O(N + K log N)

2nd solution: find the kth smallest element in O(N), then return return all points with distance closer than kth smallest; complexity: O(N)

- ??? May 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your second solutions would require an additional array of O(N) for finding the 'kth' smallest element of the array. I assume you are talking about 'Quick Select' algorithm.
But nice one though,
Time Complexity O(N)
Space Complexity O(N).

- Pavan Dittakavi May 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

building a min heap will take O(nLogn)

- guneesh June 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We need a max heap here, dont we?
My code with max heap works just fine.

- epsilon May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity: O(N + N log K)

void firstKPoints(multimap<int, int> &twoDpoints, size_t k, multimap<int, int> &kpoints)
{
	multimap<float, map<int,int> > distKey;

	//compute distance
	for (multimap<int, int>::iterator it = twoDpoints.begin(); it != twoDpoints.end(); it++){
		if (it->first > (int)k || it->second > (int)k)
			continue;
		float dist = sqrt(pow((float)it->first, (float)2.0)+pow((float)it->second, (float)2.0));
		map<int,int> pnt;
		pnt[it->first] = it->second;
		distKey.insert(pair<float,map<int,int> >(dist, pnt));
	}

	//use limited size heap to sort distance
	priority_queue<float> heapK;
	for (multimap<float, map<int,int> >::iterator it = distKey.begin(); it != distKey.end(); it++){
		float dist = it->first;
		heapK.push(dist);
		if (heapK.size() > k){
			heapK.pop();
		}
	}

	//output points
	int pnum = 0;
	while (!heapK.empty()){
		pair<multimap<float,map<int,int> >::iterator,multimap<float,map<int,int> >::iterator> keyRange = distKey.equal_range(heapK.top());

		for (multimap<float,map<int,int> >::iterator it = keyRange.first; it != keyRange.second; it++){
			kpoints.insert(pair<int,int>(it->second.begin()->first, it->second.begin()->second));
			pnum++;
			if (pnum == k){
				return;
			}
			heapK.pop();
		}
	}
}

- farzad May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

let min=first x,y co-ordinate
for rest all (x,y)
if((x*x)+(y*y))<min
min=that x,y co-ordinate

index with min is the point

- okaysh June 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@pkn:- tumhara amazon me selection hua??

- go4gold July 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a temporary scratch array where each index will be having x^2 + y^2[of each D point].
Take a max-heap of size k & act accordingly.
The heap will contain k nearest points.

- john.matheus July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The exact complexity of the code is k for building max heap and log k for each of the elemetns after that


so the total complexity is O(k+(n-k)log k)

- sreeram September 23, 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