chtnnh's Digital Garden

quickRefresher

13 min read

DSA and Competitive Programming: A Concise Preparation Guide

Goal: To provide a focused review of essential DSA concepts and problem-solving patterns for competitive programming and technical interviews.

Table of Contents

  1. Arrays and Strings
  2. Linked Lists
  3. Trees (Binary Trees)
  4. Hash Maps (Dictionaries)
  5. Heaps (Priority Queues)
  6. Dynamic Programming
  7. Greedy Algorithms
  8. Graph Algorithms
  9. Sorting and Searching
  10. Additional Tips and Resources

1. Arrays and Strings

  • Key Points:
    • Basic Operations: Traversal, indexing, slicing, concatenation, and manipulation.
    • Sliding Window: Efficiently process contiguous subarrays or substrings.
      • When to use: Optimization problems on contiguous segments.
      • Example: Find the maximum sum of a subarray of size k.
    • Two Pointers: Using two pointers to iterate through the array/string, often from opposite ends.
      • When to use: Problems involving sorted data or finding pairs/combinations.
      • Example: Check if a string is a palindrome.
    • Prefix Sum: Calculate cumulative sums for efficient range queries.
      • When to use: Problems involving frequent calculations of sums over ranges.
      • Example: Given an array, find the sum of elements between indices i and j for multiple queries.
    • Common String Operations: String matching, reversing, and searching.
  • References:
  • Practice Problems:
    • Problem 1: Two Sum

      • Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

      • Solution:

        def twoSum(nums, target):
    """
    Finds two numbers in a list that add up to a target value.
 
    Args:
        nums: A list of integers.
        target: The target sum.
 
    Returns:
        A list of two indices, or None if no solution is found.
    """
    num_map = {}  # Create a dictionary to store numbers and their indices
    for index, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], index]
        num_map[num] = index
    return None  # Return None if no solution exists
    • Problem 2: Reverse String

      • Write a function that reverses a string in place.

      • Solution:

        def reverseString(s):
    """Reverses a string in place.
 
    Args:
        s: A list of characters representing the string.
    """
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

2. Linked Lists

  • Key Points:
    • Basic Operations: Insertion, deletion, traversal, and reversal.
    • Types of Linked Lists: Singly, doubly, and circular linked lists.
    • Fast and Slow Pointers (Floyd’s Algorithm): Detect cycles and find the middle node.
      • When to use: Cycle detection, finding the k-th element from the end.
      • Example: Determine if a linked list has a cycle.
    • Dummy Nodes: Simplify operations at the head of the list.
    • Recursion: Useful for reversing linked lists or solving problems with recursive structures.
  • References:
  • Practice Problems:
    • Problem 1: Reverse Linked List

      • Reverse a singly linked list.

      • Solution:

        class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def reverseList(head):
    """Reverses a singly linked list.
 
    Args:
        head: The head of the linked list.
 
    Returns:
        The head of the reversed linked list.
    """
    prev, curr = None, head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev
    • Problem 2: Detect Cycle in a Linked List

      • Determine if a linked list has a cycle.

      • Solution:

        def hasCycle(head):
    """Detects if a linked list has a cycle.
 
    Args:
        head: The head of the linked list.
 
    Returns:
        True if the list has a cycle, False otherwise.
    """
    if not head or not head.next:
        return False
    slow, fast = head, head.next
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    return True

3. Trees (Binary Trees)

  • Key Points:
    • Tree Traversal:
      • Depth-First Search (DFS): Inorder, preorder, postorder.
      • Breadth-First Search (BFS): Level order traversal.
    • Recursion: Essential for solving many tree problems.
    • Tree Properties: Balanced, complete, and perfect binary trees.
    • Binary Search Trees (BSTs): Ordered trees that allow for efficient searching, insertion, and deletion.
  • References:
  • Practice Problems:
    • Problem 1: Binary Tree Inorder Traversal

      • Given the root of a binary tree, return the inorder traversal of its nodes’ values.

      • Solution:

        class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def inorderTraversal(root):
    """Performs an inorder traversal of a binary tree.
 
    Args:
        root: The root of the binary tree.
 
    Returns:
        A list of the nodes' values in inorder.
    """
    result = []
 
    def _inorder(node):
        if not node:
            return
        _inorder(node.left)
        result.append(node.val)
        _inorder(node.right)
 
    _inorder(root)
    return result
    • Problem 2: Maximum Depth of Binary Tree

      • Given the root of a binary tree, find its maximum depth.

      • Solution:

        def maxDepth(root):
    """Finds the maximum depth of a binary tree.
 
    Args:
        root: The root of the binary tree.
 
    Returns:
        The maximum depth of the tree.
    """
    if not root:
        return 0
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    return max(left_depth, right_depth) + 1

