Part1: It's year 2032, and flying cars are finally here. For safety, each is equipped with a black box that logs (every second): GPS timestamp, GPS latitude, longitude, and altitude.
To keep its flying registration, your flying car transmits this data nightly to the FAA, so your safe flying record can be verified (or appropriate tickets issued if not).
Your job as a contractor for the FAA is to write queries that generate tickets. Your database gets 50 million car records per day (all flying cars in the US, in year 2032), each one logging their position every second for the entire day. Your task is:
1. Write a query that identifies speeders (anyone flying over 500mph). What's the running time of your query (how will the database execute your SQL?).
2. Airborne flying cars must keep a distance of 50 feet away from any other airborne flying car. Write a query that identifies violators and tickets *both* cars [assume airborne means 50 feet altitude]. Again, what's the running time of your query?
Note, millions of records, you can't just do an inner join and compare distances.
Part2: It's year 2022, and the city is strapped for cash. You notice license-plate reading cameras at highway entrances and exits (and all intersections), and get an idea... someone is taking a picture and logging the license plate in a database for every car that goes near those cameras. We get: GPS timestamp, GPS latitude and longitude of camera, and car license plate.
Your job as a DMV contractor: write a query to ticket top 5% of speeders, assuming max speed within the city (including highways) is 50mph.
Hint: If a car is photographed at location X, at 9:00:00am, and is then photographed again at some other random location Y, that is 1 mile away at 9:01:00am, that implies the car drove at 60mph (1-mile in 1-minute) between the two locations. Note that we don't care which road the driver used---unless they can bend space-time and teleport, they *had* to have gone at *least* 60mph between the two locations.
Note that part2 is somewhat different from part1... For both parts, assume your database is *huge* (millions of records---try to come up with solutions that are faster than O(n^2))