DSA Concepts

12 Core Data Structure & Algorithm Concepts — The foundation of EVERY coding interview. Not coding problems, but the deep understanding that makes you solve any problem they throw at you.

Time & Space Complexity

Core 5 min

Every algorithm has a cost. Big-O measures worst-case growth as input grows. This is the FIRST thing interviewers evaluate in any coding question.

Big-O measures growth rate, not exact time. O(n) = input doubles, time doubles. O(n²) = input doubles, time quadruples.

Common Complexities (fastest to slowest):

O(1) — Constant: hash table lookup. Works for 10 items or 10 billion.

O(log n) — Logarithmic: binary search. Each step eliminates half.

O(n) — Linear: scanning an array. Each element visited once.

O(n log n) — Linearithmic: merge sort, quicksort average. Best for comparison sorting.

O(n²) — Quadratic: nested loops. Bubble sort. Avoid for large inputs.

O(2ⁿ) — Exponential: recursive Fibonacci without memoization.

Key Interview Points

O(1) ideal, O(log n) excellent, O(n) acceptable, O(n log n) typical for sorting, O(n²) and above = red flag
Space complexity matters too: O(n) extra space = array/hashmap proportional to input
Drop constants and lower-order terms: O(3n² + 5n + 100) = O(n²)
Amortized analysis: some operations expensive occasionally (array resize) but O(1) on average
Time-space tradeoff: hash table = O(n) space for O(1) lookup. Often worth it

Competitive Edge

Know Master Theorem for divide-and-conquer: T(n) = aT(n/b) + O(n^d). a = subproblems, b = input shrink factor, d = work per level. This lets you analyze merge sort O(n log n), binary search O(log n) without drawing recursion trees.

Follow-up Questions

Complexity of checking array duplicates?

Brute force nested loops: O(n²). HashSet: O(n) time, O(n) space. Sort then check adjacent: O(n log n) time, O(1) space.

Why drop constants?

Growth rate matters as n grows to infinity. For n=1 million, O(2n) and O(n) both process ~million items. The constant is noise vs O(n) vs O(n²) difference.

Arrays & Strings

Core 4 min

Arrays: contiguous memory, O(1) access by index. Strings: arrays of characters. Most common data structures in interviews — 60%+ of LeetCode involves them.

Array: Access by index O(1). Search unsorted O(n). Search sorted (binary search) O(log n). Insert at end (amortized) O(1). Insert at beginning O(n).

Strings: Immutable in Java/Python. Every modification creates new object. Use StringBuilder (Java) or list join (Python) for repeated concatenation.

Key Interview Points

Two-pointer: Start and end pointers. O(n) palindrome check, reverse, pair sum in sorted array
Sliding window: Window slides over array. Perfect for subarray/substring problems (max sum, longest substring)
Prefix sum: Precompute cumulative sums for O(1) range queries. Build once, query many
Strings immutable in Java/Python — StringBuilder or join() for efficiency
Hash map for counting: Character frequencies in O(n). Anagram, frequency problems

Competitive Edge

Know the sliding window template: (1) Expand right pointer, (2) When window invalid, shrink from left, (3) Track max/min valid window. Solves: longest substring without repeating chars, minimum window substring, max sum subarray of size K. The #1 array/string pattern.

Follow-up Questions

Two strings anagrams?

Sort both and compare: O(n log n). Count character frequencies: O(n). Interview wants hash map approach.

Rotate array by K positions?

Three reversals: reverse entire array, reverse first K, reverse remaining. O(n) time, O(1) space.

Linked Lists

Core 4 min

Nodes pointing to next. No contiguous memory needed. O(1) insert/delete at known position. But no random access — must traverse from head.

Array vs Linked List: Array O(1) access, O(n) insert/delete. Linked List O(n) access, O(1) insert/delete if you have the pointer.

Singly: Node → next. Forward only. Doubly: Node → next AND prev. Both directions. Used in LRU cache, browser history.

Key Interview Points

Fast & slow pointer: Detect cycles, find middle. Fast 2 steps, slow 1. Meet = cycle
Dummy head: Fake head node simplifies insertion/deletion edge cases
Reverse linked list: Core pattern. Three pointers: prev, current, next
Linked lists excel for frequent insertions/deletions in middle
Always draw it out — pointer manipulation easier to reason visually

Competitive Edge

Know Floyd Cycle Detection. Fast pointer 2x speed. If cycle exists, they meet (faster laps slower). To find cycle START: after meeting, reset one pointer to head, move both at same speed — they meet at cycle start. Asked ALL the time.

Follow-up Questions

Merge two sorted linked lists?

