American Express Interview Questions (2026): Real Q&A

This is a warm-up question most candidates report finishing in a few minutes, and its only real trap is misreading the input format. Cars contribute four tyres each, bikes contribute two, and the input is usually a count of each vehicle type per dealership, sometimes nested across multiple dealerships that need summing.

int totalTyres(int[] cars, int[] bikes) {
 int total = 0;
 for (int i = 0; i < cars.length; i++) {
  total += cars[i] * 4 + bikes[i] * 2;
 }
 return total;
}

The only thing worth double checking out loud is whether the counts are per dealership or a single flat array, because that assumption changes the loop structure and interviewers do notice if you start coding before confirming it.

Track four shrinking boundaries, top, bottom, left, right, and walk each edge in turn, moving the corresponding boundary inward after each pass. The loop stops once top crosses bottom or left crosses right.

List<Integer> spiralOrder(int[][] matrix) {
 List<Integer> result = new ArrayList<>();
 int top = 0, bottom = matrix.length - 1;
 int left = 0, right = matrix[0].length - 1;
 while (top <= bottom && left <= right) {
  for (int c = left; c <= right; c++) result.add(matrix[top][c]);
  top++;
  for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);
  right--;
  if (top <= bottom) {
   for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
   bottom--;
  }
  if (left <= right) {
   for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);
   left--;
  }
 }
 return result;
}

The bug almost everyone writes on the first try is forgetting the two inner guard checks, which double-count a row or column once the matrix isn't square. Test it on a single row and a single column before you call it done.

A stack backed by a fixed array needs a top pointer, push increments it and writes, pop reads and decrements. The interesting part interviewers ask about is capacity: a fixed array either rejects further pushes once top reaches the array length, or you resize by allocating a new array at roughly double the size and copying over, the same amortized-doubling trick behind ArrayList and Vector at the implementation level.

class ArrayStack {
 private int[] data;
 private int top = -1;

 ArrayStack(int capacity) { data = new int[capacity]; }

 void push(int val) {
  if (top == data.length - 1) {
   data = Arrays.copyOf(data, data.length * 2);
  }
  data[++top] = val;
 }

 int pop() {
  if (top == -1) throw new RuntimeException("Stack is empty");
  return data[top--];
 }
}

BFS explores level by level using a queue, visiting every node at distance k before any node at distance k+1. That property makes it the right tool whenever you need the shortest path in an unweighted graph, or you specifically need to process nodes in order of distance from a source. DFS explores as deep as possible before backtracking, using a stack (explicit or via recursion), which suits problems about reachability, cycle detection, or exhaustive path enumeration where distance from the source doesn't matter.

void bfs(Map<Integer, List<Integer>> graph, int start) {
 Set<Integer> visited = new HashSet<>();
 Queue<Integer> queue = new LinkedList<>();
 queue.add(start);
 visited.add(start);
 while (!queue.isEmpty()) {
  int node = queue.poll();
  for (int neighbor : graph.getOrDefault(node, List.of())) {
   if (!visited.contains(neighbor)) {
    visited.add(neighbor);
    queue.add(neighbor);
   }
  }
 }
}

Rather than scanning all eight winning lines after every move, track running sums per row, column, and both diagonals, incrementing for one player and decrementing for the other on each move. A line is won the instant its running sum hits plus or minus the board size.

int move(int[] rows, int[] cols, int[] diag, int[] antiDiag, int row, int col, int player, int n) {
 int val = player == 1 ? 1 : -1;
 rows[row] += val;
 cols[col] += val;
 if (row == col) diag[0] += val;
 if (row + col == n - 1) antiDiag[0] += val;
 if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n
   || Math.abs(diag[0]) == n || Math.abs(antiDiag[0]) == n) {
  return player;
 }
 return 0;
}

A checked exception extends Exception (but not RuntimeException) and the compiler forces you to either catch it or declare it in the method signature with throws. IOException is the classic example, since any code doing file or network I/O has to acknowledge that failure is possible. An unchecked exception extends RuntimeException, and the compiler doesn't require handling it at all, NullPointerException and IllegalArgumentException are the common ones.

