Ziphq Software Engineer Phone Screen Questions

## Problem A pursuer and a target move on an N x M grid. They alternate turns — pursuer moves first. Each turn, a player may move to any orthogonally adjacent cell or stay in place. The pursuer catches the target if they occupy the same cell at the end of any turn. Given the grid dimensions, starting positions, and a maximum number of turns `T`, determine the minimum number of turns for the pursuer to guarantee a catch, or return -1 if impossible within `T` turns. ```python def min_turns_to_catch( n: int, m: int, pursuer: tuple[int, int], target: tuple[int, int], T: int ) -> int: pass ``` ``` Input: n=4, m=4, pursuer=(0,0), target=(3,3), T=10 Output: 6 # Manhattan distance = 6; pursuer closes one step per turn if target runs away Input: n=2, m=2, pursuer=(0,0), target=(1,1), T=3 Output: 2 ``` ## Follow-ups 1. How does BFS on a game-state space `(pursuer_pos, target_pos, turn)` apply here? 2. If the target moves optimally to escape, does Manhattan distance still give the correct answer? 3. How would you extend this to multiple pursuers? 4. What changes if the grid has obstacles that block movement?

## Problem You are given a list of variable assignments and a list of boolean expressions to evaluate. Each expression is a string of the form `"a == b"` or `"a != b"` where `a` and `b` are lowercase letters or integer literals. Return a list of booleans. Variables may reference other variables (no cycles guaranteed). Evaluate all expressions after resolving the full variable chain. ```python def evaluate_conditions( assignments: list[tuple[str, str]], # [(var, value_or_var), ...] expressions: list[str] ) -> list[bool]: pass ``` ``` Input: assignments = [("a", "1"), ("b", "a"), ("c", "2")] expressions = ["a == b", "b != c", "a == 1"] Output: [True, True, True] Input: assignments = [("x", "y"), ("y", "3")] expressions = ["x == 3", "x != y"] Output: [True, False] ``` ## Follow-ups 1. How would you detect and handle circular references in variable assignments? 2. Can Union-Find be applied here for equality expressions? How? 3. What if expressions include `<` and `>` comparisons on numeric values? 4. How do you extend this to support compound expressions like `"a == b AND b != c"`?

## Problem Normalize or convert email addresses according to formatting rules such as stripping dots or plus-suffixes in the local part. ## Likely LeetCode equivalent LC 929 - Unique Email Addresses (>80% confident) ## Tags strings, hash_table

## Problem You are given a list of words and an integer `width`. Format the words into lines such that each line contains as many words as possible without exceeding `width` characters. Words on the same line are separated by a single space. Return the list of formatted lines. ```python def display_strings(words: list[str], width: int) -> list[str]: pass ``` ``` Input: words = ["the", "quick", "brown", "fox", "jumps"], width = 12 Output: ["the quick", "brown fox", "jumps"] # "the quick" = 9 chars (fits), "the quick brown" = 15 (too long) Input: words = ["hello", "world"], width = 5 Output: ["hello", "world"] # Each word exactly fills the width ``` ## Follow-ups 1. What if a single word is longer than `width` — should you truncate, split, or raise an error? 2. Modify the solution to justify text fully: distribute extra spaces evenly between words on each line (last line left-aligned). 3. How would you handle unicode characters that have display widths of 2 (e.g., CJK characters)? 4. What is your time and space complexity?

## Problem You start at position 0 on a number line with a full tank of `fuel` units. There are `n` stations at given positions, each with a certain amount of additional fuel. You can stop at any subset of stations. Return the furthest position you can reach. ```python def furthest_distance( stations: list[tuple[int, int]], # (position, fuel_available) initial_fuel: int ) -> int: pass ``` ``` Input: stations = [(10, 60), (20, 30), (30, 40), (60, 50)], initial_fuel = 40 Output: 70 # Reach station at 10 (use 10 fuel, pick up 60) -> tank=90 # Reach station at 20 (use 10, pick up 30) -> tank=110 # Reach station at 30 (use 10, pick up 40) -> tank=140 # Reach 70 (use 40) -> stops here, tank=100... actually can reach further # Max is 70 without overshoot logic; trace carefully. Input: stations = [(5, 10)], initial_fuel = 3 Output: 3 # Cannot reach any station, stop at 3 ``` ## Follow-ups 1. How does a greedy approach with a max-heap of passed stations help here? 2. What is the time complexity of your solution? 3. How would you track which stations were actually visited? 4. If there is a destination `D` you must reach exactly, how does the problem change?

