Patreon Software Engineer Interview Questions

LeetCode #243: Shortest Word Distance. Difficulty: Easy. Topics: Array, String. Asked at Patreon in the last 6 months.

## Problem Design a caching layer with eviction policies, supporting multi-level or tiered caching using OOD principles. ## Likely LeetCode equivalent LeetCode 146 - LRU Cache. ## Tags hash_table,design,ood,swe

## Problem Implement the Unix 'cd' command for navigating a virtual filesystem, handling relative and absolute paths with '..' and '.' components. ## Likely LeetCode equivalent LeetCode 71 - Simplify Path. ## Tags strings,stack,design,swe

## Round 1 - Coding ## Problem Given a tree (not necessarily binary), where each node has an ID and a list of children, return a list where the `i`-th element is the number of nodes at depth `i` (root is depth 0). ```python class TreeNode: def __init__(self, node_id: int, children: list['TreeNode'] = None): self.node_id = node_id self.children = children or [] def count_per_level(root: TreeNode) -> list[int]: ... ``` ## Example ``` 1 / | \ 2 3 4 /| | 5 6 7 count_per_level(root) # Level 0: [1] -> 1 # Level 1: [2,3,4] -> 3 # Level 2: [5,6,7] -> 3 # -> [1, 3, 3] ``` ## Follow-ups 1. How do you implement this iteratively using a queue versus recursively? What are the trade-offs? 2. How would you extend this to return the sum of node values at each level? 3. Given two trees, how do you find the deepest common level where both trees have the same node count? 4. If the tree has millions of nodes, how do you process it level by level without running out of memory?

## Round 1 - Coding ## Problem Given a list of `(employee_id, manager_id)` pairs representing a company hierarchy, implement queries to find: direct reports, all reports in the subtree, the management chain to the root, and the lowest common manager of two employees. ```python class OrgChart: def __init__(self, reports: list[tuple[int, int]]): # reports: (employee_id, manager_id); root has manager_id = -1 ... def direct_reports(self, emp_id: int) -> list[int]: ... def all_reports(self, emp_id: int) -> list[int]: # entire subtree ... def management_chain(self, emp_id: int) -> list[int]: # emp -> root ... def lowest_common_manager(self, emp1: int, emp2: int) -> int: ... ``` ## Example ``` reports = [(2,1),(3,1),(4,2),(5,2),(6,3)] chart = OrgChart(reports) chart.direct_reports(1) -> [2, 3] chart.all_reports(2) -> [4, 5] chart.management_chain(5) -> [5, 2, 1] chart.lowest_common_manager(4, 6) -> 1 ``` ## Follow-ups 1. What is the time complexity of `lowest_common_manager`? How can you optimize it with preprocessing? 2. How would you handle an employee who reports to multiple managers (matrix org structure)? 3. How do you detect cycles in the reporting structure (e.g., employee A reports to B who reports to A)? 4. How would you store this hierarchy in a relational database and write a recursive CTE to fetch the full subtree?

## Round 1 - Frontend ## Problem Build a Kanban board in React with at least three columns (To Do, In Progress, Done). Cards should be draggable between columns using the HTML5 Drag and Drop API (no external libraries). Each column shows its card count. ```jsx const initialCards = [ { id: 1, title: "Design DB schema", column: "todo" }, { id: 2, title: "Write API endpoints", column: "inprogress" }, { id: 3, title: "Deploy to staging", column: "done" }, ]; function KanbanBoard() { // Your implementation } ``` ## Example ``` Initial state: | To Do (1) | In Progress (1) | Done (1) | | Design DB schema | Write API endpoints | Deploy to staging| User drags "Design DB schema" to "In Progress": | To Do (0) | In Progress (2) | Done (1) | | | Design DB schema | Deploy to staging| | | Write API endpoints | | ``` ## Follow-ups 1. How do you preserve card order within a column when a card is dropped at a specific position? 2. How would you persist board state to `localStorage` so it survives a page refresh? 3. How do you add an "Add Card" form to a column inline, and cancel it with Escape? 4. How would you make the board accessible for keyboard-only users who cannot drag?

## Problem Implement a map with a maximum size limit, evicting entries when the limit is exceeded (likely LRU or LFU eviction policy). ## Likely LeetCode equivalent LeetCode 146 - LRU Cache. ## Tags hash_table,design,frontend,swe

