Data Structures and Algorithms: Key Concepts, Patterns and a 12-Week Plan

Why DSA and what interviewers want

Data structures and algorithms (DSA) are how companies test problem solving, because the questions are language-independent and can be graded fairly. A good performance is not about memorising 500 solutions. It is about recognising patterns, choosing the right structure, writing correct code and explaining your thinking and complexity. Product companies test DSA heavily (Amazon, Google, Microsoft) and many service companies include easier versions in online tests (assessment tips).

Choose one language (Python, Java or C++) and stay with it (Python, Java, C/C++).

1. Complexity: the language of every answer

Big-O describes how time or memory grows with the input size n. Always state both time and space.

Complexity	Name	Typical example
O(1)	Constant	Array index, hash lookup
O(log n)	Logarithmic	Binary search, balanced tree
O(n)	Linear	One pass over an array
O(n log n)	Linearithmic	Merge sort, heap sort, sort()
O(n²)	Quadratic	Nested loops, bubble sort
O(2ⁿ)	Exponential	Naive recursion over subsets

A rough rule from input size: n up to 10⁵ needs O(n log n) or better; n up to 10³ allows O(n²); n up to 20 allows exponential approaches. Use this to guess the intended solution.

2. Data structures cheat sheet

Structure	Access	Search	Insert / delete	Notes
Array	O(1)	O(n)	O(n)	Contiguous memory
Linked list	O(n)	O(n)	O(1) at a known node	Pointer chasing
Stack (LIFO)			O(1)	Undo, parentheses, DFS
Queue (FIFO)			O(1)	BFS, scheduling
Hash map / set		O(1) avg	O(1) avg	Frequency, lookup
Heap	O(1) top		O(log n)	Top-k, scheduling
Binary search tree (balanced)		O(log n)	O(log n)	Sorted data
Trie		O(length)	O(length)	Prefix search
Graph				Adjacency list is the default

Know how each works internally (a hash map uses a hash function and buckets, a heap is an array-based complete binary tree) because interviewers ask follow-ups.

3. The patterns that solve most problems

Hash map for counting and lookup

"Have I seen this before?" "How many of each?"

def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i

Related: anagrams, subarray sum equals k (prefix sums with a map), longest substring without repeating characters.

Two pointers

Used on sorted arrays or strings: pair with a target sum, remove duplicates, reverse, palindrome check, container with most water, 3Sum.

Sliding window

For "longest/shortest subarray or substring that satisfies a condition".

def longest_unique_substring(s):
    last, start, best = {}, 0, 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1
        last[ch] = i
        best = max(best, i - start + 1)
    return best

Binary search

Not only for sorted arrays: whenever the answer is monotonic ("minimum capacity that works", "smallest speed"), binary search on the answer.

def binary_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x: return mid
        if a[mid] < x: lo = mid + 1
        else: hi = mid - 1
    return -1

Write it carefully; off-by-one errors are the usual failure. Also practise rotated sorted arrays and first/last occurrence.

Prefix sums

Precompute running totals so any range sum is O(1). Used in subarray and 2D matrix problems.

Fast and slow pointers (linked lists)

Detect a cycle, find the middle, find the start of a cycle; reverse a linked list (iteratively and recursively); merge two sorted lists.

Stack and monotonic stack

Valid parentheses, next greater element, daily temperatures, largest rectangle in a histogram, evaluate expressions.

Recursion and backtracking

Generate all subsets, permutations and combinations; N-Queens; word search; sudoku. Template: choose, explore, un-choose.

def subsets(nums):
    res, path = [], []
    def go(i):
        if i == len(nums):
            res.append(path[:]); return
        go(i + 1)               # skip nums[i]
        path.append(nums[i])    # take nums[i]
        go(i + 1)
        path.pop()
    go(0)
    return res

Trees

