Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
When a customer selects for a delivery to be made-
1) They should be assigned a locker number closest to his zip code.
2) They should be allowed to cancel a locker delivery until the order has been shipped.
3) You can assume that you have several concurrent requests coming in. When I asked for the hourly/monthly requests we should expectedly be processing, I was told to assume it is tight but not extraordinary. However, the design should allow to scale up.
4) Service should be highly available.
I was also asked to think about how an update would be made to make a locker available when an order is picked up.
Suppose we have a city of a given length and width which we can represent as a grid (int[][]) and a list of locker points (x and y coordinates), then we can pre-compute the distance of the closest locker to each point in the grid:
private static int[][] getLockerDistanceGrid(int cityLength, int cityWidth, List<Point> lockerPositions) {
int[][] grid = new int[cityLength][cityWidth];
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
grid[row][col] = findClosestManhattanDistance(getCoordinate(row), getCoordinate(col), lockerPositions);
}
}
return grid;
}
private static int getCoordinate(int zeroBasedPosition) {
return zeroBasedPosition + 1;
}
private static int findClosestManhattanDistance(int x, int y, List<Point> lockerPositions) {
int closesDistance = Integer.MAX_VALUE;
for (Point p : lockerPositions) {
int distance = Math.abs(x - p.x) + Math.abs(y - p.y);
closesDistance = Math.min(distance, closesDistance);
// we know we can't get better than 0 distance
if (closesDistance == 0)
return closesDistance;
}
return closesDistance;
}
static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
Data-structure 1 - ZipGraph - represents zips in a state
Data-structure 2 - Node{
represents node of above graph i.e. Data-structure 1 ,
Node {
zip code,
H : heap data-structure of LockObject
}
LockObject{
LockNumber,
status (1/0) 1=> available 0 => not available},
zip code
}
}
assign Locker number (orderID)-
for(Node node : for all Node which have zip code belongs to customer’s zip code & find all adjacent zip codes using Data-structure 1){
lock( Node );
LockObject lockObj = Node.H.getRoot()
if( lockObj != null ){
lockObj . status = 0;
assign(lockObj.LockNumber , orderID)
rearrange the heap H
unlock(Node);
break;
}
unlock(Node);
}
}
cancel Locker(lockObject){
Node node = Traverse Data-structure 1 (Graph) to find zip code
lock(node){
lockerObject = search(node.H, lockObject)
lockerObject.status=1;
rearrange the heap
}
}
make available(lockObject){
cancel Locker(lockObject)
}
Data-structure 1 - ZipGraph - represents zips in a state
Data-structure 2 - Node{
represents node of above graph i.e. Data-structure 1 ,
Node {
zip code,
H : heap data-structure of LockObject
}
LockObject{
LockNumber,
status (1/0) 1=> available 0 => not available},
zip code
}
}
assign Locker number (orderID)-
for(Node node : for all Node which have zip code belongs to customer’s zip code & find all adjacent zip codes using Data-structure 1){
lock( Node );
LockObject lockObj = Node.H.getRoot()
if( lockObj != null ){
lockObj . status = 0;
assign(lockObj.LockNumber , orderID)
rearrange the heap H
unlock(Node);
break;
}
unlock(Node);
}
}
cancel Locker(lockObject){
Node node = Traverse Data-structure 1 (Graph) to find zip code
lock(node){
lockerObject = search(node.H, lockObject)
lockerObject.status=1;
rearrange the heap
}
}
make available(lockObject){
cancel Locker(lockObject)
}
Can you please elaborate the functionality of lockers ?
- Kaushik Lele October 30, 2016