🏗️ DSA Patterns + OOP + Practice

Why it matters

Patterns plus structure turn random coding into reliable problem solving.

The idea

Most interview questions are a handful of patterns: two-pointer, sliding window, prefix sum, BFS/DFS, hash-map counting, binary search. Recognise the pattern, then apply the template.

Try it

Two-pointer — pair sum on a sorted array:

def two_sum_sorted(nums, target):
  l, r = 0, len(nums) - 1
  while l < r:
      s = nums[l] + nums[r]
      if s == target:
          return (l, r)
      if s < target:
          l += 1
      else:
          r -= 1
  return None

print(two_sum_sorted([1, 2, 4, 7, 11, 15], 13))
print(two_sum_sorted([1, 2, 4, 7, 11, 15], 99))

Prefix sums — answer "sum of any range" in O(1) after O(n) preprocessing:

nums = [2, 4, 5, 1, 9, 3, 7]
prefix = [0]
for x in nums: prefix.append(prefix[-1] + x)

def range_sum(l, r):
  # inclusive l, exclusive r
  return prefix[r] - prefix[l]

print(range_sum(1, 4))   # 4 + 5 + 1 = 10
print(range_sum(0, len(nums)))  # all

OOP — a small Stack with type hints:

class Stack:
  def __init__(self):
      self._data: list = []
  def push(self, x):
      self._data.append(x)
  def pop(self):
      if not self._data: raise IndexError("pop from empty stack")
      return self._data.pop()
  def peek(self):
      return self._data[-1] if self._data else None
  def __len__(self):
      return len(self._data)
  def __repr__(self):
      return f"Stack({self._data!r})"

s = Stack()
for x in [1, 2, 3]: s.push(x)
print(s, "len:", len(s))
print("pop:", s.pop())
print("peek:", s.peek())

Pattern templates

Memorise the skeletons; the problem just fills in the condition.

Sliding window

l = 0
for r in range(len(arr)):
    # expand window with r
    # shrink from the left when the condition fails
    if condition:
        l += 1

Stack pattern

stack = []
for ch in s:
    if stack and ch == stack[-1]:
        stack.pop()
    else:
        stack.append(ch)

OOP basics

class Player:
    def __init__(self, name):
        self.name = name
        self.score = 0

    def add(self, points):
        self.score += points

• A class defines a blueprint.
• An instance is a concrete object.
• self refers to the current object.

DSA patterns cheatsheet

| Pattern | When to reach for it | | --- | --- | | Two pointers | Sorted arrays, pair from the ends | | Sliding window | Subarray with a sum / condition | | Prefix sums | Range-sum queries | | Hash map (dict) | Count frequency, complement lookup | | Stack | Valid parentheses, monotonic stack |

If you see X, think Y

• "Unique elements" → set
• "Count frequency" → dict
• "Lookup complement / previously seen" → dict
• "Reverse / palindrome / pair from ends" → two pointers
• "Running total" → prefix sum

Must-memorize built-ins

len, type, range, enumerate, sorted, sum, min, max

Practice system

Bug journal

Use this format whenever you get stuck — the goal is to extract a reusable rule from each bug:

• Date:
• Problem:
• What I expected:
• What happened:
• Root cause:
• Fix:
• Rule for next time:

Example root cause: used b = a instead of a.copy().

LeetCode tracker (sample)

| # | Problem | Topic | Status | Key Idea | Mistake | Retry | | - | ------- | ----- | ------ | -------- | ------- | ----- | | 1 | Two Sum | dict | | complement lookup | | | | 2 | Valid Palindrome | strings | | normalize + two pointers | | | | 3 | Contains Duplicate | set | | set-length compare | | | | 4 | Valid Anagram | dict | | frequency counts | | | | 5 | Running Sum | lists | | prefix running total | | |

Quick check

• Q: When should you use a class? A: When state and behaviour belong together.

Mini drills

• Implement two-pointer reverse.
• Write a tiny class with two methods.

Do's and don'ts

• Do write small templates you can reuse.
• Do keep classes simple and focused.
• Don't over-engineer when a function is enough.

Common mistakes

• Mistake: Forgetting to update pointers in loops. Fix: Always move at least one pointer.
• Mistake: Overusing classes for simple data. Fix: Start with functions, refactor later.

Key takeaways

• Two-pointer: sorted array, find a pair / partition.
• Sliding window: contiguous subarray with a constraint (longest, smallest).
• Prefix sum: many range-sum queries on a fixed array.
• OOP: encapsulate STATE; behaviour follows. Use __repr__ to make debugging painless.
• Keep a bug journal and a problem tracker — tracking mistakes is how you improve fastest.