INTERVIEW PREP

MASTER STUDY GUIDE

Data Structures & Algorithms • Software Engineering
Machine Learning & GenAI • Logical Reasoning
 SECTION 1: DATA STRUCTURES & ALGORITHMS

1. Sorting Algorithms

1.1 Quick Sort — Deep Dive

Quick Sort is a divide-and-conquer algorithm that picks a pivot and partitions the array around it. Average time
complexity: O(n log n). Worst case: O(n²) when the pivot is always the smallest or largest element.

Partition Schemes
① Lomuto Partition Scheme
Pivot = last element. Maintains a pointer i for the 'smaller region'. Scans left to right, swapping elements ≤ pivot
into the smaller region.

def lomuto_partition(arr, low, high):

pivot = arr[high] # pivot is LAST element
i = low - 1 # i tracks end of smaller-region
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1] # place pivot
return i + 1 # return pivot's final index

② Hoare Partition Scheme

Pivot = first element (or middle). Uses two pointers moving inward. More efficient in practice (fewer swaps). Note:
pivot is NOT necessarily at the returned index.

def hoare_partition(arr, low, high):

pivot = arr[low] # pivot is FIRST element
i = low - 1
j = high + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j # j is partition index (NOT pivot pos)
arr[i], arr[j] = arr[j], arr[i]

Pivot Selection Strategies

Strategy Pros Cons Best For
Last element Simple to implement O(n²) on sorted arrays Random / unsorted data
First element Simple O(n²) on sorted arrays Rarely recommended
 Random pivot Avoids worst-case RNG overhead General purpose
reliably
Median-of-3 Better balance in Extra comparisons Production code
practice
Median-of-medians Guaranteed O(n log n) High constant factor Theoretical guarantee

Quick Sort — Full Implementation

def quicksort(arr, low, high):
if low < high:
pi = lomuto_partition(arr, low, high)
quicksort(arr, low, pi - 1)
quicksort(arr, pi + 1, high)

# Call: quicksort(arr, 0, len(arr)-1)

⚡ Quick Sort — Interview Key Points

• Average: O(n log n) | Worst: O(n²) | Space: O(log n) stack space

• Lomuto: simpler code, slightly more swaps; Hoare: fewer swaps, harder to get right

• 3-way partition (Dutch National Flag) handles duplicates in O(n) on all-same arrays

• In-place algorithm — no auxiliary array needed

• Not stable — equal elements may change relative order

1.2 Heap Sort — Deep Dive

Heap Sort builds a Max-Heap from the array, then repeatedly extracts the maximum. Guaranteed O(n log n) — no
worst case degradation. Not stable, but in-place.

Step 1 — Build Max Heap (Bottom-up Heapify)

Start from the last non-leaf node (index = n//2 - 1) and call heapify downward. This runs in O(n) — NOT O(n log n)
as intuition might suggest.
def heapify(arr, n, i):
largest = i # assume root is largest
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]: largest = left
if right < n and arr[right] > arr[largest]: largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest) # recursively fix the affected subtree

Step 2 — Heap Sort

def heap_sort(arr):
 n = len(arr)
