Uber Interview Question
Backend DevelopersCountry: United States
Interview Type: In-Person
Maintain a grid of latitude and longitude of some particular length and set of cabs in each grid element.
So if a cab moves from one grid to another. You can update the grid sets in O(1) time.
When a user at position(uLat,uLong) queries for cabs within a radius r, we will process all grid elements between (uLat-r) to (uLat+r) and (uLong-r) to (uLong+r). For every cab in such grid element, we check whether they are at a distance r from the user. This takes O(total no. of cabs considered) or O(total no. of grids considered) time.
Simply use a K-D tree using long and lang as 2 dimensions of each node and build a K-D tree based on long, lat of all cabs and search the position of user in the K-D tree and while searching check if euclid dist(user,cab) <=R.
- rexwulf October 08, 2018Updation: O(logn)/ O(d)
Search: O(logn)/ O(d)
d->max depth of K-D tree.
n->current number of cabs.
A more refined solution will be to create a grid for the location by maintaining a K-D tree with a threshold depth and group cabs according to criteria then simply search with user's location and assign valid groups.