Know pre, in and post-order traversal (recursive and iterative), level-order with a queue, height, diameter, lowest common ancestor, validate a BST, and path sum problems. Most tree problems are solved by a recursive function that returns information from its children.

Graphs

Represent with an adjacency list. BFS gives shortest paths in unweighted graphs; DFS explores and detects cycles. Practise number of islands, clone graph, course schedule (topological sort), connected components, shortest path (Dijkstra for weighted edges), and union-find (disjoint set) for connectivity.

from collections import deque
def bfs(graph, start):
    seen, q = {start}, deque([start])
    while q:
        node = q.popleft()
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt); q.append(nxt)
    return seen

Heap / priority queue

Top-k elements, kth largest, merge k sorted lists, median of a data stream (two heaps), task scheduling.

Dynamic programming

Break the problem into overlapping subproblems and store the answers. Learn it as a separate topic (dynamic programming explained).

Greedy

Make the locally best choice: interval scheduling, jump game, gas station. Always be ready to argue why greedy is correct, or find a counterexample.

Bit manipulation

XOR for the single number, checking powers of two, counting set bits (C guide).

4. Sorting and searching you must know

• Bubble, selection, insertion: simple, O(n²)
• Merge sort: O(n log n), stable, extra space
• Quick sort: average O(n log n), worst O(n²), in place
• Heap sort: O(n log n), in place
• Counting and radix: linear time with limits on the input
• Be able to explain stability and write merge sort and quick sort partition from memory
• Binary search variants and searching in a 2D matrix

5. How to solve a problem in the interview

1. Clarify: inputs, constraints, duplicates, empty input, negative values, expected output
2. Examples: work through a small one by hand
3. Brute force: say it aloud and state its complexity
4. Optimise: look for the pattern, ask "what is repeated?" and "what structure makes this faster?"
5. Code: clean variable names, helper functions, no silent assumptions
6. Test: run through your example, then edge cases (empty, one element, all same, large)
7. Analyse: time and space complexity

If you are stuck, think aloud, simplify the problem, try a smaller input or ask for a hint. Interviewers value your reasoning more than a silent perfect answer.

6. The 12-week plan

Weeks	Focus	Target
1	Language fluency, complexity, arrays and strings	20 problems
2	Hash maps, two pointers, sliding window	25 problems
3	Binary search, sorting, prefix sums	20 problems
4	Linked lists, stacks, queues	20 problems
5	Recursion and backtracking	15 problems
6	Trees and binary search trees	25 problems
7	Graphs: BFS, DFS, topological sort	20 problems
8	Heaps, tries, union-find	15 problems
9	Dynamic programming (1D, grid, knapsack)	25 problems
10	Greedy, intervals, bit manipulation, mixed review	20 problems
11	Timed mock contests and weak topics	3 mock rounds
12	Revision, mock interviews, system design basics	Mock interviews

Around 200 well-understood problems beat 600 skimmed ones. For each problem, write down the pattern and what you got wrong, then re-solve it after a week.

7. Study habits that work

• Spend 20 to 30 minutes trying before reading a solution; then study the solution until you can explain it, and re-code it from memory
• Keep a notebook or sheet: problem, pattern, mistake, complexity
• Practise on a plain editor sometimes, since interviews may not give autocomplete
• Do timed practice (30 to 45 minutes per medium problem)
• Use platforms such as LeetCode, GeeksforGeeks, HackerRank, Codeforces and CodeChef, and pick curated lists instead of random problems
• Learn the standard library of your language (Python collections, Java collections)

8. Common mistakes

• Jumping to code without clarifying or planning
• Memorising solutions instead of patterns
• Ignoring edge cases such as empty input, a single element and integer overflow
• Not stating complexity unless asked
• Avoiding a topic (graphs, DP) until the last week
• Practising only easy problems

9. Where DSA meets the rest of the interview

Strong candidates also prepare core CS subjects, system design basics and behavioural answers. Use the technical interview checklist in the final week.