Microsoft Software Engineer (Mid-Level) Interview Preparation Guide 2026

Correlating a frontend performance complaint with backend traces requires the frontend's own timing data to be joined with backend spans through a shared identifier, not just guessed at from backend metrics alone.

The method

1. Real User Monitoring (RUM) in the browser captures actual page-load and interaction timing for real users (not synthetic tests), including navigation timing, resource timing, and any custom spans around the slow interaction.
2. Propagate a correlation ID from the frontend request through to the backend (as a header on the API call the slow page makes), so a specific user's slow page load can be joined to the exact backend trace that served it. Concretely: the frontend attaches a header like traceparent: 00-8f2b1c7d4e...-01 to the API call the slow page makes; the backend reads that same header and logs it as the trace ID on its own span, so a frontend span named pageload.dashboard stitches directly to a backend span named GET /api/dashboard sharing that identifier.
3. Consistent span naming conventions across frontend and backend spans (matching operation names/prefixes) let a single trace view stitch a "page load" frontend span to the backend spans it triggered, rather than requiring manual correlation by timestamp guessing.
4. Sampling strategy: full RUM capture for a sampled percentage of real users, escalated to full detail specifically for sessions that already look slow (a threshold-triggered upgrade in fidelity: a cheap, low-overhead signal runs always-on for every session, and only once a session already looks anomalous does the system escalate to full, expensive-to-collect detail, since capturing full detail for every user by default would be too costly at scale, while waiting until a complaint arrives before capturing anything loses the very data needed to diagnose it).

A related worked instance

A load-balancer misconfiguration causing 502/503s for a subset of users is diagnosed the same way in reverse: correlate the client-visible symptom (which users, which requests) against infra-layer logs/metrics (LB health-check status, backend pool membership) using the same request-level correlation ID, rather than assuming the cause is in application code just because that's where the symptom is visible.

Trade-offs and pitfalls

RUM data can be noisy (real user devices/networks vary far more than a controlled synthetic test), so a single slow session is weak evidence on its own; the technique's value is in aggregating across many correlated frontend-to-backend traces to find a consistent pattern (a specific endpoint, a specific backend service) rather than chasing one anomalous session.

Direct answer. Interface Segregation: don't force a client to depend on methods it doesn't use. Split one large interface into several smaller, role-specific ones so each implementer/consumer only needs to know about the subset that's actually relevant to it.

The problem

A public SDK exposes one large interface:

interface DataStore {
    void read(String key);
    void write(String key, byte[] value);
    void delete(String key);
    void backup();
    void restore();
    void migrateSchema();
}

A client that only ever needs to READ data is still forced to implement (or mock, in tests) write, delete, backup, restore, and migrateSchema -- either as no-ops that silently do nothing (dangerous if accidentally called) or as a large surface a test double has to fully satisfy just to compile.

Splitting the interface

interface DataReader { void read(String key); }
interface DataWriter { void write(String key, byte[] value); void delete(String key); }
interface DataStoreAdmin { void backup(); void restore(); void migrateSchema(); }

class FullDataStore implements DataReader, DataWriter, DataStoreAdmin { /* full implementation */ }

A read-only client now depends on DataReader alone -- its code, its test doubles, and its compile-time contract all shrink to exactly what it uses, and it becomes IMPOSSIBLE (not just unlikely) for that client to accidentally call migrateSchema.

How to decide where the split lines go

Group methods by CONSUMER ROLE, not by implementation convenience: ask 'which distinct kinds of caller need which distinct subset of this surface?' Methods that are always needed TOGETHER by the same callers stay together; methods needed by only a subset of callers split out. Here, ordinary application code needs read/write; only an ops/admin tool needs backup/restore/schema migration -- that's the natural seam.

Trade-offs and pitfalls

• Splitting too finely (one interface per method) recreates the parameter-list problem in a different shape: now callers who genuinely need several related operations have to implement/depend on many tiny interfaces instead of one cohesive one. The goal is role-shaped interfaces, not maximally-fragmented ones.
• A single concrete class can (and often should) implement several of the smaller interfaces at once -- ISP is about how CONSUMERS depend on the surface, not about forcing a 1:1 mapping between interfaces and implementing classes.
• Retrofitting ISP onto an existing large interface used by many callers requires a migration path (extract the smaller interfaces, have the existing large interface EXTEND all of them for backward compatibility, then migrate callers to the smaller ones over time) rather than a breaking change in one release.

Direct answer. A shape-mismatch error tells you two tensors disagreed in dimension somewhere in the forward pass, but the traceback often points at the operation that FAILED, not the operation that introduced the wrong shape several layers earlier, so the debugging process is really about walking the shape forward from the input until it diverges from what you expect.

Step-by-step approach.

