Technical interviews can feel intimidating, but they are not a test of memorizing thousands of competitive programming puzzles. Interviewers at top technology companies and engineering teams use Data Structures and Algorithms (DSA) to evaluate three core practical traits: how you structure data in memory, how you reason through trade-offs between execution speed and RAM, and how clearly you communicate under pressure.
This guide is written the way an experienced developer explains concepts to a colleague preparing for an upcoming interview. We avoid academic jargon, give you direct answers first, break down the intuition in simple English, provide clean code implementations, and analyze both Time Complexity and Space Complexity for every problem.
Who Should Use This Guide?
- College Graduates & Freshers: Master foundational data structures (Arrays, Linked Lists, Stacks, Queues, Binary Trees) and core sorting/searching techniques.
- Experienced Developers (1–8+ Years): Refresh complex patterns (Two Pointers, Sliding Window, Heaps, Graph BFS/DFS, Dynamic Programming, Tries, and System-scale B-Trees).
- Engineers Switching Stacks: Transitioning from frontend, backend, or legacy systems into product-based tech companies.
- Last-Minute Interview Revision: Looking for a concise, structured 24-hour review of time complexities and classic coding patterns.
Core Data Structures: Time & Space Complexity Cheat Sheet
Keep this quick reference in mind when discussing Big-O trade-offs with your interviewer:
| Data Structure | Access (by index) | Search (by value) | Insertion | Deletion | Space Complexity |
|---|---|---|---|---|---|
| Array / Dynamic Array | O(1) | O(n) | O(n) (amortized O(1) at end) | O(n) | O(n) |
| Singly Linked List | O(n) | O(n) | O(1) (at head/known node) | O(1) (at head) / O(n) | O(n) |
| Doubly Linked List | O(n) | O(n) | O(1) (at head or tail) | O(1) (given node pointer) | O(n) |
| Stack (LIFO) | O(n) | O(n) | O(1) (Push) | O(1) (Pop) | O(n) |
| Queue (FIFO) | O(n) | O(n) | O(1) (Enqueue) | O(1) (Dequeue) | O(n) |
| Hash Table (HashMap) | N/A | O(1) average (O(n) worst) | O(1) average | O(1) average | O(n) |
| Binary Search Tree (Balanced) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Binary Heap (Min/Max) | O(1) (Peek min/max) | O(n) | O(log n) | O(log n) (Extract) | O(n) |
| Trie (Prefix Tree) | N/A | O(L) (L = key length) | O(L) | O(L) | O(Alphabet * Total Chars) |
Filter Questions by Category & Experience Level:
Select a group below, or type in the instant search box to filter questions by topic (e.g. trees, sliding window, dynamic programming, sorting).
No matching questions found.
Try searching for a different keyword or click “All Questions”.
What is the difference between an Array and a Linked List, and how do you choose between them?
Think of an Array like a row of reserved lockers in a gym numbered 0 to 9. Because they sit right next to each other in memory, if you know the base address and an index, the computer calculates the exact memory location with simple math: address = base + (index * element_size). This makes array reads instantaneous.
A Linked List is like a treasure hunt. Each clue (node) holds a piece of data and the address of the next clue. The nodes can live anywhere in RAM. You cannot jump directly to clue #5; you must start at clue #1 and follow each clue in sequence.
| Operation | Array | Linked List |
|---|---|---|
| Access by Index | O(1) (Constant time) | O(n) (Must traverse from head) |
| Insert / Delete at Beginning | O(n) (Must shift all elements) | O(1) (Update head pointer) |
| Insert / Delete at End | O(1) amortized | O(1) with tail pointer, else O(n) |
| Insert / Delete in Middle | O(n) (Shifting required) | O(1) if position is already found |
| Memory Overhead | Minimal (only raw values) | Higher (stores extra pointer per node) |
| Cache Locality | Excellent (CPU prefetching works) | Poor (scattered heap memory pointers) |
When to use which: Choose an Array when you read frequently by index and know the approximate size upfront. Choose a Linked List when you frequently insert or delete elements at the head or when you cannot predict collection size and want to avoid bulk memory reallocations.
Array Indexing: O(1) | Linked List Traversal: O(n)
💾 Space Complexity: Array: O(n) contiguous | Linked List: O(n) + O(n) pointer overhead// 1. Array: Single contiguous block of 5 integers
int arr[5] = {10, 20, 30, 40, 50};
// Access 3rd element directly:
int val = arr[2]; // O(1) - immediate address offset
// 2. Singly Linked List Node: Scattered heap allocations
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Traversal requires chasing pointers:
Node* curr = head;
while (curr != nullptr) {
// Process curr->data...
curr = curr->next; // O(n) sequential hops
}What is the difference between Linear Search and Binary Search, and why does Binary Search require sorted data?
Imagine searching for the word “Algorithm” in an English dictionary. You would never check page 1, then page 2, then page 3 (that would be Linear Search). Instead, you open the book in the middle. If you see the letter “M”, you know instantly that “A” must be in the left half, so you throw away the right half completely. That is Binary Search.
If the pages of the dictionary were completely scrambled and unsorted, opening to the middle would tell you nothing about where “Algorithm” is hiding. You would have no choice but to scan every single page one by one.
Linear Search: O(n) | Binary Search: O(log n)
💾 Space Complexity: Iterative Binary Search: O(1) auxiliary space | Recursive: O(log n) call stackdef binary_search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
# Prevents integer overflow in languages like C++/Java:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid # Target found, return index
elif nums[mid] < target:
left = mid + 1 # Target is in the right half
else:
right = mid - 1 # Target is in the left half
return -1 # Target not found in the arrayHow do Stacks and Queues differ in principle and practical use?
Real-World Analogies:
- Stack (LIFO): A stack of dinner plates. You place clean plates on top, and people pick clean plates from the top. If you try to pull a plate from the very bottom, the tower crashes.
- Queue (FIFO): A line of customers at a cinema ticket counter. The first person to join the line is the first person served and tickets are issued in arrival order.
Practical Software Applications:
- Stack Uses: Function call stacks (recursion memory), browser back/forward buttons, undo/redo features in text editors, and matching balanced parentheses in compilers.
- Queue Uses: Printer job scheduling, web server request buffers, BFS graph traversal, and asynchronous message queues (RabbitMQ, Kafka).
Push/Enqueue: O(1) | Pop/Dequeue: O(1) | Peek: O(1)
💾 Space Complexity: O(n) where n is the number of elements storedfrom collections import deque
# 1. Stack (LIFO using Python list)
stack = []
stack.append(10) # Push
stack.append(20)
top_item = stack.pop() # Pops 20 first (Last In, First Out)
# 2. Queue (FIFO using collections.deque)
queue = deque()
queue.append("Customer A") # Enqueue
queue.append("Customer B")
first_item = queue.popleft() # Removes "Customer A" first (First In, First Out)What is the difference between a Singly Linked List, a Doubly Linked List, and a Circular Linked List?
| Type | Pointers per Node | Traversal Direction | Memory Cost | Best Use Case |
|---|---|---|---|---|
| Singly Linked | next only | Forward only | Lowest (1 pointer) | Simple forward streams, symbol tables. |
| Doubly Linked | next and prev | Forward & Backward | Higher (2 pointers) | LRU Cache implementations, browser tab navigation. |
| Circular Linked | next (points to head) | Continuous loop | Same as Singly | Round-robin CPU scheduling, turn-based board games. |
The primary advantage of a Doubly Linked List is that you can delete a given node in O(1) time if you already have a pointer to it, because you can immediately reach its previous neighbor (node->prev->next = node->next). In a Singly Linked List, you must traverse from the head to find the predecessor, which takes O(n) time.
Traversal: O(n) | Deletion with known node: O(1) in Doubly, O(n) in Singly
💾 Space Complexity: Singly: 1 pointer per node | Doubly: 2 pointers per nodestruct DoublyNode {
int val;
DoublyNode* prev; // Points to previous neighbor
DoublyNode* next; // Points to next neighbor
DoublyNode(int data) : val(data), prev(nullptr), next(nullptr) {}
};
// O(1) Deletion given direct pointer to node:
void deleteNode(DoublyNode* target) {
if (target->prev) target->prev->next = target->next;
if (target->next) target->next->prev = target->prev;
delete target;
}What is the difference between Bubble Sort, Selection Sort, and Insertion Sort?
While none of these three are used for massive production datasets (where O(n log n) Merge Sort or Quick Sort are standard), they are frequently asked in fresher interviews to test understanding of sorting stability and mechanics:
- Bubble Sort: In each pass, adjacent elements are compared and swapped if out of order. The largest unsorted element ‘bubbles up’ to the end. Best case is
O(n)if an early-exit flag detects no swaps. - Selection Sort: Scans the unsorted portion, finds the minimum element, and swaps it with the first unsorted position. It always takes
O(n^2)time, even if the array is already sorted, because it never stops scanning. - Insertion Sort: Takes elements one by one and inserts them into the already sorted left partition (just like sorting a hand of playing cards). Highly efficient for very small arrays ($n \le 16$) or nearly sorted data with
O(n)best-case time.
Bubble: O(n) to O(n^2) | Selection: O(n^2) always | Insertion: O(n) to O(n^2)
💾 Space Complexity: All three are In-Place: O(1) auxiliary spacedef insertion_sort(arr: list[int]) -> list[int]:
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# Shift elements of arr[0..i-1] that are greater than key to one position ahead
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arrWhat is the difference between Big-O, Big-Omega (Ω), and Big-Theta (Θ) notations?
When software engineers talk about algorithm efficiency, they use asymptotic notation to describe how runtime or memory consumption scales as input size $n$ grows toward infinity:
- Big-O ($O$): Upper Bound. Guarantees that the algorithm will not take longer than this. Example: Quick Sort is $O(n^2)$ because in the absolute worst case (poor pivot selection on sorted input), it degrades to quadratic time.
- Big-Omega ($\Omega$): Lower Bound. Describes the fastest possible scenario. Example: Linear Search is $\Omega(1)$ because the target might be the very first element you inspect.
- Big-Theta ($\Theta$): Tight Bound. Used when the upper and lower bounds grow at the exact same rate. Example: Merge Sort is $\Theta(n \log n)$ because it always takes $n \log n$ operations, regardless of whether the input is sorted, reversed, or random.
N/A (Theoretical Framework)
💾 Space Complexity: N/AO(1) <-- Constant (Hash table lookup, array index)
O(log n) <-- Logarithmic (Binary search, balanced BST operations)
O(n) <-- Linear (Single loop through array, linear search)
O(n log n) <-- Linearithmic (Merge sort, Heap sort, Quick sort average)
O(n^2) <-- Quadratic (Nested loops, Bubble sort, Matrix multiplication)
O(2^n) <-- Exponential (Recursive subsets, Fibonacci without memo)
O(n!) <-- Factorial (Traveling Salesperson via brute-force)How does a Dynamic Array (ArrayList / std::vector / Python list) resize, and why is insertion amortized O(1)?
A standard static array has a fixed capacity allocated upfront. A dynamic array wraps a static array under the hood and tracks two values: size (number of items currently stored) and capacity (total slots allocated in memory).
The Resizing Process (Geometric Doubling):
- Suppose capacity is 4 and you insert 4 elements:
[1, 2, 3, 4]. Size is now 4. - You insert a 5th element. The array detects
size == capacity. - It allocates a new buffer of capacity 8 ($4 imes 2$).
- It copies the 4 elements into the new array and deallocates the old buffer.
- It appends 5:
[1, 2, 3, 4, 5, _, _, _].
Why is it Amortized $O(1)$?
Although the resize operation takes $O(n)$ time to copy $n$ items, doubling the capacity guarantees that you can perform another $n$ insertions for free ($O(1)$ each) before the next resize occurs. Summing the total work across $n$ insertions yields approximately $2n$ operations. Dividing total work by $n$ items gives $2n / n = 2$, which is constant time $O(1)$.
Appends: Amortized O(1), Worst Case O(n) during resize | Indexing: O(1)
💾 Space Complexity: O(n) memory allocation with up to 2x capacity bufferclass SimpleVector {
private:
int* data;
int capacity;
int length;
void resize() {
capacity *= 2; // Geometric doubling
int* new_data = new int[capacity];
for (int i = 0; i < length; i++) {
new_data[i] = data[i]; // Copy elements
}
delete[] data;
data = new_data;
}
public:
SimpleVector() : capacity(2), length(0) { data = new int[capacity]; }
void push_back(int val) {
if (length == capacity) resize(); // O(n) triggered rarely
data[length++] = val; // O(1) standard insert
}
};Why are Strings immutable in languages like Java, Python, and C#, and how do you concatenate strings efficiently?
When you execute str += 'a' inside a loop running 10,000 times, the runtime does not simply append ‘a’ to the end of the existing memory buffer. Instead, on every single iteration, it allocates an entirely new string, copies all previous characters over, and leaves the old string for garbage collection.
If you concatenate 1 character across $n$ iterations, the total number of copied characters is $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} = O(n^2)$. This can turn a 5-millisecond function into a 30-second freeze.
The Efficient Alternative: Use an expandable buffer like StringBuilder in Java/C#, or collect items into a list and call "".join(list) in Python. These resize dynamically in amortized $O(1)$ time, yielding total linear $O(n)$ performance.
Naive loop concatenation: O(n^2) | StringBuilder / join: O(n)
💾 Space Complexity: StringBuilder: O(n) single buffer | Naive: Allocates O(n^2) temporary objects// Inefficient: O(n^2) allocations
String result = "";
for (int i = 0; i < 10000; i++) {
result += i; // Allocates 10,000 intermediate objects on heap!
}
// Efficient Java: O(n) time
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10000; i++) {
sb.append(i);
}
String fastResult = sb.toString();
# Efficient Python: O(n) time
parts = [str(i) for i in range(10000)]
fast_python = "".join(parts) # Single-pass memory allocation!What is a Hash Collision, and what are the two main collision resolution techniques?
A Hash Table maps keys to array indices using a mathematical hash function: index = hash(key) % table_size. Because the universe of possible keys is infinitely larger than the fixed size of an array, the Pigeonhole Principle guarantees that collisions will happen.
Collision Resolution Methods:
- Chaining (Separate Chaining): Each array bucket contains the head of a linked list (or Red-Black tree in Java 8+). When keys collide, the new key-value pair is simply appended to the list at that bucket.
- Open Addressing: All elements live directly inside the array. If a collision occurs at index $i$, the table looks for another empty cell using:
- Linear Probing: Check $i+1, i+2, i+3 \dots$
- Quadratic Probing: Check $i+1^2, i+2^2, i+3^2 \dots$
- Double Hashing: Use a secondary hash function to calculate step size: $i + k \cdot \text{hash}_2(\text{key})$.
Average Lookup/Insert: O(1) | Worst Case (All keys collide): O(n)
💾 Space Complexity: O(n) storage for n key-value pairs// Separate Chaining: Vector of Linked Lists
class HashMapChaining {
private:
static const int BUCKETS = 1000;
std::list<std::pair<int, string>> table[BUCKETS];
int hashFunction(int key) {
return key % BUCKETS;
}
public:
void insert(int key, string value) {
int bucket = hashFunction(key);
for (auto& pair : table[bucket]) {
if (pair.first == key) {
pair.second = value; // Update existing
return;
}
}
table[bucket].emplace_back(key, value); // Append to chain
}
};What is Recursion, and what causes a Stack Overflow error?
Every time a function is called, the runtime pushes a Stack Frame onto the thread’s call stack. This frame stores function parameters, local variables, and the return address where execution must resume after the call finishes.
Every valid recursive function requires two critical ingredients:
- Base Case: The termination condition that returns an answer immediately without making further recursive calls.
- Recursive Step: The logic that breaks the problem into a strictly smaller input that moves closer to the base case.
If you forget the base case, or if your recursive step fails to shrink the problem (e.g., calling f(n) instead of f(n-1)), recursive calls continue infinitely. Each call consumes stack memory (typically 1MB to 8MB max per thread) until the OS throws a fatal StackOverflowError.
Depends on recurrence relation (e.g. Factorial: O(n), Fibonacci: O(2^n))
💾 Space Complexity: O(d) auxiliary stack memory, where d is maximum recursion depthdef factorial(n: int) -> int:
# 1. Base Case: Stops the recursion
if n <= 1:
return 1
# 2. Recursive Step: Moves toward base case (n - 1)
return n * factorial(n - 1)
# Memory Call Stack visualization for factorial(3):
# | factorial(1) -> returns 1 | (Top of Stack)
# | factorial(2) -> waits for f(1) |
# | factorial(3) -> waits for f(2) | (Bottom of Stack)
# Once base case hits, stack frames pop and multiply back up.What is the Two-Pointer technique, and when can it reduce an O(n^2) problem to O(n)?
When solving problems that ask you to find a pair of elements (e.g. two numbers that sum to a target in a sorted array), a brute-force approach tests every combination using two nested loops: for i in range(n): for j in range(i+1, n):, taking $O(n^2)$ operations.
The Convergent Two-Pointer Optimization:
- Sort the array (if not already sorted).
- Place pointer
leftat index 0 and pointerrightat index $n-1$. - Calculate
current_sum = arr[left] + arr[right]. - If
current_sum == target: match found! - If
current_sum < target: the sum is too small. Because the array is sorted, incrementingleftguarantees a larger sum. - If
current_sum > target: the sum is too large. Decrementingrightguarantees a smaller sum.
Every step eliminates at least one element from consideration without ever inspecting it again, processing the array in a single linear pass of $O(n)$ steps.
O(n) on sorted arrays | O(n log n) if sorting is required upfront
💾 Space Complexity: O(1) auxiliary space (only 2 pointer variables)def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
left = 0
right = len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left, right] # Indices of the pair
elif current_sum < target:
left += 1 # Need a larger sum
else:
right -= 1 # Need a smaller sum
return [] # No valid pair existsHow does the Sliding Window pattern work, and how do you differentiate between Fixed and Dynamic windows?
Imagine finding the maximum sum of any contiguous subarray of size $k = 3$ in an array of 1,000 numbers.
A naive algorithm would sum elements 0..2, then sum elements 1..3, then 2..4, recalculating 3 additions every time ($O(n \cdot k)$).
A Sliding Window computes the sum of the first 3 numbers once. When moving to the next window, it simply adds the incoming element on the right and subtracts the outgoing element on the left: window_sum = window_sum + arr[right] - arr[left]. This takes $O(1)$ operations per slide!
Fixed vs Dynamic Windows:
- Fixed Window: The distance between
leftandrightis always constant $k$. (Example: Maximum average of $k$ consecutive days). - Dynamic Window: The window expands by moving
rightto include elements until a condition breaks (e.g. duplicate character encountered), then shrinks by advancingleftuntil validity is restored. (Example: Longest substring without repeating characters).
O(n) time (each element enters and exits the window at most once)
💾 Space Complexity: Fixed Window: O(1) space | Dynamic Window: O(k) space for frequency hash mapdef max_sub_array_of_size_k(k: int, arr: list[int]) -> int:
if len(arr) < k:
return 0
# 1. Compute sum of initial window
window_sum = sum(arr[:k])
max_sum = window_sum
# 2. Slide the window from index k to the end
for right in range(k, len(arr)):
# Add new element, subtract departing element
window_sum += arr[right] - arr[right - k]
max_sum = max(max_sum, window_sum)
return max_sumWhat is the difference between a Binary Tree and a Binary Search Tree (BST)?
Because a generic Binary Tree has no ordering constraints, searching for a value requires checking every single node via BFS or DFS, taking $O(n)$ time in the worst case.
A Binary Search Tree (BST) organizes data like binary search in tree form. At each node, you compare the search target with the node value:
- If
target == node.val: Found! - If
target < node.val: Discard the entire right subtree and go left. - If
target > node.val: Discard the entire left subtree and go right.
On a balanced BST with height $h = \log_2(n)$, searching, inserting, and deleting takes $O(\log n)$ time. However, if values are inserted in sorted order (e.g. 1, 2, 3, 4, 5), an unbalancing BST degenerates into a skewed line (like a linked list) with $O(n)$ search time.
Balanced BST: O(log n) search/insert/delete | Skewed BST: O(n) worst case
💾 Space Complexity: O(n) storage | O(h) recursion call stack where h is tree heightstruct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* searchBST(TreeNode* root, int target) {
TreeNode* curr = root;
while (curr != nullptr) {
if (curr->val == target) return curr;
else if (target < curr->val) curr = curr->left; // Search left
else curr = curr->right; // Search right
}
return nullptr; // Target not found
}What are the four primary Tree Traversal orders, and how do they differ?
Tree traversal means visiting every node in the tree exactly once. The order depends on when the parent/root node is processed relative to its children:
| Traversal | Processing Order | Typical Practical Use Case |
|---|---|---|
| Preorder (DFS) | Root → Left → Right | Serializing/deserializing tree structures, creating a deep clone of a tree. |
| Inorder (DFS) | Left → Root → Right | Validating a BST, retrieving sorted list of elements from a BST. |
| Postorder (DFS) | Left → Right → Root | Bottom-up calculations (calculating tree height, subtree sizes, deleting nodes safely). |
| Level Order (BFS) | Level 0 → Level 1 → Level 2 | Finding shortest path in unweighted trees, printing tree views (left view, right view). |
All 4 Traversals take O(n) time (every node is visited once)
💾 Space Complexity: DFS: O(h) recursion stack (h = height) | BFS: O(w) queue (w = max level width)from collections import deque
# 1. Recursive DFS Traversals:
def inorder(root):
return inorder(root.left) + [root.val] + inorder(root.right) if root else []
def preorder(root):
return [root.val] + preorder(root.left) + preorder(root.right) if root else []
def postorder(root):
return postorder(root.left) + postorder(root.right) + [root.val] if root else []
# 2. BFS Level Order Traversal:
def level_order(root):
if not root: return []
result, queue = [], deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(current_level)
return resultWhat is a Heap (Min-Heap / Max-Heap), and how is it represented as an array?
Unlike standard binary trees that require left/right pointer addresses, a Complete Binary Tree has all levels completely filled except possibly the last level, which fills from left to right. This guarantees zero gaps, allowing it to map directly to array indices:
- Root node is at index
0(or 1 in 1-based indexing). - For any element at index
i:- Left Child:
2 * i + 1 - Right Child:
2 * i + 2 - Parent:
(i - 1) // 2
- Left Child:
Core Operations:
- Insert (
push): Add element to end of array, then Heapify-Up (bubble up by swapping with parent until heap property holds). Time: $O(\log n)$. - Extract Min/Max (
pop): Replace root with last array element, remove last element, then Heapify-Down (bubble down by swapping with smaller child). Time: $O(\log n)$. - Peek: Inspect root element at index 0. Time: $O(1)$.
- Build Heap (
heapify): Converts an arbitrary array of $n$ elements into a valid heap in $O(n)$ time using bottom-up sift-downs.
Peek: O(1) | Push/Pop: O(log n) | Heapify Array: O(n)
💾 Space Complexity: O(n) stored compactly inside a single flat arrayimport heapq
# Python heapq implements a Min-Heap by default
heap = []
# Push elements: O(log n) each
heapq.heappush(heap, 30)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
# Peek smallest: O(1)
smallest = heap[0] # Returns 10
# Pop smallest: O(log n)
popped = heapq.heappop(heap) # Pops 10
# For a Max-Heap in Python, invert values by multiplying by -1:
max_heap = []
heapq.heappush(max_heap, -1 * 50)
max_val = -1 * heapq.heappop(max_heap) # Returns 50What is the difference between Quick Sort and Merge Sort, and why is Quick Sort often faster in practice despite its O(n^2) worst case?
| Criteria | Merge Sort | Quick Sort |
|---|---|---|
| Best & Average Time | O(n log n) | O(n log n) |
| Worst-Case Time | O(n log n) (Guaranteed) | O(n^2) (Poor pivot choice on sorted data) |
| Auxiliary Space | O(n) (Requires temporary arrays) | O(log n) (Call stack for recursion, in-place swaps) |
| Stability | Stable (Preserves equal-element order) | Unstable (Swaps across partitions) |
| Cache Locality | Lower (Copies data to temp buffers) | Excellent (Iterates contiguous memory in-place) |
| Best Use Case | External sorting, Linked Lists, when stability is mandatory. | Standard in-memory array sorting (e.g. C++ `std::sort`). |
How Modern Runtimes Eliminate Quick Sort's Worst Case: Modern implementations (like Introsort in C++ and .NET) choose pivots using Median-of-Three or random selection. Furthermore, if recursion depth exceeds $2 \log n$, Introsort automatically switches to Heap Sort to guarantee $O(n \log n)$ worst-case safety.
Merge Sort: O(n log n) always | Quick Sort: O(n log n) avg, O(n^2) worst
💾 Space Complexity: Merge Sort: O(n) extra arrays | Quick Sort: O(log n) stack spacedef quicksort(arr: list[int], low: int, high: int):
if low < high:
# Partition index
pi = partition(arr, low, high)
quicksort(arr, low, pi - 1)
quicksort(arr, pi + 1, high)
def partition(arr: list[int], low: int, high: int) -> int:
pivot = arr[high] # Choose last element as pivot
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i] # Swap
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1What is 'Binary Search on Answer' (Search Space Reduction), and how do you recognize it in interviews?
You can identify this pattern when a problem contains phrases like:
- "Find the minimum capacity to ship all packages within D days." (LeetCode 1011)
- "Find the minimum eating speed to eat all bananas within H hours." (LeetCode 875 - Koko Eating Bananas)
- "Maximize the minimum distance between cows placed in stalls." (Aggressive Cows)
The Core Monotonic Property:
If speed $X$ is sufficient to finish the job within the time limit, then any speed greater than $X$ will also be sufficient. Conversely, if speed $Y$ fails, any speed less than $Y$ will also fail. Because the feasibility function outputs a monotonic sequence: [False, False, False, True, True, True], Binary Search can instantly pinpoint the boundary transition where True first begins.
O(n * log(max_ans - min_ans)) where n is the check function cost
💾 Space Complexity: O(1) auxiliary spacedef min_capacity_to_ship(weights: list[int], days: int) -> int:
# 1. Define answer search boundary:
# Minimum possible: heaviest single package; Maximum: sum of all packages
left = max(weights)
right = sum(weights)
ans = right
def can_ship(capacity: int) -> bool:
needed_days = 1
curr_load = 0
for w in weights:
if curr_load + w > capacity:
needed_days += 1
curr_load = 0
curr_load += w
return needed_days <= days
# 2. Binary search on the feasible answer space:
while left <= right:
mid = left + (right - left) // 2
if can_ship(mid):
ans = mid # Feasible! Try to find a smaller valid capacity
right = mid - 1
else:
left = mid + 1 # Infeasible! Must increase capacity
return ansWhat is the difference between Depth-First Search (DFS) and Breadth-First Search (BFS) in Graph Traversal?
| Dimension | Breadth-First Search (BFS) | Depth-First Search (DFS) |
|---|---|---|
| Data Structure | Queue (FIFO) | Stack (LIFO) or System Call Stack (Recursion) |
| Traversal Style | Expands in concentric ripples (Level by Level) | Plunges to deepest leaf before backtracking |
| Shortest Path Guarantee | Yes (on unweighted graphs) | No (might find a convoluted deep path first) |
| Memory Requirement | O(V) (can store wide levels in memory) | O(V) worst case, but O(h) on balanced graphs |
| Primary Applications | Social network distance (degrees of separation), web crawlers, flood fill. | Connected components, cycle detection, topological sorting (Tarjan/Kosaraju). |
Visited Set is Mandatory: Unlike trees (which have no cycles), graphs can contain cycles. Both BFS and DFS require a visited hash set or boolean array to track visited vertices and prevent infinite loops.
Both algorithms take O(V + E) time (V = vertices, E = edges)
💾 Space Complexity: O(V) to store the visited set and traversal queue/stackfrom collections import deque
# Graph represented as Adjacency List: {vertex: [neighbors]}
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [], 'E': ['F'], 'F': []
}
# 1. BFS Traversal using Queue (Level by level)
def bfs(start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 2. DFS Traversal using Recursion
def dfs(node, visited=None):
if visited is None: visited = set()
visited.add(node)
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor, visited)What is a Monotonic Stack, and how does it solve 'Next Greater Element' in O(n) time?
Suppose you have the array [2, 1, 2, 4, 3] and want to find the next greater element to the right of each number.
A brute-force solution checks every element to the right using nested loops, taking $O(n^2)$ time.
A Monotonic Decreasing Stack processes elements one by one. The stack maintains elements that are waiting for a larger number to arrive:
- Push 2: Stack is
[2]. - Next is 1 (smaller than 2): Push 1. Stack is
[2, 1](decreasing order maintained). - Next is 2 (greater than 1): 2 is the next greater element for 1! Pop 1, record 2 as its answer. Push 2. Stack is
[2, 2]. - Next is 4 (greater than both 2s): Pop 2 (answer is 4), pop the next 2 (answer is 4). Push 4. Stack is
[4].
Because each element is pushed to the stack exactly once and popped at most once, the total time across all elements is strictly $O(n)$.
O(n) linear time (amortized O(1) operations per element)
💾 Space Complexity: O(n) auxiliary stack spacedef next_greater_elements(nums: list[int]) -> list[int]:
n = len(nums)
result = [-1] * n
stack = [] # Stores INDICES of elements waiting for next greater
for i in range(n):
# When current element is greater than stack's top element:
while stack and nums[i] > nums[stack[-1]]:
smaller_idx = stack.pop()
result[smaller_idx] = nums[i] # Current number is its next greater!
stack.append(i) # Push current index
return resultWhat are common Bitwise Operations and tricks every developer must know?
Key Bitwise Tricks Frequently Tested in Technical Interviews:
- Check if a number is Odd or Even:
(n & 1) == 0→ Even,(n & 1) == 1→ Odd. (Much faster thann % 2). - Check if a number is a Power of Two:
n > 0 and (n & (n - 1)) == 0. Powers of two have exactly one bit set (e.g. $8 = 1000_2$, $8-1 = 7 = 0111_2$; $1000 \ \& \ 0111 = 0000$). - Clear the lowest set bit (Brian Kernighan's Algorithm):
n = n & (n - 1)turns off the rightmost 1-bit. Used to count set bits in $O(\text{set bits})$ time. - XOR Properties:
- $x \oplus 0 = x$ (Identity)
- $x \oplus x = 0$ (Self-inverse)
- $x \oplus y \oplus x = y$ (Commutative and associative)
- Enables finding the single non-repeating number in an array where every other number appears twice (LeetCode 136 - Single Number).
All bitwise operations are O(1) single-cycle CPU instructions
💾 Space Complexity: O(1) auxiliary space# 1. Find Single Non-Duplicate Number: O(n) time, O(1) space
def single_number(nums: list[int]) -> int:
unique = 0
for num in nums:
unique ^= num # Duplicate numbers cancel out to 0!
return unique
# 2. Count Set Bits (Hamming Weight via Brian Kernighan)
def count_set_bits(n: int) -> int:
count = 0
while n > 0:
n &= (n - 1) # Drops the lowest set bit
count += 1
return countWhat is Dynamic Programming, and how do you differentiate between Memoization (Top-Down) and Tabulation (Bottom-Up)?
To use Dynamic Programming, a problem must possess two mathematical characteristics:
- Overlapping Subproblems: The same subproblems are solved repeatedly in the recursion tree (e.g. computing
fib(3)multiple times when calculatingfib(5)). - Optimal Substructure: The optimal solution to the overall problem can be constructed from optimal solutions to its subproblems (e.g. shortest path from A to C via B is shortest(A, B) + shortest(B, C)).
| Dimension | Top-Down (Memoization) | Bottom-Up (Tabulation) |
|---|---|---|
| Strategy | Recursive. Starts with the original large problem and checks a cache before executing recursive calls. | Iterative. Starts with the smallest base cases (e.g. dp[0], dp[1]) and builds up toward the answer. |
| Call Stack Overhead | Consumes $O(n)$ recursion call stack memory; risks stack overflow on large inputs. | Zero call stack overhead (pure loops). |
| Subproblem Computation | Computes only the subproblems strictly needed by the execution path. | Computes all subproblems in table order. |
| Space Optimization | Harder to optimize space since state depends on recursion frames. | Easier: often you only need the previous 1 or 2 rows/variables ($O(1)$ space). |
Reduces exponential O(2^n) brute force to polynomial O(n) or O(n * k) time
💾 Space Complexity: Memoization: O(n) cache + O(n) stack | Tabulation: O(n) table or O(1) space optimized# 1. Top-Down Memoization (with decorator cache)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
if n <= 1: return n
return fib_memo(n - 1) + fib_memo(n - 2)
# 2. Bottom-Up Tabulation with O(1) Space Optimization
def fib_tabulation(n: int) -> int:
if n <= 1: return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1How does Dijkstra's Algorithm find the shortest path, and why does it fail on negative edge weights?
How Dijkstra Works (Greedy Invariant):
- Maintain a
distancesarray initialized to $\infty$, settingdistances = 0. - Push
(0, source)into a Min-Heap (priority queue ordered by current shortest distance). - Pop the vertex $u$ with the minimum tentative distance. Mark $u$ as finalized.
- Relax all outgoing edges $(u, v, \text{weight})$: if
distances[u] + weight < distances[v], updatedistances[v]and push the new distance into the min-heap. - Repeat until the priority queue is empty.
Why Negative Edge Weights Break Dijkstra:
Dijkstra operates on the greedy principle that once a node is popped from the min-heap, its shortest distance is finalized forever and will never be revisited. If an edge has a negative weight (e.g. $-10$), taking a detour through that negative edge could result in a total path cost smaller than the finalized distance, producing incorrect results. For graphs with negative edge weights, use Bellman-Ford ($O(V \cdot E)$) or SPFA.
O((V + E) log V) using Min-Heap priority queue | O(V^2) with simple array
💾 Space Complexity: O(V) for distances array and min-heap priority queueimport heapq
def dijkstra(graph: dict, source: str) -> dict:
# graph: {u: [(v, weight), ...]}
distances = {node: float('inf') for node in graph}
distances = 0
# Min-Heap stores tuples: (current_distance, node)
min_heap = [(0, source)]
while min_heap:
curr_dist, u = heapq.heappop(min_heap)
# Skip if we already found a shorter path to u
if curr_dist > distances[u]:
continue
for v, weight in graph[u]:
distance = curr_dist + weight
# Edge relaxation
if distance < distances[v]:
distances[v] = distance
heapq.heappush(min_heap, (distance, v))
return distancesWhat is a Trie (Prefix Tree), and why is it superior to a Hash Table for Autocomplete and IP Routing?
In a standard Hash Table, checking whether any string in a dictionary begins with prefix "app" requires iterating through all $N$ keys in the table, taking $O(N \cdot L)$ time.
In a Trie:
- The root node is empty.
- Each node has an array or hash map of child pointers (e.g. 26 pointers for lowercase English letters 'a' through 'z').
- A boolean flag
is_end_of_wordmarks whether the node completes a valid word. - Keys sharing common prefixes (e.g.,
"app","apple","apply") share the exact same branch nodes.
To check if a prefix exists, you follow child pointers character by character. If you reach the end of the prefix string, it exists in $O(L)$ time, regardless of whether the dictionary contains 10 words or 100,000,000 words!
Insert: O(L) | Search: O(L) | Prefix Search (startsWith): O(L) where L = word length
💾 Space Complexity: O(Total Characters in Dictionary * Alphabet Size)class TrieNode:
def __init__(self):
self.children = {} # Maps char -> TrieNode
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
curr = self.root
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.is_end_of_word = True
def search(self, word: str) -> bool:
curr = self._traverse(word)
return curr is not None and curr.is_end_of_word
def starts_with(self, prefix: str) -> bool:
return self._traverse(prefix) is not None
def _traverse(self, text: str) -> TrieNode:
curr = self.root
for char in text:
if char not in curr.children:
return None
curr = curr.children[char]
return currWhat is Disjoint Set Union (DSU / Union-Find), and how do Path Compression and Union by Rank achieve near O(1) time?
DSU is the gold-standard algorithm for dynamic connectivity problems, such as finding connected components, detecting cycles in undirected graphs, and Kruskal's Minimum Spanning Tree algorithm.
The Two Crucial Optimizations:
- Union by Rank / Size: When merging two trees, always attach the shorter tree under the root of the taller tree. This prevents the tree from degenerating into a tall, unbalanced linked list of height $O(n)$, capping height at $O(\log n)$.
- Path Compression: During a
find(x)query, as you traverse up to the root, you update every visited node's parent pointer to point directly to the root. Subsequent searches for any of those nodes resolve in instantaneous $O(1)$ time.
Together, they bring the amortized time per operation down to $O(\alpha(n))$, where $\alpha(n) \le 4$ for any input size $n$ up to the number of atoms in the observable universe ($10^{80}$).
Find & Union: Amortized O(alpha(n)) ≈ O(1) nearly constant time
💾 Space Complexity: O(n) arrays for parent and rank pointersclass UnionFind:
def __init__(self, size: int):
self.parent = list(range(size))
self.rank = [0] * size
# Find with Path Compression: O(alpha(n))
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Flatten the tree!
return self.parent[x]
# Union by Rank: O(alpha(n))
def union(self, x: int, y: int) -> bool:
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # Already in the same set (cycle detected!)
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return TrueWhat is Topological Sort, and how do Kahn's Algorithm (BFS) and DFS detect cycles in directed graphs?
Topological Sorting is essential for dependency resolution: build systems (e.g. compiling source files in Makefile), package managers (npm/pip installing prerequisites first), and course prerequisite scheduling (LeetCode 207 - Course Schedule).
Kahn's Algorithm (BFS In-Degree Method):
- Calculate the in-degree (number of incoming edges) for every vertex.
- Initialize a Queue with all vertices that have
in_degree == 0(dependencies already satisfied). - While the queue is not empty:
- Dequeue vertex $u$ and append it to the topological order list.
- For each outgoing neighbor $v$ of $u$, decrement its in-degree:
in_degree[v] -= 1. - If
in_degree[v] == 0, push $v$ into the queue.
- Cycle Detection: If the count of sorted elements is strictly less than the total number of vertices $V$, there is a circular dependency (cycle) preventing in-degrees from reaching zero.
O(V + E) linear time in terms of vertices and edges
💾 Space Complexity: O(V + E) for adjacency list, in-degree array, and queuefrom collections import deque
def topological_sort_kahn(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
# 1. Build adjacency list and compute in-degrees
adj = {i: [] for i in range(num_courses)}
in_degree = [0] * num_courses
for dest, src in prerequisites:
adj[src].append(dest)
in_degree[dest] += 1
# 2. Queue all vertices with 0 in-degree (no prerequisites)
queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
order = []
# 3. Process BFS
while queue:
curr = queue.popleft()
order.append(curr)
for neighbor in adj[curr]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# 4. Verify if all nodes were scheduled (no cycle)
if len(order) == num_courses:
return order
return [] # Empty list indicates circular dependency (cycle detected)What is the difference between the 0/1 Knapsack Problem and the Fractional Knapsack Problem?
Understanding this distinction is a favorite interview test of algorithmic decision-making:
- Fractional Knapsack (Greedy): Because you can take fractions of items, you greedily pick the item with the highest density (value per unit weight $\frac{v_i}{w_i}$). If the knapsack runs out of capacity, take whatever fraction fits. Greedy choice is proven to be optimal.
- 0/1 Knapsack (Dynamic Programming): Greedy fails! An item with high density might be very heavy and block you from taking two slightly lower-density items that together yield far greater total value. You must evaluate both decisions (take or skip) for every item across remaining capacities using DP: $$dp[i][w] = \max(dp[i-1][w], \ dp[i-1][w - w_i] + v_i)$$
Note on Pseudo-Polynomial Time: 0/1 Knapsack runtime is $O(n \cdot W)$, where $W$ is the maximum weight capacity. This is pseudo-polynomial because it depends on the numerical value of $W$, not just the number of items.
Fractional (Greedy): O(n log n) | 0/1 Knapsack (DP): O(n * W)
💾 Space Complexity: Fractional: O(1) extra space | 0/1 Knapsack: O(W) with 1D array optimizationdef knapsack_01(capacity: int, weights: list[int], values: list[int]) -> int:
n = len(weights)
# 1D DP array of size (capacity + 1)
dp = [0] * (capacity + 1)
for i in range(n):
w_i, v_i = weights[i], values[i]
# Iterate BACKWARDS from capacity down to w_i to avoid reusing the same item!
for w in range(capacity, w_i - 1, -1):
dp[w] = max(dp[w], dp[w - w_i] + v_i)
return dp[capacity]What is a Segment Tree, and why is it used over a simple array for Range Minimum / Range Sum queries?
Consider the trade-off dilemma between simple arrays and prefix sums:
| Data Structure | Range Query Time | Point Update Time |
|---|---|---|
| Raw Array | O(n) (Must loop through range) | O(1) (Direct index write) |
| Prefix Sum Array | O(1) (prefix[R] - prefix[L-1]) | O(n) (Must recalculate prefix array) |
| Segment Tree / Fenwick Tree | O(log n) (Balanced segment tree) | O(log n) (Update leaf and bubble up) |
When you have a dynamic dataset with $Q = 100,000$ operations containing a mix of both range queries and frequent updates, a simple array or prefix sum will time out ($O(Q \cdot n) = 10^{10}$ ops). A Segment Tree processes all $100,000$ operations in a fraction of a second ($O(Q \log n) \approx 1.7 \times 10^6$ ops).
Build Tree: O(n) | Range Query: O(log n) | Point Update: O(log n)
💾 Space Complexity: O(4n) stored in a flat arrayclass SegmentTree {
private:
vector<int> tree;
int n;
void build(const vector<int>& arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = start + (end - start) / 2;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] + tree[2 * node + 1]; // Internal node holds sum
}
public:
SegmentTree(const vector<int>& arr) {
n = arr.size();
tree.resize(4 * n, 0);
build(arr, 1, 0, n - 1);
}
// Queries range [L, R] in O(log n) by combining intersecting segment nodes
};Why do relational databases (MySQL, PostgreSQL) use B-Trees / B+Trees for disk indexes instead of Binary Search Trees (AVL / Red-Black Trees)?
The speed bottleneck in database systems is Disk I/O latency. Fetching data from RAM takes ~100 nanoseconds, while an SSD takes ~100 microseconds and an HDD takes ~10 milliseconds (100,000x slower!).
The Flaw of Binary Trees on Disk:
To store 10,000,000 records in a balanced Binary Tree (Red-Black tree), the tree height is $\log_2(10^7) \approx 24$. Finding a record requires traversing down 24 node levels. Because nodes are allocated on the heap across different disk pages, this requires up to 24 separate disk reads.
Why B+Trees Dominate Databases:
- Massive Fan-out: Each B+Tree node is sized to match an operating system disk page (e.g. 16KB). If each key is 16 bytes, a single node holds hundreds of keys and children (fan-out $B \approx 1,000$).
- Tiny Height: With a fan-out of 1,000, a 3-level tree holds $1,000^3 = 1,000,000,000$ (one billion) records! A search requires only 3 disk reads instead of 24.
- Linked Leaf Nodes: In a B+Tree, all data pointers live exclusively in the leaf nodes, which are linked together in a doubly linked list. Range queries (e.g.
WHERE age BETWEEN 20 AND 30) simply seek to the first leaf node and perform sequential disk reads along the linked list.
Search/Insert/Delete: O(log_B n) where B is the block fan-out (100-1000)
💾 Space Complexity: O(n) organized into contiguous 4KB/16KB disk page blocksBinary Tree: 24 levels deep -> 24 random disk seeks!
[Node] -> [Node] -> [Node] -> [Node] -> ... (Ouch)
B+Tree (16KB Block Size): Only 3 levels deep -> 3 disk seeks!
Level 1 (Root): [ 100 | 500 | 900 ] (Cached in RAM!)
/ | Level 2 (Branch): [Child] [Child] [Child] (1 Disk Read)
/ | Level 3 (Leaves): [D1,D2] <-> [D3,D4] <-> [D5,D6] (Linked Leaf Nodes for range scans)Two Sum: Find two numbers in an array that add up to a target
Problem Statement: Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target. You may assume each input has exactly one solution, and you cannot use the same element twice.
Brute Force vs Optimized Logic:
- Brute Force: Check all pairs using nested loops: $O(n^2)$ time.
- Hash Map One-Pass: For each number $x$, the value we need is
complement = target - x. Before adding $x$ to our hash map, we check: "Did we already see its complement earlier in the array?" If yes, we immediately return the stored index and the current index!
O(n) - Single pass through the array
💾 Space Complexity: O(n) - To store up to n elements in the hash mapdef two_sum(nums: list[int], target: int) -> list[int]:
seen = {} # Maps value -> index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i] # Match found!
seen[num] = i # Record current number and index
return []Reverse a Singly Linked List (Iterative & In-Place)
Problem Statement: Given the head of a singly linked list, reverse the list in-place and return the reversed list's head.
Step-by-Step Pointer Flipping:
- Before changing any pointer, save the next node:
next_temp = curr.next(otherwise you lose the rest of the list!). - Reverse the pointer:
curr.next = prev. - Advance
prevforward tocurr:prev = curr. - Advance
currforward tonext_temp:curr = next_temp.
When curr reaches None, prev sits at the last original node, which is the new head of the reversed list.
O(n) - Visits every node exactly once
💾 Space Complexity: O(1) - In-place pointer manipulation, zero extra allocationsclass ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_linked_list(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_temp = curr.next # 1. Save next node
curr.next = prev # 2. Reverse link backward
prev = curr # 3. Advance prev
curr = next_temp # 4. Advance curr
return prev # prev is now the new head!Valid Parentheses: Determine if brackets are properly closed and nested
Problem Statement: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
Rules of Validity:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order (e.g.
"([)]"is INVALID). - Every close bracket must have a corresponding open bracket.
O(n) - Single pass through string of length n
💾 Space Complexity: O(n) - Stack can hold up to n/2 opening bracketsdef is_valid_parentheses(s: str) -> bool:
stack = []
# Map closing bracket to its corresponding opening bracket
bracket_map = {')': '(', '}': '{', ']': '['}
for char in s:
if char in bracket_map:
# Closing bracket: top must match
top_element = stack.pop() if stack else '#'
if bracket_map[char] != top_element:
return False
else:
# Opening bracket: push to stack
stack.append(char)
return len(stack) == 0 # Must be completely empty at the end!Longest Substring Without Repeating Characters
Problem Statement: Given a string s, find the length of the longest substring without repeating characters.
Sliding Window Optimization:
- Maintain window
[left, right]. - As
rightadvances across the string, ifs[right]was seen previously at indexlast_idx, andlast_idx >= left(meaning it sits inside the current window), jumpleft = last_idx + 1. - Update the character's last seen index:
seen[s[right]] = right. - Update max length:
max_len = max(max_len, right - left + 1).
O(n) - Each character is visited once by the right pointer
💾 Space Complexity: O(min(n, m)) where m is character set size (e.g. 26 letters or 128 ASCII)def length_of_longest_substring(s: str) -> int:
char_map = {} # Maps character -> latest index seen
left = 0
max_len = 0
for right, char in enumerate(s):
if char in char_map and char_map[char] >= left:
# Duplicate inside window! Jump left pointer past old occurrence:
left = char_map[char] + 1
char_map[char] = right
max_len = max(max_len, right - left + 1)
return max_lenMerge Two Sorted Linked Lists into One Sorted List
Problem Statement: Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
The Dummy Head Pattern:
Creating an artificial dummy = ListNode(0) node avoids messy edge-case conditionals when determining which list provides the true head. At the end, you simply return dummy.next.
O(n + m) where n and m are lengths of the two lists
💾 Space Complexity: O(1) auxiliary space (in-place pointer splicing)def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
# Splicing the remaining non-empty tail:
curr.next = l1 if l1 else l2
return dummy.nextLowest Common Ancestor (LCA) in a Binary Tree
Problem Statement: Given a binary tree and two nodes $p$ and $q$, find their Lowest Common Ancestor (LCA). The LCA is the deepest node in the tree that has both $p$ and $q$ as descendants (where a node can be a descendant of itself).
Recursive Intuition:
- Search left subtree:
left = lca(root.left, p, q). - Search right subtree:
right = lca(root.right, p, q). - If both
leftandrightreturn non-null, it means $p$ is on one side and $q$ is on the other side. Therefore, the currentrootis their split point—the Lowest Common Ancestor! - If only one returns non-null, both nodes must reside in that subtree, so return whichever side was non-null.
O(n) - In the worst case, visits all n nodes
💾 Space Complexity: O(h) - Where h is tree height for the recursion call stackdef lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
# Base Case: Reached null or found p or q
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If p and q are found in different subtrees, root is the LCA:
if left and right:
return root
# Otherwise return the non-null side:
return left if left else rightMerge Overlapping Intervals
Problem Statement: Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Why Sorting Start Times is the Key:
Once intervals are sorted chronologically by start time: [start, end], any overlapping intervals will sit adjacent to each other. You only ever need to compare the incoming interval with the most recently merged interval in your result list.
O(n log n) - Dominated by the initial sort
💾 Space Complexity: O(n) - To store the merged output arraydef merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
# 1. Sort intervals by start time
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
# If merged list is empty or current interval does NOT overlap:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
# Overlap exists: Merge by extending the end time
merged[-1][1] = max(merged[-1][1], interval[1])
return mergedKth Largest Element in an Array
Problem Statement: Given an integer array nums and an integer k, return the $k^{\text{th}}$ largest element in the array.
Comparing 3 Approaches:
- Sort the entire array:
nums.sort(reverse=True); return nums[k-1]. Takes $O(n \log n)$ time. Acceptable, but interviewers will ask for an optimization. - Min-Heap of size $k$: Keep the $k$ largest elements seen so far in a Min-Heap. The smallest among the top $k$ sits at the root. Takes $O(n \log k)$ time and $O(k)$ space. Ideal for streaming data where $N$ is infinite.
- QuickSelect (Hoare's Selection): Partitions the array like QuickSort, but only recurses into the partition containing the target index. Average time is linear $O(n)$.
Min-Heap: O(n log k) | QuickSelect: Average O(n), Worst Case O(n^2)
💾 Space Complexity: Min-Heap: O(k) auxiliary space | QuickSelect: O(1) in-placeimport heapq
def find_kth_largest(nums: list[int], k: int) -> int:
min_heap = []
for num in nums:
heapq.heappush(min_heap, num)
# Keep heap size bounded to exactly k:
if len(min_heap) > k:
heapq.heappop(min_heap) # Discard the smallest
# The top of the heap is the kth largest element:
return min_heap[0]Number of Islands: Count connected components in a 2D binary grid
Problem Statement: Given an $m \times n$ 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Sink the Island Pattern (In-Place Mutation):
Instead of maintaining a separate $O(m \times n)$ visited matrix, as soon as you visit a land cell '1', immediately mutate it to '0' (sink it into water). This prevents infinite loops and guarantees each cell is processed at most once with zero extra memory allocations.
O(M * N) - Every cell in the grid is visited at most twice
💾 Space Complexity: O(M * N) worst-case recursion call stack (if the entire grid is land)def num_islands(grid: list[list[str]]) -> int:
if not grid: return 0
rows, cols = len(grid), len(grid[0])
island_count = 0
def dfs(r: int, c: int):
# Base case: Out of bounds or water ('0')
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r] != '1':
return
# Sink the land cell:
grid[r] = '0'
# Recurse in 4 cardinal directions:
dfs(r + 1, c) # Down
dfs(r - 1, c) # Up
dfs(r, c + 1) # Right
dfs(r, c - 1) # Left
for r in range(rows):
for c in range(cols):
if grid[r] == '1':
island_count += 1
dfs(r, c) # Sinks the entire connected island!
return island_countCoin Change: Minimum number of coins needed to make a given amount
Problem Statement: You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Why Greedy Fails:
If coins are [1, 3, 4] and target is 6: a greedy approach picks the largest coin 4 first, leaving 2, which requires two 1s: $4 + 1 + 1 = 3$ coins. However, the optimal answer is two 3s: $3 + 3 = 2$ coins! Therefore, Dynamic Programming is required.
O(amount * n) where n is the number of coin denominations
💾 Space Complexity: O(amount) for the 1D DP tabledef coin_change(coins: list[int], amount: int) -> int:
# dp[i] = min coins to make amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # Base case: 0 coins needed for 0 amount
for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1Top 6 Mistakes Candidates Make in DSA Coding Interviews
Technical interviewers evaluate your thought process just as much as your final code. Here are the most frequent mistakes that disqualify candidates, and how to avoid them:
1. Jumping into Code Too Quickly
Starting to code in the first 2 minutes without asking questions is a major red flag. Always take 3–5 minutes to clarify input constraints, ask about duplicates, negative numbers, empty arrays, and discuss potential approaches before touching the editor.
2. Staying Silent While Thinking
Interviewers cannot read your mind. If you are quiet for 4 minutes, they do not know if you are stuck or designing an optimal solution. Think out loud: "I'm considering a hash map here to trade space for time..."
3. Ignoring Time & Space Constraints
If $N ≤ 10^5$, an $O(n^2)$ algorithm will exceed the typical 1-second execution limit ($10^{10}$ operations → Time Limit Exceeded). You must aim for $O(n)$ or $O(n \log n)$. Check constraints to infer the intended time complexity.
4. Forgetting Boundary Edge Cases
Always test: null / empty list, single element, all elements identical, sorted in reverse, and extreme values (integer overflow). Mentioning edge cases proactively proves real-world engineering maturity.
5. Premature Optimization
If you don't immediately see the $O(n)$ optimal trick, state the $O(n^2)$ brute-force solution clearly first! It gives you a guaranteed baseline, proves you understand the problem, and gives you a foundation to optimize.
6. Not Dry-Running with Sample Input
Never announce: "I'm done!" without stepping through your code line by line with a small example (e.g. [3, 1, 4]). Walking through your variables catches off-by-one errors before the interviewer points them out.
The 4-Step Technical Interview Framework
Use this structured method during your live coding interview to keep your communication calm, professional, and methodical:
- Step 1: Clarify & Agree on Constraints (3–5 min): Confirm input types, array size bounds, duplicates, memory limits, and write 2 test cases (one standard, one edge case).
- Step 2: State the Brute Force Approach (2–3 min): Briefly describe the naive solution, state its Big-O time and space complexity, and identify the exact bottleneck causing slowness.
- Step 3: Propose the Optimized Pattern (5–8 min): Explain why an optimal pattern fits (e.g. "Since we need fast lookups, a Hash Map trades O(n) space for O(1) time"). Get verbal agreement from the interviewer before writing code.
- Step 4: Clean Coding & Manual Verification (15–20 min): Write modular, clean code with sensible variable names. Trace a small test case by hand, confirm time/space complexity, and discuss potential scale-up improvements.
24-Hour Final Revision Checklist
Review these core checkpoints the day before your technical coding round:
- [ ] Know standard library syntax for your language by heart (Stack, Queue/Deque, PriorityQueue/Heap, HashMap, Set, Sorting with custom comparator).
- [ ] Review binary search templates (preventing infinite loops with
left <= rightandmid = left + (right - left) // 2). - [ ] Review linked list pointer reversal (prev, curr, next_temp) and fast/slow pointer cycle detection.
- [ ] Understand sliding window templates (expanding right, contracting left).
- [ ] Memorize DFS vs BFS implementations for trees and 2D grid matrix traversals.
- [ ] Review how to recognize 0/1 Knapsack vs Unbounded Knapsack DP transitions.
- [ ] Practice verbalizing Big-O complexity for sorting, hashing, trees, and heaps.
Practice DSA Problems & Explore Engineering Tools on RTSALL
Continue your preparation with RTSALL's curated problem sets, interactive calculators, and technical roadmaps:
Frequently Asked Questions: DSA Technical Interviews
How much DSA is really needed for software engineering jobs?
For most product-based tech companies, mastering medium-difficulty problems on core patterns (Arrays, Hash Maps, Two Pointers, Sliding Window, Trees, BFS/DFS, Heaps, and basic Dynamic Programming) covers 85% of interview questions. You do not need esoteric competitive programming algorithms (like Heavy-Light Decomposition or Suffix Automata) unless interviewing for specialized algorithmic research roles.
Which programming language is best for coding interviews?
Use the language you are most comfortable with. Python is extremely popular because of its concise syntax, built-in data structures (lists, dicts, deque, heapq), and rapid coding speed during timed 45-minute interviews. Java, C++, and C# are equally respected. The key is knowing your language's standard library collections and time complexities inside and out.
What should I do if I get completely stuck during a coding interview?
First, don't panic. Start by stating the brute force solution out loud. Work through a concrete small example by hand on paper or on the screen. Ask clarifying questions: 'Can we assume the array is sorted? Can numbers be negative?' Often, tracing an example by hand reveals patterns (like monotonicity or repeated work) that naturally point toward two pointers, a hash map, or a heap.
How do I know whether to use Dynamic Programming or a Greedy approach?
Use a Greedy approach if making a locally optimal choice at each step is mathematically proven to lead to a globally optimal solution (like Fractional Knapsack or Dijkstra on positive graphs). If making an immediate locally optimal choice can block a better future combination (like 0/1 Knapsack or Coin Change), you must evaluate overlapping subproblems using Dynamic Programming.
Is it better to write fast code or clean, readable code in an interview?
Both matter, but clean, bug-free, readable code with an optimal asymptotic Big-O runtime is the true goal. Writing overly clever one-liners that are hard to debug will hurt you if there is an off-by-one error. Choose clear variable names, break complex logic into helper functions, and write code that would pass a real production code review.
Leave a comment