Chapter 6: Problem-Solving (DSA) - Interview Preparation Notes

Focus on essential data structures and algorithms commonly asked in interviews.

Arrays and Strings
Hashmaps and Frequency Counting
Stacks and Queues
Recursion and Backtracking
Searching and Sorting
Linked Lists
Trees (Basics)
Common Interview Patterns
Practice Problems with Solutions

1. Arrays and Strings

Two Pointers Technique

# Two Sum (sorted array)
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []
 
# Remove duplicates from sorted array
def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    
    write_index = 1
    for read_index in range(1, len(nums)):
        if nums[read_index] != nums[read_index - 1]:
            nums[write_index] = nums[read_index]
            write_index += 1
    
    return write_index

Sliding Window

# Maximum sum of subarray of size k
def max_sum_subarray(nums: list[int], k: int) -> int:
    if len(nums) < k:
        return 0
    
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum = window_sum - nums[i - k] + nums[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum
 
# Longest substring without repeating characters
def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

2. Hashmaps and Frequency Counting

Two Sum (unsorted)

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

Anagram Problems

# Group anagrams
def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = {}
    for s in strs:
        key = ''.join(sorted(s))
        if key not in groups:
            groups[key] = []
        groups[key].append(s)
    return list(groups.values())
 
# Valid anagram
def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)
 
# Using frequency counting
def is_anagram_freq(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    
    for char in t:
        if char not in freq or freq[char] == 0:
            return False
        freq[char] -= 1
    
    return True

Frequency Counting Patterns

# Top K frequent elements
from collections import Counter
import heapq
 
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    return [num for num, _ in heapq.nlargest(k, count.items(), key=lambda x: x[1])]
 
# First non-repeating character
def first_uniq_char(s: str) -> int:
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    
    for i, char in enumerate(s):
        if freq[char] == 1:
            return i
    return -1

3. Stacks and Queues

Stack Problems

# Valid parentheses
def is_valid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            stack.append(char)
    
    return not stack
 
# Daily temperatures (monotonic stack)
def daily_temperatures(temperatures: list[int]) -> list[int]:
    result = [0] * len(temperatures)
    stack = []  # stores indices
    
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index
        stack.append(i)
    
    return result

Queue Problems

from collections import deque
 
# Binary tree level order traversal (BFS)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def level_order(root: TreeNode) -> list[list[int]]:
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

4. Recursion and Backtracking

Basic Recursion

# Fibonacci with memoization
def fibonacci(n: int, memo: dict = None) -> int:
    if memo is None:
        memo = {}
    
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
 
# Factorial
def factorial(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Backtracking

# Generate all permutations
def permute(nums: list[int]) -> list[list[int]]:
    result = []
    
    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        for num in nums:
            if num not in current:
                current.append(num)
                backtrack(current)
                current.pop()
    
    backtrack([])
    return result
 
# Generate all subsets
def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    
    def backtrack(start, current):
        result.append(current[:])
        
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(0, [])
    return result

5. Searching and Sorting

Binary Search

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
 
# Search in rotated sorted array
def search_rotated(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        
        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

Sorting Algorithms

# Merge sort
def merge_sort(nums: list[int]) -> list[int]:
    if len(nums) <= 1:
        return nums
    
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    
    return merge(left, right)
 
def merge(left: list[int], right: list[int]) -> list[int]:
    result = []
    i = j = 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
 
# Quick sort
def quick_sort(nums: list[int]) -> list[int]:
    if len(nums) <= 1:
        return nums
    
    pivot = nums[len(nums) // 2]
    left = [x for x in nums if x < pivot]
    middle = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

6. Linked Lists

Basic Operations

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
# Reverse linked list
def reverse_list(head: ListNode) -> ListNode:
    prev = None
    current = head
    
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    
    return prev
 
# Detect cycle (Floyd's algorithm)
def has_cycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False
    
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False
 
# Merge two sorted lists
def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    current.next = l1 or l2
    return dummy.next

7. Trees (Basics)

Tree Traversals

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
# Inorder traversal (left, root, right)
def inorder_traversal(root: TreeNode) -> list[int]:
    result = []
    
    def inorder(node):
        if node:
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
    
    inorder(root)
    return result
 
# Preorder traversal (root, left, right)
def preorder_traversal(root: TreeNode) -> list[int]:
    result = []
    
    def preorder(node):
        if node:
            result.append(node.val)
            preorder(node.left)
            preorder(node.right)
    
    preorder(root)
    return result
 
# Postorder traversal (left, right, root)
def postorder_traversal(root: TreeNode) -> list[int]:
    result = []
    
    def postorder(node):
        if node:
            postorder(node.left)
            postorder(node.right)
            result.append(node.val)
    
    postorder(root)
    return result

Tree Properties

# Maximum depth of binary tree
def max_depth(root: TreeNode) -> int:
    if not root:
        return 0
    
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    
    return 1 + max(left_depth, right_depth)
 
# Validate binary search tree
def is_valid_bst(root: TreeNode) -> bool:
    def validate(node, min_val, max_val):
        if not node:
            return True
        
        if node.val <= min_val or node.val >= max_val:
            return False
        
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))
    
    return validate(root, float('-inf'), float('inf'))
 
# Symmetric tree
def is_symmetric(root: TreeNode) -> bool:
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        
        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))
    
    if not root:
        return True
    
    return is_mirror(root.left, root.right)