Dummy head + two pointers. Compare heads, attach smaller, advance. O(n+m) time, O(1) space.

Linked list palindrome?

Find middle with slow/fast pointer → reverse second half → compare → restore. O(n) time, O(1) space.

Stacks & Queues

Core 4 min

Stack = LIFO (last in, first out). Queue = FIFO (first in, first out). Simple but powerful — used in recursion, BFS, parsing, scheduling.

Stack: push/pop/peek all O(1). Undo/redo, function call stack, expression evaluation, backtracking.

Queue: enqueue/dequeue/peek all O(1). BFS, task scheduling, message processing.

Key Interview Points

Stack for balanced parentheses: push opening, pop on closing. Empty at end = balanced
Monotonic stack: Increasing/decreasing order. Next greater element, largest rectangle in histogram
Queue for BFS: Process nodes level by level
Deque: Insert/delete both ends. Sliding window maximum
Implement stack using queues or queue using stacks — classic question

Competitive Edge

Know monotonic stack pattern. Maintain stack where elements always increase/decrease. When new element violates order, pop and process. Solves: Next Greater Element, Largest Rectangle in Histogram, Daily Temperatures.

Follow-up Questions

Queue using two stacks?

Stack A for enqueue, Stack B for dequeue. Dequeue: if B empty, pop all from A to B (reverses order), pop B. Amortized O(1).

Min element in stack O(1)?

Auxiliary stack tracking minimum. Push current min alongside each element. Pop both. O(n) space.

Hash Tables / HashMaps

Important 5 min

Maps keys to values in O(1) average time. Most used data structure in practice. Python dict, Java HashMap, JS Object, Go map — all hash tables.

How: Hash function converts key → integer → array index. Store value there. Collisions handled by chaining (linked list per bucket) or open addressing (find next empty slot).

Load factor: n/size. Exceeds 0.75 → resize 2x and rehash. O(n) resize but amortized O(1).

Key Interview Points

O(1) average insert/lookup/delete. O(n) worst case (all keys collide)
Good hash: fast, uniform distribution, deterministic
Use cases: counting, two-sum, caching, grouping, deduplication
If problem says find pairs, count occurrences, check exists — think hash map
Python dict, Java HashMap, JS Map, Go map, C++ unordered_map

Competitive Edge

Know why Java 8 HashMap uses Red-Black Trees for long collision chains. When bucket linked list exceeds 8 entries, converts to balanced BST. Worst-case O(log n) instead of O(n). Shows deep understanding that impresses interviewers.

Follow-up Questions

Design a hash table from scratch?

Array of buckets + hash function. Hash key % capacity → index. Chaining for collisions. Resize at load factor threshold. Rehash all entries.

What makes a good hash function?

Deterministic, uniform distribution, fast, avalanche effect (small input change = different hash). Java String: s[0]*31^(n-1) + s[1]*31^(n-2) + ...

Trees & Binary Search Trees

Important 5 min

Hierarchical data: root at top, branches down. BST: left < parent < right. Enables O(log n) search when balanced.

Types:

Binary Tree: 0-2 children per node. General.

BST: Left < Node < Right. O(log n) search if balanced.

Complete Binary Tree: All levels full except last, filled left to right. Heaps.

AVL/Red-Black: Self-balancing BSTs. O(log n) guaranteed. Java TreeMap, C++ std::map.

Key Interview Points

In-order traversal of BST = sorted order. Left → Node → Right
Pre-order: Node, Left, Right (serialization). Post-order: Left, Right, Node (deletion)
BFS (level-order): Queue. Level by level. Shortest path unweighted
DFS: Stack/recursion. Deep first. Backtracking, path finding
Check valid BST: each node in range (min, max). Root: (-inf, +inf). Recursive. Very common interview Q

Competitive Edge

Know Lowest Common Ancestor. BST: if both targets < node go left, both > go right, else current = LCA. O(log n). Binary tree: recurse both sides, if both return non-null = current is LCA.

Follow-up Questions

LCA in BST?

Both targets < node → go left. Both > node → go right. Else current node is LCA. O(log n).

Diameter of binary tree?

Longest path between any two nodes. For each node: diameter through it = left_height + right_height. Track max. O(n) post-order.

Graphs

Important 5 min

Nodes connected by edges. Social networks, maps, web pages, dependencies — all graphs. Common at Google, Meta, Amazon interviews.

Adjacency List: Each node stores its neighbors. O(V+E) space. Most common.

Adjacency Matrix: 2D array. O(V²) space. Fast lookup but wasteful for sparse graphs.

