Key Code Examples
1. Binary Search Algorithm
def binary_search(arr, target):
"""Search for target in sorted array using divide-and-conquer.
Time Complexity: O(log n)"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # Element not found
# Example usage
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
result = binary_search(data, 23)
print(f"Element found at index: {result}") # Output: 5
2. Linked List Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def display(self):
elements = []
current = self.head
while current:
elements.append(str(current.data))
current = current.next
return " -> ".join(elements)
# Example
ll = LinkedList()
for val in [10, 20, 30, 40]:
ll.append(val)
print(ll.display()) # Output: 10 -> 20 -> 30 -> 40
3. QuickSort Algorithm
def quicksort(arr):
"""Divide-and-conquer sorting algorithm.
Average Time Complexity: O(n log n), Worst: O(n²)"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Example
data = [38, 27, 43, 3, 9, 82, 10]
print(quicksort(data)) # Output: [3, 9, 10, 27, 38, 43, 82]
4. Dijkstra's Shortest Path
import heapq
def dijkstra(graph, start):
"""Find shortest path from start node to all other nodes.
Time Complexity: O((V + E) log V)"""
distances = {node: float('infinity') for node in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_dist, current_node = heapq.heappop(priority_queue)
if current_dist > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# Graph represented as adjacency list
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'C': 1, 'D': 5},
'C': {'A': 2, 'B': 1, 'D': 8},
'D': {'B': 5, 'C': 8}
}
print(dijkstra(graph, 'A'))
# Output: {'A': 0, 'B': 3, 'C': 2, 'D': 8}
5. Stack with Min Tracking
class MinStack:
"""Stack that tracks minimum element in O(1) time."""
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def get_min(self):
return self.min_stack[-1]
def top(self):
return self.stack[-1]
# Example
s = MinStack()
s.push(3); s.push(5); s.push(2); s.push(1)
print(s.get_min()) # Output: 1
s.pop()
print(s.get_min()) # Output: 2
6. Graph Traversal — BFS
from collections import deque
def bfs(graph, start):
"""Breadth-First Search traversal of a graph.
Time Complexity: O(V + E)"""
visited = set()
queue = deque([start])
result = []
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
return result
# Graph as adjacency list
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 4],
3: [1, 5],
4: [1, 2, 5],
5: [3, 4]
}
print(bfs(graph, 0)) # Output: [0, 1, 2, 3, 4, 5]
7. Dynamic Programming — Fibonacci with Memoization
def fibonacci(n, memo=None):
"""Calculate Fibonacci using DP with memoization.
Time Complexity: O(n), Space: O(n)"""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# Compare with naive recursion
print(fibonacci(10)) # Output: 55
print(fibonacci(50)) # Output: 12586269025
8. Hash Table Implementation
class HashTable:
"""Simple hash table using chaining for collision resolution."""
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def get(self, key):
index = self._hash(key)
for k, v in self.table[index]:
if k == key:
return v
raise KeyError(f"Key '{key}' not found")
def remove(self, key):
index = self._hash(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index].pop(i)
return
raise KeyError(f"Key '{key}' not found")
# Example
ht = HashTable()
ht.insert("apple", 3)
ht.insert("banana", 7)
ht.insert("cherry", 11)
print(ht.get("banana")) # Output: 7
9. Object-Oriented Design — Bank Account
class BankAccount:
"""A simple bank account class demonstrating OOP principles."""
bank_name = "EduVerse Bank"
_account_counter = 1000
def __init__(self, owner, balance=0):
BankAccount._account_counter += 1
self._account_number = BankAccount._account_counter
self._owner = owner
self._balance = balance
self._transactions = []
@property
def balance(self):
return self._balance
@property
def account_number(self):
return self._account_number
def deposit(self, amount):
if amount <= 0:
raise ValueError("Deposit amount must be positive")
self._balance += amount
self._transactions.append(f"Deposit: +${amount}")
return self._balance
def withdraw(self, amount):
if amount > self._balance:
raise ValueError("Insufficient funds")
self._balance -= amount
self._transactions.append(f"Withdrawal: -${amount}")
return self._balance
def get_history(self):
return self._transactions.copy()
# Example
acct = BankAccount("Alice", 1000)
acct.deposit(500)
acct.withdraw(200)
print(f"Balance: ${acct.balance}") # Output: Balance: $1300
print(f"Account: {acct.account_number}") # Output: Account: 1001
10. Threading — Producer/Consumer Pattern
import threading
import queue
import time
def producer(q, items):
"""Produce items and add them to the queue."""
for item in items:
print(f"Producing: {item}")
q.put(item)
time.sleep(0.1)
q.put(None) # Sentinel value
def consumer(q):
"""Consume items from the queue."""
while True:
item = q.get()
if item is None:
break
print(f"Consuming: {item}")
q.task_done()
# Example
q = queue.Queue(maxsize=5)
items = list(range(1, 8))
t1 = threading.Thread(target=producer, args=(q, items))
t2 = threading.Thread(target=consumer, args=(q,))
t1.start()
t2.start()
t1.join()
t2.join()
print("Done!")
Core Concepts
Big-O Notation
Definition: Big-O notation describes the upper bound of an algorithm's time or space complexity as a function of input size n. It characterizes the worst-case scenario.
Common Classes:
- O(1) — Constant: Array access, hash table lookup
- O(log n) — Logarithmic: Binary search
- O(n) — Linear: Simple loop, linear search
- O(n log n) — Linearithmic: Merge sort, heap sort
- O(n²) — Quadratic: Bubble sort, insertion sort
- O(2ⁿ) — Exponential: Brute-force subset generation
- O(n!) — Factorial: Traveling salesman brute force
Recursion
Definition: A programming technique where a function calls itself to solve a problem by breaking it into smaller subproblems. Every recursive function needs a base case (stopping condition) and a recursive case.
Key Principle: Each recursive call must make progress toward the base case to avoid infinite recursion.
Data Structures
Definition: A data structure is a way of organizing, storing, and managing data to enable efficient access and modification.
- Arrays: Contiguous memory, O(1) access, O(n) search
- Linked Lists: Non-contiguous nodes, O(1) insert at head, O(n) search
- Stacks: LIFO structure — push/pop in O(1)
- Queues: FIFO structure — enqueue/dequeue in O(1)
- Trees: Hierarchical — BST gives O(log n) average search
- Graphs: Networks of nodes — BFS/DFS traversal
- Hash Tables: Key-value pairs, O(1) average lookup
Object-Oriented Programming (OOP)
Definition: A programming paradigm based on "objects" containing data (attributes) and code (methods).
- Encapsulation: Bundling data and methods; hiding internal state
- Inheritance: Creating new classes from existing ones
- Polymorphism: Same interface, different implementations
- Abstraction: Simplifying complex reality by modeling classes
Algorithm Design Paradigms
- Divide and Conquer: Split problem into subproblems (MergeSort, QuickSort, Binary Search)
- Dynamic Programming: Break problem into overlapping subproblems, store results (Fibonacci, Knapsack, LCS)
- Greedy Algorithms: Make locally optimal choices at each step (Dijkstra's, Kruskal's, Huffman coding)
- Backtracking: Try solutions incrementally, abandon if invalid (N-Queens, Sudoku, graph coloring)
Memory Management
Definition: The process of allocating and deallocating memory during program execution.
- Stack Memory: Automatic allocation for local variables, LIFO order, limited size
- Heap Memory: Manual/dynamic allocation, flexible size, requires deallocation
- Garbage Collection: Automatic memory reclamation (Python, Java, JavaScript)
- Memory Leak: Unreleased memory that is no longer accessible but still allocated
Turing Machine & Computability
Definition: An abstract machine that manipulates symbols on a tape according to rules. It defines the theoretical limits of what can be computed.
Church-Turing Thesis: Any function that can be computed by an algorithm can be computed by a Turing machine.
Halting Problem: It is impossible to create a general algorithm that determines whether an arbitrary program will halt or run forever.
Amortized Analysis
Definition: A method of analyzing algorithms that averages the time complexity over a sequence of operations, rather than worst-case per operation.
Example: Dynamic array (ArrayList) append is O(1) amortized — occasional O(n) resize is spread across many O(1) appends.
Worked Examples
Example 1: Analyzing Time Complexity
Problem: What is the time complexity of the following function?
def find_pairs(arr, target):
pairs = []
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] + arr[j] == target:
pairs.append((arr[i], arr[j]))
return pairs
Solution:
- Outer loop runs n times
- Inner loop runs (n-1) + (n-2) + ... + 1 = n(n-1)/2 times
- Total iterations: n × n(n-1)/2 = O(n²)
- The inner if-statement and append are O(1)
- Final Answer: O(n²)
Example 2: Recursion Tree for MergeSort
Problem: Prove that MergeSort has O(n log n) time complexity.
Solution:
- Recurrence relation: T(n) = 2T(n/2) + O(n)
- At each level of the recursion tree, total work is O(n)
- Number of levels: log₂n (we halve each time)
- Total work: O(n) × log₂n = O(n log n)
- Final Answer: O(n log n)
Example 3: Dynamic Programming — Coin Change
Problem: Given coins of denominations [1, 5, 10, 25], find the minimum number of coins needed to make 30 cents.
Solution using DP:
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 5, 10, 25], 30)) # Output: 2 (25 + 5)
Explanation: Build solution bottom-up. For each amount i, try each coin and pick the minimum. dp[30] = min(dp[29]+1, dp[25]+1, dp[20]+1, dp[5]+1) = min(6, 1, 2, 1) = 2.
Example 4: Binary Search Step-by-Step
Problem: Search for 17 in the sorted array [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21].
Solution:
- Step 1: left=0, right=10, mid=5 → arr[5]=11 < 17 → go right
- Step 2: left=6, right=10, mid=8 → arr[8]=17 → FOUND!
- Only 2 comparisons needed vs 9 for linear search
- Final Answer: Found at index 8 in O(log 11) ≈ 3.5 steps
Example 5: Graph Shortest Path
Problem: Use Dijkstra's to find shortest path from A to D in a graph with edges: A→B(2), A→C(5), B→C(1), B→D(6), C→D(3).
Solution:
- Initialize: dist[A]=0, dist[B]=∞, dist[C]=∞, dist[D]=∞
- Visit A: update B=2, C=5
- Visit B (dist=2): update C=min(5, 2+1)=3, D=2+6=8
- Visit C (dist=3): update D=min(8, 3+3)=6
- Visit D (dist=6): done
- Final Answer: Shortest path A→B→C→D with distance 6
Practice Problems
Problem 1: Time Complexity Analysis
What is the time complexity of this code?
def mystery(n):
count = 0
for i in range(n):
for j in range(i, n):
count += 1
return count
Answer: O(n²) — The inner loop runs n-i times, total = n(n+1)/2 ≈ n²/2 iterations.
Problem 2: Implement a Queue Using Two Stacks
Design a queue that supports enqueue and dequeue using only two stacks.
class QueueUsingStacks:
def __init__(self):
self.s1 = [] # For enqueue
self.s2 = [] # For dequeue
def enqueue(self, x):
self.s1.append(x)
def dequeue(self):
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()
def is_empty(self):
return not self.s1 and not self.s2
Problem 3: Detect Cycle in Linked List
Given a linked list, determine if it has a cycle. Use O(1) space.
def has_cycle(head):
"""Floyd's Cycle Detection (Tortoise and Hare)"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Problem 4: Implement LRU Cache
Design a Least Recently Used (LRU) cache with O(1) get and put operations.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # Mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # Remove oldest
# Example
cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1)) # 1
cache.put(3, 3) # Evicts key 2
print(cache.get(2)) # -1 (not found)
Problem 5: Longest Common Subsequence
Find the length of the longest common subsequence between two strings.
def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs("ABCBDAB", "BDCABA")) # Output: 4 ("BCBA")
Problem 6: Topological Sort
Given a directed acyclic graph (DAG), return a topological ordering of vertices.
def topological_sort(graph):
"""Kahn's Algorithm for topological sorting."""
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] += 1
queue = [u for u in in_degree if in_degree[u] == 0]
result = []
while queue:
u = queue.pop(0)
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(result) != len(graph):
raise ValueError("Graph has a cycle!")
return result
# Example: Course prerequisites
graph = {
"CS101": ["CS201", "CS202"],
"CS201": ["CS301"],
"CS202": ["CS301"],
"CS301": []
}
print(topological_sort(graph))
# Output: ['CS101', 'CS201', 'CS202', 'CS301'] (or similar valid order)
Problem 7: Implement a Trie (Prefix Tree)
Build a trie that supports insert, search, and startsWith operations.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# Example
trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # True
print(trie.search("app")) # False
print(trie.starts_with("app")) # True
Problem 8: N-Queens
Place N queens on an N×N chessboard so that no two queens attack each other.
def solve_n_queens(n):
def is_safe(board, row, col):
for i in range(row):
if board[i] == col or \
abs(board[i] - col) == abs(i - row):
return False
return True
def place_queens(row):
if row == n:
result.append(board[:])
return
for col in range(n):
if is_safe(board, row, col):
board[row] = col
place_queens(row + 1)
result = []
board = [-1] * n
place_queens(0)
return result
# Example: 4-Queens has 2 solutions
solutions = solve_n_queens(4)
print(f"Number of solutions: {len(solutions)}") # 2
Problem 9: Edit Distance
Find minimum operations (insert, delete, replace) to convert word1 to word2.
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1]) # replace
return dp[m][n]
print(edit_distance("horse", "ros")) # Output: 3
print(edit_distance("intention", "execution")) # Output: 5
Problem 10: Merge K Sorted Lists
Merge k sorted linked lists into one sorted list. Optimize for O(N log k) time.
import heapq
def merge_k_sorted(lists):
"""Merge k sorted lists using a min-heap."""
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
result = []
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(lists[list_idx]):
next_val = lists[list_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
return result
# Example
lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
print(merge_k_sorted(lists))
# Output: [1, 1, 2, 3, 4, 4, 5, 6]