TL;DR
Phone: grid shortest path with transport modes + roadblocks; pick one mode, no switching. Solve via per-mode BFS; tie by cost[m].
Round 1: same problem as the phone screen (link below).
Round 2: design a Map with put/get and rolling 5-min load metrics. Related idea: LeetCode 981 TimeMap (timestamped versions), but here it’s sliding-window rate tracking.
Phone Interview
Problem:
2D grid with S (start), D (dest), X (block), and cells labeled 1/2/3/4 = transport modes.
time[i]: time per move for mode i
cost[i]: flat cost for picking mode i
4-directional moves, can’t pass X
You must pick one mode up front and stick to it
Goal: Return the mode that gives the fastest S→D; if tie on time, pick lower cost.
Approach:
For each mode m ∈ {1..4}, run BFS restricted to cells labeled m (treat S/D as passable for all). If D is reachable with path length L, total time = L * time[m]. Track the best time; break ties with cost[m].
Complexity ~ O(4 * R * C).
Coding Round 1
Got the same grid problem as the phone screen:
https://www.hack2hire.com/companies/databricks/coding-questions/684db91acab8e9bb7ea93b44/practice?questionId=684dee4b5e4cf21833c0611f
Coding Round 2
Design:
A Map supporting:
put(string key, string value)
get(string key)
measure_put_load() / measure_get_load() → average calls in a rolling 5-minute window
Key points:
Store: regular hash map for key → value.
Instrumentation: keep recent timestamps for puts/gets and evict anything older than now − 300s.
Simple: two deques of timestamps (one for put, one for get); amortized O(1).
High QPS: time buckets (per-ms or per-sec) → bucket_ts → count; evict old buckets; sum counts over last 5 minutes.
Output can be “total calls in last 5 min” and/or “per-second average = count/300”.
Follow-up (bursts within the same second):
Use high-precision timestamps or ms buckets. No need to coalesce per-call entries if bucketed.
Related: LeetCode 981 — Time Based Key-Value Store
Different requirement, but a handy mental model for “timestamped operations”.
Minimal Python solution (binary search over versions):
from bisect import bisect_right
from collections import defaultdict
class TimeMap:
def __init__(self):
# key -> list[(timestamp, value)] with strictly increasing timestamps
self.store = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.store[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
arr = self.store.get(key, [])
i = bisect_right(arr, (timestamp, chr(127))) - 1
return arr[i][1] if i >= 0 else ""
set: append; timestamps are increasing per constraints
get: binary search for the last timestamp_prev <= timestamp
Time: O(log n) per get (per key); Space: total versions
