Algorithm Design and Analysis Questions

import redis
import time

# Redis client (configure connection pool in real deploy)
r = redis.Redis(host='localhost', port=6379, db=0)

# Parameters
CAPACITY = 100.0
RATE = 10.0  # tokens per second

# Lua script: KEYS[1]=user_key, ARGV[1]=now, ARGV[2]=cost, ARGV[3]=capacity, ARGV[4]=rate
TOKEN_BUCKET_LUA = """
local key = KEYS[1]
local now = tonumber(ARGV[1])
local cost = tonumber(ARGV[2])
local capacity = tonumber(ARGV[3])
local rate = tonumber(ARGV[4])

local v = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(v[1]) or capacity
local ts = tonumber(v[2]) or now

-- refill
local elapsed = math.max(0, now - ts)
tokens = math.min(capacity, tokens + elapsed * rate)
if tokens < cost then
  -- not allowed; persist current state and return 0
  redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
  -- optional TTL to free memory for inactive users
  redis.call('EXPIRE', key, 3600)
  return 0
else
  tokens = tokens - cost
  redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
  redis.call('EXPIRE', key, 3600)
  return 1
end
"""

token_bucket_sha = r.script_load(TOKEN_BUCKET_LUA)

def allow_request(user_id: str, timestamp: float = None) -> bool:
    now = timestamp if timestamp is not None else time.time()
    key = f"bucket:{user_id}"
    allowed = r.evalsha(token_bucket_sha, 1, key, str(now), "1", str(CAPACITY), str(RATE))
    return bool(allowed)

from collections import defaultdict, deque

def topo_sort(services, edges, soft_edges=set()):
    # services: iterable of service names
    # edges: list of (A, B) meaning A depends on B (hard)
    # soft_edges: set of (A, B) meaning soft dependency
    deps = defaultdict(set)        # A -> set of B (hard)
    rev = defaultdict(set)         # B -> set of A
    indeg = defaultdict(int)
    for s in services:
        indeg[s] = 0
    for a,b in edges:
        deps[a].add(b); rev[b].add(a); indeg[a]+=1
    q = deque([s for s in services if indeg[s]==0])
    order = []
    while q:
        s = q.popleft()
        order.append(s)
        for dependent in list(rev[s]):
            indeg[dependent]-=1
            if indeg[dependent]==0:
                q.append(dependent)
    if len(order)!=len(services):
        # cycle detected: run DFS to extract cycles
        return None, find_cycles(services, deps)
    # annotate soft deps satisfaction
    unsatisfied_soft = []
    deployed = set()
    for s in order:
        for a,b in soft_edges:
            if a==s and b not in deployed:
                unsatisfied_soft.append((a,b))
        deployed.add(s)
    return order, unsatisfied_soft

def find_cycles(services, deps):
    visited, stack, cycles = set(), [], []
    def dfs(u, pathset):
        visited.add(u); pathset.add(u); stack.append(u)
        for v in deps[u]:
            if v not in visited:
                dfs(v, pathset)
            elif v in pathset:
                # record cycle path
                idx = stack.index(v)
                cycles.append(stack[idx:]+[v])
        stack.pop(); pathset.remove(u)
    for s in services:
        if s not in visited:
            dfs(s, set())
    return cycles