The practical reason this distinction exists: checked exceptions are meant for conditions a caller can reasonably recover from, a missing file, a network timeout, while unchecked exceptions usually signal a programming bug that no amount of catch blocks should paper over.

An abstract class can hold state (instance fields), constructors, and a mix of implemented and abstract methods, and a class can only extend one abstract class. An interface, since Java 8, can have default and static methods with bodies, but no instance fields and no constructors, and a class can implement any number of interfaces.

abstract class Shape {
 protected String color;
 abstract double area();
}

interface Drawable {
 void draw();
 default void highlight() { System.out.println("Highlighting shape"); }
}

class Circle extends Shape implements Drawable {
 double radius;
 double area() { return Math.PI * radius * radius; }
 public void draw() { System.out.println("Drawing circle"); }
}

The single-inheritance limit on abstract classes is usually the deciding factor in a design discussion: reach for an interface when you need a class to satisfy multiple unrelated contracts, and an abstract class when you're sharing real implementation and state across a tight family of related types.

On a variable, final means the reference can't be reassigned after initialization, though if it points to a mutable object, the object's own fields can still change. On a method, final blocks any subclass from overriding it. On a class, final blocks any other class from extending it entirely, String is the best-known example.

final int max = 100; // can't reassign max

class Base {
 final void configure() { } // subclasses can't override this
}

final class Utils { } // no class can extend Utils

Reach for SQL when the data has clear relationships that need to stay consistent, transactions, financial records, anything where a partial write leaving related tables out of sync is unacceptable, and where the schema is reasonably stable. Reach for NoSQL when you need to scale horizontally across many nodes more easily than a relational database typically allows, the data is naturally document-shaped or doesn't fit a fixed schema well, or you're optimizing for very high write throughput over strict cross-record consistency.

In practice, most real systems end up using both, a relational store for the transactional core, a document or key-value store for something like session data or a product catalog, rather than picking one dogmatically for an entire system.

A naive approach with LIMIT and OFFSET after an ORDER BY works but breaks silently if there are duplicate top salaries. DENSE_RANK handles ties correctly by treating equal values as sharing a rank, so the query still returns a meaningful second-highest value even when several employees are tied for first.

SELECT salary AS second_highest_salary
FROM (
 SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
 FROM employees
) ranked
WHERE rnk = 2
LIMIT 1;

This opener is doing more work than it sounds like. Interviewers are listening for a coherent thread, not a chronological resume recitation, why each move made sense given where you were, and why this specific role is the next logical step rather than a random application. Two or three minutes is the right length. Longer than that and you've lost the thread; shorter and it reads like you haven't thought about the connective tissue between jobs.

A generic answer about "a stable company with growth opportunities" is instantly forgettable and interviewers hear it constantly. A specific answer names something concrete, the scale of transaction data the engineering org works with, a product area you've actually used or followed, or a value on the Blue Box list that genuinely resonates with how you already work, and ties it to something you want out of your own next move.

Pick one or two projects, not five, and go deep enough on each that you can answer a follow-up about a specific decision. Breadth without depth here reads as padding, and the interviewer will usually pick whichever project sounded thinnest and ask a pointed question about it.

Give a range grounded in actual market data for the role, level, and location rather than a single number, and be ready to explain briefly where that range came from if asked. Deflecting entirely ("whatever's fair") tends to read as unprepared rather than flexible, and it usually just gets the question repeated in a different form later in the process.

The useless version of this answer is a vague statement about growth. The useful version connects a specific direction, deeper technical specialization, moving toward a design or architecture-focused track, growing into people leadership, to something concrete this specific role would actually let you build toward, so the interviewer can picture the next few years as a coherent story rather than a platitude.

Always have at least two ready, and skip the ones you could answer yourself by reading the job posting. Candidates on Reddit specifically mention asking about team dynamics, what the team is currently struggling with, and the interviewer's own experience at the company as questions that land well, since they signal genuine interest rather than checking a box.

This is the classic decode-ways problem in a candidate-reported wrapper (some reports call it a Death Note style question). It's a one-dimensional dynamic programming problem: at each position, the current digit can stand alone if it's not zero, and it can combine with the previous digit if that two-digit number falls between 10 and 26.