1. Print the input shape first, and compare it against what the first layer actually expects. A surprising number of shape bugs are simply "the input isn't shaped the way I assumed," not a bug in the model at all.
2. Use a model summary tool (or manually print .shape after each layer in a quick forward pass) to see the shape at every stage in one pass, rather than binary-searching by commenting out layers one at a time.
3. Add explicit shape assertions inside custom layers, at the point where a specific shape is assumed (assert x.shape[-1] == self.expected_dim, f"got {x.shape}"). This turns a downstream, confusing shape error into an immediate, precisely-located one the next time the bug is triggered, which pays for itself the first time someone else hits a variant of the same bug.
4. Write a small unit test with a known, fixed input shape that exercises just the suspect layer or block in isolation, rather than the whole model, so you can iterate on the fix without paying the cost of a full forward pass through everything else.

A concrete example of why step 1 matters. A very common real case: a model expects batch-first input (batch, seq_len, features) but receives (seq_len, batch, features) from a data loader or a different framework's convention. The shapes are individually valid tensors, nothing crashes until several layers in when a dimension that "coincidentally" matched for a while finally doesn't, at which point the error message points at a layer far from the true cause (the data loader).

The unit test that prevents recurrence. Something as small as:

def test_encoder_output_shape():
    x = torch.randn(4, 10, 32)  # (batch=4, seq_len=10, features=32), the CONTRACT this layer expects
    out = encoder(x)
    assert out.shape == (4, 10, 64), f"expected (4, 10, 64), got {out.shape}"

run in CI on every change to the layer or anything upstream of it, catches this class of bug the moment a shape contract is violated, rather than three deploys later when someone finally notices predictions look wrong.

Direct answer
This is a behavioral question best answered with a specific story showing you distinguished a genuine pattern from a one-off, kept the accountability conversation separate from the group postmortem, and led with coaching rather than punishment, while still being clear about the standard expected going forward.

Structured elaboration
A strong answer covers: the situation (what happened, why it warranted an accountability conversation rather than just the standard blameless process), how you determined it was a genuine pattern rather than bad luck, how you had the conversation itself (privately, focused on support and root cause rather than judgment), and the outcome, including how you protected the person's and the team's trust in future incident reporting.

Worked example
"An engineer on my team was involved in a second incident within two months, both traced to skipping the same pre-deploy verification step under time pressure. Before assuming it was negligence, I checked whether this was a genuine pattern: both incidents shared the same specific gap, so it was, rather than two unrelated issues that happened to involve the same person. I had a private conversation, not as part of the group postmortem, focused on understanding what was driving it. It turned out they'd been covering an unsustainable amount of on-call load for a teammate on leave and had started rushing to keep up. I addressed both sides: the workload issue got fixed by redistributing on-call coverage, which was the real systemic driver, and I paired them with a more experienced engineer on deploy discipline for a few weeks as direct support, framed clearly as investment in them, not punishment. Separately, the second incident's actual group postmortem stayed fully blameless and produced an automated pre-deploy gate that makes that specific step impossible to skip regardless of who's deploying, which is the fix that protects the whole team, not just this one person. Three months later there'd been no recurrence, and, just as important, the engineer's incident-reporting behavior stayed just as open as before, which told me the accountability conversation hadn't damaged their trust in the process."

Trade-offs and pitfalls
The most common weak answer either skips the distinction between pattern and coincidence (treating any second incident as automatic proof of a problem) or focuses entirely on the disciplinary angle without addressing what was actually driving the pattern, which misses the more senior insight that repeated mistakes are frequently a symptom of a systemic issue (workload, unclear process, inadequate training) rather than a character flaw.

Direct answer

Two clean variants exist. Variant 1, in-place, O(1) extra space: a single write-pointer pass that swaps every element satisfying the predicate to the front; O(n) time, O(1) extra space, but does NOT preserve relative order within either group. Variant 2, order-preserving: build two lists (matched, unmatched) in a single pass and concatenate them; O(n) time, O(n) extra space, and DOES preserve relative order. In general, O(1) extra space and stability cannot both be had in O(n) time; achieving both simultaneously needs O(n log n) time instead, the same trade-off behind why C++'s std::stable_partition switches to a slower algorithm specifically when it cannot get extra memory.

Structured elaboration

Variant 1 mechanics (swap-based partition). Maintain a write pointer starting at 0. Scan read from 0 to n-1; whenever predicate(arr[read]) holds, swap arr[write] and arr[read], then increment write. After the scan, everything before write satisfies the predicate and everything from write onward does not, but a swap can move an unmatched element out of its original relative position among other unmatched elements (or vice versa for matched elements).

Variant 2 mechanics. A single pass builds two separate lists, matched and unmatched, in original encounter order, then concatenates them. Correctness is immediate: each list is built purely by appends in scan order, and appends never reorder elements relative to each other within their own list.

Can O(1) space and stability be achieved together? Yes, but not in O(n) time. A divide-and-conquer approach recursively stable-partitions each half of the array, then merges the two halves' now-partitioned matched and unmatched runs using an in-place rotation (rotation itself can be done with O(1) extra space via the three-reversals trick, in time proportional to the rotated range). This gives the recurrence T(n) = 2T(n/2) + O(n), which solves to O(n log n) time with O(1) extra space (or O(log n) if counting recursion-stack space). This mirrors exactly what C++'s standard library documents for std::stable_partition: O(n) swaps when extra memory is available for a temporary buffer, up to O(n log n) swaps if allocation fails and it must fall back to in-place. It is a genuine impossibility result at O(n) time: you cannot have in-place (O(1) space), stable, AND O(n) time simultaneously for a general predicate-based partition; you must give up exactly one of the three.

