Glean Software Engineer Phone Screen Questions

Given m nodes and x documents, input two vectors: the first represents the absolute processing time for each document, and the second represents the processing duration for each document. Iterate thro

## Problem Compress an array by encoding consecutive duplicate elements as value-count pairs. ## Likely LeetCode equivalent LeetCode 443 - String Compression. ## Tags arrays, two_pointers, strings

## Problem Implement a basic calculator that evaluates a string expression with +, -, and parentheses. ## Likely LeetCode equivalent LeetCode 224 - Basic Calculator. ## Tags stack, strings, math

## Round 1 - Coding ## Problem Given an `N x N` board and a piece at position `(r, c)`, return all valid positions the piece can move to in one step. The piece moves like a chess knight (L-shape). Positions that fall off the board are invalid. ```python def valid_moves(board_size: int, row: int, col: int) -> list[tuple[int, int]]: ... ``` ## Example ``` valid_moves(8, 4, 4) -> [(2,3),(2,5),(3,2),(3,6),(5,2),(5,6),(6,3),(6,5)] valid_moves(8, 0, 0) -> [(1,2),(2,1)] valid_moves(3, 1, 1) -> [(0,3-invalid),(2,3-invalid)...] -> [] # A knight at center of a 3x3 board has no valid moves. ``` ## Follow-ups 1. Extend this: given a starting position and `k` moves, return all positions reachable in exactly `k` knight moves. What is the time complexity? 2. How would you modify your solution for a different piece — e.g., a bishop or queen? 3. If the board has blocked cells, how do you incorporate that constraint? 4. Find the minimum number of moves for a knight to travel from `(r1,c1)` to `(r2,c2)`. What algorithm applies?

## Round 1 - SQL / Schema Design ## Problem Design a normalized relational schema for an e-commerce platform that supports products, customers, orders, and order items. Then write queries to answer business questions. ```sql -- Proposed schema (you may modify) CREATE TABLE customers (id INT PRIMARY KEY, name TEXT, email TEXT); CREATE TABLE products (id INT PRIMARY KEY, name TEXT, price DECIMAL, stock INT); CREATE TABLE orders (id INT PRIMARY KEY, customer_id INT, created_at TIMESTAMP); CREATE TABLE order_items (order_id INT, product_id INT, qty INT, unit_price DECIMAL); ``` ## Example Queries ```sql -- Q1: Total revenue per customer in the last 30 days SELECT c.name, SUM(oi.qty * oi.unit_price) AS revenue FROM customers c JOIN orders o ON o.customer_id = c.id JOIN order_items oi ON oi.order_id = o.id WHERE o.created_at >= NOW() - INTERVAL '30 days' GROUP BY c.name ORDER BY revenue DESC; -- Q2: Products never ordered SELECT p.name FROM products p LEFT JOIN order_items oi ON oi.product_id = p.id WHERE oi.product_id IS NULL; ``` ## Follow-ups 1. A customer can have multiple shipping addresses per order — how do you extend the schema? 2. Which columns would you index and why? 3. How would you query the top 3 best-selling products per product category? 4. How do you handle `unit_price` to preserve historical price at order time even if `products.price` changes?

## Problem Split a chocolate bar among k people maximizing the minimum sweetness of any piece using binary search. ## Likely LeetCode equivalent LeetCode 1231 - Divide Chocolate. ## Tags binary_search, arrays, greedy

## Round 1 - Coding ## Problem You have a list of synonym pairs. Given a query word, return all words reachable from it through any chain of synonyms. Synonyms are bidirectional. ```python def find_synonyms(pairs: list[tuple[str, str]], query: str) -> set[str]: ... ``` ## Example ``` pairs = [("happy","joyful"),("joyful","elated"),("sad","unhappy"),("big","large")] find_synonyms(pairs, "happy") -> {"joyful", "elated"} find_synonyms(pairs, "elated") -> {"happy", "joyful"} find_synonyms(pairs, "big") -> {"large"} find_synonyms(pairs, "cold") -> set() # not in any pair ``` ## Approach Model as an undirected graph (Union-Find or BFS/DFS). Each word is a node; each pair is an edge. Return the connected component of `query`, excluding `query` itself. ## Follow-ups 1. How does your runtime change if pairs are added dynamically after the initial build? How would Union-Find help? 2. Suppose synonyms have weights (similarity score 0-1). How would you return only synonyms above a threshold? 3. How would you extend this to support antonyms as a separate relationship type? 4. Given two words, return the shortest synonym chain connecting them.

## Round 1 - Coding ## Problem A house is built in stages. Each stage has a name, a duration in days, and a list of prerequisite stages that must be completed first. Return the minimum number of days to complete the entire house, and the order stages should be executed. ```python def build_schedule(stages: list[dict]) -> dict: # stages: [{"name": str, "days": int, "deps": list[str]}] # returns: {"total_days": int, "order": list[str]} ... ``` ## Example ``` stages = [ {"name": "foundation", "days": 5, "deps": []}, {"name": "framing", "days": 10, "deps": ["foundation"]}, {"name": "roofing", "days": 7, "deps": ["framing"]}, {"name": "plumbing", "days": 4, "deps": ["framing"]}, {"name": "electrical", "days": 3, "deps": ["framing"]}, {"name": "finishing", "days": 6, "deps": ["roofing","plumbing","electrical"]}, ] build_schedule(stages) # -> {"total_days": 28, "order": ["foundation","framing","plumbing","electrical","roofing","finishing"]} # Critical path: foundation(5)+framing(10)+roofing(7)+finishing(6)=28 ``` ## Follow-ups 1. How do you detect a cycle in the dependency graph? 2. If multiple workers are available in parallel, how does that change the minimum duration calculation? 3. How would you identify the critical path — the sequence of stages that directly determines the total time? 4. What data structure makes topological sort most efficient here?

