CareerCup

One solution can be using the PriorityQueue

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class PrioRQueueExample {


	public static void main(String[] args){
		
		PriorityQueue<Double> pq = new PriorityQueue<Double>((x,y)-> {Double z = y-x;return z.intValue(); });
		PrioRQueueExample pqe = new PrioRQueueExample();
		
		//Number of ATMs to return i.e. K
		int num_ATMs = 3;
		
		double curr_loc = 0.00;

		Map<String,Double> nallATMLocs = new HashMap<String,Double>();
		
		//Map of ATM names and their distance co-ordinates
		nallATMLocs.put("atm1",45.0);
		nallATMLocs.put("atm2",78.0);
		nallATMLocs.put("atm3",54.0);
		nallATMLocs.put("atm4",64.0);
		nallATMLocs.put("atm5",35.0);
		nallATMLocs.put("atm6",42.0);
		nallATMLocs.put("atm7",57.0);
		nallATMLocs.put("atm7",1.00);
		
		
		
		nallATMLocs.forEach((atm,dist) ->{if(pq.size() < num_ATMs){
			pq.add(pqe.getLocation(curr_loc,dist));}
		else{
			if(	pq.peek() > pqe.getLocation(curr_loc,dist)){
				pq.poll();
				pq.add(pqe.getLocation(curr_loc,dist));
			}
		}
			});

		pq.forEach(atmLoc -> System.out.println(atmLoc));	
	}
	
	
	private double getLocation(double curr,double atm){	
		return atm - curr;
	}
}

Assuming that getDistance(a, b) is O(1)...

We can iteratively quickselect the 1st closest ATM in the list, k times, by making comparisons based on each ATM's distance.

We can return the result in a list of size k.

He

Assuming getDistance() is O(1)...

Quickselect the 1st closest ATM, k times, and store the result in an array of size k.

Quickselect the Kth closest ATM. Loop through the list of ATMS and select all ATMS closer than the kth closest ATM that was previosuly selected.

Runtime O(2n) = O(n)
Space O(k)

Suppose you are in one location and they gave the 20 ATM's list, We have to invoke getDistance() 20 times to get the distance of all the ATM's, then do the sort and pick the first K locations? Am i right? O(1) for each ATM distance, O(n) for get all the distances and O(n) to select the K ATM centers, am i right?

we can use a K size queue to maintain k smallest distance ATMs or we can also use MAXHeap of size k to store k closet ATMs...I think to K space for K sized heap and it takes O(n) times to store them

PriorityQueue can also be used.

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class PrioRQueueExample {


	public static void main(String[] args){
		
		PriorityQueue<Double> pq = new PriorityQueue<Double>((x,y)-> {Double z = y-x;return z.intValue(); });
		PrioRQueueExample pqe = new PrioRQueueExample();
		
		//Number of ATMs to return i.e. K
		int num_ATMs = 3;
		
		double curr_loc = 0.00;

		Map<String,Double> nallATMLocs = new HashMap<String,Double>();
		
		//Map of ATM names and their distance co-ordinates
		nallATMLocs.put("atm1",45.0);
		nallATMLocs.put("atm2",78.0);
		nallATMLocs.put("atm3",54.0);
		nallATMLocs.put("atm4",64.0);
		nallATMLocs.put("atm5",35.0);
		nallATMLocs.put("atm6",42.0);
		nallATMLocs.put("atm7",57.0);
		nallATMLocs.put("atm7",1.00);
		
		
		
		nallATMLocs.forEach((atm,dist) ->{if(pq.size() < num_ATMs){
			pq.add(pqe.getLocation(curr_loc,dist));}
		else{
			if(	pq.peek() > pqe.getLocation(curr_loc,dist)){
				pq.poll();
				pq.add(pqe.getLocation(curr_loc,dist));
			}
		}
			});

		pq.forEach(atmLoc -> System.out.println(atmLoc));	
	}
	
	
	private double getLocation(double curr,double atm){	
		return atm - curr;
	}
}

jsahusu

hello ahmedthehack,

thanks for posting this, i've applied at amazon video uk as well and they've sent me this online coding assessment. can you kindly share the problems of your online coding assessment as well ?

thanks

hello ahmedthehack,

i've applied at amazon video uk as well and they've sent me an online technical test. Was wondering if you can share the problems your online technical test as well?

Thanks