Notion Software Engineer Phone Screen Questions

## Round 1 - Coding ## Problem Implement a backend for a multi-room chat service. Users can join rooms, send messages, and fetch message history. Each message has a sender, timestamp, and content. ```python from datetime import datetime class ChatService: def create_room(self, room_id: str) -> None: ... def join_room(self, user_id: str, room_id: str) -> bool: ... def send_message(self, user_id: str, room_id: str, content: str) -> dict: # returns message dict with auto-generated timestamp ... def get_history(self, room_id: str, limit: int = 50, before_ts: datetime = None) -> list[dict]: ... def active_users(self, room_id: str) -> list[str]: ... ``` ## Example ``` chat = ChatService() chat.create_room("general") chat.join_room("alice", "general") chat.join_room("bob", "general") chat.send_message("alice", "general", "Hello!") # -> {"id": "uuid", "sender": "alice", "content": "Hello!", "ts": ...} chat.get_history("general", limit=10) # -> [{"sender":"alice","content":"Hello!","ts":...}] chat.active_users("general") -> ["alice", "bob"] ``` ## Follow-ups 1. How would you implement `get_history` with cursor-based pagination for efficient scrolling? 2. How do you handle a user sending a message to a room they haven't joined? 3. How would you push new messages to connected clients in real time (WebSockets vs. SSE vs. long polling)? 4. How do you design the data model if rooms can have thousands of messages and you need fast lookups by time range?

## Problem Design a document store supporting create, read, update, and delete operations with potentially hierarchical document structures. ## Likely LeetCode equivalent No direct equivalent. ## Tags database,design,hash_table,swe

## Round 1 - Coding / SQL ## Problem Build an in-memory database that stores records as key-value rows with typed fields. Support inserting records, querying by field values, updating, and deleting — all through a simple API that mirrors SQL semantics. ```python class InlineDB: def __init__(self): ... def insert(self, table: str, record: dict) -> int: # returns row_id ... def select(self, table: str, where: dict = None, columns: list[str] = None) -> list[dict]: # where: {field: value} — equality filter ... def update(self, table: str, where: dict, new_values: dict) -> int: # returns count of updated rows ... def delete(self, table: str, where: dict) -> int: # returns count of deleted rows ... def count(self, table: str, where: dict = None) -> int: ... ``` ## Example ``` db = InlineDB() db.insert("users", {"name": "Alice", "age": 30, "active": True}) db.insert("users", {"name": "Bob", "age": 25, "active": False}) db.select("users", where={"active": True}, columns=["name","age"]) # -> [{"name":"Alice","age":30}] db.update("users", where={"name":"Bob"}, new_values={"active":True}) db.count("users", where={"active":True}) -> 2 db.delete("users", where={"name":"Alice"}) -> 1 ``` ## Follow-ups 1. How would you add an index on a specific field to make `select` lookups O(1) instead of O(N)? 2. How do you support compound WHERE conditions like `age > 25 AND active = True`? 3. How would you implement transactions so a sequence of inserts/updates is atomic? 4. How do you handle schema enforcement — rejecting records that are missing required fields?

## Problem You are given an arbitrary JSON object (potentially deeply nested) and asked to render it as an interactive, collapsible tree in the browser — similar to Chrome DevTools' JSON viewer. ```js // Signature function renderJSON(container, data) { // container: HTMLElement to mount into // data: any valid JSON value (object, array, primitive) } ``` **Example input:** ```json {"user": {"id": 1, "tags": ["admin", "beta"]}, "active": true} ``` **Expected rendered output (collapsed):** ``` > user: {2 keys} active: true ``` Expanding `user` reveals `id: 1` and `> tags: [2 items]`. ## Follow-ups 1. How do you handle circular references in the JSON object without crashing? 2. What changes are needed to support syntax highlighting (strings vs numbers vs booleans)? 3. How would you make deeply nested paths copyable to the clipboard on click? 4. If the JSON blob is 50 MB, how do you avoid blocking the main thread during render?

