Here is solutions for User Location Key Value Store.

1. Understand the problem

• We need to design a key-value store where:

  • Key = userId

  • Value = user’s location

• We must support operations like:

  • put(userId, location)

  • get(userId)

• Possibly:

  • Updating locations

  • Querying users by location

  • Handling large scale

So the core problem is:

• Design an efficient way to store, retrieve, and update user locations using a key-value model.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. Scale

• How many users?

• How many location data points do we want to keep per user?

• How frequently do these location objects get sent up?

• Do we want to optimize for runtime? Or memory usage?

• Can I assume timestamps are monotonically increasing for a device?

1. Reads vs Writes?

• Is this read-heavy (tracking users) or write-heavy (live GPS updates)?

1. Single machine or distributed?

• Do we need historical locations or only the latest?

1. Do we need reverse lookup?

• Example: “Find all users in New York”

Edge cases to consider

• Timestamp provided is earlier than the first location → we should return “” because no such timestamp exist

• If the user_id doesn’t exist → return “” or throw an exception, doesn’t matter

• If they did binary search, does their “mid” calculation support overflow? [minor] i.e., (hi+lo)//2 can cause overflow if hi+lo » max int

• Boundary conditions with binary search

  • input such that timestamp > the max timestamp in the store

  • input such that timestamp matches the very first location

• Which timestamp to use? The client timestamp or the server timestamp? Timestamps coming in from different timezones ?

• What if the officer uses multiple devices that have different clocks/timestamps?

3. Explore examples.

set(1, t=5,  lat=2, lon=5)
set(1, t=10, lat=3, lon=6)
set(2, t=4,  lat=0, lon=0)

get(1, 8)  → (3,6)
get(1, 4)  → (2,5)
get(1, 11) → None
get(2, 1)  → (0,0)

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

• Set: O(1).

• Get: O(logN).

class Location:
    def __init__(self, timestamp, lat, lon):
        self.timestamp = timestamp
        self.lat = lat
        self.lon = lon

    def __repr__(self):
        return f"({self.lat}, {self.lon}) @ t={self.timestamp}"


class LocationStore:
    def __init__(self):
        self.store = {}   # user_id -> List[Location]

    def set(self, user_id, timestamp, lat, lon):
        if user_id not in self.store:
            self.store[user_id] = []
        self.store[user_id].append(Location(timestamp, lat, lon))
        # assumes timestamps are inserted in sorted order

    def get(self, user_id, query_time):
        if user_id not in self.store:
            return None

        locations = self.store[user_id]
        n = len(locations)

        # Binary Search
        left, right = 0, n - 1
        closest = None
        min_diff = float("inf")

        while left <= right:
            mid = left + (right - left) // 2
            loc = locations[mid]

            diff = abs(loc.timestamp - query_time)
            if diff < min_diff:
                min_diff = diff
                closest = loc

            if loc.timestamp == query_time:
                return loc
            elif loc.timestamp < query_time:
                left = mid + 1
            else:
                right = mid - 1

        return closest


store = LocationStore()

store.set(1, 1, 1, 4)
store.set(1, 5, 2, 5)
store.set(1, 10, 3, 6)

print(store.get(1, 8))   # (3,6) at t=10
print(store.get(1, 4))   # (2,5) at t=5
print(store.get(1, 1))   # (1,4) at t=1
print(store.get(1, 0))   # (1,4) at t=1
print(store.get(1, 20))  # (3,6) at t=10
print(store.get(99, 5))  # None


# assert (store.get(1, 1).timestamp == 1)
# assert (store.get(1, 0).timestamp == 1)
# assert (store.get(1, 3).timestamp == 4)
# assert (store.get(1, 4).timestamp == 4)
# assert (store.get(1, 5).timestamp == 4)
# assert (store.get(1, 6).timestamp == 4)
# assert (store.get(1, 8).timestamp == 10)
# assert (store.get(1, 15).timestamp == 10)

5. Implement solutions.

6. Dry run testcases.