int numDecodings(String s) {
 int n = s.length();
 int[] dp = new int[n + 1];
 dp[0] = 1;
 dp[1] = s.charAt(0) != '0' ? 1 : 0;
 for (int i = 2; i <= n; i++) {
  int oneDigit = s.charAt(i - 1) - '0';
  int twoDigit = Integer.parseInt(s.substring(i - 2, i));
  if (oneDigit >= 1) dp[i] += dp[i - 1];
  if (twoDigit >= 10 && twoDigit <= 26) dp[i] += dp[i - 2];
 }
 return dp[n];
}

The interviewer follow-up almost always targets the zero case: a lone zero has no valid single-digit decoding, it can only exist as the second half of 10 or 20. Get that wrong and the whole recurrence silently produces the wrong count for any string containing a zero.

Treat the array as a graph problem in disguise. Pair each value with its target sorted position, then find cycles in that mapping. A cycle of length k needs k minus 1 swaps to resolve, so the total answer is the sum of (cycle length minus 1) across every cycle.

int minSwaps(int[] arr) {
 int n = arr.length;
 int[][] indexed = new int[n][2];
 for (int i = 0; i < n; i++) indexed[i] = new int[]{arr[i], i};
 Arrays.sort(indexed, (a, b) -> a[0] - b[0]);
 boolean[] visited = new boolean[n];
 int swaps = 0;
 for (int i = 0; i < n; i++) {
  if (visited[i] || indexed[i][1] == i) continue;
  int cycleSize = 0;
  int j = i;
  while (!visited[j]) {
   visited[j] = true;
   j = indexed[j][1];
   cycleSize++;
  }
  swaps += cycleSize - 1;
 }
 return swaps;
}

Candidates who reach for a naive bubble-sort swap count get an answer that's technically correct for that one algorithm but doesn't generalize, and interviewers usually ask directly whether your solution is the minimum, not just a valid one.

The sequence is an arithmetic progression with a first term of 2 and a common difference of 10, so the nth term is simply 10 times (n minus 1) plus 2. The candidate-reported version of this question isn't testing whether you can derive the formula, most people spot the pattern in seconds, it's testing whether you handle large n without overflow and validate the input.

long nthTerm(long n) {
 if (n < 1) throw new IllegalArgumentException("n must be positive");
 return 10 * (n - 1) + 2;
}

Some variants of this question extend it to a general "numbers ending in digit d" family, which is worth asking about explicitly since the formula changes shape depending on whether d is itself a valid trailing digit under the base you're working in.

Detection uses Floyd's cycle-finding algorithm, two pointers moving at different speeds that must meet inside the cycle if one exists. Removal is the part interviewers push on: once you've found the meeting point, reset one pointer to the head and advance both one step at a time. Where they meet again is the cycle's entry node, and you break the cycle by setting that node's predecessor's next pointer to null.

void detectAndRemoveCycle(ListNode head) {
 ListNode slow = head, fast = head;
 boolean hasCycle = false;
 while (fast != null && fast.next != null) {
  slow = slow.next;
  fast = fast.next.next;
  if (slow == fast) { hasCycle = true; break; }
 }
 if (!hasCycle) return;
 slow = head;
 ListNode prev = null;
 while (slow != fast) {
  prev = fast;
  slow = slow.next;
  fast = fast.next;
 }
 prev.next = null;
}

The proof of why the meeting point after resetting one pointer lands exactly on the cycle's entry is a nice piece of math, but most interviewers are satisfied if you can state the algorithm correctly and reason about why two pointers moving at different speeds must eventually coincide inside a finite cycle.

This is a sliding window with a frequency map capped at two distinct keys. Expand the right edge, tracking counts per fruit type. The moment a third distinct type appears, shrink from the left, decrementing counts and removing a key entirely once its count hits zero, until only two distinct types remain.