Worked example

def partition_inplace_unstable(arr, predicate):
    '''O(1) extra space, O(n) time. Relative order NOT guaranteed.'''
    write = 0
    for read in range(len(arr)):
        if predicate(arr[read]):
            arr[write], arr[read] = arr[read], arr[write]
            write += 1

def partition_stable(arr, predicate):
    '''O(n) extra space, O(n) time. Preserves relative order in each group.'''
    matched = [x for x in arr if predicate(x)]
    unmatched = [x for x in arr if not predicate(x)]
    return matched + unmatched

data = [1, 4, 2, 7, 3, 8, 5, 9, 6]  # pinned
is_even = lambda x: x % 2 == 0

unstable_copy = data.copy()
partition_inplace_unstable(unstable_copy, is_even)
print("input                    =", data)
print("unstable in-place result =", unstable_copy)

stable_result = partition_stable(data, is_even)
print("stable (extra space)     =", stable_result)

evens_in_order = [x for x in data if is_even(x)]
odds_in_order = [x for x in data if not is_even(x)]
print("stability check (evens):", stable_result[:len(evens_in_order)] == evens_in_order)
print("stability check (odds): ", stable_result[len(evens_in_order):] == odds_in_order)

evens_after_unstable = [x for x in unstable_copy if is_even(x)]
odds_after_unstable = [x for x in unstable_copy if not is_even(x)]
print("unstable evens order matches original order?", evens_after_unstable == evens_in_order)
print("unstable odds order matches original order? ", odds_after_unstable == odds_in_order)

Output:

input                    = [1, 4, 2, 7, 3, 8, 5, 9, 6]
unstable in-place result = [4, 2, 8, 6, 3, 1, 5, 9, 7]
stable (extra space)     = [4, 2, 8, 6, 1, 7, 3, 5, 9]
stability check (evens): True
stability check (odds):  True
unstable evens order matches original order? True
unstable odds order matches original order?  False

The stable variant preserves order for BOTH groups, as guaranteed. The unstable variant's evens [4, 2, 8, 6] happen to keep their original relative order for this particular input, but the odds group does not: it ends as [3, 1, 5, 9, 7] instead of the original relative order [1, 7, 3, 5, 9]. That asymmetry is instructive: instability is not a guarantee that EVERY group gets scrambled, it is the absence of a guarantee that ANY group stays in order, and this input concretely demonstrates the odds group breaking.

Trade-offs and pitfalls

• The three-way trade-off (space, stability, time) is the deep point of this question: claiming the swap-based partition is "basically the same as the stable one, just in place" misses that the relative-order guarantee is genuinely lost, not merely an implementation detail.
• A common bug is forgetting to swap (writing arr[write] = arr[read] instead) in the O(1)-space version, which overwrites and destroys data rather than reordering it; this only works if discarding the unmatched values is acceptable, otherwise a real swap is required.
• The O(n)-space stable variant needs no swapping subtlety at all; that simplicity is itself a valid engineering argument, plenty of real systems accept O(n) extra space for a partition specifically to keep the code obviously correct.
• Do not assume "in-place" always means "faster": the swap-based version is not asymptotically faster than the two-list version, both are O(n) time, it only saves memory, and if that memory saving is not needed, the added subtlety may not be worth it.

Direct answer
A JUnit 5 suite for fib(n) needs at least six categories: both base cases (n=0, n=1), a typical small value, a negative-input rejection, a duplicate/repeated-call determinism check, and the exact boundary where the result stops fitting a 32-bit signed integer. The overflow boundary is fib(46) (fits) and fib(47) (does not), the implementation should document and enforce which it does on overflow, either an explicit exception or a widened/BigInteger return type, rather than silently wrapping.

Structured elaboration

Choosing n=46/n=47 specifically (rather than "a large n") is what makes case 5 and 6 real boundary tests: fib(46) = 1836311903 <= Integer.MAX_VALUE, and fib(47) = 2971215073 > Integer.MAX_VALUE, so these two inputs are the exact pair that separates "correct" from "must not silently corrupt."

JUnit 5 examples (3 of the 6, executed against a real implementation)

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

class FibonacciTest {
 @Test
 void baseCaseZero() {
 assertEquals(0, Fibonacci.fib(0));
 }

 @Test
 void negativeInputThrows() {
 assertThrows(IllegalArgumentException.class, () -> Fibonacci.fib(-5));
 }

 @Test
 void overflowAtFortySeven() {
 assertThrows(ArithmeticException.class, () -> Fibonacci.fib(47));
 }
}

Implementation, plus the driver that actually invokes it (a JUnit runner was not available in this sandbox, so this is the reproducible equivalent of the three @Test methods above, executed against a real Java JVM):

