Pinterest Software Engineer Phone Screen Questions

The introduction then asked about the CAP theorem. It seems to confirm that with Partition Tolerance (P), we cannot have both Control (C) and Availability (A). I hadn't carefully reviewed the CAP part

Recently had a phone screen with Pinterest for an L14 SWE 2 position. Got the following question: https://leetcode.com/problems/count-subarrays-with-score-less-than-k/description/ Initially brute forced the solution, interviewer asked on ways to optimize. Proposed a solution...

I gave my Pinterest onsite interview on June 30 and it ended up in reject. Phone screen: https://leetcode.com/discuss/interview-question/2133879/pinterest-phone-screen-usa/1475896 Each interview length is about 45 minutes except the system design which was about...

## Problem Given an expression or set of numbers, determine whether a target value can be reached through algebraic operations. ## Tags math, dynamic_programming, recursion

## Round 1 - Coding ## Problem A group of friends shared expenses during a trip. Given a list of payments (who paid, how much, for whom), compute the minimum number of transactions to settle all debts. ```python def min_transfers(transactions: list[tuple[str, str, float]]) -> list[tuple[str, str, float]]: # transactions[i] = (payer, beneficiary, amount) # Returns: list of (from, to, amount) settlement transfers # Minimize the number of transfers ... ``` ``` Example: transactions = [ ("Alice", "Bob", 30), ("Alice", "Carol", 20), ("Bob", "Carol", 10), ] # Net balances: Alice=+50, Bob=-20, Carol=-30 # Settlement: # Bob -> Alice: 20 # Carol -> Alice: 30 min_transfers(transactions) -> [ ("Bob", "Alice", 20), ("Carol", "Alice", 30) ] ``` ## Follow-ups 1. Can you settle with fewer transactions by finding a chain (A owes B who owes C -> A pays C directly)? 2. What if amounts must be rounded to cents - how does that affect correctness? 3. Is the minimum-transfer problem NP-hard in the general case? When is a greedy approach optimal? 4. How would you handle a currency conversion requirement between friends in different countries?

## Round 1 - Coding / OOD ## Problem Design a system that models Pinterest boards and pins. Users can create boards, add pins to boards, and search pins by keyword. ```python class Pin: def __init__(self, pin_id: int, title: str, url: str, tags: list[str]): ... class Board: def __init__(self, board_id: int, name: str, owner: str): ... def add_pin(self, pin: Pin) -> None: ... def remove_pin(self, pin_id: int) -> None: ... def get_pins(self) -> list[Pin]: ... class PinSystem: def create_board(self, name: str, owner: str) -> Board: ... def save_pin(self, board_id: int, pin: Pin) -> None: ... def search(self, keyword: str) -> list[Pin]: ... def get_boards_for_user(self, user: str) -> list[Board]: ... ``` ``` Example: sys = PinSystem() b = sys.create_board("Recipes", "alice") p = Pin(1, "Pasta Carbonara", "http://...", ["pasta", "italian"]) sys.save_pin(b.board_id, p) sys.search("italian") -> [Pin(1, ...)] ``` ## Follow-ups 1. How would you index pins for fast keyword search at millions of pins? 2. A pin can be saved to multiple boards - how does your data model handle this? 3. How would you implement a "recommended pins" feature based on a board's existing pins? 4. How would you paginate results from `get_pins` and `search`?

## Round 1 - Coding ## Problem Given a set of candidates, each represented as a point in N-dimensional space, a candidate A *dominates* candidate B if A is strictly better than B in every dimension. Return the count of candidates that are not dominated by any other candidate (the Pareto front). ```python def count_non_dominated(candidates: list[list[int]]) -> int: # candidates[i] = list of scores in each dimension (higher is better) # A dominates B if A[d] > B[d] for ALL dimensions d # Return count of candidates not dominated by any other ... ``` ``` Example: candidates = [ [3, 1], # C0 [1, 3], # C1 [2, 2], # C2 [1, 1], # C3 ] # C0 dominates C3 (3>1 and 1>1? No - tie on dim 1) # Strictly: C2 dominates C3 (2>1 and 2>1) # C0, C1, C2 are non-dominated count_non_dominated(candidates) -> 3 ``` ## Follow-ups 1. What is your time complexity for 2D vs N-dimensional inputs? 2. In 2D, can you solve this in O(n log n)? Describe the approach. 3. How would you return the actual non-dominated set, not just the count? 4. How does the definition change if "better" means lower score (minimization)?

## Problem Count pixels connected to a target cell in a 2D grid, equivalent to a flood fill or island counting problem. ## Likely LeetCode equivalent LC 733 - flood-fill ## Tags graph, matrix, recursion

