← Back to Tutorials Chapter 14

Practice & Certification

This chapter brings everything together. You will find example problems with solutions, exercises organized by difficulty, quiz questions, a syllabus outline, an 8-week study plan, interview preparation tips, and DSA certification paths.

Example Problems with Solutions

Problem 1: Two Sum (Easy)

Given an array of integers and a target, return indices of two numbers that add up to the target.

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

Time: O(n), Space: O(n).

Problem 2: Maximum Subarray (Medium)

Find the contiguous subarray with the largest sum (Kadane's Algorithm).

def max_subarray(nums):
    max_ending = max_sofar = nums[0]
    for x in nums[1:]:
        max_ending = max(x, max_ending + x)
        max_sofar = max(max_sofar, max_ending)
    return max_sofar

Time: O(n), Space: O(1).

Problem 3: Merge K Sorted Lists (Hard)

Merge k sorted linked lists into one sorted list. Use a min-heap.

import heapq

def merge_k_lists(lists):
    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

Time: O(N log k), where N is total elements and k is number of lists.

Exercises by Difficulty

Easy

• Find the maximum element in an array.
• Reverse a linked list iteratively and recursively.
• Check if a string is a palindrome.
• Implement binary search on a sorted array.
• Find the first non-repeating character in a string.
• Implement a stack using two queues.
• Count the number of set bits in an integer.

Medium

• Find the longest substring without repeating characters.
• Clone a graph (BFS / DFS approach).
• Check if a binary tree is a valid BST.
• Find the LCA (Lowest Common Ancestor) of two nodes in a binary tree.
• Implement Dijkstra's shortest path algorithm.
• Flatten a binary tree to a linked list.
• Detect a cycle in a linked list and find the start of the cycle.

Hard

• Maximum path sum in a binary tree.
• Serialize and deserialize a binary tree.
• Median of two sorted arrays in O(log(m+n)) time.
• Trapping rain water (two-pointer approach).
• Word ladder (shortest transformation sequence).
• N-Queens problem (backtracking).
• Design a LRU (Least Recently Used) cache.

Quiz Questions

1. What is the time complexity of binary search? Answer: O(log n)
2. Which sorting algorithm has the best worst-case time complexity? Answer: Merge Sort / Heap Sort (O(n log n))
3. What data structure is used for DFS? Answer: Stack (recursive call stack)
4. What is the space complexity of Merge Sort? Answer: O(n)
5. When does a greedy algorithm fail? Answer: When the greedy choice property does not hold — local optima do not lead to global optimum.
6. What is the key difference between Prim's and Kruskal's algorithms? Answer: Prim grows vertex-by-vertex; Kruskal grows edge-by-edge using Union-Find.
7. State the Max-Flow Min-Cut theorem. Answer: The maximum flow value equals the minimum cut capacity.
8. Explain the difference between memoization and tabulation in DP. Answer: Memoization is top-down (recursion + cache); tabulation is bottom-up (iterative table filling).

Syllabus Outline

Module	Topics
1. Foundations	Complexity analysis, recursion, problem-solving patterns
2. Arrays & Sorting	Array manipulations, sorting algorithms, searching
3. Linked Lists	Singly, doubly, circular, fast & slow pointer
4. Stacks & Queues	Stack, queue, deque, priority queue, monotonic stack
5. Hash Tables	Hashing, collision resolution, hash map patterns
6. Trees	Binary trees, BST, traversals, AVL, heaps, tries
7. Graphs	Representation, BFS, DFS, cycle detection, topological sort
8. Advanced Graphs	Shortest paths, MST, maximum flow
9. DP & Greedy	Dynamic programming, greedy algorithms
10. Advanced Topics	Backtracking, bit manipulation, string algorithms, segment trees

8-Week Study Plan

Week	Focus	Problems per Day
1	Complexity, Arrays, Sorting, Searching	2
2	Linked Lists, Stacks, Queues	2
3	Hash Tables, Recursion	2
4	Trees, BST, Heaps	2
5	Graphs: BFS, DFS, Topological Sort	2
6	Shortest Paths, MST, Maximum Flow	1-2
7	Dynamic Programming	2
8	Greedy, Backtracking, Review & Mock Interviews	3

Interview Preparation Tips

• Understand the problem — Ask clarifying questions. Identify input/output constraints. Discuss edge cases.
• Brute force first — Propose a naive solution, then optimize. Interviewers want to see your thought process.
• Use a whiteboard / paper — Draw diagrams to visualize data structures and algorithms.
• Test your code — Walk through example inputs and edge cases (empty, single element, duplicates).
• Communicate — Explain your reasoning, time and space complexity, and trade-offs.
• Practice with a timer — Simulate real interview conditions on platforms like LeetCode, HackerRank, or CodeSignal.
• Review fundamentals — Know array, string, tree, graph, DP, and hash table patterns by heart.

Certification Paths

• LeetCode — Weekly contests, study plans, and interview assessments.
• HackerRank — Skill certification tests (Problem Solving, Java, Python).
• CodeSignal — General Coding Assessment (GCA) used by companies.
• Google Tech Dev Guide — Free learning path with curated resources.
• Coursera / edX — Data Structures and Algorithms specializations (UC San Diego, Stanford, Princeton).
• GitHub Copilot — Use AI-assisted coding to accelerate practice and learn patterns faster.