Programming Aptitude Exam Survival Guide

Window: Placement coding tests • Online judges • Tech screens | Components: DS&A • Implementation • Complexity/Debugging • SQL/OOP basics

Must-do topics (80/20)

• Patterns you’ll reuse:
  Arrays/hash (freq maps) • Two pointers • Sliding window (counts/validity) • Prefix/suffix sums • Sort + sweep • Binary search (value & on answer/feasibility) • Greedy (intervals/activities) • Monotonic stack/deque (NGE, histogram, sliding max) • Heap/PQ (k-best, merges) • DSU/Union-Find • Graph: BFS/DFS, shortest paths (BFS/Dijkstra; note: no negatives), topo sort & cycle checks • Trees: traversals, BST invariants, LCA (binary lift optional) • DP (0/1 & unbounded knapsack, LIS, coin change, edit distance, grid paths) • Backtracking (perm/subsets, N-Queens) • Bits (masks, set/clear/test) • Math (gcd, sieve, powmod).
• CS fluency (light): Big-O targets; mutability/refs; recursion depth; memory.
• SQL basics: SELECT→WHERE→GROUP BY→HAVING→ORDER; JOINs (INNER/LEFT/RIGHT/FULL); simple window (ROW_NUMBER, SUM OVER PARTITION).
• OOP/Java/C++/Py quicks: collections vs arrays; hash vs tree maps; strings/immutability; fast I/O.

Top traps (avoid)

• Off-by-one, 0/1-index mix; not handling empty/singleton cases.
• Overflow (32-bit → use 64-bit); float equality checks.
• Greedy without a proven invariant; forgetting to restore state in backtracking.
• Graph: not resetting/marking visited; using Dijkstra with negative weights.
• TLE from O(n2)O(n^2)O(n2) when constraints scream O(nlog⁡n)O(n\log n)O(nlogn).
• Python: using list.pop(0) instead of deque, recursion depth; C++: missing ios::sync_with_stdio(false); / long long; Java: slow I/O, String concatenation (use StringBuilder).

Time split (prep & test)

• Prep week: 50% patterns+impl • 25% timed mixed sets • 15% error-log redo • 10% SQL/OOP.
• Per problem (contest): 2–4 min parse/examples → 20–25 min code → 5–8 min edge tests.

Last-48h checklist

• Write from memory these templates: two-pointers, sliding window (validity loop), binary search on answer, BFS, Dijkstra, DSU, monotonic stack, DP (coin change & LIS), backtracking skeleton.
• Solve 8–12 mixed (2 easy, 6 medium, 2 hard-ish).
• 3 SQL joins (agg + HAVING + simple window).
• Build your edge-case ring (see below) & a 1-page complexity map.

Quick frames & facts (carry card)

• Constraints→Complexity: n ⁣≤ ⁣2⋅105⇒O(nlog⁡n)n\!\le\!2\cdot10^5\Rightarrow O(n\log n)n≤2⋅105⇒O(nlogn) or better; n ⁣≤ ⁣105n\!\le\!10^5n≤105 graphs → adjacency list.
• Binary search on answer: need monotone predicate; move hi/lo accordingly.
• Greedy works when exchange argument or matroid/substructure holds (interval scheduling by earliest finish).
• DSU with path compression + union-by-rank ≈ amortized O(α(n))O(\alpha(n))O(α(n)).
• Shortest paths: BFS (unweighted) • Dijkstra (non-negative) • Bellman-Ford (negatives, small E⋅VE\cdot VE⋅V).
• Mod math: (a±b) mod M(a\pm b)\bmod M(a±b)modM and (a⋅b) mod M(a\cdot b)\bmod M(a⋅b)modM keep mod each step; fast-pow for exponents.
• Testing set: ∅, single, all equal, inc/dec, duplicates, extremes, negatives/zeros, big nnn, already-sorted, impossible case.

Speed tactics (during test)

• Target complexity first, then pick pattern.
• Write a mini I/O harness & print diagnostic on small samples; remove before submit.
• Prefer iterative over deep recursion; pre-size arrays; reuse buffers.
• Backsolve/tight bounds for MCQ variants; use sentinel values to kill branches.

Exam-day mini-plan

• Triage: attempt 1–2 sure problems → bank points.
• For each: restate in own words + design 2–3 self tests → code → run → edge sweep with your ring.
• If stuck >6–8 min in wrong path, reframe pattern (e.g., set → map; DP ↔ greedy).
• Last 10 min: revisit WAs, add bounds/overflow/visited checks.

Practice cycle (weekly)

1. Diagnose: 20 mixed (tag by pattern & failure type: TLE/WA/RE).
2. Deep fix: rebuild the smallest passing template for each tag.
3. Retest: new set under time; compare error tags.
4. Summarize: add 1–2 lines per pattern to your ring (when it fits / when it fails).

Micro-templates (pseudocode)

Binary search (on answer)

lo, hi = min_possible, max_possible

while lo < hi:

  mid = (lo+hi)//2

  if feasible(mid): hi = mid

  else: lo = mid+1

return lo

Sliding window (validity)

l=0; for r in range(n):

  add(a[r])

  while not valid(): remove(a[l]); l+=1

  update_best(l,r)

BFS (shortest steps, unweighted)

q=[s]; dist[s]=0

while q: u=q.pop(0)  # use deque

  for v in adj[u]:

    if dist[v] unvisited: dist[v]=dist[u]+1; q.push(v)

Dijkstra (non-negative weights)

pq=[(0,s)]; dist[*]=INF; dist[s]=0

while pq:

  d,u = heappop(pq)

  if d>dist[u]: continue

  for v,w in adj[u]:

    if d+w < dist[v]: dist[v]=d+w; heappush(pq,(dist[v],v))

DSU (Union-Find)

find(x): parent[x]= (x if parent[x]==x else find(parent[x]))

union(a,b): ra=find(a); rb=find(b)

  if ra!=rb: attach smaller rank under larger; update rank

DP coin change (min coins, unbounded)

dp[0]=0; dp[1..S]=INF

for c in coins:

  for s in c..S:

    dp[s]=min(dp[s], dp[s-c]+1)