Instacart

Design a system to calculate average travel times between locations.

API Methods:

public void pickup(int timestamp, String pickUpLocation, int shopperId)
public void deliver(int timestamp, String deliverLocation, int shopperId)
public double calculateAverage(String locationA, String locationB)

Example Usage:

pickup(0, "A", 1);    // shopper1 picks up at location A at time 0
deliver(5, "B", 1);   // shopper1 delivers at location B at time 5
pickup(0, "A", 2);    // shopper2 picks up at location A at time 0
deliver(6, "B", 2);   // shopper2 delivers at location B at time 6
calculateAverage("A", "B") -> 5.5  // Average of (5 + 6)/2

Design a versioned key-value store with timestamp support.

Part 1: Basic Store

KV kv = new KV();
kv.set("foo", "bar");
kv.get("foo");  // Returns "bar"

Part 2: Version Support

KV kv = new KV();
long timestamp = kv.set("foo", "bar");
Thread.sleep(1000);
kv.set("foo", "bar2");

kv.get("foo", timestamp);  // Returns "bar"
kv.get("foo");            // Returns "bar2"

Part 3: Time-Based Retrieval

KV kv = new KV();
long timestamp = kv.set("foo", "bar");
Thread.sleep(1000);
kv.set("foo", "bar2");

kv.get("foo");                    // Returns "bar2"
kv.get("foo", timestamp + 750);   // Returns "bar"