4. Hash Maps (Dictionaries)

  • Key Points:
    • Basic Operations: Insertion, deletion, and lookup.
    • Collision Handling: Understanding how collisions are resolved (e.g., chaining, open addressing).
    • Applications: Frequency counting, caching, and efficient lookups.
      • When to use: Problems requiring fast lookups, checking for existence, or counting occurrences.
      • Example: Implement a “two sum” problem.
    • Ordered vs. Unordered Maps: Consider the need for sorted keys.
  • References:
  • Practice Problems:
    • Problem 1: Two Sum

      • Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

      • Solution:

        def twoSum(nums, target):
    """
    Finds two numbers in a list that add up to a target value.
 
    Args:
        nums: A list of integers.
        target: The target sum.
 
    Returns:
        A list of two indices, or None if no solution is found.
    """
    num_map = {}  # Create a dictionary to store numbers and their indices
    for index, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], index]
        num_map[num] = index
    return None  # Return None if no solution exists
    • Problem 2: Group Anagrams

      • Given an array of strings, group the anagrams together.

      • Solution:

        def groupAnagrams(strs):
    """Groups anagrams together.
 
    Args:
        strs: A list of strings.
 
    Returns:
        A list of lists, where each inner list contains anagrams.
    """
    anagram_map = {}
    for s in strs:
        sorted_s = "".join(sorted(s))  # Sort the string to identify anagrams
        if sorted_s not in anagram_map:
            anagram_map[sorted_s] = []
        anagram_map[sorted_s].append(s)
    return list(anagram_map.values())

5. Heaps (Priority Queues)

  • Key Points:
    • Heap Properties: Min-heap and max-heap.
    • Basic Operations: Insertion, extraction of minimum/maximum.
    • Applications:
      • Sorting (heap sort).
      • Priority queues.
      • Graph algorithms (Dijkstra’s algorithm).
      • Finding the k-th largest/smallest element.
    • Implementation: Typically implemented using arrays.
  • References:
  • Practice Problems:
    • Problem 1: Kth Largest Element in a Stream

      • Design a class to find the kth largest element in a stream.

      • Solution:

        import heapq
 
class KthLargest:
    def __init__(self, k, nums):
        """
        Initializes the KthLargest object.
 
        Args:
            k: The value of k.
            nums: The initial list of numbers.
        """
        self.k = k
        self.heap = nums[:k]  # Initialize the heap with the first k elements
        heapq.heapify(self.heap)  # Convert the list to a min-heap
        for num in nums[k:]:
            if num > self.heap[0]:
                heapq.heapreplace(self.heap, num)
 
    def add(self, val):
        """
        Adds a new element to the stream and returns the kth largest element.
 
        Args:
            val: The new element to add.
 
        Returns:
            The kth largest element after adding the new element.
        """
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap, val)
        return self.heap[0]
    • Problem 2: Merge k Sorted Lists

      • Merge k sorted linked lists into one sorted linked list.

      • Solution:

        import heapq
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def mergeKLists(lists):
    """Merges k sorted linked lists.
 
    Args:
        lists: A list of linked list heads.
 
    Returns:
        The head of the merged sorted linked list.
    """
    heap = []
    for head in lists:
        if head:
            heapq.heappush(heap, (head.val, head))  # Push (value, node)
 
    dummy = ListNode()
    curr = dummy
    while heap:
        val, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, node.next))
    return dummy.next