## Problem You are given a hand of cards represented as an integer array. Rearrange the cards into groups of exactly `k` consecutive cards (e.g., `[1,2,3]`, `[2,3,4]`). Return `True` if this is possible, `False` otherwise. ```python def can_group_cards(hand: list[int], k: int) -> bool: pass ``` ``` Input: hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], k = 3 Output: True # Groups: [1,2,3], [2,3,4], [6,7,8] Input: hand = [1, 2, 3, 4, 5], k = 4 Output: False # 5 cards not divisible into groups of 4 Input: hand = [1, 1, 2, 2, 3, 3], k = 3 Output: True # Groups: [1,2,3], [1,2,3] ``` ## Follow-ups 1. What is the time complexity of your approach using a sorted map? 2. If `k` is not fixed — find the minimum `k >= 2` for which grouping is possible — how do you solve it? 3. How does this problem relate to LeetCode 846 and 1296? What differs? 4. What if cards can be repeated in the same group?

## Problem Implement a vending machine (`Jihanki` is Japanese for vending machine). The machine accepts coins, displays available items with prices, dispenses an item if enough coins have been inserted, and returns change. ```python class Jihanki: def __init__(self, inventory: dict[str, tuple[int, int]]): """inventory: {item_name: (price_cents, quantity)}""" pass def insert_coin(self, amount: int) -> None: """Insert a coin of given denomination.""" pass def select_item(self, item: str) -> tuple[str, int]: """Attempt to purchase item. Return (status, change_returned). status: 'dispensed', 'insufficient_funds', 'out_of_stock', 'invalid_item' """ pass def cancel(self) -> int: """Cancel and return all inserted coins as total cents.""" pass def get_balance(self) -> int: pass ``` ``` m = Jihanki({"cola": (150, 5), "water": (100, 2)}) m.insert_coin(100) m.insert_coin(50) m.select_item("cola") -> ("dispensed", 0) m.insert_coin(200) m.select_item("cola") -> ("dispensed", 50) ``` ## Follow-ups 1. How would you enforce valid coin denominations (e.g., only 5, 10, 25, 50, 100 cents)? 2. How do you handle concurrent access if multiple users interact simultaneously? 3. Extend to support a maintenance mode that blocks purchases and allows restocking. 4. How would you model this as a formal state machine with defined states and transitions?

## Problem You are given an array of integers. In each turn you may swap any one pair of adjacent elements. Return the minimum number of turns (swaps) needed to sort the array in non-decreasing order. ```python def minimum_turns(arr: list[int]) -> int: pass ``` ``` Input: arr = [3, 1, 2] Output: 2 # [3,1,2] -> [1,3,2] -> [1,2,3] (2 swaps) Input: arr = [4, 3, 2, 1] Output: 6 # Reverse of 4 elements = 4*3/2 = 6 inversions Input: arr = [1, 2, 3] Output: 0 ``` ## Follow-ups 1. What is the relationship between minimum adjacent swaps and the number of inversions in the array? 2. How can merge sort be used to count inversions in O(n log n)? 3. If you can swap any two elements (not just adjacent), what is the minimum number of swaps then? 4. How does duplicate handling change the inversion count logic?