## Problem Find the kth largest element in an array using a min-heap of size k. ## Likely LeetCode equivalent LeetCode 215 - Kth Largest Element in an Array. ## Tags heap, sorting, arrays

## Round 1 - Coding ## Problem Given an `M x N` grid of integers, find the largest connected region where all cells share the same value. Connectivity is 4-directional (up, down, left, right). Return the size and value of that region. ```python def largest_shape(grid: list[list[int]]) -> tuple[int, int]: # returns (size, value) ... ``` ## Example ``` grid = [ [1, 1, 2, 3], [1, 2, 2, 3], [4, 2, 2, 3], [4, 4, 1, 1], ] largest_shape(grid) -> (4, 2) # The 2s form a connected region of size 4 (positions (0,2),(1,1),(1,2),(2,1),(2,2)) -> actually 5 # Trace carefully: (0,2),(1,1),(1,2),(2,1),(2,2) = size 5 largest_shape(grid) -> (5, 2) ``` ## Approach BFS/DFS from each unvisited cell, tracking region size and value. Keep a visited set to avoid double-counting. ## Follow-ups 1. How does your solution change if you also allow diagonal connectivity (8-directional)? 2. If the grid is very large (10,000 x 10,000), how do you handle memory constraints? 3. Return all regions sorted by size descending — what is the overall time and space complexity? 4. How would you extend this to count the perimeter of the largest shape?

## Problem Find the minimum number of parenthesis deletions to make a string valid using a stack or greedy counter. ## Likely LeetCode equivalent LeetCode 1249 - Minimum Remove to Make Valid Parentheses. ## Tags stack, strings, greedy

## Round 1 - Coding ## Problem A character wants to reach a snack at the far corner of a grid without being seen. Each cell has a detection cost (0 means safe, higher means riskier). Find the path from top-left `(0,0)` to bottom-right `(M-1,N-1)` that minimizes total detection cost. You can only move right or down. ```python def min_detection_cost(grid: list[list[int]]) -> int: ... ``` ## Example ``` grid = [ [0, 3, 1], [2, 0, 4], [1, 2, 0], ] min_detection_cost(grid) -> 0 # Path: (0,0)->(1,1)->(2,2), all zeros. grid = [ [1, 2, 3], [4, 5, 6], [7, 8, 9], ] min_detection_cost(grid) -> 21 # Path: 1->2->3->6->9 ``` ## Follow-ups 1. Now allow movement in all 4 directions. What algorithm would you use and why? 2. Some cells are completely blocked (cost = -1) — how do you handle that? 3. Return the actual path, not just the cost. 4. How would you solve this if you could move through at most one blocked cell for free?

## Round 1 - Coding ## Problem Given a list of words and a maximum line width `W`, format the words so that each line is exactly `W` characters wide using full justification. Extra spaces are distributed as evenly as possible from left to right. The last line is left-justified. ```python def full_justify(words: list[str], max_width: int) -> list[str]: ... ``` ## Example ``` words = ["This","is","an","example","of","text","justification."] max_width = 16 Output: ["This is an", "example of text", "justification. "] words = ["What","must","be","acknowledgment","shall","be"] max_width = 16 Output: ["What must be", "acknowledgment ", "shall be "] ``` ## Follow-ups 1. How do you distribute spaces when the extra count is not divisible evenly by the number of gaps? 2. A line with a single word — how do you pad it correctly? 3. What changes if you must right-justify the last line instead of left-justify it? 4. How would you extend this to support unicode characters that may be multi-byte?

## Problem Find a path through a word graph or transform one word to another in minimum steps, similar to word ladder. ## Likely LeetCode equivalent Similar to LC 127 Word Ladder but not confirmed as identical. ## Tags graph, bfs, strings

## Round 1 - Coding ## Problem Given a list of tasks with integer costs and `k` workers, assign every task to exactly one worker to minimize the maximum total cost assigned to any single worker. ```python def min_max_load(tasks: list[int], k: int) -> int: ... ``` ## Example ``` tasks = [3, 2, 3], k = 3 -> 3 # Assign each task to one worker. Max load = 3. tasks = [1, 2, 4, 7, 3, 3], k = 3 -> 8 # Optimal: [7,1], [3,3,2], [4] -> max = 8 # Greedy or binary search on answer. tasks = [10, 10, 10, 10], k = 2 -> 20 ``` ## Approach Binary search on the answer `X`. Check feasibility: can all tasks be assigned with no worker exceeding `X`? Use greedy packing. ## Follow-ups 1. Walk through why binary search on the answer works here. What are the search bounds? 2. How does the problem change if each worker can take at most `m` tasks, regardless of total cost? 3. If tasks have dependencies (task B must start after task A finishes), how does that affect assignment? 4. What is the time complexity of your binary search + feasibility check approach?