6. Dynamic Programming (DP)

  • Key Points:
    • Optimal Substructure: The optimal solution to a problem contains optimal solutions to subproblems.
    • Overlapping Subproblems: The same subproblems are solved multiple times.
    • Memoization (Top-Down): Store the results of expensive function calls and reuse them.
    • Tabulation (Bottom-Up): Build a table of solutions to subproblems.
    • Common DP Problems:
      • Fibonacci sequence.
      • Knapsack problem.
      • Longest common subsequence.
      • Edit distance.
  • References:
  • Practice Problems:
    • Problem 1: Fibonacci Number

      • Calculate the nth Fibonacci number.

      • Solution (Tabulation):

        def fib(n):
    """Calculates the nth Fibonacci number using tabulation.
 
    Args:
        n: The index of the Fibonacci number to calculate.
 
    Returns:
        The nth Fibonacci number.
    """
    if n <= 1:
        return n
    dp = [0, 1]  # Initialize the first two Fibonacci numbers
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[n]
    • Problem 2: Coin Change

      • Given a set of coin denominations and an amount, find the minimum number of coins to make up that amount.

      • Solution (Tabulation):

        def coinChange(coins, amount):
    """Calculates the minimum number of coins to make up an amount.
 
    Args:
        coins: A list of coin denominations.
        amount: The target amount.
 
    Returns:
        The minimum number of coins, or -1 if it's not possible.
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins needed for amount 0
    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 -1

7. Greedy Algorithms

  • Key Points:
    • Make the locally optimal choice at each step in the hope of finding a global optimum.
    • Not always guaranteed to produce the optimal solution.
    • Applications:
      • Activity selection.
      • Coin change problem.
      • Fractional knapsack.
    • Proof of Correctness: Important to prove why a greedy algorithm works.
  • References:
  • Practice Problems:
    • Problem 1: Activity Selection

      • Given a set of activities with start and finish times, select the maximum number of non-overlapping activities.

      • Solution:

        def activitySelection(start, finish):
    """Selects the maximum number of non-overlapping activities.
 
    Args:
        start: A list of start times.
        finish: A list of finish times (sorted by finish times).
 
    Returns:
        A list of indices of the selected activities.
    """
    n = len(start)
    selected = [0]  # Select the first activity
    j = 0  # Index of the last selected activity
    for i in range(1, n):
        if start[i] >= finish[j]:
            selected.append(i)
            j = i
    return selected
    • Problem 2: Coin Change (Greedy - Not Always Optimal)

      • Given a set of coin denominations, find the minimum number of coins to make up a given amount. (Greedy approach - not always optimal for all coin denominations)

      • Solution:

        def coinChangeGreedy(coins, amount):
    """Calculates the minimum number of coins to make up an amount using a greedy approach.
 
    Args:
        coins: A list of coin denominations (sorted in descending order).
        amount: The target amount.
 
    Returns:
        The minimum number of coins, or -1 if it's not possible.
    """
    coins.sort(reverse=True)  # Sort coins in descending order
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

8. Graph Algorithms

  • Key Points:
    • Graph Representations: Adjacency matrix and adjacency list.
    • Graph Traversal:
      • Breadth-First Search (BFS): Shortest path in unweighted graphs.
      • Depth-First Search (DFS): Exploring all reachable nodes.
    • Shortest Path Algorithms:
      • Dijkstra’s algorithm: Shortest path in graphs with non-negative edge weights.
      • Bellman-Ford algorithm: Shortest path in graphs with negative edge weights.
    • Minimum Spanning Tree:
      • Kruskal’s Algorithm
      • Prim’s Algorithm
    • Topological Sorting: Ordering of nodes in a directed acyclic graph (DAG).
  • References:
  • Practice Problems:
    • Problem 1: Breadth-First Search (BFS)

      • Given a graph and a starting node, perform a BFS traversal.

      • Solution:

        from collections import deque
 
def bfs(graph, start):
    """Performs a breadth-first search on a graph.
 
    Args:
        graph: An adjacency list representation of the graph.
        start: The starting node for the traversal.
 
    Returns:
        A list of nodes visited in BFS order.
    """
    visited = {start}
    queue = deque([start])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result
    • Problem 2: Depth-First Search (DFS)

      • Given a graph and a starting node, perform a DFS traversal.

      • Solution:

        def dfs(graph, start):
    """Performs a depth-first search on a graph.
 
    Args:
        graph: An adjacency list representation of the graph.
        start: The starting node for the traversal.
 
    Returns:
        A list of nodes visited in DFS order.
    """
    visited = {start}
    result = []
 
    def _dfs(node):
        visited.add(node)
        result.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                _dfs(neighbor)
 
    _dfs(start)
    return result

9. Sorting and Searching

  • Key Points:
    • Sorting Algorithms:
      • Comparison-based: Merge sort, quicksort, heap sort.
      • Linear time: Counting sort, radix sort.
    • Searching Algorithms:
      • Linear search: O(n).
      • Binary search: O(log n) (for sorted data).
    • Lower Bound for Sorting: Ω(n log n) for comparison-based sorting.
  • References:
  • Practice Problems:
    • Problem 1: Binary Search

      • Given a sorted array and a target value, find the index of the target value in the array.

      • Solution:

        def binarySearch(arr, target):
    """Performs a binary search on a sorted array.
 
    Args:
        arr: A sorted list of integers.
        target: The target value to search for.
 
    Returns:
        The index of the target value, or -1 if not found.
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
    • Problem 2: Merge Sort

      • Sort an unsorted array using the merge sort algorithm.

      • Solution:

        def mergeSort(arr):
    """Sorts an array using the merge sort algorithm.
 
    Args:
        arr: A list of integers.
 
    Returns:
        A new sorted list.
    """
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = mergeSort(arr[:mid])
    right_half = mergeSort(arr[mid:])
    return _merge(left_half, right_half)
 
def _merge(left, right):
    """Merges two sorted lists.
 
    Args:
        left: A sorted list.
        right: A sorted list.
 
    Returns:
        A new sorted list containing elements from both input lists.
    """
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

10. Additional Tips and Resources

  • Practice Platforms:
  • Key Strategies:
    • Understand the Problem: Clarify constraints and edge cases.
    • Develop an Algorithm: Design a step-by-step approach before coding.
    • Write Clean Code: Use meaningful variable names and proper indentation.
    • Analyze Complexity: Determine the time and space complexity of your solution.
    • Test Thoroughly: Test with various inputs, including edge cases.
  • Additional Resources:
    • MIT Introduction to Algorithms (CLRS): A comprehensive textbook.
    • “Competitive Programming” by Steven Halim: A guide for competitive programming.

This document provides a starting point for your DSA and competitive programming preparation. Remember that consistent practice and problem-solving are crucial for success.

Graph View