BFS: Queue, level by level. Shortest path unweighted. O(V+E).

DFS: Stack/recursion, deep first. Cycles, topo sort, components. O(V+E).

Key Interview Points

BFS = shortest path unweighted. First reach = shortest distance
DFS = cycle detection, topological sort, connected components
Topological Sort: For DAGs. DFS + stack or Kahn algorithm (BFS + in-degree)
Dijkstra: Shortest weighted path. Min-heap. O((V+E) log V). No negative weights
Common: island counting, clone graph, course schedule (topo sort)

Competitive Edge

Know when to use BFS vs DFS. BFS: shortest path, level-order processing, finding minimum steps. DFS: exploring all paths, cycle detection, backtracking, topological sort. Most interview graph problems are either BFS or DFS with a twist.

Follow-up Questions

Cycle in directed graph?

DFS with 3 states: white (unvisited), gray (in current path), black (done). Gray encountered = cycle. Or Kahn: count nodes with in-degree 0, remove. If count not equal total = cycle.

Connected components in undirected graph?

BFS/DFS from every unvisited node. Each traversal covers one component. Count starts. O(V+E).

Sorting Algorithms

Concept 4 min

Arranging elements in order. Merge sort and quicksort are most important — they represent divide-and-conquer and appear in many interview solutions.

Merge Sort: Divide in half, sort, merge. O(n log n) always. Stable. O(n) extra space.

Quicksort: Pivot, partition, recurse. Average O(n log n). In-place. Worst O(n²).

Heap Sort: Build max-heap, extract max repeatedly. O(n log n). In-place. Unstable.

Counting Sort: Count occurrences, rebuild. O(n+k). Integers in small range only.

Key Interview Points

Merge sort: guaranteed O(n log n). Used externally, for merging sorted arrays. Java TimSort base
Quicksort: O(n log n) average, faster in practice (cache locality). C qsort, Java primitive sort
You rarely implement sort from scratch, but DO implement merge and partition logic
Stable: equal elements keep original order. Merge sort = stable. Quicksort = unstable
Python sort = TimSort (merge+insertion). Java = TimSort objects, dual-pivot quicksort primitives

Competitive Edge

Know Quickselect — find Kth smallest in O(n) average. Like quicksort but only recurse into partition containing K. Much faster than sorting entire array. Powers find median and top K problems.

Follow-up Questions

When counting sort?

Sorting integers in known small range (ages 0-120, scores 0-100). O(n+k) where k = range. When k much less than n, faster than comparison sorts.

Merge two sorted arrays?

Two pointers. Compare, take smaller, advance. O(n+m). Core of merge sort merge step.

Binary Search

Important 3 min

Find target in sorted array in O(log n). 1 billion elements = only 30 comparisons. Simple concept but tricky to implement — off-by-one errors are common.

low=0, high=n-1. While low ≤ high: mid = low + (high-low)/2. Target = mid? Found. < mid? Search left. > mid? Search right.

Key Interview Points

Works ONLY on sorted arrays. Not sorted? Sort first O(n log n) or use hash O(n)
mid = low + (high-low)/2 avoids integer overflow
Binary search works on ANY monotonic function, not just arrays
Lower bound: first position for target. Upper bound: last. Both O(log n)
Variations: rotated sorted array, first/last occurrence, matrix search

Competitive Edge

Know binary search on answer. If problem is is X possible? where answer is monotonic (NO below threshold, YES above), binary search the threshold. Solves minimum speed to finish, minimum capacity to ship, split array largest sum. Turns O(n²) into O(n log max).

Follow-up Questions

Search in rotated sorted array?

One half always sorted. Check if target in sorted half → search there. Else search unsorted half. O(log n). Meta favorite.

First occurrence of target with duplicates?

Binary search, but when found save position and search left for earlier. O(log n).

Dynamic Programming

Important 5 min

Break into overlapping subproblems, solve each once, store results. If optimal X depends on optimal smaller Xs — probably DP. Most feared topic but follows patterns.

Top-down (Memoization): Recursive + cache. Natural to write. Stack overflow risk.

Bottom-up (Tabulation): Iterative from base cases. More efficient. Usually space-optimizable.

Fibonacci: fib(n) = fib(n-1)+fib(n-2). Without memo: O(2ⁿ). With: O(n).

Key Interview Points

Identify DP: (1) Overlapping subproblems, (2) Optimal substructure
Top-down = recursive + cache. Bottom-up = iterative table. Usually bottom-up more efficient
1D DP: Fibonacci, climbing stairs, house robber, coin change, LIS
2D DP: Grid paths, LCS, edit distance, knapsack
Space optimization: if dp[i] depends only on dp[i-1] and dp[i-2], need just 2 variables