public class Driver {
 static int fib(int n) {
 if (n < 0) throw new IllegalArgumentException("n must be non-negative");
 if (n == 0) return 0;
 if (n == 1) return 1;
 int a = 0, b = 1;
 for (int i = 2; i <= n; i++) {
 int next = Math.addExact(a, b);
 a = b;
 b = next;
 }
 return b;
 }
 public static void main(String[] args) {
 System.out.println("fib(0) = " + fib(0));
 System.out.println("fib(1) = " + fib(1));
 System.out.println("fib(10) = " + fib(10));
 System.out.println("fib(46) = " + fib(46));
 try { fib(-5); } catch (IllegalArgumentException e) { System.out.println("fib(-5) threw IllegalArgumentException: " + e.getMessage()); }
 try { fib(47); } catch (ArithmeticException e) { System.out.println("fib(47) threw ArithmeticException: " + e.getMessage()); }
 }
}

fib(0) = 0
fib(1) = 1
fib(10) = 55
fib(46) = 1836311903
fib(-5) threw IllegalArgumentException: n must be non-negative
fib(47) threw ArithmeticException: integer overflow

(Cross-checked independently in Python against an exact big-integer reference: fib(46) == 1836311903 and fib(47) == 2971215073, confirming the Java implementation's boundary values are correct, not an artifact of the Java implementation itself.)

Expected overflow behavior
The best practice for an SDET reviewing this API is to insist on explicit, documented overflow behavior rather than "whatever the language happens to do": Math.addExact throwing ArithmeticException is one valid contract; returning long or BigInteger instead of int is another (it moves the boundary far out rather than eliminating it); silently wrapping past Integer.MAX_VALUE is the one behavior that should never ship, since it produces a wrong-looking-right number (fib(47) computed with plain unchecked int addition wraps to a negative value, which at least looks obviously wrong, but a later overflow could wrap back into positive, plausible-looking-but-wrong territory).

Complexity and edge cases
The iterative fib shown is O(n) time and O(1) space (two running variables, no recursion stack); a naive recursive implementation without memoization is O(2^n) time and O(n) stack depth, which is its own distinct edge case (see below). Edge cases: n=0 and n=1 (base cases), a typical small value, n=-5 (negative, must reject), n=46 (last value fitting signed int32), n=47 (first value overflowing it), and repeated calls with the same n (determinism).

Trade-offs & pitfalls
A naive recursive (non-memoized) implementation has its own distinct failure mode, unrelated to integer overflow: stack overflow from recursion depth at moderately large n, well before n=47, so testing "large n" for a recursive implementation actually needs a StackOverflowError test in addition to (not instead of) the arithmetic-overflow tests above. A common mistake is testing only n=50 or another arbitrary "big" value instead of the precise n=46/n=47 pair, which either doesn't reach the boundary at all or overshoots it, missing the exact transition the test is supposed to pin down.

Situation: When I hit a tricky bug that blocks progress or could recur, I treat it as both a technical problem and an opportunity to spread knowledge.

Preparation (before asking):

• Reproduce reliably and capture steps, logs, stack traces, environment, and timeline.
• Narrow the blast radius: isolate a minimal repro or a focused testcase.
• Form a clear hypothesis list (most to least likely) and what I’ve already tried.
• Prepare a short summary (one-pager/slack thread) with links to repro, logs, and branches so peers can review quickly.

Structuring the debugging session:

• Choose format based on scope:
  • Pair debugging (one-on-one) for focused code-level fixes.
  • Mob debugging for cross-cutting issues (infra, APIs, or ambiguous ownership).
  • Show-and-tell for knowledge-sharing after the fix.
• Set agenda and timebox (15–60 minutes): goal, hypothesis, actions, next steps.
• Assign roles: driver (controls IDE), navigator (asks questions/hypothesis), scribe (notes decisions).
• Walk through minimal repro, run experiments live, validate or rule out hypotheses, and agree on an action (patch, revert, rollout plan).

Knowledge transfer and follow-up:

• Open a concise postmortem or incident note with root cause, timeline, and decision rationale.
• Raise a PR with detailed description and link to the session notes; include tests and comments in code.
• Record the session or do a short demo during standup or tech sync.
• Pair the person who will own the code for next-week follow-up and add automated checks to prevent regression.

This approach respects peers’ time, leverages senior experience when needed, and leaves the codebase and team wiser.

Direct answer: Optimal scheduling of dependent tasks across N workers to minimize makespan (total completion time) is NP-hard in general (it's a generalization of job-shop scheduling / multiprocessor scheduling, both classically NP-hard), so exact optimal solutions become computationally infeasible past a small number of tasks. In practice, a greedy heuristic like longest-processing-time-first (LPT) or critical-path-first, combined with respecting the dependency DAG via a topological-order constraint, gives a solution computable in polynomial time (typically O(n log n) for sorting plus O(n + edges) for the scheduling pass) that is provably within a bounded factor of optimal (LPT is within 4/3 of optimal for the classic multiprocessor scheduling problem without dependencies).

Structured elaboration

• Why it's NP-hard: even without any dependencies, minimizing makespan across N identical machines (partitioning tasks into N groups to minimize the maximum group sum) is the classic "multiprocessor scheduling" problem, a well-known NP-hard problem (closely related to the partition/subset-sum problem). Adding a dependency DAG (some tasks must finish before others start) only makes the search space more constrained, not easier - exact solutions require exploring an exponential number of valid orderings/assignments in the worst case.
• Longest-processing-time-first (LPT): sort tasks by duration descending, then greedily assign each task (in that order) to whichever currently-least-loaded worker is idle and dependency-eligible (all its prerequisite tasks are already scheduled/complete). Sorting is O(n log n); the assignment pass is O(n log W) if worker loads are tracked in a heap (W = number of workers), or O(n * W) with a naive scan - either way polynomial, a world apart from exponential exact search.
• Critical-path-first: prioritize tasks that sit on the longest dependency chain (the "critical path" through the DAG) first, since delaying a critical-path task directly delays the whole schedule; tasks off the critical path have more scheduling slack. Computing the critical path is a single O(V+E) pass over the DAG (longest path in a DAG, computable via topological sort plus dynamic programming), making this heuristic's overall cost also polynomial.

Worked example

LPT's classical approximation guarantee (Graham's bound, 1969, for the dependency-free case): the makespan produced by LPT is never worse than $\frac{4}{3} - \frac{1}{3W}$ times the optimal makespan, where W is the number of workers - meaning for a 2-worker case, LPT is guaranteed within roughly 17% of optimal, and this guarantee HOLDS regardless of the specific task durations, without ever needing to compute the true optimal for comparison. Adding dependency constraints breaks this exact bound (LPT with dependencies loses the clean approximation guarantee since a critical-path task might get delayed behind an unrelated long task), but it remains a widely-used, empirically strong heuristic in practice for exactly this reason: polynomial-time and consistently close-to-optimal on realistic task-duration distributions, even without a formal bound in the dependency-constrained case.

Trade-offs & pitfalls

• Recognizing "this is NP-hard" is itself valuable interview signal - it tells you and your team that chasing an exact optimal solution at scale is the wrong investment, and that evaluating heuristics against their approximation guarantees (or empirically, against realistic workloads) is the right frame.
• The dependency DAG constraint means a heuristic must ALSO respect topological ordering, not just balance load - a heuristic that ignores dependencies (like naive LPT without the eligibility check) can produce an invalid or badly-delayed schedule.
• For genuinely small task counts (say under 20-30), exact approaches (integer linear programming, or exhaustive branch-and-bound with pruning) become tractable again and can be worth using when the problem size allows it - "NP-hard" is a worst-case-scaling statement, not a blanket ban on exact methods at small scale.

Direct answer

I treat this as a trade-off, not a knowledge threshold: I ship once I understand the parts that are actually load-bearing for correctness and for whoever maintains this afterward, I explicitly flag whatever I still don't understand at that point rather than hiding it, and I shape the first version to limit how much damage an unknown could cause.

Structured elaboration

• The real question isn't "do I know enough" in the abstract. It's whether I know enough of the parts that matter for this specific decision. I weigh the cost of continuing to study against the cost of the unknown parts causing wrong behavior, against how easily the team that inherits this, including future me, will be able to reason about it later.
• Separate load-bearing unknowns from cosmetic ones. A load-bearing unknown would silently break correctness or be expensive to unwind later; a cosmetic one is something like unfamiliar style conventions or a minor part of the interface I could look up when I need it. Only the first kind should actually block shipping.
• Flag what's still unknown, don't hide it. If something genuinely isn't understood yet at ship time, I say so directly: a comment in the code, a note in the review, or a follow-up item, so it's a visible, tracked risk instead of a silent one that surprises someone later.
• Shape the ship to limit exposure. Smaller surface area, behind a flag (a toggle that turns the new code path on for only a slice of users, so it's cheap to switch back off), easy to reverse, reviewed by someone who does know the tool well: all of these reduce how much damage an unknown can do if I turn out to be wrong about it.

Worked example

Picking up a new library for managing application state under a real deadline, I got comfortable enough with the common patterns within a couple of days but hadn't dug into how it handled a specific edge case around concurrent updates. I decided that edge case was load-bearing, since getting it wrong could cause silent data corruption, so I spent an extra half-day specifically verifying that one behavior with a small isolated test, while deciding I didn't need to fully understand the library's less-common configuration options, since those were cosmetic and easy to look up later if we ever needed them. I shipped behind a flag on a low-traffic part of the product first, and in the code review I explicitly flagged that I hadn't yet tested how the library behaved under our heaviest load, since I hadn't had time to simulate that realistically, and the team agreed that was an acceptable known gap to track rather than block on, given the limited blast radius of where it first shipped.

Trade-offs and pitfalls

The clearest failure on one side is perfectionism: waiting until you feel fully confident before shipping anything, which in practice means never shipping, since real fluency usually only comes from using something for real. The failure on the other side is shipping recklessly without distinguishing which unknowns actually matter, or worse, not flagging them at all, so the team inherits invisible risk they didn't agree to take on. The trade-off only works if the parts you decide are safe to ship with gaps genuinely are cosmetic, and you're honest with yourself, and with reviewers, about which unknowns you're actually still carrying.

The idea

A subsequence keeps characters in their original order but may skip some ("ace" is a subsequence of "abcde"). A palindrome reads the same forwards and backwards. The longest palindromic subsequence (LPS) of a string asks for the longest palindrome you can get by deleting characters. The insight is that the two ends of a stretch of the string either match, in which case both belong to some best answer, or they do not, in which case at least one of them is not used and you can drop it.

DP definition

• State: a window of the string, written by its two ends (i, j).
• One cell: dp[i][j] is the LPS length of the substring s[i..j] (both ends included).
• Recurrence: if s[i] == s[j], dp[i][j] = 2 + dp[i+1][j-1]. Otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
• Base cases: dp[i][i] = 1 (one character), and an empty window (i > j) is 0. For a two-character window with matching ends the inner window is empty and contributes 0, which the code writes as 0 when i + 1 > j - 1.
• Fill order: each cell needs the cell below it, the cell to its left and the cell diagonally below-left, so rows run from i = n-1 up to 0 and columns from left to right. The answer is dp[0][n-1].

Brute force and why it is not enough

Plain recursion on the window (i, j) does exactly the recurrence above without remembering results. When the ends never match, each call spawns two calls on a window one character shorter, so calls follow T(n) = 1 + 2T(n-1) with T(1) = 1, which gives 2^n - 1 for n >= 1 (and one call for the empty string). The run below counts the calls and they match that formula for n = 0 to 10. There are only n(n+1)/2 distinct windows (i, j) with i <= j, so the table needs only that many filled cells (the code allocates the full n*n square, which is the table_cells column below). Remembering results turns exponential into quadratic.

Code

import random


def lps_table(s):
    """dp[i][j] = length of the longest palindromic subsequence of s[i..j]."""
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):          # rows from the bottom up
        dp[i][i] = 1                         # one character is a palindrome
        for j in range(i + 1, n):            # columns left to right
            if s[i] == s[j]:
                inner = dp[i + 1][j - 1] if i + 1 <= j - 1 else 0
                dp[i][j] = 2 + inner
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp


def solve(s):
    """Return (length, one LPS, shortest palindrome that contains s as a subsequence)."""
    n = len(s)
    if n == 0:
        return 0, "", ""
    dp = lps_table(s)
    keep, full, mid = [], [], ""
    i, j = 0, n - 1
    while i <= j:
        if i == j:
            mid = s[i]
            break
        if s[i] == s[j]:                     # matched pair: kept in the LPS
            keep.append(s[i]); full.append(s[i]); i += 1; j -= 1
        elif dp[i + 1][j] >= dp[i][j - 1]:   # drop s[i]; its mirror is an insertion
            full.append(s[i]); i += 1
        else:                                # drop s[j]; its mirror is an insertion
            full.append(s[j]); j -= 1
    lps = "".join(keep) + (mid if mid else "") + "".join(reversed(keep))
    pal = "".join(full) + mid + "".join(reversed(full))
    return dp[0][n - 1], lps, pal


def lcs_length(a, b):
    prev = [0] * (len(b) + 1)
    for x in a:
        cur = [0]
        for k, y in enumerate(b):
            cur.append(prev[k] + 1 if x == y else max(prev[k + 1], cur[k]))
        prev = cur
    return prev[-1]


calls = 0


def brute(s, i, j):
    """Plain recursion on s[i..j], counting every call."""
    global calls
    calls += 1
    if i > j:
        return 0
    if i == j:
        return 1
    if s[i] == s[j]:
        return 2 + brute(s, i + 1, j - 1)
    return max(brute(s, i + 1, j), brute(s, i, j - 1))


def is_subsequence(a, b):
    it = iter(b)
    return all(ch in it for ch in a)


def shortest_palindrome_supersequence_len(s, alphabet):
    """Try every palindrome of length L = n, n+1, ... and test containment."""
    from itertools import product
    n = len(s)
    for length in range(n, 2 * n + 1):
        half = (length + 1) // 2
        for h in product(alphabet, repeat=half):
            p = "".join(h) + "".join(reversed(h[:length // 2]))
            if is_subsequence(s, p):
                return length
    return None


def subsequence_bruteforce(s):
    n, best = len(s), 0
    for mask in range(1 << n):
        t = "".join(s[k] for k in range(n) if mask >> k & 1)
        if t == t[::-1]:
            best = max(best, len(t))
    return best


s = "agbcba"
dp = lps_table(s)
print("table for", s, "(row i, column j, cell = LPS of s[i..j])")
print("    " + " ".join(s))
for i, row in enumerate(dp):
    print(s[i], " ", " ".join(str(v) if j >= i else "." for j, v in enumerate(row)))
length, sub, pal = solve(s)
print("length", length, "| one LPS", sub, "| insertions", len(s) - length, "| palindrome", pal)
print("LCS(s, reverse(s)) =", lcs_length(s, s[::-1]))

print("\nrecursion calls when all letters differ (measured vs 2^n - 1 from T(n) = 1 + 2T(n-1))")
for n in range(0, 11):
    calls = 0
    brute("abcdefghij"[:n], 0, n - 1)
    formula = (2 ** n - 1) if n >= 1 else 1
    print(f"n={n:2d} calls={calls:5d} formula={formula:5d} table_cells={n * n}")

rng = random.Random(41)
checked = 0
for _ in range(400):
    n = rng.randint(0, 9)
    t = "".join(rng.choice("abc") for _ in range(n))
    length, sub, pal = solve(t)
    calls = 0
    assert brute(t, 0, n - 1) == length
    assert subsequence_bruteforce(t) == length
    assert lcs_length(t, t[::-1]) == length
    assert sub == sub[::-1] and len(sub) == length and is_subsequence(sub, t)
    assert pal == pal[::-1] and is_subsequence(t, pal) and len(pal) == 2 * n - length
    if n <= 6:
        assert shortest_palindrome_supersequence_len(t, "abc") == len(pal)
    checked += 1
print("\nchecked", checked, "random strings over abc, lengths 0 to 9: all agree")


def leftmost_positions(t, text):
    """Positions of the characters of t in text, taking the earliest possible each time."""
    pos, start = [], 0
    for ch in t:
        start = text.index(ch, start)
        pos.append(start)
        start += 1
    return pos


def proof_demo(s, common):
    """Show the two groups used in the LCS <= LPS argument for one common subsequence."""
    n = len(s)
    i_pos = leftmost_positions(common, s)
    q_pos = [n - 1 - p for p in leftmost_positions(common, s[::-1])]
    m = next((k for k in range(len(common)) if i_pos[k] >= q_pos[k]), len(common))
    first = sorted(i_pos[:m] + q_pos[:m])
    second = sorted(set(i_pos[m:] + q_pos[m:]))
    print("common subsequence", common, "of", s, "and", s[::-1])
    print("  positions in s from the left :", i_pos)
    print("  positions in s from the right:", q_pos)
    print("  first k (0-based) with i_k >= q_k:", m)
    print("  group before m:", "".join(s[p] for p in first), "at", first)
    print("  group from m on:", "".join(s[p] for p in second), "at", second)
    print("  group lengths", len(first), len(second), "| 2L - 1 =", 2 * len(common) - 1)


def all_subsequences(s):
    n = len(s)
    return {"".join(s[k] for k in range(n) if m >> k & 1) for m in range(1 << n)}


proof_demo("agbcba", "abcba")
t = "abcab"
common = all_subsequences(t) & all_subsequences(t[::-1])
longest = max(map(len, common))
print("\nlongest common subsequences of", t, "and", t[::-1], ":", sorted(x for x in common if len(x) == longest))
print("LPS length of", t, "is", solve(t)[0], "so the lengths agree but not every LCS string is a palindrome")

Output and trace

table for agbcba (row i, column j, cell = LPS of s[i..j])
    a g b c b a
a   1 1 1 1 3 5
g   . 1 1 1 3 3
b   . . 1 1 3 3
c   . . . 1 1 1
b   . . . . 1 1
a   . . . . . 1
length 5 | one LPS abcba | insertions 1 | palindrome agbcbga
LCS(s, reverse(s)) = 5

recursion calls when all letters differ (measured vs 2^n - 1 from T(n) = 1 + 2T(n-1))
n= 0 calls=    1 formula=    1 table_cells=0
n= 1 calls=    1 formula=    1 table_cells=1
n= 2 calls=    3 formula=    3 table_cells=4
n= 3 calls=    7 formula=    7 table_cells=9
n= 4 calls=   15 formula=   15 table_cells=16
n= 5 calls=   31 formula=   31 table_cells=25
n= 6 calls=   63 formula=   63 table_cells=36
n= 7 calls=  127 formula=  127 table_cells=49
n= 8 calls=  255 formula=  255 table_cells=64
n= 9 calls=  511 formula=  511 table_cells=81
n=10 calls= 1023 formula= 1023 table_cells=100

checked 400 random strings over abc, lengths 0 to 9: all agree
common subsequence abcba of agbcba and abcbga
  positions in s from the left : [0, 2, 3, 4, 5]
  positions in s from the right: [5, 4, 3, 2, 0]
  first k (0-based) with i_k >= q_k: 2
  group before m: abba at [0, 2, 4, 5]
  group from m on: abcba at [0, 2, 3, 4, 5]
  group lengths 4 5 | 2L - 1 = 9

longest common subsequences of abcab and bacba : ['aba', 'aca', 'acb', 'bab', 'bca', 'bcb']
LPS length of abcab is 3 so the lengths agree but not every LCS string is a palindrome

Reading the table for "agbcba": dp[0][5] looks at the ends a and a, which match, so it is 2 + dp[1][4]. The window "gbcb" has ends g and b that differ, so dp[1][4] = max(dp[2][4], dp[1][3]) = max(3, 1) = 3 (the 3 is "bcb"). That gives 5, and the reconstruction walk pairs the two a's, skips g (the larger neighbour is dp[2][4], reached by dropping g), pairs the two b's and ends on c, producing "abcba".

Relation to the common-subsequence problem

LPS(s) equals the longest common subsequence (LCS) of s and reverse(s). One direction is easy: a palindrome subsequence P of s equals its own reverse, so it is a subsequence of s and of reverse(s). For the other direction, take a common subsequence T of length L and give each of its characters two positions in s: i_k, where it sits when T is read inside s, and q_k, where it sits when T is read inside the reversed string, translated back to a position in s (so q_k = n - 1 - position in the reversed string). Reading left to right in s the i_k increase; reading left to right in the reversed string means reading right to left in s, so the q_k decrease. Matching characters give s[i_k] = s[q_k].

Concrete case: s = "agbcba", T = "abcba" (L = 5). The i_k are 0, 2, 3, 4, 5 and the q_k are 5, 4, 3, 2, 0, as the proof_demo lines of the output print. Let m be the first k (0-based, here 2) where i_k >= q_k, or m = L if there is none.

• For k before m, i_k < q_k, the i_k increase and the q_k decrease, so the positions i_0 < i_1 < ... < q_1 < q_0 are in order and read T_0 T_1 ... T_1 T_0, a palindrome subsequence of s with 2m characters. Here positions 0, 2, 4, 5 read "abba".
• For k from m on, i_k >= q_k, so the positions q_last < ... < q_m <= i_m < ... < i_last are in order and read the characters in the order T_last ... T_m T_m ... T_last: another palindrome subsequence, with 2(L - m) characters, or one fewer when i_m = q_m (that position is shared). Here positions 0, 2, 3, 4, 5 read "abcba".

Together the groups have 2L characters, or 2L - 1 when i_m = q_m. Two numbers that add to at least 2L - 1 cannot both be below L, so one palindrome subsequence has at least L characters. Hence LPS >= L.

The run confirms the lengths agree on 400 random strings, but the strings differ: for "abcab" the longest common subsequences with its reverse include "acb" and "bca", which are not palindromes, although the LPS length is 3 too. So to print an actual palindrome, rebuild it from the LPS table as the code does, not from an LCS backtrack. The LCS route is still handy when you already have an LCS routine: lcs_length above uses two rows, so it needs O(n) space when only the length is wanted.

Fewest insertions to make the string a palindrome

Characters of s that belong to an LPS already have mirror partners. Every other character needs a new mirror copy inserted, so n - LPS(s) insertions are enough. They are also needed: take any palindrome P that contains s as a subsequence and was made with k insertions. Pair each position of P with its mirror position. The characters of s whose mirror position also holds a character of s form a symmetric set, so they read as a palindrome subsequence of s. Each inserted position is the mirror of just one position, so at most k characters of s lose their mirror to an insertion, which leaves at least n - k characters in that palindrome: n - k <= LPS, so k >= n - LPS. Together: the minimum insertions are exactly n - LPS(s). For "agbcba" that is 6 - 5 = 1 (insert one g before the final a to get "agbcbga"). The walk in solve builds the palindrome: on a skipped end it emits that character on the left and its mirror on the right, which is one insertion. The shipped check compares n minus LPS with an independent brute force that tries every palindrome of length n, n+1, ... over the alphabet and tests whether s is a subsequence of it (for strings up to length 6), and also checks that the rebuilt palindrome has length 2n - LPS and contains s as a subsequence. Insertions may go anywhere in the string.

Complexity

• Time: O(n^2). There are about n^2/2 cells and each is computed in O(1). Reconstruction is one walk of at most n steps.
• Space: O(n^2) for the table, which reconstruction needs. The length alone can be had in O(n) by keeping only the row below. Recursion depth is not an issue because the code is iterative.
• Brute force: 2^n - 1 calls in the worst case (no matching ends), as the table in the output shows. For n = 0, 1 and 2 the counts are 1, 1 and 3.

Edge cases and common mistakes

• Empty string: length 0, subsequence "", no insertions. One character: length 1.
• All letters equal: every pair matches, the LPS is the whole string. Plain recursion is then linear.
• Mistake: confusing subsequence with substring. The longest palindromic substring (contiguous) is a different problem, solvable by expanding around centres (try each of the 2n - 1 possible centres and grow outward while both sides match) in O(n^2) time and O(1) space. Interviews typically ask for the expand-around-centres method; Manacher's algorithm, a linear-time refinement that reuses earlier results, is deeper material.
• Mistake: filling rows top to bottom, so the cell below is still zero when it is read.
• Unnecessary, not wrong: when the ends match, also taking the max with the skip options. It never changes the result, because matching ends can always both be kept.
• Mistake: returning the LCS string of s and reverse(s) as the palindrome.

Running the code

Save the code as lps.py and run python lps.py with Python 3.12. It uses only the standard library, runs in well under a second, and its output is deterministic (seed 41).