Amazon Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
Assuming prices are charged by hour, the most efficient (and simpler) way of storing the price rules is just an array:
arr[h] = price --> where h = hours - 1
This gives you O(1) query time and O(1) (hours are limited to 24) storage time
While a Balanced Interval Tree makes sense for a more general case, you should always consider the specifics of the problem.
For the architecture design point. I think the previous answer is a good idea:
" you can get geoLocation of the mobile application and use near functionality in mongo."
For a more vendor agnostic (and architecture complete) solution:
- get the customers location from the mobile device's location service (could be GPS or whatever)
- send the location to a (load balanced) web server to solve the request
- the web server will consult a k-d tree-like structure to find the corresponding price map, given the coordinates (could be another service)
- the price map will be as described before
Of course, you should have some caching mechanism in your architecture if you expect to scale.
Store in a vector array so that its extensible, use direct indexing either using hash to find right entry
For APP -
APP ------ HTTP REST GET (apps lat/long) -----> Server
App < -------- 200OK (JSON - list of nearby stores --- Server
At server:
Have a Parking DB model with -
lat
long
nfreespaces
For searching - use Apache solr or elastic search geodist utility .... search engines
For question 1 you can use a Balanced Interval Tree.
- Anonymous March 06, 2016For question 2 you can get geoLocation of the mobile application and use near functionality in mongo.