## Problem You are hosting a party and have `n` potential guests numbered `1` to `n`. You are given a list of conflict pairs — two people who refuse to attend if the other is present. Find the maximum number of guests you can invite such that no conflict pair is both present. ```python def max_party_guests(n: int, conflicts: list[tuple[int, int]]) -> int: pass ``` ``` Input: n = 4, conflicts = [(1,2), (1,3), (2,4)] Output: 2 # e.g., invite {2,3} -> conflict (1,3)? No, 1 not invited. (2,4)? 4 not invited. # Actually {2,3} has no conflict -> valid, size 2 # Can we get 3? {1,4}: conflict (1,2)? 2 not there. (1,3)? 3 not there. -> valid! size 2+? # {1,4} = 2 guests; {2,3} = 2 guests; {3,4} = 2. Answer = 2 here? Check {1,4}: size 2. # If no constraints, answer is n. Input: n = 3, conflicts = [] Output: 3 ``` ## Follow-ups 1. Is this equivalent to Maximum Independent Set? What does that imply about complexity in general graphs? 2. If the conflict graph is bipartite, how can you find the exact answer efficiently? 3. For a general graph, what approximation strategies exist? 4. How would you extend this to weighted guests where you maximize total "importance" instead of count?

## Problem You are given a list of `(node_id, parent_id)` pairs representing a forest (collection of trees). A root node is one that does not appear as a child of any other node. Return all root node IDs in sorted order. ```python def find_root_ids(edges: list[tuple[int, int]]) -> list[int]: """edges: list of (node, parent). Return sorted list of roots.""" pass ``` ``` Input: edges = [(2,1), (3,1), (4,2), (5,3), (6,0)] Output: [1, 0] # Node 1 has no parent listed -> root # Node 0 has no parent listed -> root # Sorted: [0, 1] Input: edges = [(2,1), (3,2)] Output: [1] ``` ## Follow-ups 1. What if the input contains a cycle? How would you detect and report it? 2. How would you reconstruct the full tree structure (children mapping) from this edge list? 3. If `node_id` values are strings instead of integers, how does your solution change? 4. How would you find all leaf nodes in O(n) using the same edge list?

## Problem A taxi driver has a single vehicle and a list of trip requests. Each trip has a start time, end time, and fare. The driver can complete only one trip at a time (trips cannot overlap). Find the maximum total fare the driver can earn. ```python def max_taxi_earnings(trips: list[tuple[int, int, int]]) -> int: """trips: [(start, end, fare), ...]. Return max total fare.""" pass ``` ``` Input: trips = [(0,5,10), (3,7,15), (5,10,20), (6,9,8)] Output: 30 # Take (0,5,10) then (5,10,20) -> total 30 # OR take (3,7,15) -> only 15 # 30 is optimal Input: trips = [(1,4,3), (2,5,6), (4,6,2)] Output: 5 # Take (1,4,3) then (4,6,2) -> total 5 # OR (2,5,6) alone -> 6 is better! Output: 6 ``` ## Follow-ups 1. This is the weighted interval scheduling problem — what DP approach solves it optimally? 2. After sorting by end time, how do you efficiently find the latest non-overlapping trip using binary search? 3. What is the time complexity of your solution? 4. Extend to `k` taxis — how does the problem change?

## Problem Two players take turns claiming tiles from a 1D array of integer-valued tiles. Each turn, the current player must take from either the left end or the right end. Both play optimally to maximize their own score. Return the score difference (player 1 score minus player 2 score) at the end of the game. ```python def winning_tiles(tiles: list[int]) -> int: """Return score_player1 - score_player2 assuming optimal play.""" pass ``` ``` Input: tiles = [5, 3, 7, 10] Output: 7 # P1 takes 10 (right), P2 takes 7, P1 takes 5, P2 takes 3 # P1=15, P2=10 -> diff=5 # OR P1 takes 5, P2 takes 10, P1 takes 7, P2 takes 3 -> P1=12, P2=13 -> diff=-1 # Optimal: P1 takes 10, then 7 -> P1=17, P2=8 -> diff=9? trace carefully. Input: tiles = [1, 5, 2] Output: 4 # P1 takes 2, P2 takes 5, P1 takes 1 -> P1=3, P2=5 -> diff=-2 # P1 takes 1, P2 takes 2, P1 takes 5 -> P1=6, P2=2 -> diff=4 <-- optimal ``` ## Follow-ups 1. Define the recurrence `dp[i][j]` = best score difference achievable by the current player on subarray `[i..j]`. 2. What is the time and space complexity of the DP solution? 3. If tiles can have negative values, does optimal play change (can a player pass)? 4. Extend to 3 players — does the same DP structure work?