Software Engineer Interview Guide

Framework — Complement lookup

The brute force approach checks every pair, which takes O(n^2). A better approach uses a hash map from value to index. As we scan the array, for each number x, the value we need is target - x. If that complement already exists in the map, we return the current index and the stored index. Otherwise, store x with its index and continue. The key correctness idea is that when we process index i, the map contains exactly the values from earlier indices. That means if a valid pair ends at i, we will find it immediately. This also avoids using the same element twice because we only match against earlier elements. Time complexity is O(n) because each value is inserted and looked up once. Space complexity is O(n) for the map. Edge cases include duplicate values, negative numbers, zero, and no valid pair if the prompt allows that case.

Framework — Sliding window with last-seen index

Use a sliding window where the window always contains unique characters. Maintain a left pointer and a map from character to its most recent index. Iterate right across the string. If the current character was seen inside the current window, move left to one position after its previous index. Then update the character index and record the maximum window length. The important detail is that left should only move forward. If a character was seen before the current window, it should not shrink the window. That is why the update is left = max(left, lastSeen[char] + 1). Time complexity is O(n) because each character is processed once and the left pointer only moves forward. Space complexity is O(k), where k is the character set size. Edge cases include empty string, all unique characters, all repeated characters, and Unicode if the language treats characters differently from bytes.

Framework — Canonical key

Anagrams share the same character composition. Create a canonical key for each word and group words by that key in a hash map. The most direct key is the sorted characters of the word. For example, “eat”, “tea”, and “ate” all map to “aet”. If strings are short, sorting each word is simple and reliable. If the alphabet is fixed to lowercase English letters and strings are long, a 26-count frequency tuple can be faster because it avoids O(k log k) sorting per word. Time complexity with sorting is O(n * k log k), where n is the number of strings and k is the average string length. With fixed alphabet counting, it can be O(n * k). Space complexity is O(n * k) for the output plus keys. Edge cases include empty strings, duplicates, uppercase/lowercase rules, and non-English characters.

Framework — Three pointers: previous, current, next

Use three pointers. previous starts as null, current starts at the head. For each node, store next = current.next, redirect current.next to previous, then move previous to current and current to next. When current becomes null, previous is the new head. The invariant is that previous points to the already-reversed portion and current points to the first node not yet reversed. Storing next before changing current.next is essential; otherwise the rest of the list is lost. Time complexity is O(n). Space complexity is O(1). Edge cases include an empty list, a single node, and ensuring the original head becomes the tail with next set to null.

Framework — Range constraints

A common mistake is checking only whether each node is greater than its left child and less than its right child. That is insufficient because the full subtree must satisfy ancestor constraints. Use DFS with lower and upper bounds. For each node, verify lower < node.value < upper. The left child receives the same lower bound and the current value as the upper bound. The right child receives the current value as the lower bound and the same upper bound. If any node violates its range, return false. Time complexity is O(n) because every node is visited once. Space complexity is O(h) for recursion depth, where h is tree height. Edge cases include duplicates, integer min/max boundaries, empty tree, and skewed trees. Clarify whether duplicates are allowed and on which side if they are.

Framework — Breadth-first search by distance layer

Model each open cell as a graph node and each move up, down, left, or right as an edge with equal weight. Because every move has the same cost, BFS gives the shortest path. Start from the source cell, push it into a queue with distance 0, and mark it visited. For each popped cell, explore valid unvisited neighbors that are inside bounds and not obstacles. The first time we reach the target, the distance is minimal. The correctness comes from BFS processing nodes in increasing distance order. Once a cell is visited, reaching it later cannot produce a shorter path in an unweighted graph. Time complexity is O(rows * cols) because each cell is visited at most once. Space complexity is O(rows * cols) for the queue and visited set. Edge cases include blocked start or end, source equals target, no path, and whether diagonal moves are allowed.

Framework — Visited map from original node to cloned node

Use a hash map that maps each original node to its cloned node. During DFS or BFS, when visiting an original node, create its clone if it does not exist. Then recursively or iteratively clone each neighbor and append the cloned neighbor to the cloned node adjacency list. The visited map solves two problems: it prevents infinite loops in cyclic graphs and preserves shared references so the cloned graph has the same topology as the original graph. Time complexity is O(V + E), where V is nodes and E is edges. Space complexity is O(V) for the map and traversal stack or queue, not counting the output graph. Edge cases include null input, self-loops, disconnected graphs if the prompt expects cloning only from a starting node, and duplicate neighbor entries.

Framework — Bottom-up DP over amount