## Round 1 - Coding ## Problem You receive a stream of user engagement events, each with a user ID, event type, and timestamp. Given a list of queries, each asking for the total engagement count for a user within a time range, answer all queries efficiently. ```python def count_engagements( events: list[tuple[str, str, int]], # (user_id, event_type, timestamp) queries: list[tuple[str, int, int]] # (user_id, start_time, end_time) ) -> list[int]: # For each query, return count of events for that user in [start, end] ... ``` ``` Example: events = [ ("u1", "click", 10), ("u1", "view", 15), ("u2", "click", 12), ("u1", "like", 20), ] queries = [ ("u1", 10, 16), # -> 2 (click + view) ("u1", 10, 25), # -> 3 (all) ("u2", 0, 20), # -> 1 ] count_engagements(events, queries) -> [2, 3, 1] ``` ## Follow-ups 1. What data structure gives O(log n) per query after preprocessing? 2. How would you handle 10M events per day - batch vs. streaming approaches? 3. What if queries also filter by event type? 4. How would you handle out-of-order event arrivals in a real-time system?

## Problem Compute the minimum time to serve all customers given service rates and queue constraints. ## Tags heap, greedy, sorting

## Problem Implement a queue where elements become available only after a specified delay, supporting enqueue and dequeue operations. ## Tags queue, heap

## Problem Group duplicate elements in a collection and return them clustered together or counted by frequency. ## Tags hash_table, arrays, sorting

## Round 1 - Coding / OOD ## Problem Design an elevator controller for a building with `n` floors and `k` elevators. Requests arrive as `(floor, direction)` pairs. Implement a scheduling policy that minimizes average wait time. ```python class ElevatorState: current_floor: int direction: str # "UP", "DOWN", or "IDLE" stops: list[int] class ElevatorController: def __init__(self, num_floors: int, num_elevators: int): ... def request(self, floor: int, direction: str) -> None: # Called when a user presses the UP or DOWN button ... def step(self) -> None: # Advance simulation by one time unit ... def get_states(self) -> list[ElevatorState]: ... ``` ``` Example: ctrl = ElevatorController(num_floors=10, num_elevators=2) ctrl.request(floor=3, direction="UP") ctrl.request(floor=7, direction="DOWN") ctrl.step() # elevator 0 moves toward floor 3 ctrl.get_states() -> [ElevatorState(floor=1, dir="UP", stops=[3]), ...] ``` ## Follow-ups 1. Describe the SCAN (elevator) algorithm. What are its weaknesses? 2. How would you handle a destination-dispatch system where users input the target floor before boarding? 3. How would you model peak-hour load (e.g. morning rush to floor 1)? 4. How does adding priority (e.g. freight elevator) change your design?

## Problem Given a list of strings and a prefix, find the first string that starts with the given prefix. ## Tags strings, arrays

## Round 1 - Coding ## Problem Advertisers are restricted to serve ads only in certain geographic regions. Each region is defined as a rectangle on a 2D coordinate grid. Given a user's location and a list of advertisers with their allowed regions, return the IDs of advertisers eligible to serve an ad to that user. ```python def eligible_advertisers( user_location: tuple[float, float], advertisers: list[dict] ) -> list[int]: # advertisers[i] = { # "id": int, # "regions": list of (x1, y1, x2, y2) rectangles (inclusive bounds) # } # user_location = (x, y) # Return sorted list of advertiser IDs whose regions contain the user ... ``` ``` Example: user_location = (3.0, 4.0) advertisers = [ {"id": 1, "regions": [(0,0,5,5), (10,10,20,20)]}, {"id": 2, "regions": [(4,4,8,8)]}, {"id": 3, "regions": [(1,1,3,3)]}, ] # User (3,4): inside advertiser 1's first region; not in 2 or 3 eligible_advertisers(user_location, advertisers) -> [1] ``` ## Follow-ups 1. How would you speed up queries if there are 1M advertisers and 10K user location queries per second? 2. What spatial indexing structures would you consider (R-tree, grid bucketing)? 3. How do you handle non-rectangular regions (e.g. polygons or radius-based circles)? 4. How would you make the system respect geo-blocking at country/state level?