## Problem Design the core data structure and merge logic for a collaborative plain-text editor. Two users can edit the same document concurrently; your system must merge their changes without data loss. ```python class Document: def __init__(self, text: str): ... def apply(self, op: 'Operation') -> 'Document': ... def transform(self, op: 'Operation', against: 'Operation') -> 'Operation': ... class Operation: # Sequence of: retain(n), insert(s), delete(n) def __init__(self, ops: list): ... ``` **Example:** ``` Base: "hello" Alice: insert " world" at index 5 -> "hello world" Bob: delete "h" at index 0 -> "ello" Merged result: "ello world" ``` ## Follow-ups 1. What invariant must hold between `base_length` and `target_length` for two operations to be composable? 2. How does your transform handle the case where both users delete the same character? 3. Why might CRDTs be preferred over OT for a distributed system with no central server? 4. How would you checkpoint document history to allow undo across sessions?

## Problem Implement a role-based access control (RBAC) system where roles can inherit permissions from parent roles. Given a user's assigned roles, determine whether they are authorized for a given action on a resource. ```python class RBACSystem: def add_role(self, role: str, parent: str = None) -> None: ... def grant(self, role: str, action: str, resource: str) -> None: ... def assign_role(self, user_id: str, role: str) -> None: ... def can(self, user_id: str, action: str, resource: str) -> bool: ... ``` **Example:** ``` add_role("editor", parent="viewer") grant("viewer", "read", "article") grant("editor", "write", "article") assign_role("alice", "editor") can("alice", "read", "article") -> True (inherited) can("alice", "delete", "article") -> False ``` ## Follow-ups 1. How do you detect and prevent circular role inheritance? 2. If a user has two roles and one explicitly denies an action, should deny override allow? 3. How would you support resource wildcards, e.g. `can(user, "read", "article:*")`? 4. How would you audit all permissions a user has at a given point in time?

## Problem Given a table of sales records, write a function that computes aggregated metrics grouped by one or more columns. The function must support arbitrary grouping keys and multiple aggregation functions (sum, avg, count, min, max) simultaneously. ```python def aggregate(rows: list[dict], group_by: list[str], agg: dict[str, str]) -> list[dict]: # rows: list of flat dicts with string keys # group_by: columns to group on, e.g. ["region", "product"] # agg: {output_col: "sum(revenue)" | "avg(quantity)" | ...} # returns: list of result dicts, one per group pass ``` **Example:** ``` Input rows: [{"region": "US", "product": "A", "revenue": 100}, ...] aggregate(rows, ["region"], {"total": "sum(revenue)", "avg_rev": "avg(revenue)"}) Output: [{"region": "US", "total": 350, "avg_rev": 116.67}, ...] ``` ## Follow-ups 1. How does your implementation scale when rows exceed available memory? 2. How would you add a `HAVING` filter (e.g., only groups where total > 1000)? 3. Can you support window functions like running totals within each group? 4. How would you parallelize the aggregation across CPU cores?

## Problem You are building a project management UI. Implement a `TaskRow` component that displays a single task, supports inline title editing on double-click, and cycles through statuses (Todo -> In Progress -> Done -> Todo) on a button click. ```tsx // React / TypeScript type Status = 'todo' | 'in_progress' | 'done'; interface TaskRowProps { task: { id: string; title: string; status: Status }; onUpdate: (id: string, patch: Partial<{ title: string; status: Status }>) -> void; } export function TaskRow({ task, onUpdate }: TaskRowProps) { ... } ``` **Requirements:** Editing commits on blur or Enter; Escape cancels. Status badge color changes with state. ## Follow-ups 1. How do you prevent accidental edits when a user single-clicks to select text? 2. If 1000 task rows are rendered, what optimizations prevent sluggish re-renders? 3. How would you add an animated transition when the status changes? 4. How would you test that Escape correctly discards unsaved edits?