int totalFruit(int[] fruits) {
 Map<Integer, Integer> count = new HashMap<>();
 int left = 0, maxLen = 0;
 for (int right = 0; right < fruits.length; right++) {
  count.merge(fruits[right], 1, Integer::sum);
  while (count.size() > 2) {
   int leftFruit = fruits[left];
   count.merge(leftFruit, -1, Integer::sum);
   if (count.get(leftFruit) == 0) count.remove(leftFruit);
   left++;
  }
  maxLen = Math.max(maxLen, right - left + 1);
 }
 return maxLen;
}

The naive check-every-pair approach is O(n squared). The stack-based approach candidates report being asked for gets it down to O(n). Push every person onto a stack, then repeatedly pop two off and eliminate one based on the knows relationship: if A knows B, A can't be the celebrity, discard A; otherwise discard B. Keep going until one person remains, then verify that candidate against everyone else, since the elimination process finds at most one valid candidate but doesn't confirm it.

int findCelebrity(int[][] knows, int n) {
 Deque<Integer> stack = new ArrayDeque<>();
 for (int i = 0; i < n; i++) stack.push(i);
 while (stack.size() > 1) {
  int a = stack.pop();
  int b = stack.pop();
  if (knows[a][b] == 1) stack.push(b);
  else stack.push(a);
 }
 int candidate = stack.pop();
 for (int i = 0; i < n; i++) {
  if (i != candidate && (knows[candidate][i] == 1 || knows[i][candidate] == 0)) {
   return -1;
  }
 }
 return candidate;
}

This isn't a trick question, it's the interviewer checking whether you actually built and operated the thing you're claiming credit for, versus describing an architecture diagram you inherited. A strong answer names the specific services involved, how they communicated (REST, a message queue, gRPC), what happened when a downstream dependency was slow or down, and what you monitored to know something had broken before a customer told you.

If you listed microservices on your resume, be ready to say whether calls were synchronous or asynchronous, how you handled a partial failure (retries, circuit breakers, a dead-letter queue), and how you'd scale the weakest link if traffic tripled overnight. Candidates who can only describe the happy path here get pushed hard on the failure scenarios, and that's usually where the round is actually decided.

A collision happens when two different keys hash to the same bucket index. Java's HashMap resolves this with separate chaining: each bucket holds a linked list (or, since Java 8, a red-black tree once a bucket's chain grows past a threshold, currently 8 entries) of all key-value pairs that landed there, and a lookup walks that chain comparing keys with equals() until it finds a match or exhausts the list.

The tree conversion matters because a pathological key set that collides constantly would otherwise degrade every lookup in that bucket to O(n). Treeifying the bucket brings worst-case lookup for that bucket down to O(log n) instead. It only kicks in once the map's overall capacity is at least 64, since below that the map just resizes instead.

Inversion of Control flips who's responsible for creating and wiring an object's dependencies. In ordinary code, a class creates the objects it depends on directly, new OrderRepository() sitting inside an OrderService constructor, say. Under IoC, that responsibility moves to an external container: the class just declares what it needs, and something else, a Spring application context, for instance, constructs and hands over the dependency.

class OrderService {
 private final OrderRepository repository;

 // repository is injected, not constructed here
 OrderService(OrderRepository repository) {
  this.repository = repository;
 }
}

Dependency injection is the specific mechanism most frameworks use to implement IoC, injecting dependencies through a constructor, a setter, or field injection. The payoff is testability: swap in a mock OrderRepository in a unit test without touching OrderService's own code at all.

The JVM tracks reachability from a set of GC roots, active thread stacks, static fields, JNI references, and anything not reachable from a root is eligible for collection. Most collectors split the heap into a young generation, where new objects are allocated and most die quickly, and an old generation, where long-lived objects get promoted after surviving several young-generation collections.

Minor GCs clean the young generation frequently and cheaply. Major (or full) GCs sweep the old generation too and cost noticeably more, which is why a service with unexpected latency spikes is often diagnosed by checking GC logs for full-GC frequency before looking anywhere else. G1GC is the default collector on modern JVMs and aims to bound pause times rather than optimize purely for throughput.

A process has its own isolated memory space, its own heap, and its own set of OS resources, so two processes can't directly read each other's variables. A thread lives inside a process and shares that process's heap and memory space with every other thread in it, which is exactly why race conditions exist for threads and not, in the same way, for separate processes.