Define dp[a] as the minimum number of coins needed to make amount a. Initialize dp[0] = 0 and all other values as infinity. For each amount from 1 to target, try every coin. If a - coin is non-negative, dp[a] = min(dp[a], dp[a - coin] + 1). At the end, if dp[target] is infinity, return -1. The recurrence works because the last coin in an optimal solution must be one of the denominations. If that last coin has value c, the remaining amount is target - c, which should also be solved optimally. Time complexity is O(amount * number of coins). Space complexity is O(amount). Edge cases include amount 0, impossible amounts, coin value 1, duplicate denominations, and large target amounts.

Framework — DP by ending position, then optimize with binary search

A clear DP solution defines dp[i] as the length of the longest increasing subsequence ending at index i. For each i, check every earlier j. If nums[j] < nums[i], then nums[i] can extend the subsequence ending at j, so dp[i] = max(dp[i], dp[j] + 1). The answer is max(dp). This takes O(n^2) time and O(n) space. The optimized O(n log n) approach maintains an array tails, where tails[length - 1] is the smallest possible ending value of an increasing subsequence of that length. For each number, binary search the first tail greater than or equal to it and replace it. The length of tails is the LIS length. In an interview, it is reasonable to present the O(n^2) DP first if time is limited, then discuss the optimized version. Edge cases include duplicates, decreasing arrays, empty input, and whether the subsequence must be strictly increasing.

Framework — Build valid prefixes only

Use backtracking with two counts: open used and close used. At each step, we can add an open parenthesis if open < n. We can add a close parenthesis if close < open. That second condition ensures every prefix remains valid, so we never generate invalid strings that need to be filtered later. When the current string length reaches 2n, add it to the result. This explores only valid prefixes and prunes impossible states early. The number of valid outputs is the nth Catalan number, so output size dominates runtime. Space complexity includes recursion depth O(n) plus the output. Edge cases include n = 0 or n = 1, depending on prompt definition.

Framework — Requirements -> API -> ID generation -> storage -> redirect path -> scale

Requirements: users submit a long URL and receive a short URL. When someone visits the short URL, they should be redirected quickly. Optional features include custom aliases, expiration, analytics, spam detection, and user accounts. Core APIs: createShortUrl(longUrl, optionalAlias, expiration) and redirect(shortCode). Data model: shortCode, longUrl, userId, createdAt, expiresAt, status, and analytics metadata if needed. For ID generation, options include auto-increment IDs encoded in base62, random base62 codes with collision checks, or distributed ID generation. Auto-increment is simple but reveals volume unless obfuscated. Random IDs are easy to distribute but need collision handling. At moderate scale, random base62 with database uniqueness is acceptable. Read path matters most. Redirect should be fast: load shortCode from cache, fall back to database, validate expiration/status, then return HTTP 301 or 302. Use 302 if analytics or destination changes matter; use 301 for permanent redirects with stronger browser caching. Scale: cache hot short codes in Redis or edge cache, shard by shortCode if needed, store analytics asynchronously through a queue, rate limit creation, and run spam/malware checks. Monitor redirect latency, cache hit rate, error rate, abuse reports, and database saturation.

Framework — Users -> posts -> fanout -> ranking -> reads -> consistency

Clarify the feed type: social following feed, recommendation feed, or mixed feed. Assume a following feed where users create posts and followers see them ordered by relevance or recency. Core objects: users, follow edges, posts, media, feed items, likes/comments, and ranking features. APIs include createPost, getFeed, followUser, unfollowUser, and interactWithPost. There are two common feed generation models. Fanout-on-write pushes new posts into follower feed stores when a post is created. This makes reads fast but writes expensive for users with many followers. Fanout-on-read computes the feed when requested by fetching posts from followed users. This makes writes cheap but reads slower. A hybrid approach is common: fanout-on-write for normal users and fanout-on-read or special handling for celebrity accounts. Architecture: post service writes posts, graph service stores follow relationships, feed service maintains feed timelines, ranking service scores candidate posts, cache stores hot feeds, and media goes to object storage/CDN. Use queues for asynchronous fanout and ranking updates. Tradeoffs: feed freshness versus ranking quality, consistency of follow changes, handling celebrity users, cache invalidation, spam, privacy blocks, and backfill after queue failures. Monitor feed load latency, freshness, fanout lag, engagement, cache hit rate, ranking errors, and abuse reports.

Framework — Connections -> message flow -> persistence -> delivery -> reliability

Requirements: one-to-one and group messages, online delivery, offline delivery, message history, read receipts, typing indicators, and push notifications. Clarify whether end-to-end encryption, attachments, and multi-device sync are required. Clients maintain WebSocket connections to a gateway service. When a user sends a message, the gateway authenticates it, assigns or receives an idempotency key, writes the message to durable storage, publishes an event, and delivers it to online recipients through their active connections. Offline users receive push notifications and can fetch history later. Data model: conversation, participant, message, delivery state, read state, and device/session. Storage needs efficient reads by conversation and time. A relational database can work at moderate scale; distributed stores are used at larger scale. Attachments should go to object storage, not the message database. Reliability concerns: duplicate sends, out-of-order delivery, reconnects, missed messages, fanout for large groups, and presence accuracy. Use idempotency keys, monotonically increasing sequence numbers per conversation, acknowledgements, retry logic, and sync-from-last-seen APIs. Monitor message send latency, delivery success rate, WebSocket connection count, reconnect rate, queue lag, push notification failures, and storage write errors.