## Round 1 - System Design ## Problem Design a notification feed system for a social platform. Users generate events (likes, comments, follows) that trigger notifications delivered to the relevant users in near-real-time. The system must support: - Generating notifications from events - Delivering them to online users via push and storing them for offline users - Marking notifications as read - Paginating a user's notification feed ## Key Components ``` Event Producers -> Message Queue (Kafka) -> Notification Service | | Push (WebSocket) Storage (DB) | Feed API (paginated) ``` **Schema (abbreviated):** ```sql CREATE TABLE notifications ( id BIGINT PRIMARY KEY, recipient_id BIGINT, actor_id BIGINT, type VARCHAR(50), -- "like", "comment", "follow" entity_id BIGINT, is_read BOOLEAN DEFAULT FALSE, created_at TIMESTAMP ); ``` ## Follow-ups 1. How do you fan out a notification to 10M followers efficiently without blocking the event producer? 2. How do you deduplicate — e.g., a user gets 50 likes in 5 minutes; show "50 people liked your post" not 50 separate notifications. 3. What index strategy enables fast unread-count queries per user? 4. How would you implement notification preferences — a user wants only follow notifications, no likes?

## Round 1 - Coding ## Problem Implement a configurable password generator that produces cryptographically random passwords based on specified rules. Support minimum counts of uppercase, lowercase, digits, and symbols, with a total length constraint. ```python import secrets import string class PasswordGenerator: def __init__(self, length: int = 16, min_upper: int = 1, min_lower: int = 1, min_digits: int = 1, min_symbols: int = 1, allowed_symbols: str = "!@#$%^&*()"): ... def generate(self) -> str: ... def validate(self, password: str) -> bool: ... ``` ## Example ``` gen = PasswordGenerator(length=12, min_upper=2, min_lower=2, min_digits=2, min_symbols=2) pwd = gen.generate() len(pwd) -> 12 gen.validate(pwd) -> True # Validation rules: gen.validate("abc") -> False # too short, no upper/digit/symbol gen.validate("Abc1234!@XYZ") -> True ``` ## Follow-ups 1. Why use `secrets` instead of `random` for password generation? 2. How do you ensure the required character counts are met while keeping the rest of the password uniformly random? 3. How would you add an option to exclude ambiguous characters like `0`, `O`, `l`, `1`, `I`? 4. How would you implement a password strength scorer as a separate method?

## Problem Design a random number generator with a specified probability distribution, possibly using rejection sampling or weighted random selection. ## Likely LeetCode equivalent LeetCode 528 - Random Pick with Weight. ## Tags probability,math,design,swe

## Round 1 - Coding ## Problem Implement a shopping cart pricing engine. Products have base prices. Support: - Quantity-based discounts (buy 3 or more, get 10% off that item) - Promo codes that apply a percentage or fixed dollar discount to the cart total - Free shipping above a subtotal threshold ```python class ShoppingCart: def add_item(self, sku: str, price: float, qty: int) -> None: ... def apply_promo(self, code: str) -> bool: # returns True if code is valid ... def subtotal(self) -> float: ... def discount(self) -> float: ... def shipping(self) -> float: # 0 if subtotal >= free_shipping_threshold, else flat rate ... def total(self) -> float: ... ``` ## Example ``` cart = ShoppingCart(free_shipping_threshold=50, shipping_rate=5.99) cart.add_item("WIDGET", 10.0, 5) # 5 units -> 10% qty discount -> 45.0 cart.add_item("GADGET", 20.0, 1) # 1 unit, no qty discount -> 20.0 cart.subtotal() -> 65.0 cart.apply_promo("SAVE10") # 10% off total cart.discount() -> 6.50 cart.shipping() -> 0.0 # subtotal >= 50 cart.total() -> 58.50 ``` ## Follow-ups 1. How do you apply discounts in the correct order — item discounts before or after promo codes? 2. How do you handle a promo code that is only valid on specific SKUs? 3. What happens if `apply_promo` is called multiple times — can multiple codes stack? 4. How would you serialize the cart state to restore an abandoned cart session?

## Problem Compute the union and intersection of two sets or arrays, returning elements in both or either. ## Likely LeetCode equivalent LeetCode 349 - Intersection of Two Arrays. ## Tags arrays,hash_table,sets,swe

## Problem Find the longest subarray or window containing all unique elements, using a hash set to track uniqueness. ## Likely LeetCode equivalent LeetCode 3 - Longest Substring Without Repeating Characters. ## Tags hash_table,sliding_window,arrays,swe

## Problem Solve a word puzzle (e.g., find valid words in a grid or from a scrambled set of letters) using backtracking and a dictionary. ## Likely LeetCode equivalent LeetCode 79 - Word Search. ## Tags backtracking,strings,graph,swe