For a Java application, this is the whole reason shared mutable state needs explicit synchronization: two threads in the same JVM process can read and write the same object concurrently, and nothing stops them from doing it at the exact same instant unless you add a lock, an atomic type, or an immutable design that sidesteps the problem entirely.

This is a window function question, reported specifically from American Express data engineering interviews. A window frame of the current row plus the six preceding rows, ordered by date, gives the trailing 7-day average without any self-join or subquery per row.

SELECT
 transaction_date,
 daily_volume,
 AVG(daily_volume) OVER (
  ORDER BY transaction_date
  ROWS BETWEEN 6 PRECEDING AND CURRENT ROW
 ) AS rolling_7day_avg
FROM daily_transactions
ORDER BY transaction_date;

The follow-up worth being ready for: what happens for the first six days of data, before a full 7-day window exists. The frame just uses however many preceding rows are actually available, so the early averages are computed over a shorter window rather than erroring out, which is worth calling out explicitly since it can look like a bug if a stakeholder isn't expecting it.

Atomicity means a transaction is all-or-nothing, either every statement in it commits or none do. Consistency means a transaction can only move the database from one valid state to another, respecting constraints and triggers. Isolation means concurrent transactions don't see each other's uncommitted intermediate state. Durability means once a transaction commits, it survives a crash immediately after.

A funds transfer is the standard example that makes atomicity concrete: debiting one account and crediting another has to happen as a single unit. If the debit commits but the credit fails and the transaction isn't rolled back atomically, money disappears from the system entirely, which is exactly the failure mode that ACID guarantees are designed to prevent.

Any index speeds up reads that filter or sort on the indexed column, since the database can use a B-tree lookup instead of a full table scan. The same index slows down every write to that table, because an insert, update, or delete now also has to update the index structure, not just the underlying row.

The decision comes down to read-to-write ratio and query patterns. Add an index to columns that show up often in WHERE clauses, JOIN conditions, or ORDER BY on a table that's read far more often than it's written. Skip indexing columns on a write-heavy table unless a specific slow query actually demands it, and check the query plan (EXPLAIN) before assuming an index will help, since the optimizer sometimes ignores an index anyway if the table is small enough that a full scan is cheaper.

The first move is confirming scope before touching anything: is this one table or the whole pipeline, and has anything downstream already consumed bad or missing data. Check the pipeline's own logs and monitoring for the actual failure point rather than guessing, a schema change upstream, a silent API timeout, a job that failed and didn't alert.

