Applied Intuition Software Engineer Interview Questions

Question: Given a 2D graph containing points, empty spaces, and obstacles, find an empty space that is the shortest distance from all the points.

The HR phone call was very friendly. After a brief greeting, they let me walk through my resume and follow up. As long as you maintain a good attitude, there shouldn't be any problems. The online asse

I just finished a call with Applied Intuition's HR department. It mainly consisted of a self-introduction, a review of my resume, and why I wanted to work at Applied. The HR also asked if I could hand

The tech screen guy was really helpful and even helped me define a helper function. Input: Given a folder path (e.g., "/a") containing multiple levels of subdirectories and files. Output: Find all fil

The following content requires a score of 188 or higher. You can already view this content. The HR lady was quite nice, and the overall interview experience was good. She asked if I was familiar with

LeetCode #317: Shortest Distance from All Buildings. Difficulty: Hard. Topics: Array, Breadth-First Search, Matrix. Asked at Applied Intuition in the last 6 months.

LeetCode #609: Find Duplicate File in System. Difficulty: Medium. Topics: Array, Hash Table, String. Asked at Applied Intuition in the last 6 months.

## Problem You are asked to design a system that ingests 10 TB of application logs per day, processes them for anomaly detection and aggregation, and serves dashboards with sub-second query latency. Walk through the architecture. ``` Requirements: - Ingest: 10 TB/day, 100k events/sec peak - Processing: real-time aggregation + batch anomaly detection - Query: dashboard queries over last 7 days, p99 < 500ms - Retention: 90 days hot, 3 years cold - Fault tolerance: no data loss ``` **Proposed architecture:** ``` Producers -> Kafka (partitioned by service) -+-> Flink (real-time agg) | -> Redis (hot counters) +-> S3 (raw parquet, partitioned by date) -> Spark (batch anomaly, daily) -> Trino/Presto (ad-hoc SQL) Dashboard -> Druid (pre-agg OLAP) ``` ## Follow-ups 1. Why partition Kafka by service rather than by timestamp? What are the tradeoffs? 2. How do you handle late-arriving events in the Flink streaming layer? 3. What compaction and partitioning strategy on S3 enables fast Trino queries? 4. How would you implement exactly-once semantics end-to-end from Kafka to the database?

## 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 Design a `JobMonitor` that tracks the lifecycle of asynchronous jobs. Jobs can be registered, updated with status, and queried. Alert (log to a provided callback) when a job fails or has not completed within a timeout period. ```python from typing import Callable import time class JobMonitor: def __init__(self, alert_callback: Callable[[str, str], None]): """alert_callback(job_id, reason) is called on failure/timeout.""" pass def register(self, job_id: str, timeout_sec: int) -> None: """Register a new job with a timeout.""" pass def update_status(self, job_id: str, status: str) -> None: """status: 'running', 'completed', 'failed'""" pass def check_timeouts(self, current_time: float | None = None) -> None: """Call periodically; alerts on any job past its timeout.""" pass def get_status(self, job_id: str) -> dict: pass ``` ``` monitor = JobMonitor(alert_callback=lambda jid, reason: print(f"{jid}: {reason}")) monitor.register("job1", timeout_sec=30) monitor.update_status("job1", "running") # ... 31 seconds later ... monitor.check_timeouts() # -> prints "job1: timeout" ``` ## Follow-ups 1. How do you efficiently find all timed-out jobs without scanning all registered jobs every check? 2. How would you persist job state so the monitor survives process restarts? 3. Extend to support job dependencies: job B should not start until job A completes. 4. How would you expose this as a REST API with endpoints for registration, status updates, and querying?

## Problem Implement a key-value store with get, set, and optionally delete operations. ## Likely LeetCode equivalent Similar to LC 146 LRU Cache design. ## Tags coding, hash_table, design, onsite

## Problem You are given a sequence of 2D waypoints that define a road lane as a polyline. Given a query point `P`, determine which segment of the polyline it belongs to (i.e., which consecutive pair of waypoints `(W[i], W[i+1])` is closest to `P`), and return the index `i`. ```python def find_lane_segment(waypoints: list[tuple[float, float]], point: tuple[float, float]) -> int: # waypoints: [(x0,y0), (x1,y1), ...], len >= 2 # Returns index i such that segment (waypoints[i], waypoints[i+1]) is closest to point pass ``` **Example:** ``` waypoints = [(0,0), (10,0), (10,10), (20,10)] point = (11, 3) -> 1 # closest to segment (10,0)-(10,10) point = (5, 2) -> 0 # closest to segment (0,0)-(10,0) ``` ## Follow-ups 1. How do you compute the perpendicular (orthogonal) distance from a point to a finite line segment vs. an infinite line? 2. What if multiple segments are equidistant? How do you break ties? 3. How would you extend this to 3D waypoints for autonomous vehicle path tracking? 4. If you need to handle thousands of query points per second, what spatial index structure would you use to speed up segment lookup?

## 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 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 `{}`.

## Problem Two players alternate turns on an N x M grid. Each cell is either empty (`.`) or a mine (`*`). A player places their token on the grid and must move it exactly one step (up, down, left, right) on their turn. A player loses if they step on a mine or have no valid moves. Both play optimally. Given the starting position and whose turn it is, determine whether the first player wins or loses. ```python def mine_game(grid: list[str], start_r: int, start_c: int) -> str: # Returns "WIN" if first player wins, "LOSE" otherwise pass ``` **Example:** ``` grid = [ "...", ".*.", "..." ] start_r, start_c = 0, 0 -> "WIN" grid = [".*", ".."], start_r=0, start_c=0 -> "WIN" # first player can avoid the mine ``` ## Follow-ups 1. What game-theory concept underpins this problem, and what is the time complexity of the minimax approach? 2. How would you use memoization to avoid recomputing states you have already visited? 3. What if a player can move 1 OR 2 steps in a single turn? How does the state space change? 4. Can you detect cycles (infinite games) and handle them as a draw rather than a win/loss?

## 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?