Whatnot Software Engineer Phone Screen Questions

## Problem Determine whether a string can become a palindrome by removing at most one character. ## Likely LeetCode equivalent Directly matches Valid Palindrome II (LC 680). ## Tags strings, two_pointers, whatnot

## Problem Given n versions where the first bad version causes all subsequent ones to be bad, find the first bad version using binary search. ## Likely LeetCode equivalent Directly matches First Bad Version (LC 278). ## Tags binary_search, whatnot

## Problem Group a list of strings into anagram clusters, where each cluster contains strings that are anagrams of each other. ## Likely LeetCode equivalent Directly matches Group Anagrams (LC 49). ## Tags hash_table, strings, sorting, whatnot

## Problem Find the K points closest to the origin from a list of 2D coordinates using Euclidean distance. ## Likely LeetCode equivalent Directly matches K Closest Points to Origin (LC 973). ## Tags heap, math, sorting, whatnot

## Problem Search for a target value in a 2D matrix with sorted rows and columns using an efficient traversal. ## Likely LeetCode equivalent Similar to Search a 2D Matrix II (LC 240). ## Tags matrix, binary_search, whatnot

## Problem Find the minimum length substring of a source string that contains all characters of a target string. ## Likely LeetCode equivalent Directly matches Minimum Window Substring (LC 76). ## Tags sliding_window, strings, hash_table, whatnot

## Problem Rate-limit notification delivery, ensuring no more than N notifications are sent within a sliding time window. ## Likely LeetCode equivalent Similar to Design Hit Counter (LC 362) or sliding window rate limiter. ## Tags sliding_window, queue, whatnot, rate_limit

## Problem Count the number of islands (connected groups of 1s) in a 2D binary grid using DFS or BFS. ## Likely LeetCode equivalent Directly matches Number of Islands (LC 200). ## Tags graph, matrix, bfs, dfs, whatnot

## Problem Compute ranking scores for items or users based on weighted criteria and return the top-K ranked results. ## Likely LeetCode equivalent Similar to Top K Frequent Elements (LC 347) with custom scoring. ## Tags heap, sorting, whatnot, ranking

## Problem Compute the dot product of two sparse vectors represented as index-value pairs, efficiently skipping zeros. ## Likely LeetCode equivalent Directly matches Dot Product of Two Sparse Vectors (LC 1570). ## Tags arrays, hash_table, two_pointers, whatnot

## Problem You are given a string and a sequence of transformation rules. Each rule is one of: - `REPLACE a b` — replace all occurrences of `a` with `b` - `REVERSE` — reverse the string - `TRUNCATE n` — keep only the first `n` characters - `REPEAT n` — repeat the string `n` times - `IF len>n THEN rule` — apply `rule` only if current string length > `n` Apply the rules in order and return the final string. ```python def apply_rules(s: str, rules: list[str]) -> str: pass ``` ## Example ``` Input: s = "hello" rules = [ "REPLACE l r", "REVERSE", "IF len>4 THEN TRUNCATE 3", "REPEAT 2" ] Steps: REPLACE l->r: "herro" REVERSE: "orreh" IF len(5)>4: TRUNCATE 3 -> "orr" REPEAT 2: "orrorr" Output: "orrorr" ``` ## Follow-ups 1. How would you add nested conditionals (`IF ... THEN IF ... THEN ...`)? 2. How do you detect rule sequences that could produce exponentially long strings (REPEAT inside a loop)? 3. What parsing technique (recursive descent vs. regex) works best for this grammar?

## Problem Build a content moderation system that flags messages containing unsafe words. Blocklist entries can be: - Exact strings: `"badword"` - Wildcards: `"bad*"` (prefix match) - Phrase patterns: `"buy * now"` (any word in the middle) The filter should be case-insensitive and must not flag safe words that contain the blocked substring (e.g., blocking `"ass"` should not flag `"assistant"`). ```python class ContentFilter: def add_rule(self, pattern: str) -> None: def is_unsafe(self, text: str) -> bool: def get_violations(self, text: str) -> list[str]: # returns matched patterns ``` ## Example ``` filter = ContentFilter() filter.add_rule("spam") filter.add_rule("buy * now") filter.is_unsafe("Buy cheap products now!") -> True # matches "buy * now" filter.is_unsafe("This is spam") -> True filter.is_unsafe("I am not a spammer") -> False # word-boundary safe filter.get_violations("Buy it now or spam") -> ["buy * now", "spam"] ``` ## Follow-ups 1. How do you enforce word-boundary matching efficiently at scale? 2. How would you handle Unicode normalization and leetspeak obfuscation (`sp4m`, `s.p.a.m`)? 3. With 100K rules and 10K messages/second, how do you make this performant (Aho-Corasick, regex compilation)?

## Problem You have a table of user events: `(user_id, event_name, ts)`. A **funnel** is an ordered list of event names that a user must complete in sequence (though non-funnel events may occur in between). For each user, determine whether they completed the funnel and, if so, the time elapsed from the first to last funnel step. ```sql -- events: user_id VARCHAR, event_name VARCHAR, ts TIMESTAMP -- Example funnel: ['view_product', 'add_to_cart', 'checkout', 'purchase'] SELECT user_id, MIN(CASE WHEN event_name = 'view_product' THEN ts END) AS step1_ts, MIN(CASE WHEN event_name = 'add_to_cart' AND ts > MIN(CASE WHEN event_name = 'view_product' THEN ts END) THEN ts END) AS step2_ts -- ... continue for each step FROM events GROUP BY user_id; ``` ## Example ``` user_id | event_name | ts alice | view_product | 10:00 alice | browse | 10:05 <- not in funnel, skipped alice | add_to_cart | 10:10 alice | purchase | 10:30 <- skipped checkout; funnel incomplete bob | view_product | 09:00 bob | add_to_cart | 09:05 bob | checkout | 09:10 bob | purchase | 09:15 -> completed in 15 min ``` ## Follow-ups 1. How do you define and handle funnel re-entry (user completes the funnel twice)? 2. What query pattern works best for this in BigQuery (ARRAY_AGG + filtering vs. self-joins)? 3. How would you compute funnel conversion rates by user segment (e.g., mobile vs. desktop)?