Once the cause is clear, the fix usually splits into two parts: stop the bleeding (pause downstream consumers if they're reading incomplete data, or roll back to the last known-good state) and then backfill correctly once the root cause is patched. The part interviewers actually listen for is whether you mention adding a monitoring check or an alert afterward so the same failure doesn't silently repeat, since fixing the immediate incident without addressing detection just guarantees a repeat.

This maps directly to Customer Commitment, and interviewers are listening for whether you sought the feedback proactively or only reacted once someone else escalated it to you. A strong answer names the specific signal (a support ticket pattern, a usage metric that dropped, a direct complaint), the concrete change you made because of it, and what you measured afterward to confirm the change actually helped rather than just assuming it did.

The weak version of this answer stops at "we got feedback and fixed it." The strong version explains the judgment call: why you believed that particular piece of feedback was worth acting on immediately versus adding to a backlog, since not every complaint deserves the same urgency.

This one's checking Teamwork and Respect for People at the same time. Interviewers want to hear how you disagreed, not just that you did, whether you brought data or reasoning rather than just asserting an opinion more loudly, whether you were willing to be wrong once you heard the other side, and what actually happened to the decision. If every story you tell ends with "and I turned out to be right," that's a signal worth noticing about yourself before the interview, not during it.

The honest answer here acknowledges the uncertainty rather than pretending you had more confidence than you did. Name what information was missing, why waiting for it wasn't an option, what you used instead, a smaller test, a domain expert's judgment, a reasonable default, and what you'd have done differently if the outcome had gone the other way. Interviewers read overconfidence in this answer as a risk signal, not a strength, especially at a company operating in a regulated financial environment where a wrong guess has real cost.

This tests Personal Accountability directly, and it's one of the few behavioral questions where picking a genuinely small, low-stakes mistake actually hurts you. Interviewers want to see that you can own something that mattered, without spending the whole answer on self-flagellation or, worse, quietly shifting blame onto a teammate or a vague "the process failed" while narrating your own role in the third person.

The part that actually differentiates candidates is the after: what specifically changed in how you work because of it, a new habit, a check you added, a conversation you now have earlier than you used to. Without that, the story is just an apology, and interviewers have heard plenty of those.

Innovative doesn't have to mean a novel algorithm or a patent. A strong answer here is often something unglamorous, automating a manual deploy step that ate an hour every release, introducing a linting rule that caught a recurring bug class before it shipped, restructuring how a team ran code review to cut turnaround time. Interviewers are checking whether you notice friction and act on it without being told to, not whether the solution sounds impressive on a slide.

The useful part of this answer is the reasoning behind the prioritization, not just the outcome. Name what the two competing things actually were, what factors you weighed (business impact, how reversible a delay was, who else was blocked waiting on each), who you communicated the trade-off to and when, and whether the deprioritized item ended up costing more than expected once it slipped. A candidate who says "I just worked extra hours to do both" usually gets a follow-up asking what happens the next time that isn't sustainable, since it isn't a repeatable answer.

Frame this around what you're moving toward, not what you're escaping. Even a legitimately bad situation at a current employer is better described in terms of what you want next (more ownership, a different tech stack, a bigger scale problem) than as a list of complaints, since the second version makes an interviewer wonder what you'll say about American Express in the same seat two years from now.

A candidate who's done real homework can talk about American Express operating a closed-loop payment network, meaning it acts as both card issuer and payment processor rather than routing transactions through a separate bank-owned network the way Visa and Mastercard typically do, plus its merchant services and corporate travel and expense product lines. You don't need financial-analyst depth here, but naming one specific fact beyond "they make credit cards" signals you actually looked the company up instead of applying on autopilot.

This one, reported from candidate write-ups of the American Express coding round, stacks two separate checks: primality of the number itself, and primality of its digit sum. Neither check alone is expensive, but doing both for every candidate above N inside a tight time limit is where people lose points.

boolean isPrime(long n) {
 if (n < 2) return false;
 for (long i = 2; i * i <= n; i++) {
  if (n % i == 0) return false;
 }
 return true;
}

int digitSum(long n) {
 int sum = 0;
 while (n > 0) { sum += n % 10; n /= 10; }
 return sum;
}

long kthGoodPrime(long start, int k) {
 long candidate = start + 1;
 int found = 0;
 while (true) {
  if (isPrime(candidate) && isPrime(digitSum(candidate))) {
   found++;
   if (found == k) return candidate;
  }
  candidate++;
 }
}

Trial-division primality is fine here since digit sums stay small and the search window candidates report is modest, but say out loud that you'd swap in a sieve if N were large enough to make per-number trial division too slow. That's the sentence interviewers are actually listening for.

A brute-force scan of every window is O(n·k), which is fine for a small OA but fails the larger hidden test cases candidates report running into. The efficient approach uses a monotonic deque that keeps indices in increasing order of value, so the front of the deque is always the minimum for the current window.

int maxOfMins(int[] arr, int k) {
 Deque<Integer> deque = new ArrayDeque<>();
 int result = Integer.MIN_VALUE;
 for (int i = 0; i < arr.length; i++) {
  while (!deque.isEmpty() && arr[deque.peekLast()] >= arr[i]) deque.pollLast();
  deque.addLast(i);
  if (deque.peekFirst() <= i - k) deque.pollFirst();
  if (i >= k - 1) result = Math.max(result, arr[deque.peekFirst()]);
 }
 return result;
}

The interviewer follow-up worth anticipating is why a simple sliding-window minimum with a plain queue doesn't work. It doesn't, because a naive queue can't efficiently discard values that are no longer the minimum once a smaller one enters the window, which is exactly the gap the monotonic deque closes.

Full sort gets you the answer in O(n log n) and is a fine starting point to state out loud, but the follow-up candidates report getting is to do better. Quickselect, a partition step borrowed from quicksort, finds the kth smallest in average O(n) by only recursing into the half of the array that actually contains the target rank, discarding the other half entirely instead of sorting it.

int quickSelect(int[] arr, int left, int right, int k) {
 int pivot = arr[right];
 int i = left;
 for (int j = left; j < right; j++) {
  if (arr[j] < pivot) { swap(arr, i, j); i++; }
 }
 swap(arr, i, right);
 if (i == k) return arr[i];
 return i < k ? quickSelect(arr, i + 1, right, k) : quickSelect(arr, left, i - 1, k);
}

Mention that worst-case Quickselect degrades to O(n squared) on an adversarial pivot choice, and that a median-of-medians pivot selection fixes the worst case at the cost of a bigger constant factor. Most interviewers don't expect you to implement median-of-medians live, just know it exists as the answer to "can you guarantee worst-case linear time."

A plain binary search breaks because the array isn't fully sorted, but at every step, at least one half of the current range is still sorted. Determine which half is sorted by comparing the endpoints, then check whether the target falls inside that sorted half's range. If it does, search there; otherwise search the other half.

int search(int[] nums, int target) {
 int left = 0, right = nums.length - 1;
 while (left <= right) {
  int mid = left + (right - left) / 2;
  if (nums[mid] == target) return mid;
  if (nums[left] < nums[mid]) {
   if (nums[left] <= target && target < nums[mid]) right = mid - 1;
   else left = mid + 1;
  } else if (nums[left] > nums[mid]) {
   if (nums[mid] < target && target <= nums[right]) left = mid + 1;
   else right = mid - 1;
  } else {
   left++;
  }
 }
 return -1;
}

Duplicates are the part that trips people up in the moment: when the left, mid, and right values are all equal, you can't tell which side is sorted, so the only safe move is to shrink the range by one from the left and re-check, which degrades worst-case time to O(n) instead of O(log n). Say this out loud, it's exactly the trade-off interviewers are checking for.

synchronized enforces mutual exclusion on a block of code or a whole method, so only one thread can hold the associated monitor lock at a time. Without it, two threads incrementing a shared counter can interleave in a way that loses an update, since count++ is really three separate steps (read, increment, write) and a thread switch between any of those steps corrupts the result.

class Counter {
 private int count = 0;

 synchronized void increment() {
  count++;
 }

 synchronized int get() {
  return count;
 }
}

The cost is contention: every thread that wants the lock has to wait for whoever holds it, so synchronized on a hot path can become a throughput bottleneck. That's usually the follow-up, whether you know alternatives like AtomicInteger for simple counters, or finer-grained locking (ReentrantReadWriteLock, or splitting one big lock into several smaller ones guarding independent pieces of state) once a single synchronized block starts showing up in a profiler.

The single most common cause is a filter condition on the right-hand table sitting in the WHERE clause instead of the JOIN's ON clause. A LEFT JOIN is supposed to keep every row from the left table even when there's no match on the right, filling unmatched columns with NULL. But if the WHERE clause then filters on a right-table column, say WHERE orders.status = 'shipped', every row where the join produced NULLs for that column (because there was no matching order at all) gets silently excluded, since NULL never satisfies an equality comparison. That converts what looks like a LEFT JOIN into the behavior of an INNER JOIN without anyone intending it.

-- Wrong: silently drops customers with no orders
SELECT c.customer_id, o.order_id
FROM customers c
LEFT JOIN orders o ON c.customer_id = o.customer_id
WHERE o.status = 'shipped';

-- Correct: filter belongs in the join condition
SELECT c.customer_id, o.order_id
FROM customers c
LEFT JOIN orders o ON c.customer_id = o.customer_id AND o.status = 'shipped';

Moving that filter into the ON clause is the fix. It preserves every customer row, including ones with zero shipped orders, showing NULL for order_id instead of disappearing from the result set entirely.

Start with EXPLAIN (or EXPLAIN ANALYZE) before changing anything, since guessing at the bottleneck on tables this size wastes time you don't have during an incident. Look specifically for a sequential scan where an index scan should be happening, a join order the optimizer picked that doesn't match the actual selectivity of your filters, or a type mismatch between the join columns that silently defeats an existing index.

If the index situation checks out and the query is still slow, the next lever is usually reducing the working set before the join happens at all, filtering each side down with its own WHERE clause first rather than joining the full tables and filtering afterward, or partitioning the larger table by date or another natural key so the query only scans the relevant partition instead of the whole table. For a genuinely huge, frequently-run aggregate query, a materialized view refreshed on a schedule is often the more honest fix than trying to make the live join faster every single time it runs.

The core is a many-to-many relationship between students and courses, which needs a junction table rather than a foreign key on either side. Students has student_id, name, and contact fields. Courses has course_id, title, and credit_hours. Enrollment sits between them with student_id and course_id as a composite key, plus enrollment-specific attributes like semester and grade that don't belong on either parent table.

CREATE TABLE students (
 student_id INT PRIMARY KEY,
 name VARCHAR(100),
 email VARCHAR(100) UNIQUE
);

CREATE TABLE courses (
 course_id INT PRIMARY KEY,
 title VARCHAR(200),
 credit_hours INT
);

CREATE TABLE enrollments (
 student_id INT REFERENCES students(student_id),
 course_id INT REFERENCES courses(course_id),
 semester VARCHAR(20),
 grade CHAR(2),
 PRIMARY KEY (student_id, course_id, semester)
);

The follow-up worth anticipating is what happens when a student retakes a course. Including semester in the composite key is what allows a second enrollment row for the same student-course pair without violating uniqueness.

A PUT to /customers/{id}/address that fully replaces the address resource is idempotent by definition: sending the same request twice leaves the system in the same state as sending it once. That matters specifically because clients retry on timeouts. If the first request actually succeeded but the response got lost in transit, a non-idempotent endpoint like a naive POST that appends a new address record would leave duplicate data behind after the client's automatic retry.

@PutMapping("/customers/{id}/address")
ResponseEntity<Void> updateAddress(@PathVariable String id, @RequestBody Address address) {
 customerService.replaceAddress(id, address);
 return ResponseEntity.noContent().build();
}

An ArrayList alone gives O(1) insert (append) and O(1) random access by index, but delete by value is O(n) unless you know the index. A plain HashMap gives O(1) delete by key but has no notion of index for random selection. The trick candidates report being asked for combines both: a HashMap mapping value to its index in a backing ArrayList, and on delete, swap the element to remove with the last element in the list, update the swapped element's index in the map, then pop the last slot. That keeps every operation O(1) because nothing in the middle ever has to shift.

class RandomizedSet {
 private List<Integer> values = new ArrayList<>();
 private Map<Integer, Integer> indexOf = new HashMap<>();
 private Random random = new Random();

 boolean insert(int val) {
  if (indexOf.containsKey(val)) return false;
  indexOf.put(val, values.size());
  values.add(val);
  return true;
 }

 boolean remove(int val) {
  if (!indexOf.containsKey(val)) return false;
  int idx = indexOf.get(val);
  int last = values.get(values.size() - 1);
  values.set(idx, last);
  indexOf.put(last, idx);
  values.remove(values.size() - 1);
  indexOf.remove(val);
  return true;
 }

 int getRandom() {
  return values.get(random.nextInt(values.size()));
 }
}

Model spots as a class with a size (compact, large, motorcycle) and an occupied flag, grouped by floor. A ParkingLot class owns a collection of floors and exposes park and leave operations. The interesting design decision, and the one candidates report interviewers pushing on, is concurrency: two cars arriving at the same moment shouldn't both be assigned the last open compact spot.

A simple fix is a lock (or a database-level row lock, if spot availability lives in a table) scoped to the specific spot being reserved, not the entire lot, so two allocations for different spots don't block each other unnecessarily. For scale, sharding spot availability by floor or by zone reduces lock contention further, and a queue at the entrance gate smooths bursts of arrivals instead of having every car hit the allocation logic simultaneously. Whether you need any of that depends entirely on the assumed scale, and saying that out loud before diving into a solution is part of what a senior answer looks like here.