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.
computer science
Description
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))
