Math
Linux
Python DSA
Patterns
Traps
Quick Recall

Counting

nPr = n! / (n-r)!          nCr = n! / (r!(n-r)!)
repeats        = n! / (a! b! c!)   e.g. COOKIE = 6!/2! = 360
circular       = (n-1)!
stars & bars   = C(n+k-1, k-1)    n identical items into k boxes
  • Adjacent/together: glue into one block → count block as 1 letter → multiply by internal arrangements
  • Never adjacent: total − adjacent
  • Derangements: D(3)=2, D(4)=9, D(5)=44
  • BOOLEAN (7 letters, 2 O's): total 7!/2!=2520; O's adjacent=6!=720; never adjacent=1800

Probability

P(A|B) = P(A∩B) / P(B)
P(at least one) = 1 - P(none)
E[X+Y] = E[X] + E[Y]  (linearity, always)
  • "Given that…" = shrink the sample space first. Two dice given at least one 6: 11 outcomes → P(both 6) = 1/11
  • Small cases: just list outcomes. n coins = 2^n, 2 dice = 36
  • 3 coins, ≥2 Heads: {HHH, HHT, HTH, THH} = 4 → P(all 3) = 1/4

Modular Arithmetic

  • Reduce the base first (7 mod 5 = 2), then find the cycle of powers, reduce exponent by cycle length
  • 7^2026 mod 5: 7≡2, cycle 2,4,3,1 (len 4), 2026 mod 4=2 → 2²=4 ✓
Last-digit cycles (mod 10):
2: 2 4 8 6      3: 3 9 7 1      7: 7 9 3 1
4: 4 6          9: 9 1          0,1,5,6: fixed
  • Fermat: a^(p-1) ≡ 1 (mod p) when p is prime and p∤a
  • Div by 3 or 9: digit sum. By 4: last 2 digits. By 11: alternating digit sum

Sets & Pigeonhole

|A∪B| = |A| + |B| - |A∩B|
|A∪B∪C| = sum singles - sum pairs + triple
neither = total - |A∪B|
Pigeonhole: to guarantee k in one box with m boxes → m*(k-1)+1
  • 3 in same day of week: 7 days × 2 + 1 = 15
  • 3 in same month: 12 × 2 + 1 = 25

Recurrences & Complexity

T(n) = T(n/2) + 1      → O(log n)
T(n) = T(n/2) + n      → O(n)
T(n) = 2T(n/2) + n     → O(n log n)   ← merge sort
T(n) = T(n-1) + 1      → O(n)
T(n) = T(n-1) + n      → O(n²)
T(n) = 2T(n-1) + 1     → O(2^n)

For small n just unroll by hand: T(1)=1, T(3)=3T(1)+3=6, T(9)=3×6+9=27

Graphs & Sums

sum of degrees = 2 × edges      (handshake lemma)
tree n nodes = n-1 edges
K_n complete = n(n-1)/2 edges
k-regular on n vertices = nk/2 edges

1+2+…+n = n(n+1)/2
1²+…+n² = n(n+1)(2n+1)/6
2^10=1024  2^16=65536  2^20≈1M  2^30≈1G

Exam Tricks

  • Four options → cross out the absurd two first
  • Words like "always", "only", "never" → usually wrong
  • Longest, most detailed option in a conceptual question → often right
  • For math → plug in n=2 or 3 to test each option

Files & Navigation

ls -la          list all, long      cd -       previous dir
pwd             current dir         mkdir -p a/b/c
cp -r src dst   copy dir            mv a b     move/rename
rm -rf dir      force delete        touch f    create/update time
cat f           print               less f     scroll
head -n 5 f     first 5             tail -n 5  last 5
wc -l f         count lines (-w words, -c bytes)
du -sh *        size of items       df -h      disk free
ln -s tgt lnk   symlink (hard link: no -s)
  • Soft link = pointer to path, breaks if target deleted. Hard link = same inode, survives.
  • Key dirs: /etc config · /var/log logs · /tmp temp · /proc process info · /boot kernel

find

find /etc -name "config.yaml"       by name (-iname case-insensitive)
find . -type f                      files only (-type d = dirs)
find /var/log -mtime -1             modified LESS than 1 day ago
find /var/log -mtime +1             modified MORE than 1 day ago
find . -size +10M                   bigger than 10 MB
find . -perm 755                    exact permissions
find . -name "*.log" -exec rm {} \; run command on each
Trap: -mtime -1 = newer than 1 day · -mtime +1 = older than 1 day

grep

grep "txt" f      match           grep -i   ignore case
grep -r "txt" .   recursive       grep -n   show line numbers
grep -v "txt" f   INVERT          grep -c   count matching lines
grep -l           only filenames  grep -w   whole word
grep -E "a|b"     regex OR        grep -A2 -B2  2 lines after/before

Redirection & Pipes

>      overwrite       >>     append
<      read from file  |      pipe
2>     stderr          2>&1   stderr → where stdout goes
&>     both to file    /dev/null  black hole
tee f  write AND show on screen
cmd > out.txt 2>&1      both stdout+stderr into out.txt
cmd 2>&1 > out.txt      NOT the same: stderr still on terminal
cmd > out.txt 2>/dev/null  stdout to file, errors discarded
  • FDs: 0=stdin, 1=stdout, 2=stderr. 2>&1 → "same place as fd 1"
  • && run if prev succeeded · || only if failed · ; always · $? last exit code

Permissions

r=4  w=2  x=1
chmod 754  → rwx r-x r--
chmod 755  → rwx r-x r-x    chmod 644 → rw- r-- r--
chmod 600  → rw- --- ---    chmod 640 → rw- r-- ---
chmod 777  → rwx rwx rwx
  • ls -l first char: - file · d dir · l symlink
  • Special: setuid 4000, setgid 2000, sticky 1000 (only owner can delete in /tmp)
  • Execute on a directory = permission to cd into it
  • umask 022 → new files 644, new dirs 755

Processes & Signals

ps aux / ps -ef   all procs      top / htop  live
kill 1234         SIGTERM (15)   kill -9     SIGKILL
Ctrl+C = SIGINT(2)  Ctrl+Z = SIGTSTP  Ctrl+D = EOF

SIGHUP 1   SIGINT 2   SIGKILL 9   SIGSEGV 11   SIGTERM 15
SIGKILL & SIGSTOP can NEVER be caught or ignored
  • Zombie (Z): finished, parent never called wait(). Can't kill it—fix the parent.
  • Orphan: parent died first → adopted by PID 1 (init/systemd)
  • fork() returns 0 in child, child's PID in parent, −1 on failure

Networking

MAC=48bit  IPv4=32bit  IPv6=128bit
usable hosts /n = 2^(32-n) - 2    /24=254  /26=62  /30=2
private: 10.0.0.0/8  172.16.0.0/12  192.168.0.0/16
ports: FTP 21  SSH 22  SMTP 25  DNS 53  HTTP 80  HTTPS 443
  • TCP: connection-oriented, ordered, reliable, 3-way handshake SYN→SYN-ACK→ACK
  • UDP: connectionless, no guarantee (DNS, video, games)
  • ARP: IP→MAC · DHCP: assigns IPs · DNS: name→IP · NAT: private→public
  • OSI: 1 Physical · 2 Data Link (MAC, switch) · 3 Network (IP, router) · 4 Transport (TCP/UDP) · 7 Application

Constraint → Complexity

Constraint on nTargetApproach
n ≤ 10O(n!) / O(2^n)Brute force, backtracking
n ≤ 100O(n³–n⁴)Triple loops, grid brute force
n ≤ 1 000O(n²)Double loop, naive simulation
n ≤ 2·10⁵O(n log n)Hashmap, prefix, sort, stack
n ≤ 10⁹O(√n) / O(log n)Formula / math observation
n ≤ 10¹⁸O(1) / O(log n)Formula only. Loop = TLE
n ≤ 10^1000digit workNever int(), work on chars
Python speed: ~10^7 simple ops/sec. 1s limit ≈ 10^7 iterations.

Fast I/O Template

import sys
input = sys.stdin.readline

n = int(input())
n, k = map(int, input().split())
a = list(map(int, input().split()))

# Or read everything at once:
data = list(map(int, sys.stdin.buffer.read().split()))
n, k = data[0], data[1]
a = data[2:2+n]

# Output: never print() in a 10^5 loop
print("\n".join(map(str, ans)))

Python Gotchas

  • // floor div: -7//2 == -4. % never negative for positive modulus.
  • Ints are unbounded — no overflow. 10^1000 fits but a loop over it doesn't.
  • pow(a, b, m) — fast modular exponentiation.
  • math.isqrt(n) — exact integer sqrt. Never use n**0.5 for exact checks.
  • math.gcd, math.lcm, math.comb(n,r), math.factorial
  • s.lstrip("0") or "0" — strip leading zeros safely
  • Building a string with += in a loop = O(n²). Use a list and join.
  • sys.setrecursionlimit(10**6) for deep recursion; prefer iteration.

Essential Patterns

Prefix sum + hashmap (subarray count)

count = defaultdict(int)
count[0] = 1   # ← seed for empty prefix
prefix = 0
for x in a:
    prefix = (prefix + x) % m
    ans += count[prefix]
    count[prefix] += 1

Sliding window (fixed size k)

current = sum(a[:k]); best = current; best_i = 0
for i in range(k, len(a)):
    current += a[i] - a[i-k]
    if current < best:        # strict < for leftmost
        best = current; best_i = i-k+1

Monotonic stack (remove k digits → smallest)

stack = []
for digit in s:
    while k > 0 and stack and stack[-1] > digit:
        stack.pop(); k -= 1
    stack.append(digit)
if k: stack = stack[:-k]
result = "".join(stack).lstrip("0") or "0"

Counting multiples (inclusion-exclusion)

# Divisible by exactly one of a or b up to n:
ans = n//a + n//b - 2*(n//lcm(a,b))

Complexity Quick Ref

ComplexityExamplen=100 000
O(1)Formula✅ Excellent
O(log n)Binary search✅ Excellent
O(n)Single pass✅ Excellent
O(n log n)Sort✅ Fine
O(n²)Nested loops⚠️ Slow
O(n³)Triple nested❌ TLE

Problem Type Catalogue

You seeIt is
count numbers up to 10^18 satisfying…inclusion–exclusion / formula
sum 1−2+3… n up to 10^9pair-up closed form
huge number as stringdigit/greedy logic on chars
how many subarrays with…prefix sum + hashmap
subarray of size k min/maxfixed sliding window
q range updates → final arraydifference array (or naive if tiny)
smallest/largest after removing k digitsmonotonic stack
grid n,m≤100, count squares/patternsbrute force + early exit
repeat until reaches 1/0simulation, watch for cycles
minimum value such that…binary search on answer
T tests each tinyO(1)/O(log) per test + fast IO
pairs (i,j) with i<jhashmap counting / two pointers

Alternating Sum Formula

+1 −2 +3 −4 … up to n terms:

  • Pair: (1−2)+(3−4)+… each pair = −1
  • n even → answer = −n/2
  • n odd → answer = (n+1)/2
pairs = n // 2
remainder = n % 2
ans = -pairs + (n if remainder else 0)

Diagonal Pattern in a Grid

  • Main diagonal of k×k at (r,c): cells (r+t, c+t) for t in 0..k-1
  • Anti-diagonal: cells (r+t, c+k-1-t)
  • Pattern "X" in k×k: diagonals = 1, rest = 0. Total 1s = 2k−1.
  • n,m ≤ 100 → brute force each window, early-exit on first mismatch.

Bit Tricks

x & 1              parity (0=even, 1=odd)
x >> 1             floor divide by 2
1 << k             2^k
x > 0 and x&(x-1)==0  power of 2?
x & -x             lowest set bit
a ^ a = 0, a ^ 0 = a   XOR: finds the single element
bin(x).count("1")  popcount

Key DSA Facts for MCQs

TopicKey fact
BST worst caseSkewed = O(n), not O(log n)
Merge SortAlways O(n log n), stable
Quick Sort worstO(n²) on sorted/reverse input
Call stack structureStack (LIFO)
Starvation riskSRTF (Shortest Remaining Time First)
In-order BSTGives sorted order
Row-major speedCache locality in C/Python
Paging eliminatesExternal fragmentation (not internal)
SIGKILLCannot be caught, blocked or ignored
SQL HAVINGFilters groups (after GROUP BY); WHERE filters rows
2NFRemoves partial dependencies (non-key on part of composite PK)
PUT vs POSTPUT = idempotent, not safe; POST = neither
CSRFExploits browser cookie auto-send to forge requests

WA Traps Checklist

  • 1range(L, R) excludes R. Use range(L, R+1) for inclusive intervals.
  • 2Float division: use // not /. Never compare means with floats—compare integer sums instead.
  • 3Off-by-one: window ends, pre[r+1], inclusive ranges, d[R+1] needs size n+1.
  • 4Seed {0:1} in prefix-sum hashmap problems. Missing this loses subarrays starting at index 0.
  • 5Tie-breaks: use strict < not <= when leftmost/first occurrence must win.
  • 6Fast IO: default input() on 2×10^5 lines can TLE. Use sys.stdin.readline.
  • 7Leading zeros: "".lstrip("0") or "0". Never forget the all-zeros / empty result case.
  • 8Output format: no labels, no debug prints. Spaces vs newlines matter.
  • 9Multiple test cases: reset all variables per test. Don't carry over state.
  • 10Read the sample explanation. It often reveals the intended meaning when the statement is ambiguous.
  • 11Monotonic stack + leftover k: if k removals remain after the scan, trim the last k from the back.
  • 12Painting queries: must be processed in order—later queries overwrite earlier ones.

Preparation Priorities

  • Secure the cheapest code problem first (math/simulation). Don't start with the 250-pointer.
  • Focus on: sliding window, greedy string, 2D arrays, basic simulation
  • MCQ priorities: recurrences, graph degrees, BST complexity, semaphores, Linux permissions
  • 20 min cap per easy problem, 40 per medium. After limit, read the idea—not the code—then solve yourself.

Embedded Systems

V = IR          P = VI
PWM avg = duty × Vcc           (25% of 5V = 1.25V)
ADC step = Vref / 2^bits       (3.3V 12-bit → 0.806 mV)
Vout = Vin × R2/(R1+R2)        (voltage divider)
UART 8N1 = 10 bits/byte        (start + 8 data + stop)
  • volatile: compiler re-reads from memory each access. Does NOT make access atomic.
  • I2C: 2 wires (SDA+SCL), addressed, half-duplex, multi-device via 7-bit address
  • SPI: 4 wires (MOSI/MISO/SCLK/CS), full-duplex, fastest
  • UART: async, TX/RX only, no clock wire
  • Watchdog: resets MCU if firmware stops petting it
  • DMA: moves data without CPU

Web / Security / ML

  • typeof null in JS → "object" (historical quirk)
  • ** in Python is right-associative: 2**3**2 = 2**9 = 512
  • bool(0), bool(''), bool([]) → all falsy → False
  • useEffect: runs side effects after rendering (componentDidMount + Update)
  • Authorization: Bearer <token> header carries JWT/Bearer tokens
  • CSRF: forges authenticated request via victim's browser
  • Stored XSS: script saved on server, injected into every response
  • Ransomware: encrypts files, demands payment
  • Precision = TP/(TP+FP): minimize false positives (spam filter blocking legit mail)
  • Backprop: computes gradient of loss w.r.t. weights using chain rule
  • Unsupervised learning: no labels (clustering, PCA)

Android

  • Lifecycle: onCreate → onStart → onResume → onPause → onStop → onDestroy
  • onStart() = right before activity becomes visible (after onCreate or onRestart)
  • remember { mutableStateOf(...) } = survives recomposition in Compose
  • val = read-only, var = mutable in Kotlin
  • AndroidManifest.xml = declares components, permissions, metadata