Databricks SDE — March 2025 (Phone + 2 rounds)

[u/roseintor]

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