Applied Intuition Software Engineer Phone Screen Questions

## Problem You manage a campground with `n` campsites. Reservations are stored as `(site_id, start_day, end_day)` (inclusive). Given a requested stay `(start, end)`, return the list of available site IDs sorted in ascending order. ```python def available_campsites( n: int, reservations: list[tuple[int, int, int]], # (site_id, start, end) request_start: int, request_end: int ) -> list[int]: pass ``` ``` Input: n = 4 reservations = [(1,1,5),(1,8,10),(2,3,7),(3,1,3)] request_start = 4, request_end = 6 Output: [1, 4] # Site 1: occupied days 1-5 overlaps [4,6] -> not available # Site 2: occupied days 3-7 overlaps [4,6] -> not available # Site 3: occupied days 1-3, no overlap with [4,6] -> available # Site 4: no reservations -> available # Sorted: [3, 4] Corrected Output: [3, 4] ``` ## Follow-ups 1. What is the interval overlap condition? Prove your predicate handles edge cases (adjacent days). 2. If `n` and reservations are large, what index structure speeds up availability queries? 3. Extend to return the site with the fewest total reserved days among available sites. 4. How would you write this as a SQL query using NOT EXISTS or a LEFT JOIN approach?

## Problem Encode a string using run-length encoding or a custom compression scheme. ## Likely LeetCode equivalent Similar to LC 443 String Compression. ## Tags coding, strings, encoding, phone

## Problem Parse and evaluate a mathematical formula string, handling operator precedence and parentheses. ## Likely LeetCode equivalent Similar to LC 224 Basic Calculator. ## Tags coding, stack, parsing, math, phone

## Problem You are given a list of 2D integer coordinates. Group them into clusters such that all points within a cluster are within Euclidean distance `r` of at least one other point in the same cluster. Return each cluster as a sorted list of point indices, with clusters sorted by their smallest index. ```python def group_coordinates( points: list[tuple[int, int]], r: float ) -> list[list[int]]: pass ``` ``` Input: points = [(0,0),(1,1),(10,10),(11,11),(0,1)] r = 2.0 Output: [[0,1,4], [2,3]] # (0,0),(1,1),(0,1) are all within r=2 of each other -> cluster # (10,10),(11,11) -> cluster Input: points = [(0,0),(100,100)] r = 1.0 Output: [[0],[1]] ``` ## Follow-ups 1. This is essentially finding connected components in a graph where edges connect points within distance `r`. What graph traversal do you use? 2. The naive approach is O(n^2) for edge construction. How does a k-d tree reduce this? 3. How does this compare to DBSCAN clustering? What is the role of `r` vs DBSCAN's epsilon? 4. Extend to 3D coordinates — what changes in your approach?

## Problem Rotate the layers of a 2D matrix by a specified number of positions. ## Likely LeetCode equivalent Similar to LC 48 Rotate Image. ## Tags coding, matrix, simulation, phone

## Problem You have a table of geographic points. Write a SQL query to return all points within a given radius (in kilometers) of a target latitude/longitude, ordered by distance ascending. ```sql -- Table: points -- id INT, name VARCHAR, lat FLOAT, lon FLOAT -- Use the Haversine approximation formula: -- distance_km = 6371 * acos( -- cos(radians(:target_lat)) * cos(radians(lat)) -- * cos(radians(lon) - radians(:target_lon)) -- + sin(radians(:target_lat)) * sin(radians(lat)) -- ) ``` **Example query parameters:** `target_lat=37.7749, target_lon=-122.4194, radius_km=10` **Expected columns:** `id, name, lat, lon, distance_km` ```sql SELECT id, name, lat, lon, 6371 * acos(...) AS distance_km FROM points HAVING distance_km <= :radius_km ORDER BY distance_km ASC; ``` ## Follow-ups 1. Why must you use `HAVING` instead of `WHERE` when filtering on the computed `distance_km` alias? 2. At what scale would this full-table scan become a bottleneck, and what index type (e.g., spatial index, geohash) would you add? 3. How does the Haversine formula break down near the poles, and what formula is more accurate? 4. Rewrite this query to also return a bounding box check first as a pre-filter before the expensive `acos` computation.