Competitive Edge

Know DP patterns: (1) Linear: dp[i] = best up to i (stairs, robber), (2) Grid: dp[i][j] = best path to (i,j), (3) String: dp[i][j] = best for substrings (LCS, edit distance), (4) Knapsack: dp[i][w] = best value with first i items weight w. Most DP fits these.

Follow-up Questions

Coin change?

dp[amount] = min coins. dp[0]=0. For each amount 1..target, each coin: dp[amt] = min(dp[amt], dp[amt-coin]+1). O(amount x coins).

Longest Common Subsequence?

dp[i][j] = LCS of first i of s1 and first j of s2. If s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1. Else max(dp[i-1][j], dp[i][j-1]). O(m x n).

Recursion & Backtracking

Concept 4 min

Function calls itself with smaller input. Backtracking = recursion + undo choices at dead ends. Permutations, combinations, puzzles, path-finding.

Recursion needs: (1) Base case, (2) Recursive case, (3) Progress toward base.

Backtracking: Make choice → recurse → undo choice. Solution found? Return. Dead end? Backtrack.

Key Interview Points

Every recursion MUST have a base case or stack overflow
Backtracking = try all possibilities, abandon impossible paths
Classic: permutations, combinations, N-Queens, Sudoku, word search
Usually exponential: O(n!) or O(2ⁿ). Exploring all possibilities
Optimize: prune branches early if current path cannot lead to solution

Competitive Edge

Know backtracking vs DP. Problem asks for ALL solutions (all permutations, all boards) = backtracking. COUNT or BEST solution = DP. Backtracking explores all, DP avoids redundant work.

Follow-up Questions

Generate all permutations?

Swap each element to first position, recurse on remaining, swap back. O(n!).

N-Queens?

Place queens row by row. Try each column. Check safe (no queen same column/diagonal). Safe? Place, recurse. No valid column? Backtrack. All rows filled = solution.

Greedy Algorithms

Concept 3 min

Make locally optimal choice at each step. Does not always work — but when it does, simplest and fastest. Key is PROVING local optimal leads to global optimal.

When greedy works: (1) Greedy choice property, (2) Optimal substructure.

Classic: Activity selection (pick compatible), Huffman (merge smallest), Dijkstra (closest), Fractional knapsack (best ratio).

Key Interview Points

Greedy is fast but not always correct. Must prove it works for specific problem
Activity selection: sort by end time, pick non-overlapping. O(n log n)
Fractional knapsack: sort by value/weight, take best ratio. O(n log n)
Huffman: repeatedly merge least frequent chars. Optimal prefix code
0-1 knapsack is NOT greedy — needs DP. Fractional knapsack IS greedy

Competitive Edge

Know greedy vs DP for knapsack. Fractional (can take fractions) = greedy works. 0-1 (whole item or nothing) = greedy FAILS, need DP. Interviewers test this distinction.

Follow-up Questions

When does greedy fail?

Coin change with arbitrary denominations. Coins [1,3,4], target 6. Greedy: 4+1+1=3 coins. Optimal: 3+3=2 coins. That is why coin change needs DP.

How to prove greedy works?

Exchange argument: show any optimal solution can be transformed into greedy solution without making it worse. If greedy = as good as optimal, greedy IS optimal.

Test Your DSA Knowledge

Practice questions covering all core data structures and algorithms.

Practice Quiz →

DSA Concepts

Time & Space Complexity

Key Interview Points

Competitive Edge

Follow-up Questions

Arrays & Strings

Key Interview Points

Competitive Edge

Follow-up Questions

Linked Lists

Key Interview Points

Competitive Edge

Follow-up Questions

Stacks & Queues

Key Interview Points

Competitive Edge

Follow-up Questions

Hash Tables / HashMaps

Key Interview Points

Competitive Edge

Follow-up Questions

Trees & Binary Search Trees

Key Interview Points

Competitive Edge

Follow-up Questions

Graphs

Key Interview Points

Competitive Edge

Follow-up Questions

Sorting Algorithms

Key Interview Points

Competitive Edge

Follow-up Questions

Binary Search

Key Interview Points

Competitive Edge

Follow-up Questions

Dynamic Programming

Key Interview Points

Competitive Edge

Follow-up Questions

Recursion & Backtracking

Key Interview Points

Competitive Edge

Follow-up Questions

Greedy Algorithms

Key Interview Points

Competitive Edge

Follow-up Questions

Test Your DSA Knowledge

READ NEXT

11. System Design

01. DBMS

05. Python Core