# BUILD MAX HEAP — O(n)
for i in range(n // 2 - 1, -1, -1): # last non-leaf → root
heapify(arr, n, i)
# EXTRACT MAX one by one — O(n log n)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # move current max to end
heapify(arr, i, 0) # restore heap on reduced array

⚡ Heap Sort — Interview Key Points

• Time: O(n log n) guaranteed (no worst-case) | Space: O(1) — in-place

• Build-heap phase is O(n) — proof uses geometric series, not O(n log n)

• NOT stable — relative order of equal elements not preserved

• Poor cache performance vs QuickSort due to non-sequential memory access

• Used when: guaranteed O(n log n) needed + O(1) space required

1.3 Complexity Comparison

Algorithm Best Average Worst Space Stable?
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Bubble Sort O(n) O(n²) O(n²) O(1) Yes
Insertion Sort O(n) O(n²) O(n²) O(1) Yes
Tim Sort O(n) O(n log n) O(n log n) O(n) Yes
2. Trees & Heaps

2.1 Binary Tree Basics

A binary tree is a hierarchical data structure where each node has at most two children (left and right). Key
properties to know:
• Height of tree: longest path from root to a leaf
• Complete binary tree: all levels filled except possibly last (filled left to right)
• Full binary tree: every node has 0 or 2 children
• Perfect binary tree: all internal nodes have 2 children, all leaves at same level

Array Representation of Binary Tree

For a node at index i (0-based):
Left child = 2*i + 1
Right child = 2*i + 2
Parent = (i - 1) // 2

Example: arr = [10, 9, 8, 7, 6, 5, 4]

Index: 0 1 2 3 4 5 6
10 → left:9(idx1), right:8(idx2)
9 → left:7(idx3), right:6(idx4)

2.2 Max Heap & Min Heap

Property Max Heap Min Heap
Root value Largest element Smallest element
Parent rule Parent ≥ both children Parent ≤ both children
Extract root Returns max in O(log n) Returns min in O(log n)
Insert O(log n) — bubble up O(log n) — bubble up
Build from array O(n) bottom-up O(n) bottom-up
Python heapq (min-heap only) heapq (negate for max)

Heap Insert (Bubble-Up / Sift-Up)

def insert(heap, val):
[Link](val) # add at end
i = len(heap) - 1
while i > 0:
parent = (i - 1) // 2
if heap[parent] < heap[i]: # Max-heap condition violated
heap[parent], heap[i] = heap[i], heap[parent]
i = parent
else:
break
Bottom-Up Heapify (Floyd's Algorithm) — O(n)
The key insight: leaf nodes are already valid heaps. Start from the last non-leaf and apply sift-down to each node
moving upward. About half the nodes are leaves → O(n) total work.
def build_heap(arr): # Modifies arr in-place — O(n)
n = len(arr)
# Start from last non-leaf: index = n//2 - 1
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, n, i)

def sift_down(arr, n, i): # O(log n) for single node

largest = i
l, r = 2*i+1, 2*i+2
if l < n and arr[l] > arr[largest]: largest = l
if r < n and arr[r] > arr[largest]: largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
sift_down(arr, n, largest)

⚡ Why Bottom-Up Heapify is O(n) — Key Interview Explanation

Intuition: Nodes near leaves do very little work (height ≈ 0), while only the root has height log(n).

Math: Sum = Σ (n / 2^h) * h for h from 0 to log(n) → This series converges to O(n).

Compare: Inserting n elements one-by-one (top-down) = O(n log n). Bottom-up is strictly better.
3. Tree Traversals & Reconstruction

3.1 The Three Core Traversals

For a binary tree node, traversal order determines when we 'visit' (process) a node relative to its subtrees.

Traversal Order Pattern Key Use Case

Inorder Left → Root → Right LNR BST gives sorted output
Preorder Root → Left → Right NLR Tree serialization / copy
Postorder Left → Right → Root LRN Deletion, eval expressions
Level-order Level by level (BFS) — Shortest path, BFS problems

Recursive Implementations
class Node:
def __init__(self, val): [Link]=val; [Link]=[Link]=None

def inorder(root, result=[]):

if root:
inorder([Link], result)
[Link]([Link]) # visit BETWEEN subtrees
inorder([Link], result)

def preorder(root, result=[]):

if root:
[Link]([Link]) # visit BEFORE subtrees
preorder([Link], result)
preorder([Link], result)

def postorder(root, result=[]):

if root:
postorder([Link], result)
postorder([Link], result)
[Link]([Link]) # visit AFTER subtrees

Iterative Inorder (using Stack)

def inorder_iterative(root):
stack, result = [], []
curr = root
while curr or stack:
while curr: # go as far left as possible
[Link](curr)
curr = [Link]
curr = [Link]() # backtrack
[Link]([Link]) # visit node
curr = [Link] # move to right subtree
return result
3.2 Tree Reconstruction from Two Traversals
Given any TWO of the three traversals, you can reconstruct the binary tree — EXCEPT Inorder + Postorder
requires a unique tree, and Preorder + Postorder does NOT uniquely determine the tree (in general).

Reconstruct from Preorder + Inorder

Key insight: preorder[0] is always the root. Find root in inorder → splits into left/right subtrees.
def build_tree(preorder, inorder):
if not preorder or not inorder: return None
root_val = preorder[0]
root = Node(root_val)
mid = [Link](root_val) # O(n) — use hashmap for O(1)
[Link] = build_tree(preorder[1:mid+1], inorder[:mid])
[Link] = build_tree(preorder[mid+1:], inorder[mid+1:])
return root

# Optimized with index map:

def build_tree_fast(pre, ino):
idx_map = {val: i for i, val in enumerate(ino)}
def helper(pre_start, pre_end, ino_start, ino_end):
if pre_start > pre_end: return None
root = Node(pre[pre_start])
mid = idx_map[pre[pre_start]]
left_size = mid - ino_start
[Link] = helper(pre_start+1, pre_start+left_size, ino_start, mid-1)
[Link] = helper(pre_start+left_size+1, pre_end, mid+1, ino_end)
return root
return helper(0, len(pre)-1, 0, len(ino)-1)

Reconstruct from Inorder + Postorder

def build_from_post_in(inorder, postorder):
if not inorder: return None
root_val = postorder[-1] # LAST element of postorder = root
root = Node(root_val)
mid = [Link](root_val)
[Link] = build_from_post_in(inorder[:mid], postorder[:mid])
[Link] = build_from_post_in(inorder[mid+1:], postorder[mid:-1])
return root

⚡ Reconstruction — Interview Rules to Memorize

• Preorder + Inorder → UNIQUE tree ✓

• Postorder + Inorder → UNIQUE tree ✓

• Preorder + Postorder → NOT unique (ambiguous for single-child nodes) ✗

• Root identification: Preorder[0] = root | Postorder[-1] = root

• Always use a hashmap for O(1) index lookup in inorder array → O(n) total vs O(n²)
4. Stacks — LIFO Principle & Applications

4.1 Stack Fundamentals

A stack follows Last-In-First-Out (LIFO). The last element pushed is the first to be popped. Python's list works
perfectly as a stack.

Operation Description Time

push(x) Add x to top O(1)
pop() Remove and return top O(1)
peek() / top() View top without removing O(1)
isEmpty() Check if empty O(1)
size() Number of elements O(1)

4.2 Iterative Tree Traversal with Stack

The call stack used in recursive traversal can be made explicit with an explicit stack — useful when the recursion
limit is a concern or when an iterative approach is required.
def preorder_iterative(root):
if not root: return []
stack, result = [root], []
while stack:
node = [Link]()
[Link]([Link])
# Push RIGHT first so LEFT is processed first (LIFO)
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
return result

4.3 Binary Number Conversion using Stack

def decimal_to_binary(n):
if n == 0: return '0'
stack = []
while n > 0:
[Link](n % 2) # remainders pushed in reverse order
n //= 2
binary = ''
while stack:
binary += str([Link]()) # pop reverses to get correct order
return binary

# decimal_to_binary(13) → '1101'
# Why stack? Remainders come out LSB first; stack reverses to MSB first

4.4 Classic Stack Problems

Balanced Parentheses
def is_balanced(s):
stack = []
pairs = {')':'(', '}':'{', ']':'['}
for ch in s:
if ch in '({[': [Link](ch)
elif ch in ')}]':
if not stack or stack[-1] != pairs[ch]: return False
[Link]()
return len(stack) == 0

Monotonic Stack — Next Greater Element

def next_greater(arr):
n = len(arr)
result = [-1] * n
stack = [] # stores indices
for i in range(n):
while stack and arr[stack[-1]] < arr[i]:
idx = [Link]()
result[idx] = arr[i] # arr[i] is next greater for arr[idx]
[Link](i)
return result
5. Bit Manipulation & Greedy Strategies

5.1 XOR Logic & Binary Representation

XOR (exclusive or) returns 1 when bits differ. Key properties make it invaluable in algorithms:

XOR Property Formula Application

Self-cancellation a^a=0 Find the one non-duplicate in array
Identity a^0=a No-op with zero
Commutativity a^b=b^a Order doesn't matter
Associativity (a^b)^c = a^(b^c) Chaining XOR operations
Find missing number XOR all 1..n with array Single missing number in O(n) O(1)
Swap without temp a^=b; b^=a; a^=b In-place swap

Common Bit Tricks

# Check if number is power of 2
is_power_of_2 = lambda n: n > 0 and (n & (n-1)) == 0

# Get i-th bit (0-indexed from right)

get_bit = lambda n, i: (n >> i) & 1

# Set i-th bit

set_bit = lambda n, i: n | (1 << i)

# Clear i-th bit

clear_bit = lambda n, i: n & ~(1 << i)

# Count set bits (Brian Kernighan's algorithm) — O(set bits)

def count_bits(n):
count = 0
while n:
n &= n - 1 # clears lowest set bit each iteration
count += 1
return count

# Find single non-duplicate in array where all others appear twice

def single_number(nums):
result = 0
for n in nums: result ^= n # duplicates cancel out
return result

5.2 Greedy Algorithms — Working Backward

Greedy algorithms make locally optimal choices at each step. 'Working backward' is a pattern where you reverse-
engineer the minimum operations needed from a target state to an initial state (or vice versa).
Pattern: Minimum Operations — Work Backward
Problem type: Given a target number, find minimum operations to reach 1 (or vice versa). Greedy approach from
target → 1:
def min_ops_to_one(n):
# Allowed ops: +1, -1, /2 (if even). Work BACKWARD from n to 1.
ops = 0
while n > 1:
if n % 2 == 0:
n //= 2 # greedy: halve when possible
elif n % 4 == 1 or n == 3:
n -= 1 # -1 then halve is better
else:
n += 1 # +1 to make divisible by 4
ops += 1
return ops

# Why work backward? Forward search has exponential branches.

# BFS/DP also valid; greedy works when optimal substructure holds.

5.3 Big-O Complexity — Quick Reference

Complexity Name Example Operations
O(1) Constant Array index, hash map lookup, stack push/pop, heap peek
O(log n) Logarithmic Binary search, BST operations, heap insert/extract
O(n) Linear Linear scan, XOR all elements, single traversal
O(n log n) Linearithmic Merge sort, heap sort, quicksort avg, build heap then sort
O(n²) Quadratic Bubble/insertion/selection sort, naive all-pairs
O(2ⁿ) Exponential Recursive fibonacci (naive), all subsets

⚡ Key O(1) Operations to Know Cold

• Array element access by index: arr[i] → O(1)

• Hash map / dictionary get, set, delete → O(1) average

• Stack push / pop (Python list): O(1) amortized

• Heap peek (min or max): O(1) — but insert/extract is O(log n)

• Checking length of list/string in Python: O(1)

• Bit operations (AND, OR, XOR, shift): O(1)

 SECTION 2: SOFTWARE ENGINEERING & CLEAN CODE

6. Refactoring & Clean Code

6.1 Extracting Complex Conditionals

Long conditional chains are hard to read, test, and maintain. Extract each condition into a well-named function
that communicates INTENT.

Before Refactoring — Hard to Read

def process_order(order):
if ([Link] == 'active' and order.payment_verified
and not order.is_fraud_flagged
and [Link] > 0
and user.account_age_days > 30):
ship_order(order)

After Refactoring — Self-Documenting

def is_order_eligible_to_ship(order, user):
return (is_order_active(order)
and is_payment_verified(order)
and not is_fraud_flagged(order)
and has_valid_total(order)
and is_trusted_user(user))

def is_order_active(order): return [Link] == 'active'

def is_payment_verified(order): return order.payment_verified
def is_fraud_flagged(order): return order.is_fraud_flagged
def has_valid_total(order): return [Link] > 0
def is_trusted_user(user): return user.account_age_days > 30

def process_order(order, user):

if is_order_eligible_to_ship(order, user):
ship_order(order)

⚡ Refactoring Rules — Interview Talking Points

• Each function should do ONE thing and have a name that reveals its intent

• A function named 'is_X' or 'has_X' is self-documenting and unit-testable in isolation

• Avoid magic numbers — extract to named constants (MAX_RETRIES = 3)

• Guard clauses (early returns) reduce nesting and improve readability

• The goal: code reads like a story — a new developer understands in seconds
6.2 Optimal Data Structures — Hash Maps for O(1) Lookups
Replacing long if-elif chains with a dictionary is one of the most impactful refactors for performance and
maintainability.

Anti-Pattern: Long Conditional Chain — O(n)

def get_category(code):
if code == 'A': return 'Electronics'
elif code == 'B': return 'Clothing'
elif code == 'C': return 'Books'
elif code == 'D': return 'Food'
# ... 50 more elifs ...
else: return 'Unknown'
# Problem: O(n) lookups, hard to maintain, violates Open/Closed Principle

Optimal Pattern: Hash Map — O(1)

CATEGORY_MAP = {
'A': 'Electronics',
'B': 'Clothing',
'C': 'Books',
'D': 'Food',
# ... easy to extend, O(1) lookup regardless of size
}

def get_category(code):
return CATEGORY_MAP.get(code, 'Unknown') # O(1)

# Bonus: store functions as values for strategy pattern

HANDLERS = {
'create': handle_create,
'update': handle_update,
'delete': handle_delete,
}
def dispatch(action, data):
handler = [Link](action)
if handler: return handler(data)

6.3 When to Choose Which Data Structure

Need Use Complexity
Frequency count Dictionary / Counter O(1) per op
Membership test (fast) Set O(1) average
Ordered unique elements Sorted list / SortedList O(log n) insert
LIFO order Stack (list in Python) O(1) push/pop
FIFO order Queue (deque in Python) O(1) push/pop
Priority / scheduling Heap (heapq) O(log n) insert/extract
Key-value with order OrderedDict / dict (Py3.7+) O(1) ops
Range queries Segment Tree / BIT O(log n)
 SECTION 3: MACHINE LEARNING & GENERATIVE AI

7. Deep Learning Architecture

7.1 The Vanishing Gradient Problem

During backpropagation, gradients are multiplied layer by layer (chain rule). If activations compress gradients to
values < 1 (like sigmoid's max derivative of 0.25), multiplying across many layers drives the gradient toward zero
— making early layers learn extremely slowly or stop learning entirely.

🔍 Vanishing Gradient — Root Causes

• Sigmoid and Tanh saturate: output approaches 0/1 (or -1/1) → derivative ≈ 0

• Deep networks: 100-layer sigmoid → 0.25^100 ≈ 10^-62 gradient at first layer

• Weight initialization: if weights are large, gradients explode; if small, they vanish

• Solutions: ReLU activations, Batch Normalization, Residual connections (ResNet), LSTM gates

7.2 Activation Functions Compared

Function Formula Range Pros Cons
Sigmoid 1/(1+e^-x) (0, 1) Output as probability Vanishing gradient,
not zero-centered
Tanh (e^x-e^-x)/(e^x+e^-x) (-1, 1) Zero-centered Still vanishes for
large x
ReLU max(0, x) [0, ∞) No vanishing gradient, Dead neurons (neg
fast inputs → 0 always)
Leaky ReLU max(0.01x, x) (-∞, ∞) Fixes dead neurons Small negative
gradient
GELU x·Φ(x) ≈(-0.17, ∞) Smooth, probabilistic Computationally
heavier
SiLU/Swish x·sigmoid(x) ≈(-0.28, ∞) Self-gated, smooth No hard zero
Softmax e^xi / Σe^xj (0,1) sum=1 Multi-class probabilities Only for output
layer

GELU vs SiLU vs ReLU — Why Modern Transformers Prefer GELU/SiLU

import math

# ReLU — hard gate (0 or identity)

relu = lambda x: max(0, x)

# GELU — probabilistic gating: x * P(X <= x) where X ~ N(0,1)

# Approximation used in practice:
gelu = lambda x: 0.5 * x * (1 + [Link]([Link](2/[Link]) * (x + 0.044715 *
x**3)))

# SiLU / Swish — smooth self-gate: x * sigmoid(x)

silu = lambda x: x / (1 + [Link](-x))

# Key differences:
# ReLU: hard zero for x < 0 → can cause dead neurons
# GELU: slightly negative for small negative x → better gradient flow
# SiLU: similar to GELU, cheaper to compute, used in EfficientNet/LLaMA

8. Generative Models — Autoencoders & VAEs

8.1 Autoencoder Architecture

An autoencoder compresses input to a low-dimensional latent space (encoding) and then reconstructs the original
(decoding). Used for dimensionality reduction, anomaly detection, and as a backbone for generative models.

Component Role Architecture Detail

Encoder Input → Latent space Decreasing layer sizes (e.g.
784→256→64→z_dim)
Latent space (z) Compressed representation Bottleneck — dimensionality is key
hyperparameter
Decoder Latent → Reconstructed input Mirror of encoder (64→256→784)
Loss function Reconstruction quality MSE (images) or BCE (binary); add KL for VAE

8.2 Impact of Latent Space Dimensions

Latent Dims Effect Result
Too few (e.g. 2) Severe bottleneck High reconstruction loss; loses fine detail
Optimal Captures essential variation Good reconstruction + meaningful
interpolation
Too many Near-identity mapping Low loss but no compression; won't
generalize

8.3 Variational Autoencoder (VAE) — Continuous Latent Space

Standard autoencoders map to a POINT in latent space. VAEs map to a DISTRIBUTION (mean μ and variance
σ²). This makes the latent space continuous and allows generating new samples by sampling z ~ N(μ, σ²).

# VAE Encoder outputs mu and log_var (not a single point)

# Reparameterization trick: z = mu + eps * sigma (eps ~ N(0,1))
# This makes z differentiable w.r.t. mu and sigma!
def reparameterize(mu, log_var):
std = [Link](0.5 * log_var)
eps = torch.randn_like(std) # sample from N(0,1)
return mu + eps * std # z is now differentiable

# VAE Loss = Reconstruction Loss + KL Divergence

# KL term: forces latent distribution to stay close to N(0,1)
# KL = -0.5 * sum(1 + log_var - mu^2 - exp(log_var))

⚡ VAE vs AE — Interview Key Differences

• AE: deterministic encoding (maps to a point) → not generative

• VAE: probabilistic encoding (maps to a distribution) → can generate new samples

• Reparameterization trick is crucial: allows backprop through random sampling

• KL divergence term regularizes latent space → smooth, continuous interpolation

• VAE latent space: nearby points decode to similar outputs (unlike AE)
9. LLM Decoding Strategies

9.1 Greedy Decoding

At each step, pick the single most probable next token. Fast, deterministic, but often leads to repetitive or
suboptimal text.
def greedy_decode(logits_sequence):
output = []
for logits in logits_sequence: # logits over vocab at each step
next_token = argmax(logits) # always pick highest prob
[Link](next_token)
return output

# Problem: 'The cat sat on the the the the...' (repetition)

# Also: misses globally better sequences (local optimum ≠ global optimum)

9.2 Temperature Scaling

Temperature T modifies the probability distribution before sampling. T < 1 makes distribution sharper (more
deterministic); T > 1 makes it flatter (more random).
import math

def temperature_softmax(logits, T=1.0):

# Scale logits by temperature
scaled = [l / T for l in logits]
# Softmax
exp_vals = [[Link](l) for l in scaled]
total = sum(exp_vals)
return [e / total for e in exp_vals]

# T → 0: near-deterministic (greedy)
# T = 1: standard softmax
# T → ∞: uniform distribution (pure random)

# Typical creative writing: T = 0.7–0.9

# Code generation (precise): T = 0.1–0.3

9.3 Beam Search

Maintains the top-k (beam width) candidate sequences at each step. Explores multiple paths simultaneously —
more thorough than greedy, less random than sampling.
# Conceptual Beam Search (beam_width = k)

# Step 1: Initialize — start with beam_width copies of start token

# Step 2: Expand — for each of k beams, generate top-k next tokens
# → k*k candidates
# Step 3: Prune — keep only top-k by cumulative log probability
# Step 4: Repeat until all beams hit <EOS> or max length
# Score = sum of log probabilities (log avoids underflow)
# Length penalty: score /= length^alpha (prevents short-sequence bias)

# beam_width=1 → greedy decoding

# beam_width=5 (typical for machine translation)

Strategy Deterministic? Quality Speed Best For

Greedy Yes Low (local optima) Fastest O(n·V) Quick inference,
testing
Temperature No (stochastic) Creative, varied Fast O(n·V) Creative writing, chat
sampling
Top-k sampling No Controlled random Fast Balancing
coherence+variety
Top-p (nucleus) No Adaptive quality Fast Most production LLMs
Beam Search Yes High (structured) Slow O(n·V·k) Translation,
summarization

⚡ Top-k and Top-p (Nucleus) Sampling

• Top-k: at each step, only sample from the k most probable tokens (k=50 typical)

• Top-p: sample from the smallest set of tokens whose cumulative prob ≥ p (e.g. p=0.9)

• Top-p adapts dynamically: if top-1 token has p=0.95, only that token is considered

• Most modern LLM APIs expose: temperature + top_p (and sometimes top_k)

10. Applied NLP — Sentiment Analysis & Classification

10.1 Key-Value Mapping for Sentiment

A foundational approach: map words/tokens to sentiment scores using a dictionary (lexicon). Aggregate scores
for the input text.
# VADER-style key-value sentiment lexicon approach
SENTIMENT_LEXICON = {
'excellent': 2.0, 'great': 1.5, 'good': 1.0, 'nice': 0.8,
'bad': -1.0, 'poor': -1.5, 'terrible': -2.0, 'awful': -2.0,
'not': -1.0, # negation modifier
'very': 1.5, # intensifier
}

def rule_based_sentiment(text):
words = [Link]().split()
score = 0
for i, word in enumerate(words):
if word in SENTIMENT_LEXICON:
word_score = SENTIMENT_LEXICON[word]
# Check for preceding negation
if i > 0 and words[i-1] == 'not':
 word_score *= -1
# Check for intensifier
if i > 0 and words[i-1] == 'very':
word_score *= 1.5
score += word_score
if score > 0.5: return 'positive'
if score < -0.5: return 'negative'
return 'neutral'

10.2 Text Classification Pipeline

Stage Approach Notes
Preprocessing Lowercase, remove punctuation, NLTK, spaCy, or regex
tokenize
Feature extraction TF-IDF, Bag of Words, embeddings Word2Vec, BERT embeddings for deep
features
Classification Naive Bayes, SVM, fine-tuned BERT Naive Bayes fast + interpretable; BERT
SOTA
Post-processing Confidence thresholding, ensemble Reject low-confidence predictions
voting
Evaluation Accuracy, F1, Precision, Recall, AUC- F1 for imbalanced classes
ROC
 SECTION 4: LOGICAL REASONING & CONSTRAINT SATISFACTION

11. Constraint Satisfaction — Seating & Logic Puzzles

11.1 Systematic Approach to Logic Puzzles

Constraint satisfaction problems (CSPs) require deductive reasoning. A reliable approach:
1. List all entities and categories (people, seats, attributes)
2. Create a grid with all possible assignments
3. Apply each clue to eliminate impossible assignments
4. Look for cells where only one option remains → assign it
5. Propagate: each assignment may eliminate more options
6. If stuck, try a hypothesis (backtrack if contradiction arises)

11.2 Sample Seating Puzzle — Worked Example

Puzzle
Five people (A, B, C, D, E) sit in a row of 5 seats (1–5, left to right).

Clue 1: A is not in seat 1 or 5.

Clue 2: B is immediately to the left of C.

Clue 3: D is in an odd-numbered seat.

Clue 4: E is to the right of A.

Clue 5: B is not adjacent to D.

Step-by-Step Deduction
From Clue 2 (B immediately left of C): valid pairs for (B,C) = (1,2), (2,3), (3,4), (4,5)
From Clue 3 (D in odd seat): D ∈ {1, 3, 5}
From Clue 1 (A not in 1 or 5): A ∈ {2, 3, 4}
From Clue 5 (B not adjacent to D): if D=1, B≠2; if D=3, B≠2 and B≠4; if D=5, B≠4

# Brute-force CSP in Python — enumerate + filter

from itertools import permutations

def solve_seating():
people = ['A','B','C','D','E']
for perm in permutations(range(1,6)):
seats = dict(zip(people, perm))
A,B,C,D,E = [seats[p] for p in people]
if A in (1,5): continue # Clue 1
if B + 1 != C: continue # Clue 2
if D % 2 == 0: continue # Clue 3
 if E <= A: continue # Clue 4
if abs(B - D) == 1: continue # Clue 5
print(f'Solution: {seats}')

solve_seating()
# Output: Solution: {'A': 2, 'B': 3, 'C': 4, 'D': 5, 'E': ... }
# Verify manually after finding candidates

11.3 Deductive Logic Grid Template

For n-entity, k-category problems, build a grid. Mark × (impossible) or ✓ (confirmed) as you apply each clue.

Seat 1 Seat 2 Seat 3 Seat 4 Seat 5

A × Possible Possible Possible ×
B Possible Possible Possible Possible ×
C × Possible Possible Possible Possible
D Possible × Possible × Possible
E Possible Possible Possible Possible Possible

⚡ Logic Puzzle Strategy — Interview Tips

• Always start with the MOST restrictive clues (absolute positions, immediate adjacency)

• 'Not adjacent' clues are powerful — eliminate two positions at once

• After each deduction, propagate: check if it eliminates options elsewhere

• If two variables have only 2 options each and they're linked → pair elimination

• For coding interviews: O(n!) brute force is fine for small n (n ≤ 8)

• For large n: use backtracking with constraint propagation (Arc Consistency / AC-3)
 QUICK REFERENCE CHEAT SHEET

Complexity Cheat Sheet

Operation / Algorithm Time Space Notes
Array access O(1) — Index-based
Hash map get/set O(1) avg O(n) Worst case O(n) on collision
Stack push/pop O(1) O(n) LIFO
Binary search O(log n) O(1) Array must be sorted
Heap insert O(log n) O(n) Sift up
Heap extract-min/max O(log n) — Sift down
Build heap O(n) O(1) Floyd's bottom-up
Quick sort (avg) O(n log n) O(log n) Stack depth
Heap sort O(n log n) O(1) In-place, guaranteed
Merge sort O(n log n) O(n) Stable, external sort
Tree traversal O(n) O(h) h = height
BFS / DFS O(V+E) O(V) Graph traversal

Key Formulas to Memorize

Concept Formula / Rule
Array: left child index: 2*i + 1
Array: right child index: 2*i + 2
Array: parent index: (i-1) // 2
Last non-leaf index: n//2 - 1
XOR: find duplicate-free element XOR all elements → duplicates cancel
Power of 2 check n > 0 and (n & (n-1)) == 0
KL Divergence (VAE) -0.5 × Σ(1 + log σ² - μ² - σ²)
Temperature softmax P(i) = exp(logit_i / T) / Σexp(logit_j / T)
Beam search score Σ log P(token_t | context) / length^α

Activation Functions at a Glance

Function Key Property Use In
ReLU Zero for x<0, identity for x>0 Hidden layers (CNNs, MLPs)
GELU Smooth, probabilistic gate Transformers (BERT, GPT)
SiLU/Swish x × sigmoid(x), smooth LLaMA, EfficientNet
Sigmoid Output in (0,1) Binary classification output
Softmax Outputs sum to 1 Multi-class classification output
Tanh Output in (-1,1) RNNs, older architectures

You've got this. Practice once daily. Review weak areas first. Good luck!