Mock 12 — Competitive Style

Interview type: Algorithmic puzzle round (Jane Street, Hudson River, Citadel, Two Sigma, ICPC-style firms; some Google L6+ rounds) Target role: Quant developer, HFT, compiler/optimization, ICPC alumni, top-tier algorithmic teams Time limit: 90 minutes Format: ONE hard algorithmic problem (Codeforces Div 2 D / Div 1 B level) Hints policy: No free hints. A hint is a hard signal of failure. Primary goal: Reach the algorithmic insight under sustained time pressure.

What This Mock Tests

This mock is not about production engineering. It’s about pure algorithmic depth and the ability to think clearly for 90 minutes on a problem with no obvious path.

The kind of problem chosen:

  • Has a clever insight that unlocks the optimal complexity
  • Brute force is far too slow
  • Standard patterns don’t directly apply — you must combine 2–3
  • Implementation is non-trivial but not the bottleneck

Scoring weights: Optimization (#4), Correctness (#5), Complexity (#6), Code Quality (#7) are key. Production / tradeoff dimensions are not relevant — these are not asked.

Pick One Problem

(Pick at random for self-mock. With a partner, they choose.)

Problem A — Maximum Subarray with At Most K Replacements

Given an array a of integers and integer k, you may replace at most k elements with any value. Find the maximum possible sum of any contiguous subarray of the resulting array.

Constraints: 1 ≤ |a| ≤ 2×10^5. -10^9 ≤ a[i] ≤ 10^9. 0 ≤ k ≤ |a|.

Examples:

a = [-3, 4, -2, 5, -1], k = 1 → 11   (replace -2 with, say, 10^9? No — wait)

(Note: replacement values are unconstrained, so this trivializes; the actual problem variant is: removals, or replacements must be 0, or replacements use given budget. The interviewer specifies. For self-mock, use: “replace at most k elements with 0” — then it becomes a real DP.)

Problem B — Count Subarrays with Median ≥ X

Given array a (distinct) and threshold X. Count contiguous subarrays whose median is ≥ X. (Median of even-length: take the right-middle.)

Constraints: 1 ≤ |a| ≤ 2×10^5.

Insight: map each element to +1 if ≥ X, else -1. A subarray’s median is ≥ X iff its sum is positive (for odd length) or ≥ 0 (for even length with right-middle). Reduces to counting subarrays with prefix sum differences satisfying inequalities — Fenwick tree.

Problem C — Minimum Cost to Make Array Strictly Increasing

Given array a, you may increase any element by 1 at cost 1 (cannot decrease). Find minimum total cost to make a strictly increasing.

Constraints: 1 ≤ |a| ≤ 3000. Values fit in int64.

Insight: strict-increasing ↔ define b[i] = a[i] - i; then b must be non-decreasing. Reduces to “min cost to make array non-decreasing using only increases” = sum(max(0, prefix_max - b[i])). Wait — that’s not quite right because we can only increase. Final formula: walk left to right, maintain prev = max(prev + 1, a[i]), cost += prev - a[i].

Problem D — Range Sum with Updates and Range Adds (LC 307 + lazy)

Implement: update(i, x), range_add(l, r, x), query_sum(l, r). All in O(log N).

Constraints: 1 ≤ N ≤ 10^5. ≤ 10^5 operations.

Tool: segment tree with lazy propagation (Phase 3 Lab 02).

Problem E — Maximum XOR of Two Numbers (LC 421)

Given an array a, find max(a[i] XOR a[j]) over all i < j. O(N · 32) time.

Insight: binary trie of all numbers; for each number, greedily traverse to find the maximally-different other number.

Expected Communication Style

For competitive mocks, communication is light but precise:

  1. Restate in one sentence.
  2. Ask 1–2 surgical clarifying questions (constraints, distinct/duplicate, output format).
  3. State a brute force with complexity — proves you understand the problem.
  4. Think aloud about reductions or patterns. (“Median question; +1/-1 transformation; subarray sum; Fenwick.”)
  5. State the optimal complexity and key insight before coding.
  6. Code carefully and minimally. Competitive code can sacrifice some readability for brevity; don’t sacrifice correctness.
  7. Test 1–2 cases including a non-obvious one.

There is no “production discussion” in this format. The interviewer cares about the algorithm and the implementation.

Common Failure Modes

  1. Couldn’t reach the insight in 60 min. Submitted the brute force. Pass-ish for the optimization dimension only if the brute is correct.
  2. Reached the insight but the implementation has bugs that take 20+ min to fix. Need to drill segment tree / Fenwick / DP from Phase 3.
  3. Stuck on the wrong approach for 30+ min. Senior signal: pivot quickly when an approach doesn’t pan out. Articulate the pivot.
  4. Forgot the standard library tool. (Python bisect, C++ lower_bound, etc.) — costs implementation time.
  5. No tests because “I’m confident.” Competitive code is wrong constantly; verify against brute force.

Passing Bar

  • Total score: 49/70 (average 3.5) — lower than other mocks because some dimensions don’t apply
  • Optimal complexity reached (or a serious near-optimal attempt with clear gap analysis)
  • Correct on given examples + at least one boundary case
  • Time ≤ 90 min
  • Algorithm articulated with insight

Follow-up Questions

Competitive-style follow-ups are harder algorithm variants:

For A:

  • Generalize: replace ≤ k elements with values from a given set. → DP becomes more state-heavy.
  • Output the actual subarray and the replacements. → DP with parent pointers.

For B:

  • Median strictly > X. → Adjust the +1/-1 mapping for equality.
  • K-th smallest in every subarray. → Much harder; persistent data structures or offline processing.

For C:

  • Allow decreases at cost 1 too. → Now O(N log N) using slope trick or O(N²) DP.
  • Strictly increasing AND in [L, R] for each element. → Constrained version; more careful greedy.

For D:

  • Add range assign as well as range add. → Two lazy tags; non-trivial composition.
  • Range mode (most frequent element). → Much harder; Mo’s algorithm.

For E:

  • Max XOR of any triple. → Open problem in some formulations; brute O(N²) over pairs + trie for third.
  • Max XOR with values ≤ K (subset). → Persistent trie indexed by element index.

Required Tests

  • All given examples
  • Boundary: N = 1, N = max
  • Adversarial: all same values, sorted, reverse-sorted
  • One stress test against the brute force if time permits (mandatory if you suspect a bug)

Required Complexity Explanation

  • Time, with reasoning
  • Space, with reasoning
  • Bound is tight or improvable?
  • For N = 2×10^5 with O(N log N), expected runtime in seconds (typically < 1 sec)

Self-Evaluation Template

Mock 12 — Competitive Style
Date: _______
Problem: _______
Time: ___ / 90 min

Scores (1–5):
___ Total /70 (note: Tradeoff/Production are N/A; weighted out)

Time to insight: _____ min
Time to first correct implementation: _____ min
Bugs found and fixed: ___

Did I pivot from a wrong approach? Y/N (at minute ___)

Action item:

What to Do If You Fail

  • Couldn’t reach the insight: This is a long-term gap, not a one-mock fix. Solve 30+ Codeforces Div 2 D problems (or LC hards tagged “competitive”) over 2–4 weeks.
  • Reached insight, implementation buggy: Drill Phase 3 (advanced data structures) — your fundamentals leak.
  • Bombed time management: Practice with stricter timers (45 min for problems you’ve already seen).
  • Pass twice consecutively, on different problems, to consider this level handled.

After All 12 Mocks

When you have passed all 12 mocks twice consecutively each, return to the READINESS_CHECKLIST to verify the overall pipeline. The mocks alone do not certify readiness — they verify performance ability. Real interviews additionally test consistency over many rounds and behavioral signals.

Most candidates do not need to pass all 12. Pass the mocks corresponding to your target role:

  • FAANG SWE-II: mocks 01–06
  • FAANG Senior: mocks 01–07, plus 09 (language)
  • FAANG Staff / Principal: mocks 01–10 except 12
  • Quant / HFT / Compiler: mocks 01–04, 09, 11, 12 (heavy on competitive)
  • Backend / Platform (Stripe, Snowflake, Confluent): mocks 01–08, 10, 11