The Stripe video platform is built on Jupyter. Requests are routed through multiple Jupyter servers; different developers are pinned to different servers based on load.
Implement route_request that accepts requests and routes them.
- Part 1: Basic load balancing. For each incoming request, route to the server with the smallest active-request count. Tie → smaller index.
- Part 2: Disconnection. Handle
CONNECTandDISCONNECTactions; rebalance correctly when a connection drops. - Part 3: Sticky session by object id. Subsequent requests for the same object id route to the same server, unless that server is unhealthy.
- Part 4:
maxConnectionsPerTargetcap. When a target hits its cap, evict the least-recently-used object on that target. - Part 5:
SHUTDOWN. When a target shuts down, re-route its evicted connections.
Working with 2 targets and high maxConnectionsPerTarget:
CONNECT, conn1, userA, obj1
CONNECT, conn2, userB, obj2
SHUTDOWN, 1
CONNECT, conn3, userC, obj3
→ conn1 userA 2, conn2 userB 2, conn1 userA 2, conn3 userC 1解法
状态：每目标负载计数、每目标对象 LRU 表、obj_id → target 黏性映射、健康标记。route 读黏性映射(缺失或不健康时选负载最低的目标)，更新 LRU，超容量时驱逐。disconnect 减负载。shutdown 翻健康标记，返回被驱逐的连接以重新路由。每次操作 O(n)，n 为目标数(一般很小)。
from collections import OrderedDict, defaultdict
class LoadBalancer:
def __init__(self, n_servers, max_per_target=float('inf')):
self.n = n_servers
self.loads = [0] * n_servers
self.connections = defaultdict(set)
self.obj_target = {}
self.target_lru = [OrderedDict() for _ in range(n_servers)]
self.max_per_target = max_per_target
self.healthy = [True] * n_servers
def _pick(self):
best = (float('inf'), -1)
for i in range(self.n):
if self.healthy[i] and self.loads[i] < best[0]:
best = (self.loads[i], i)
return best[1]
def route(self, conn_id, user, obj_id):
target = self.obj_target.get(obj_id)
if target is None or not self.healthy[target]:
target = self._pick()
self.obj_target[obj_id] = target
lru = self.target_lru[target]
if obj_id in lru:
lru.move_to_end(obj_id)
elif len(lru) >= self.max_per_target:
evicted = next(iter(lru))
del lru[evicted]
lru[obj_id] = True
self.connections[target].add(conn_id)
self.loads[target] += 1
return target
def disconnect(self, conn_id, target):
if conn_id in self.connections[target]:
self.connections[target].remove(conn_id)
self.loads[target] -= 1
def shutdown(self, target):
self.healthy[target] = False
evicted = list(self.connections[target])
self.connections[target].clear()
self.loads[target] = 0
return evictedclass LoadBalancer {
int n, maxPerTarget;
int[] loads;
boolean[] healthy;
Map<Integer, Set<String>> connections = new HashMap<>();
Map<String, Integer> objTarget = new HashMap<>();
List<LinkedHashMap<String, Boolean>> targetLRU;
LoadBalancer(int n, int maxPerTarget) {
this.n = n; this.maxPerTarget = maxPerTarget;
loads = new int[n]; healthy = new boolean[n];
targetLRU = new ArrayList<>();
for (int i = 0; i < n; i++) {
healthy[i] = true;
connections.put(i, new HashSet<>());
targetLRU.add(new LinkedHashMap<>());
}
}
int pick() {
int best = -1, bestLoad = Integer.MAX_VALUE;
for (int i = 0; i < n; i++)
if (healthy[i] && loads[i] < bestLoad) { bestLoad = loads[i]; best = i; }
return best;
}
int route(String connId, String user, String objId) {
Integer target = objTarget.get(objId);
if (target == null || !healthy[target]) {
target = pick();
objTarget.put(objId, target);
}
LinkedHashMap<String, Boolean> lru = targetLRU.get(target);
if (lru.containsKey(objId)) lru.remove(objId);
else if (lru.size() >= maxPerTarget) lru.remove(lru.keySet().iterator().next());
lru.put(objId, true);
connections.get(target).add(connId);
loads[target]++;
return target;
}
void disconnect(String connId, int target) {
if (connections.get(target).remove(connId)) loads[target]--;
}
List<String> shutdown(int target) {
healthy[target] = false;
List<String> evicted = new ArrayList<>(connections.get(target));
connections.get(target).clear();
loads[target] = 0;
return evicted;
}
}class LoadBalancer {
public:
int n; size_t maxPerTarget;
vector<int> loads;
vector<bool> healthy;
vector<unordered_set<string>> connections;
unordered_map<string, int> objTarget;
vector<list<string>> targetOrder;
vector<unordered_map<string, list<string>::iterator>> targetIndex;
LoadBalancer(int nServers, size_t maxPerTgt = SIZE_MAX)
: n(nServers), maxPerTarget(maxPerTgt), loads(nServers, 0),
healthy(nServers, true), connections(nServers),
targetOrder(nServers), targetIndex(nServers) {}
int pick() {
int best = -1, bestLoad = INT_MAX;
for (int i = 0; i < n; ++i)
if (healthy[i] && loads[i] < bestLoad) { bestLoad = loads[i]; best = i; }
return best;
}
int route(const string& connId, const string&, const string& objId) {
int target;
auto it = objTarget.find(objId);
if (it == objTarget.end() || !healthy[it->second]) {
target = pick();
objTarget[objId] = target;
} else target = it->second;
auto& order = targetOrder[target];
auto& idx = targetIndex[target];
if (idx.count(objId)) { order.erase(idx[objId]); }
else if (order.size() >= maxPerTarget) {
idx.erase(order.front());
order.pop_front();
}
order.push_back(objId);
idx[objId] = prev(order.end());
connections[target].insert(connId);
loads[target]++;
return target;
}
void disconnect(const string& connId, int target) {
if (connections[target].erase(connId)) loads[target]--;
}
vector<string> shutdown(int target) {
healthy[target] = false;
vector<string> evicted(connections[target].begin(), connections[target].end());
connections[target].clear();
loads[target] = 0;
return evicted;
}
};Given transactions_list, merchants_list, rules_list. Initialize each merchant's current_score = base_score. Apply rules in separate passes:
- If
transaction.amount > rule.min_transaction_amount, multiply the merchant's score byrule.multiplicative_factor. - If the same
customer_idhas made ≥ 3 transactions at this merchant (including the current one), add each matching rule'sadditive_factorto the merchant. - If a transaction is the 3rd-or-later from the same customer at the same merchant within the same hour:
- hour in
[12, 17]: addpenalty_each_time(also retroactively for the 1st and 2nd in the hour). - hour in
[9, 11]or[18, 21]: subtractpenalty_each_time. - else: no change.
Return comma-separated "merchant_id,score" strings in lexicographic merchant order.
解法
对交易三次独立扫描，依次更新商户分数。第 2 步用 (merchant, customer) 计数器跟终身交易，第 3 步用 (merchant, customer, hour) 跟小时交易。总复杂度 O(T · R)，T 为交易数、R 为规则数。
from collections import defaultdict
def merchant_score(transactions, merchants, rules):
score = {m["id"]: m["base_score"] for m in merchants}
for t in transactions:
for r in rules:
if t["amount"] > r["min_transaction_amount"]:
score[t["merchant_id"]] *= r["multiplicative_factor"]
customer_count = defaultdict(int)
for t in transactions:
customer_count[(t["merchant_id"], t["customer_id"])] += 1
if customer_count[(t["merchant_id"], t["customer_id"])] >= 3:
for r in rules:
score[t["merchant_id"]] += r["additive_factor"]
hour_count = defaultdict(int)
for t in transactions:
h = t["hour"]
hour_count[(t["merchant_id"], t["customer_id"], h)] += 1
if hour_count[(t["merchant_id"], t["customer_id"], h)] >= 3:
for r in rules:
p = r["penalty_each_time"]
if 12 <= h <= 17: score[t["merchant_id"]] += p
elif (9 <= h <= 11) or (18 <= h <= 21): score[t["merchant_id"]] -= p
return [f"{m},{score[m]}" for m in sorted(score)]class Solution {
static List<String> merchantScore(List<Map<String, Object>> transactions,
List<Map<String, Object>> merchants,
List<Map<String, Object>> rules) {
Map<String, Double> score = new TreeMap<>();
for (var m : merchants) score.put((String) m.get("id"), ((Number) m.get("base_score")).doubleValue());
for (var t : transactions) {
double amt = ((Number) t.get("amount")).doubleValue();
String mid = (String) t.get("merchant_id");
for (var r : rules)
if (amt > ((Number) r.get("min_transaction_amount")).doubleValue())
score.merge(mid, ((Number) r.get("multiplicative_factor")).doubleValue(), (a, b) -> a * b);
}
Map<String, Integer> ccount = new HashMap<>();
for (var t : transactions) {
String key = t.get("merchant_id") + "|" + t.get("customer_id");
int c = ccount.merge(key, 1, Integer::sum);
if (c >= 3) {
String mid = (String) t.get("merchant_id");
for (var r : rules)
score.merge(mid, ((Number) r.get("additive_factor")).doubleValue(), Double::sum);
}
}
Map<String, Integer> hcount = new HashMap<>();
for (var t : transactions) {
int h = ((Number) t.get("hour")).intValue();
String key = t.get("merchant_id") + "|" + t.get("customer_id") + "|" + h;
int c = hcount.merge(key, 1, Integer::sum);
if (c >= 3) {
String mid = (String) t.get("merchant_id");
for (var r : rules) {
double p = ((Number) r.get("penalty_each_time")).doubleValue();
if (h >= 12 && h <= 17) score.merge(mid, p, Double::sum);
else if ((h >= 9 && h <= 11) || (h >= 18 && h <= 21)) score.merge(mid, -p, Double::sum);
}
}
}
List<String> out = new ArrayList<>();
for (var e : score.entrySet()) out.add(e.getKey() + "," + e.getValue());
return out;
}
}// Pseudo-C++ sketch — actual JSON-typed structs depend on the harness.
struct Transaction { string merchant_id, customer_id; double amount; int hour; };
struct Merchant { string id; double base_score; };
struct Rule { double min_transaction_amount, multiplicative_factor, additive_factor, penalty_each_time; };
vector<string> merchantScore(vector<Transaction>& transactions,
vector<Merchant>& merchants,
vector<Rule>& rules) {
map<string, double> score;
for (auto& m : merchants) score[m.id] = m.base_score;
for (auto& t : transactions)
for (auto& r : rules)
if (t.amount > r.min_transaction_amount) score[t.merchant_id] *= r.multiplicative_factor;
map<pair<string, string>, int> ccount;
for (auto& t : transactions) {
if (++ccount[{t.merchant_id, t.customer_id}] >= 3)
for (auto& r : rules) score[t.merchant_id] += r.additive_factor;
}
map<tuple<string, string, int>, int> hcount;
for (auto& t : transactions) {
if (++hcount[{t.merchant_id, t.customer_id, t.hour}] >= 3) {
for (auto& r : rules) {
double p = r.penalty_each_time;
if (t.hour >= 12 && t.hour <= 17) score[t.merchant_id] += p;
else if ((t.hour >= 9 && t.hour <= 11) || (t.hour >= 18 && t.hour <= 21))
score[t.merchant_id] -= p;
}
}
}
vector<string> out;
for (auto& [m, s] : score) out.push_back(m + "," + to_string(s));
return out;
}Stripe Risk groups merchants based on shared link attributes. Given day1, day2, day3 batches of (merchant_id, link_type, link_duration, day) tuples, output per-day clusters.
Clustering rules. Two merchants are connected if they share an active link of the same link_type. A cluster is a connected component over active links.
Pinning rules. Each cluster has a pin = the merchant with the highest degree (ties → smallest merchant_id). When clusters merge, the new pin is the highest-degree merchant in the merged cluster. When removing an expired link splits a cluster, each sub-cluster gets its own pin.
For each day output "Day X" followed by the day's clusters in descending member count (ties → pin name ascending).
解法
对每一天枚举当天活跃的 link(day_added ≤ day < day_added + duration)，按 link_type 建无向图，BFS 找连通块，取度最大的点作为 pin。逐日重算而非增量维护——OA 规模下 O((N + E) · D) 可接受。
from collections import defaultdict, deque
def cluster_days(batches):
edges = []
out = []
for day, batch in enumerate(batches, 1):
for u, link_type, dur, _ in batch:
edges.append((u, link_type, day + dur, day))
active = [e for e in edges if e[3] <= day < e[2]]
g = defaultdict(set)
link_groups = defaultdict(list)
for u, lt, _, _ in active:
link_groups[lt].append(u)
for members in link_groups.values():
for i in range(len(members)):
for j in range(i + 1, len(members)):
g[members[i]].add(members[j])
g[members[j]].add(members[i])
visited = set()
clusters = []
for node in g:
if node in visited: continue
comp = []
dq = deque([node])
visited.add(node)
while dq:
u = dq.popleft()
comp.append(u)
for v in g[u]:
if v not in visited:
visited.add(v); dq.append(v)
deg = {u: len(g[u]) for u in comp}
pin = max(comp, key=lambda x: (deg[x], -ord(str(x)[0]) if isinstance(x, str) else 0))
clusters.append((len(comp), pin, comp))
clusters.sort(key=lambda x: (-x[0], x[1]))
out.append(f"Day {day}")
out.extend(f" cluster size={c[0]} pin={c[1]}" for c in clusters)
return out