## Problem Given an array of 2D points and an integer `k`, return the `k` points closest to the origin `(0, 0)`. Distance is Euclidean. The result can be in any order. ```python def k_closest(points: list[list[int]], k: int) -> list[list[int]]: pass ``` **Example:** ``` points = [[1,3],[-2,2],[5,8],[0,1]], k = 2 -> [[-2,2],[0,1]] # distances: sqrt(10), sqrt(8), sqrt(89), 1 points = [[3,3],[5,-1],[-2,4]], k = 2 -> [[3,3],[-2,4]] # distances: sqrt(18), sqrt(26), sqrt(20) ``` ## Round 1 - Coding Implement a solution using a max-heap of size `k`. ## Follow-ups 1. What is the time complexity of the heap approach vs. a full sort? When does each become preferable? 2. How would you use the Quickselect algorithm to achieve average O(n) time? 3. If points arrive as a stream and you must always return the current `k` closest, how do you maintain the heap efficiently? 4. How does the solution change if distance is Manhattan distance instead of Euclidean?

## Problem You are implementing a software UART (Universal Asynchronous Receiver-Transmitter) receiver in C. Given a stream of raw bit samples (sampled at 8x the baud rate), decode the data bytes. A UART frame consists of: 1 start bit (0), 8 data bits (LSB first), 1 stop bit (1). Framing errors should be flagged. ```c typedef struct { uint8_t data; bool framing_error; } UartFrame; int uart_decode(const uint8_t* samples, int n_samples, UartFrame* out_frames, int max_frames); // Returns number of frames decoded ``` **Example:** ``` // Baud rate = 9600, sample rate = 76800 (8x oversampling) // Bit 0 sampled at positions 4,12,20,28... (center of each bit window) // Frame for byte 0xA5 (10100101): // START=0, bits=1,0,1,0,0,1,0,1, STOP=1 // -> {data=0xA5, framing_error=false} ``` ## Follow-ups 1. Why do you sample at the center of the bit window rather than the edge, and how does oversampling reduce bit-error rate? 2. How do you detect and recover from framing errors (missing stop bit) without losing subsequent frames? 3. What changes if you add parity support (even/odd parity bits)? 4. How would you implement the transmit (TX) side to produce the same bit stream at a target baud rate?

## Problem Simulate vehicle collision detection based on positions and velocities along a road. ## Likely LeetCode equivalent Similar to LC 2211 Count Collisions on a Road. ## Tags coding, arrays, simulation, phone

## Problem You are given a list of 3D vertices and a face list (triangles as index triples). Two vertices are considered duplicates if their Euclidean distance is below a threshold `eps`. Merge all duplicates into a single representative vertex, update the face list accordingly, and return the compressed mesh. ```python def compress_vertices( vertices: list[tuple[float,float,float]], faces: list[tuple[int,int,int]], eps: float ) -> tuple[list[tuple[float,float,float]], list[tuple[int,int,int]]]: # Returns (new_vertices, new_faces) pass ``` **Example:** ``` vertices = [(0,0,0),(0,0,0.0001),(1,0,0),(1,0,0)] faces = [(0,1,2),(1,2,3)] eps = 0.001 -> new_vertices = [(0,0,0), (1,0,0)] new_faces = [(0,0,1), (0,1,1)] ``` ## Follow-ups 1. What data structure would you use to make the O(n^2) pairwise comparison more efficient (e.g., k-d tree, spatial hash grid)? 2. After merging vertices, degenerate faces (all three indices the same) may appear. How do you detect and remove them? 3. How would you handle vertex attributes (normals, UVs) when merging -- average, take first, or discard? 4. What is weld tolerance and why is it important in game engine asset pipelines?

## Problem You are given a raw message string from a custom text protocol. Each message consists of fields separated by `|`, where each field is a `key=value` pair. Some values may themselves contain escaped pipes `\|`. Parse the message and return a dictionary of field names to values, with escape sequences resolved. ```python def parse_message(raw: str) -> dict[str, str]: # Returns {field_name: value, ...} pass ``` **Example:** ``` raw = "type=ORDER|id=42|note=buy\|sell|qty=10" -> {"type": "ORDER", "id": "42", "note": "buy|sell", "qty": "10"} raw = "status=OK|msg=all good" -> {"status": "OK", "msg": "all good"} raw = "a=1||b=2" # empty field between double-pipe -> {"a": "1", "": "", "b": "2"} # or raise, based on spec ``` ## Follow-ups 1. How would you handle duplicate keys? Last-write-wins, first-write-wins, or collect as list? 2. What changes if values can also contain escaped equals signs `\=`? 3. How would you validate that required fields (e.g., `type`, `id`) are always present and raise a descriptive error otherwise? 4. Extend the parser to support nested messages, where a value is itself a `key=value|...` block wrapped in `{}`.