Python
OOP + अभ्यास · #10 / 11

DSA Patterns + OOP + Practice

Two pointers, prefix sums, और साफ़ design

यह क्यों मायने रखता है

Patterns और संरचना मिलकर अनियमित coding को भरोसेमंद समस्या-समाधान में बदल देते हैं।

मूल विचार

ज़्यादातर interview सवाल गिने-चुने patterns होते हैं: two-pointer, sliding window, prefix sum, BFS/DFS, hash-map गिनती, binary search। Pattern पहचानिए, फिर template लगाइए।

आज़माकर देखिए

Two-pointer — किसी sorted array पर pair sum:

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))
not loaded

Prefix sums — O(n) पूर्व-प्रसंस्करण के बाद "किसी भी range का योग" O(1) में उत्तर दीजिए:

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
not loaded

OOP — type hints के साथ एक छोटा Stack:

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())
not loaded

Pattern templates

ढाँचों को याद कर लीजिए; समस्या बस शर्त भर देती है।

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 की बुनियादी बातें

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

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

DSA patterns की चीटशीट

| Pattern | इसकी ओर कब बढ़ें | | --- | --- | | Two pointers | Sorted arrays, सिरों से जोड़ा | | Sliding window | किसी sum / शर्त वाला subarray | | Prefix sums | Range-sum queries | | Hash map (dict) | Frequency गिनती, complement lookup | | Stack | Valid parentheses, monotonic stack |

अगर X दिखे, तो Y सोचें

ज़रूर याद करने वाले built-ins

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

अभ्यास की व्यवस्था

Bug journal

जब भी आप अटक जाएँ इस प्रारूप का इस्तेमाल कीजिए — लक्ष्य है हर bug से एक दोबारा इस्तेमाल होने वाला नियम निकालना:

उदाहरण root cause: a.copy() के बजाय b = a इस्तेमाल किया।

LeetCode tracker (नमूना)

| # | 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 | | |

झटपट जाँच

छोटे अभ्यास

क्या करें और क्या न करें

आम ग़लतियाँ

मुख्य बातें