## Round 1 - Coding ## Problem You are given a grid representing a hiking map. Each cell has an elevation value. You start at the top-left corner and want to reach the bottom-right corner. You can move up, down, left, or right. Find the path that minimizes the maximum elevation change between any two consecutive steps. ```python def hiking_trail(grid: list[list[int]]) -> int: # grid[i][j] = elevation at cell (i, j) # Return the minimum possible value of: # max |elevation[step_k] - elevation[step_k+1]| over all steps in path ... ``` ``` Example: grid = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] # Path: (0,0)->1, (0,1)->2, (0,2)->3, (1,2)->6, (2,2)->9 # Max step diff: max(1,1,3,3) = 3 # Optimal path minimizes this. Answer: hiking_trail(grid) -> 1 # via zigzag path with all diffs = 1 ``` ## Follow-ups 1. Is BFS or Dijkstra more appropriate here? Why? 2. Can binary search on the answer help? How would you combine it with BFS? 3. How does the problem change if you want to minimize total elevation gain (sum) rather than max step? 4. How would you handle a grid with impassable cells?

## Round 1 - Coding ## Problem Implement a hyperparameter grid search generator. Given a dictionary mapping parameter names to lists of possible values, generate all possible combinations in a deterministic order. ```python def generate_configs( param_grid: dict[str, list] ) -> list[dict]: # Returns all combinations of hyperparameter values # Order: iterate last key fastest (lexicographic of keys) ... ``` ``` Example: param_grid = { "lr": [0.01, 0.1], "batch_size": [32, 64], "dropout": [0.1] } generate_configs(param_grid) -> [ {"lr": 0.01, "batch_size": 32, "dropout": 0.1}, {"lr": 0.01, "batch_size": 64, "dropout": 0.1}, {"lr": 0.1, "batch_size": 32, "dropout": 0.1}, {"lr": 0.1, "batch_size": 64, "dropout": 0.1}, ] ``` **Extension:** Implement early stopping - accept a `budget: int` and return only the first `budget` configs from a random shuffle. ```python def generate_random_configs( param_grid: dict[str, list], budget: int, seed: int = 42 ) -> list[dict]: ... ``` ## Follow-ups 1. How would you implement this as a generator (lazy evaluation) to handle huge grids? 2. What is the total config count given the example above? How do you compute it without generating all configs? 3. How does random search compare to grid search statistically? 4. How would you add support for conditional parameters (e.g. `num_layers` only applies if `model_type == "deep"`)?

## Round 1 - Coding ## Problem Design a keyword alerting system. Users register alert rules specifying a keyword and a callback. As text messages stream in, fire all matching callbacks. ```python class KeywordAlert: def register( self, keyword: str, callback: callable, case_sensitive: bool = False ) -> int: # Returns rule_id ... def unregister(self, rule_id: int) -> bool: ... def process(self, message: str) -> int: # Fire callbacks for all matching rules # Returns count of rules triggered ... ``` ``` Example: alert = KeywordAlert() alert.register("error", lambda m: print(f"ALERT: {m}")) alert.register("ERROR", lambda m: print(f"STRICT: {m}"), case_sensitive=True) alert.process("System error detected") # fires rule 1 only -> 1 alert.process("ERROR in module") # fires rule 1 and rule 2 -> 2 alert.process("All clear") # fires nothing -> 0 ``` ## Follow-ups 1. How would you handle multi-keyword rules (e.g. alert if message contains BOTH "error" AND "critical")? 2. What data structure enables O(1) average keyword lookup vs. O(k) scan of all rules? 3. How would you scale this to 100K concurrent alert rules? 4. How would you add rate limiting so a single rule fires at most once per minute?

## Round 1 - Coding ## Problem Implement an in-memory API routing engine. You register URL patterns (which may include path parameters like `/user/{id}`) and handler functions. Given an incoming request path, resolve it to the correct handler and extract path parameters. ```python class Router: def add_route( self, method: str, pattern: str, handler: callable ) -> None: # pattern can include {param} placeholders ... def resolve( self, method: str, path: str ) -> tuple[callable, dict[str, str]]: # Returns (handler, extracted_params) # Raises KeyError if no match ... ``` ``` Example: r = Router() r.add_route("GET", "/users/{id}", get_user) r.add_route("POST", "/users", create_user) r.add_route("GET", "/users/{id}/posts/{pid}", get_post) r.resolve("GET", "/users/42") -> (get_user, {"id": "42"}) r.resolve("GET", "/users/42/posts/7") -> (get_post, {"id": "42", "pid": "7"}) r.resolve("POST", "/users") -> (create_user, {}) ``` ## Follow-ups 1. How do you handle route conflicts (e.g. `/users/new` vs `/users/{id}`)? 2. What data structure (trie vs. list) works best for large route tables? 3. How would you add wildcard routes (e.g. `/static/*filepath`)? 4. How do you handle optional path segments?

## Problem Maximize profit from stock prices or transactions by choosing optimal buy/sell times. ## Likely LeetCode equivalent LC 122 - best-time-to-buy-and-sell-stock-ii ## Tags dynamic_programming, greedy, arrays