Framework — Validate -> scope -> recent changes -> dependency breakdown -> mitigate

First validate the signal. Check whether the latency increase appears in multiple monitoring systems and whether it affects p50, p95, p99, or only a specific endpoint. Confirm whether it is user-visible. Then scope the issue by endpoint, region, availability zone, customer segment, version, host, dependency, and request type. A global increase suggests a shared dependency or deployment. A narrow increase points to a specific route, query, customer, or infrastructure zone. Next inspect recent changes: deployments, configuration changes, database migrations, traffic spikes, feature flags, cache changes, or downstream service incidents. Break down latency by service spans using traces. Check database query time, cache hit rate, queue lag, CPU, memory, garbage collection, thread pools, connection pools, and external APIs. Mitigation comes before perfect root cause if users are affected. Roll back, disable a feature flag, scale capacity, bypass a slow dependency, or increase cache TTL if safe. After recovery, write the root cause, detection gap, and prevention plan.

Framework — Unit cases -> boundaries -> invalid inputs -> invariants

I would start by clarifying the rules: discount types, stacking behavior, expiration, minimum spend, user eligibility, currency rounding, and whether taxes or shipping are included. Unit tests should cover normal cases, boundary cases, invalid inputs, and interactions between rules. Examples: no discount, percentage discount, fixed discount, discount greater than subtotal, minimum spend exactly met, minimum spend just below threshold, expired discount, ineligible user, multiple discounts if allowed, and rounding for cents. I would also test invariants: final price should never be negative, discount should not exceed eligible subtotal, expired promotions should not apply, and repeated calculation should be deterministic. If this touches payments, add integration tests with the pricing service and snapshot tests for invoice outputs. For production safety, log discount decisions with reason codes so support and engineering can diagnose pricing complaints without guessing.

Framework — Correctness -> maintainability -> risk -> clarity

I review code in layers. First, does it solve the intended problem and preserve correctness? Second, is it maintainable: clear names, reasonable boundaries, no unnecessary complexity, and consistent style? Third, what is the risk: migrations, concurrency, security, performance, backward compatibility, and observability? Fourth, are tests sufficient for the changed behavior? Good code review is not about showing superiority. It should improve the code while preserving team velocity. I separate blocking issues from suggestions. A correctness bug, security issue, or migration risk is blocking. A naming preference or minor refactor can be non-blocking. I also look for missing context: unclear product behavior, untested edge cases, silent failure paths, weak error handling, and lack of metrics around risky changes.

Framework — Context -> options -> tradeoffs -> decision -> outcome

Choose a decision with real tradeoffs: build versus buy, SQL versus NoSQL, monolith versus service, fast patch versus deeper refactor, or strong consistency versus availability. Start with context and constraints, then explain the options you considered. A strong answer names the tradeoff clearly. For example: “Option A let us ship in one week but increased operational burden. Option B took three weeks but removed a scaling bottleneck.” Then explain what evidence drove the decision: traffic, customer deadline, incident history, team capacity, or long-term roadmap. Close with the result and what you learned. If the decision was imperfect, say what you would do differently. Interviewers value mature judgment more than pretending every decision was obvious.

Framework — Incident -> impact -> response -> root cause -> prevention

Use a real incident if possible. Start with the user impact: what broke, who was affected, and how severe it was. Then explain your role in the response: detection, triage, rollback, mitigation, communication, or root-cause analysis. The best answers show calm prioritization. During an incident, restoring service matters more than proving a theory. Mention how you used logs, metrics, traces, feature flags, rollbacks, or dependency checks. After mitigation, explain the root cause and prevention. Good prevention might include better tests, safer rollout, monitoring, alert tuning, runbooks, circuit breakers, backpressure, or migration safeguards. Avoid blaming people. Strong teams improve systems so the same mistake is harder to repeat.

Framework — Shared goal -> constraints -> options -> tradeoffs -> decision

I start by aligning on the user goal and business goal. Many disagreements are not truly about engineering versus product; they are about different assumptions. I would explain the technical constraint clearly: complexity, reliability risk, timeline, maintainability, security, or performance. Then I would propose options instead of just saying no. For example: ship a smaller MVP, use a manual workflow temporarily, hide the feature behind a flag, sequence the technical work, or choose a simpler design that still solves the core user problem. If the tradeoff is serious, I document the options, risks, and recommendation so the decision is transparent. The goal is not for engineering to win. The goal is for the team to make a clear decision with eyes open.