8. Common Interview Patterns

Pattern Recognition

Two Pointers: Sorted arrays, palindromes
Sliding Window: Substring problems, subarray sums
Hashmap: Frequency counting, lookups
Stack: Matching brackets, monotonic problems
BFS/DFS: Tree/graph traversal
Binary Search: Sorted arrays, peak finding
Dynamic Programming: Optimization problems

Time Complexity Cheat Sheet

O(1): Hashmap lookup, array access
O(log n): Binary search
O(n): Single pass through array
O(n log n): Sorting, heap operations
O(n²): Nested loops, bubble sort
O(2ⁿ): Exponential (recursive without memoization)

9. Practice Problems with Solutions

Easy Level

Remove Duplicates from Sorted Array

def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    
    write_index = 1
    for read_index in range(1, len(nums)):
        if nums[read_index] != nums[read_index - 1]:
            nums[write_index] = nums[read_index]
            write_index += 1
    
    return write_index

Valid Anagram

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Maximum Subarray (Kadane’s Algorithm)

def max_subarray(nums: list[int]) -> int:
    max_sum = current_sum = nums[0]
    
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

Medium Level

Longest Palindromic Substring

def longest_palindrome(s: str) -> str:
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    longest = ""
    for i in range(len(s)):
        # Odd length palindromes
        odd = expand_around_center(i, i)
        # Even length palindromes
        even = expand_around_center(i, i + 1)
        
        longest = max(longest, odd, even, key=len)
    
    return longest

3Sum

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            if current_sum == 0:
                result.append([nums[i], nums[left], nums[right]])
                
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
            elif current_sum < 0:
                left += 1
            else:
                right -= 1
    
    return result

Hard Level

Merge k Sorted Lists

import heapq
 
def merge_k_lists(lists: list[ListNode]) -> ListNode:
    min_heap = []
    
    # Add first node from each list to heap
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(min_heap, (head.val, i, head))
    
    dummy = ListNode(0)
    current = dummy
    
    while min_heap:
        val, i, node = heapq.heappop(min_heap)
        current.next = node
        current = current.next
        
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))
    
    return dummy.next

Key Takeaways for Interviews

Start with brute force, then optimize
Think out loud - explain your approach
Consider edge cases - empty inputs, single elements
Use appropriate data structures - hashmap for lookups, stack for matching
Practice time complexity analysis - be ready to explain Big O
Code cleanly - use meaningful variable names, proper indentation

Next Steps

After mastering these DSA concepts:

Practice on LeetCode (Easy → Medium → Hard)
Focus on pattern recognition
Time yourself during practice
Review solutions and understand different approaches

Remember: Consistent practice is key to success in coding interviews!

Notes

Explorer

6.Problem_Solving

Chapter 6: Problem-Solving (DSA) - Interview Preparation Notes

Table of Contents

1. Arrays and Strings

Two Pointers Technique

Sliding Window

2. Hashmaps and Frequency Counting

Two Sum (unsorted)

Anagram Problems

Frequency Counting Patterns

3. Stacks and Queues

Stack Problems

Queue Problems

4. Recursion and Backtracking

Basic Recursion

Backtracking

5. Searching and Sorting

Binary Search

Sorting Algorithms

6. Linked Lists

Basic Operations

7. Trees (Basics)

Tree Traversals

Tree Properties

8. Common Interview Patterns

Pattern Recognition

Time Complexity Cheat Sheet

9. Practice Problems with Solutions

Easy Level

Medium Level

Hard Level

Key Takeaways for Interviews

Next Steps

Graph View

Table of Contents