# ================================================================
# CREATION
# ================================================================
lst = []                        # empty list
lst = [1, 2, 3]                 # literal syntax
lst = list(range(5))            # [0,1,2,3,4] — from any iterable
lst = list("hello")             # ['h','e','l','l','o'] — from string
lst = [0] * 5                   # [0,0,0,0,0] — ⚠️ careful with mutables!
 
# ================================================================
# ADDING ELEMENTS
# ================================================================
lst = [1, 2, 3]
 
lst.append(4)
# → [1, 2, 3, 4]
# append ALWAYS adds the object AS-IS (single element)
 
lst.append([5, 6])
# → [1, 2, 3, 4, [5, 6]]  ← nested! NOT flat!
# append does NOT unpack iterables
 
lst.extend([7, 8])
# → [1, 2, 3, 4, [5, 6], 7, 8]
# extend unpacks the iterable — adds each element individually
# equivalent to: for x in [7,8]: lst.append(x)
 
lst.insert(0, 99)
# → [99, 1, 2, 3, 4, [5, 6], 7, 8]
# insert(index, element) — shifts everything from index onwards → O(n)
 
lst += [10, 11]
# += is same as extend — modifies in place
# NOT same as lst = lst + [10,11] (which creates new list)
 
# ================================================================
# REMOVING ELEMENTS
# ================================================================
lst = [10, 20, 30, 20, 40]
 
val = lst.pop()
# → returns 40, lst = [10, 20, 30, 20]
# pop() with no argument removes LAST element → O(1)
 
val = lst.pop(1)
# → returns 20, lst = [10, 30, 20]
# pop(i) removes at index i → O(n) because of shifting
 
lst.remove(30)
# → lst = [10, 20]
# remove removes FIRST occurrence of the VALUE
# ⚠️ raises ValueError if value not found!
 
del lst[0]
# → lst = [20]
# del by index — statement not method
 
lst = [1, 2, 3, 4, 5]
del lst[1:3]
# → [1, 4, 5] — delete a slice
 
lst.clear()
# → [] — empties the list, same object (id unchanged)
 
# ================================================================
# SEARCHING / QUERYING
# ================================================================
lst = [10, 20, 30, 20, 40]
 
20 in lst                       # True  — O(n) membership test
lst.index(20)                   # 1     — FIRST index of value
lst.index(20, 2)                # 3     — search starting from index 2
# ⚠️ lst.index(99) → ValueError if not found!
 
lst.count(20)                   # 2     — count all occurrences
len(lst)                        # 5     — O(1), stored internally
 
# ================================================================
# SORTING AND REVERSING
# ================================================================
lst = [3, 1, 4, 1, 5, 9, 2, 6]
 
lst.sort()
# sorts IN PLACE → [1, 1, 2, 3, 4, 5, 6, 9]
# returns None! ← common interview trap
 
lst.sort(reverse=True)          # descending: [9, 6, 5, 4, 3, 2, 1, 1]
lst.sort(key=abs)               # sort by absolute value
 
new_lst = sorted(lst)
# returns NEW sorted list — original UNCHANGED
# sorted() works on any iterable, sort() only on lists
 
lst.reverse()
# reverses IN PLACE → returns None
# alternative: reversed(lst) returns iterator (no new list)
 
# ================================================================
# COPYING
# ================================================================
lst = [1, [2, 3], 4]
 
shallow = lst.copy()            # same as lst[:] or list(lst)
# ⚠️ shallow copy: nested objects are SHARED REFERENCES
shallow[1].append(99)           # lst ALSO becomes [1, [2, 3, 99], 4]!
 
import copy
deep = copy.deepcopy(lst)       # recursively copies EVERYTHING
deep[1].append(100)             # lst unchanged — fully independent

lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# Syntax: lst[start : stop : step]
# start = inclusive, stop = exclusive, step = direction & skip
 
lst[2:5]        # [2, 3, 4]       — index 2 up to (not including) 5
lst[:3]         # [0, 1, 2]       — from beginning
lst[7:]         # [7, 8, 9]       — from index 7 to end
lst[::2]        # [0, 2, 4, 6, 8] — every 2nd element (even indices)
lst[1::2]       # [1, 3, 5, 7, 9] — every 2nd starting at index 1
 
lst[::-1]       # [9,8,7,6,5,4,3,2,1,0] — REVERSE (creates new list)
lst[2:6][::-1]  # [5, 4, 3, 2]   — reverse a sub-portion
 
lst[-1]         # 9               — last element (negative index from end)
lst[-3:]        # [7, 8, 9]       — last 3 elements
lst[:-2]        # [0,1,2,3,4,5,6,7] — all except last 2
 
# Assign to slice (in-place modification):
lst[2:4] = [20, 30]             # replace elements at index 2 and 3
lst[1:1] = [99]                 # INSERT at index 1 (nothing removed)
lst[2:5] = []                   # delete elements at index 2, 3, 4
 
# Copy with slice:
copy = lst[:]                   # shallow copy of entire list

# ✅ LIST AS STACK (LIFO) — Efficient
stack = []
stack.append(1)                 # push  → O(1)
stack.append(2)
stack.append(3)
top = stack[-1]                 # peek  → O(1) (no removal)
val = stack.pop()               # pop   → O(1), returns 3
 
# ❌ LIST AS QUEUE (FIFO) — Inefficient!
queue = []
queue.append(1)                 # enqueue at end   → O(1)
queue.append(2)
front = queue.pop(0)            # dequeue from front → O(n)!
# WHY O(n)? Every remaining element must shift left:
# Before: [1, 2, 3, 4, 5]
# After:  [2, 3, 4, 5]   ← indices 1,2,3,4 all shift to 0,1,2,3
 
# ✅ USE collections.deque FOR O(1) QUEUE
from collections import deque
q = deque()
q.append(1)                     # enqueue right → O(1)
q.append(2)
val = q.popleft()               # dequeue left  → O(1)
# deque is a doubly-linked list of fixed-size blocks internally

# ================================================================
# PATTERN 1: TWO POINTERS — Opposite Ends
# Use case: palindrome check, two-sum on sorted array
# ================================================================
def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1        # start at both ends
    while left < right:                  # move toward center
        if s[left] != s[right]:          # mismatch found
            return False
        left += 1                        # move inward
        right -= 1
    return True                          # all matched
 
# ================================================================
# PATTERN 2: TWO POINTERS — Same Direction (Fast & Slow)
# Use case: remove duplicates from sorted array in-place
# ================================================================
def remove_duplicates(nums: list) -> int:
    if not nums:
        return 0
    slow = 0                             # slow = write position
    for fast in range(1, len(nums)):     # fast = read position
        if nums[fast] != nums[slow]:     # found new unique element
            slow += 1                    # advance write position
            nums[slow] = nums[fast]      # write unique element
    return slow + 1                      # length of unique portion
 
# ================================================================
# PATTERN 3: SLIDING WINDOW — Fixed Size
# Use case: maximum sum of subarray of size k
# ================================================================
def max_sum_subarray(nums: list, k: int) -> int:
    window_sum = sum(nums[:k])           # sum of first window
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i]            # add element entering window
        window_sum -= nums[i - k]        # remove element leaving window
        max_sum = max(max_sum, window_sum)
    return max_sum
    # Time: O(n), Space: O(1)
 
# ================================================================
# PATTERN 4: SLIDING WINDOW — Variable Size
# Use case: smallest subarray with sum >= target
# ================================================================
def min_subarray_len(target: int, nums: list) -> int:
    left = 0
    current_sum = 0
    min_len = float('inf')
    for right in range(len(nums)):       # expand right edge
        current_sum += nums[right]
        while current_sum >= target:     # shrink from left while valid
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1
    return min_len if min_len != float('inf') else 0
    # Time: O(n) — each element visited at most twice

# ================================================================
# TRAP 1: Modifying list while iterating
# ================================================================
lst = [1, 2, 3, 4, 5]
for x in lst:
    if x % 2 == 0:
        lst.remove(x)           # ❌ DANGER! Skips elements!
# Result might look correct but is UNRELIABLE
 
# ✅ FIX 1: list comprehension (cleanest)
lst = [x for x in lst if x % 2 != 0]
 
# ✅ FIX 2: iterate over a copy
for x in lst[:]:
    if x % 2 == 0:
        lst.remove(x)
 
# ================================================================
# TRAP 2: Shallow copy of nested list
# ================================================================
grid = [[0] * 3] * 3            # ❌ All 3 rows are SAME object!
grid[0][0] = 1
print(grid)   # [[1,0,0],[1,0,0],[1,0,0]] ← ALL rows changed!
 
grid = [[0] * 3 for _ in range(3)]  # ✅ Each row is independent
grid[0][0] = 1
print(grid)   # [[1,0,0],[0,0,0],[0,0,0]] ← Only first row
 
# ================================================================
# TRAP 3: Mutable default argument
# ================================================================
def add_item(item, lst=[]):     # ❌ lst is shared across ALL calls!
    lst.append(item)
    return lst
 
add_item(1)                     # [1]
add_item(2)                     # [1, 2] ← NOT [2]!
 
def add_item(item, lst=None):   # ✅ FIX: use None as sentinel
    if lst is None:
        lst = []                # create fresh list each call
    lst.append(item)
    return lst
 
# ================================================================
# TRAP 4: sort() returns None
# ================================================================
lst = [3, 1, 2]
result = lst.sort()             # ❌ result = None !
result = sorted(lst)            # ✅ result = [1, 2, 3], lst unchanged
 
# ================================================================
# TRAP 5: is vs == for list comparison
# ================================================================
[1, 2, 3] == [1, 2, 3]         # True  — value comparison
[1, 2, 3] is [1, 2, 3]         # False — different objects in memory
# Always use == for value comparison
# Use 'is' ONLY for None checks: if x is None

# Enumerate — index + value together
for i, val in enumerate(["a", "b", "c"], start=1):
    print(i, val)               # 1 a, 2 b, 3 c
 
# Zip — iterate parallel lists
names = ["Alice", "Bob"]
scores = [95, 87]
for name, score in zip(names, scores):
    print(f"{name}: {score}")   # Alice: 95, Bob: 87
 
# Star unpacking
first, *middle, last = [1, 2, 3, 4, 5]
# first=1, middle=[2,3,4], last=5
 
# Flatten nested list — one-liner
nested = [[1, 2], [3, 4], [5]]
flat = [x for sub in nested for x in sub]   # [1, 2, 3, 4, 5]
# Read: "for each sub in nested, for each x in sub, collect x"
 
# Transpose a matrix
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transposed = list(zip(*matrix))              # [(1,4,7),(2,5,8),(3,6,9)]
# *matrix unpacks rows as arguments to zip
 
# Frequency map
freq = {}
for char in "abracadabra":
    freq[char] = freq.get(char, 0) + 1
 
# Anagram key
key = ''.join(sorted("listen"))             # "eilnst" — same as "silent"
 
# Check if sorted
is_sorted = all(lst[i] <= lst[i+1] for i in range(len(lst)-1))

def two_sum(nums: list, target: int) -> list:
    """
    Problem: Find indices of two numbers that sum to target.
    Example: nums = [2, 7, 11, 15], target = 9 → [0, 1]
 
    Approach: Hash map — store each number's index.
              For each new number, check if complement exists.
    """
    seen = {}                               # value → index
 
    for i, num in enumerate(nums):          # single pass through array
        complement = target - num           # what we need to find
        if complement in seen:              # O(1) hash map lookup
            return [seen[complement], i]    # found both indices!
        seen[num] = i                       # store this number's index
 
    return []                               # no solution found
    # Time: O(n) — single pass
    # Space: O(n) — hash map stores up to n elements

def max_subarray(nums: list) -> int:
    """
    Problem: Find contiguous subarray with largest sum.
    Example: [-2,1,-3,4,-1,2,1,-5,4] → 6 (subarray [4,-1,2,1])
 
    Approach: At each position, decide:
              - Start fresh from this element, OR
              - Extend the previous subarray
    """
    max_sum = nums[0]                       # global max (handles all-negative)
    current_sum = nums[0]                   # current subarray sum
 
    for i in range(1, len(nums)):           # start from index 1
        # Either extend current subarray or start new one here
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum) # update global max if better
 
    return max_sum
    # Time: O(n), Space: O(1)

lst[::-1]                            # reverse (new copy)
lst.sort(key=lambda x: -x)          # sort descending
[x for x in lst if x > 0]           # filter positives
list(zip(*matrix))                   # transpose matrix
[i for i,v in enumerate(lst) if v==target]  # all indices of value
sum(lst) / len(lst)                  # average
lst[::2]                             # every other element
first, *rest = lst                   # unpack first and rest
all(x > 0 for x in lst)             # check all positive
any(x > 0 for x in lst)             # check any positive
lst.copy()  # or lst[:]              # shallow copy
import copy; copy.deepcopy(lst)      # deep copy
[[0]*m for _ in range(n)]           # n×m zero matrix (CORRECT way)

# ================================================================
# USE CASE 1: Dictionary keys (lists can't be dict keys — mutable!)
# ================================================================
location = (40.7128, -74.0060)                  # lat, lng as tuple key
distances = {(0, 0): 0, (1, 2): 5}             # grid coords as keys
# d = {[0,0]: 0}  ← TypeError: unhashable type: 'list'
 
# ================================================================
# USE CASE 2: Returning multiple values from a function
# ================================================================
def min_max(nums: list) -> tuple:
    return min(nums), max(nums)                 # implicitly creates tuple
 
lo, hi = min_max([3, 1, 4, 1, 5, 9])           # unpack directly
# lo = 1, hi = 9
 
def divmod_custom(a, b) -> tuple:
    return a // b, a % b                        # quotient and remainder
 
quotient, remainder = divmod_custom(17, 5)      # q=3, r=2
 
# ================================================================
# USE CASE 3: Fixed / named constants
# ================================================================
RGB_RED = (255, 0, 0)                           # color — shouldn't change
DIRECTIONS = [(0,1), (0,-1), (1,0), (-1,0)]    # 4-directional grid traversal
DIAG_DIRS  = [(1,1),(1,-1),(-1,1),(-1,-1)]     # diagonal directions
 
# ================================================================
# USE CASE 4: Elements in a set (lists can't be in sets!)
# ================================================================
visited = set()
visited.add((0, 0))                             # ✅ tuple in set
visited.add((1, 2))
# visited.add([1, 2])  ← TypeError: unhashable type: 'list'
 
# Common BFS/DFS pattern for grids:
queue = [(0, 0)]                                # start with tuple coordinates
for r, c in queue:
    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
        new_pos = (r + dr, c + dc)
        if new_pos not in visited:
            visited.add(new_pos)

# Basic unpacking
a, b, c = (1, 2, 3)                    # a=1, b=2, c=3
x, y = (10, 20)                         # swap/unpack
 
# Star unpacking (Python 3)
first, *middle, last = (1, 2, 3, 4, 5)
# first=1, middle=[2,3,4], last=5
 
head, *tail = (1, 2, 3, 4)             # head=1, tail=[2,3,4]
*init, last = (1, 2, 3, 4)             # init=[1,2,3], last=4
 
# Swap without temp variable
a, b = b, a
# Python creates tuple (b, a) on the right, then unpacks to a, b
 
# Ignore values with _
_, important, _ = (1, 42, 3)           # only care about middle
name, *_, age = ("Alice", "B", "C", 30) # skip middle fields
 
# Nested unpacking
(a, b), (c, d) = (1, 2), (3, 4)       # a=1, b=2, c=3, d=4
 
# In for loops
pairs = [(1, 'a'), (2, 'b'), (3, 'c')]
for num, char in pairs:                 # auto-unpack each tuple
    print(f"{num}: {char}")

from collections import namedtuple
 
# Define a named tuple class
Point = namedtuple('Point', ['x', 'y'])     # or 'x y' as space-separated string
 
p = Point(3, 4)
print(p.x, p.y)             # 3 4  — readable named access
print(p[0], p[1])           # 3 4  — still works by index
print(p)                     # Point(x=3, y=4) — readable repr!
 
# Immutable — cannot modify:
# p.x = 5  ← AttributeError: can't set attribute
 
# More useful examples:
Employee = namedtuple('Employee', 'name dept salary')
emp = Employee('Alice', 'Engineering', 120000)
print(emp.name)              # 'Alice'
print(emp.salary)            # 120000
 
# Convert to dict
emp._asdict()                # {'name': 'Alice', 'dept': 'Engineering', 'salary': 120000}
 
# Create from existing dict
data = {'name': 'Bob', 'dept': 'Sales', 'salary': 90000}
emp2 = Employee(**data)      # unpack dict as keyword args
 
# Create modified copy (tuples are immutable, this returns NEW namedtuple)
emp3 = emp._replace(salary=130000)   # emp unchanged, emp3 is new
print(emp.salary)            # 120000 — original unchanged
print(emp3.salary)           # 130000
 
# Default values (Python 3.6.1+)
Config = namedtuple('Config', ['host', 'port', 'debug'], defaults=['localhost', 8080, False])
cfg = Config()               # Config(host='localhost', port=8080, debug=False)
cfg2 = Config(port=9000)     # Config(host='localhost', port=9000, debug=False)

# ================================================================
# TRAP 1: Single-element tuple REQUIRES trailing comma
# ================================================================
not_a_tuple = (42)              # This is just int 42 in parentheses!
type(not_a_tuple)               # <class 'int'>
 
is_a_tuple = (42,)              # The COMMA makes it a tuple
type(is_a_tuple)                # <class 'tuple'>
 
also_tuple = 42,                # Parentheses optional! Comma = tuple
type(also_tuple)                # <class 'tuple'>
 
# ================================================================
# TRAP 2: Tuples containing mutables are partially mutable!
# ================================================================
t = ([1, 2], [3, 4])
 
t[0].append(5)                  # ✅ Works! t = ([1, 2, 5], [3, 4])
# The TUPLE is immutable (can't reassign t[0] to a new object)
# But the LIST inside is still mutable!
 
# t[0] = [9, 9]               # ❌ TypeError: 'tuple' object doesn't support item assignment
 
# ================================================================
# TRAP 3: Tuple concatenation creates NEW tuple
# ================================================================
t1 = (1, 2)
t2 = t1 + (3, 4)               # (1, 2, 3, 4) — new tuple object, O(n+m)
 
# ❌ For repeated concatenation in a loop:
result = ()
for x in range(1000):
    result = result + (x,)     # O(n²) total! Creates new tuple each time
 
# ✅ Build list, convert at end:
items = []
for x in range(1000):
    items.append(x)
result = tuple(items)           # O(n) total
 
# ================================================================
# TRAP 4: Tuple packing in return statements
# ================================================================
def get_coords():
    return 1, 2                 # Python automatically packs as tuple (1, 2)
 
x, y = get_coords()            # works perfectly
coords = get_coords()           # coords = (1, 2)

(42,)                            # single-element tuple (COMMA required!)
a, b = b, a                      # swap values (tuple packing/unpacking)
first, *rest = (1, 2, 3, 4)      # star unpacking
tuple(lst)                       # convert list to tuple
hash((1, 2, 3))                  # tuples are hashable (can be dict keys/set elements)
Point = namedtuple('Point','x y')# readable tuples with named fields
t.count(x)                       # count occurrences in tuple
t.index(x)                       # first index of value
(1, 2) + (3, 4)                  # concatenation → (1, 2, 3, 4)
(1, 2) * 3                       # repetition → (1, 2, 1, 2, 1, 2)

# ================================================================
# CREATION
# ================================================================
s = set()                       # ✅ empty set
s = {}                          # ❌ this is an empty DICT, NOT a set!
 
s = {1, 2, 3}                   # set literal
s = set([1, 2, 2, 3])          # from list → {1, 2, 3} (duplicates removed!)
s = set("hello")               # {'h', 'e', 'l', 'o'} — unique chars
 
# ================================================================
# ADDING ELEMENTS
# ================================================================
s = {1, 2, 3}
s.add(4)                        # {1, 2, 3, 4}
s.add(2)                        # {1, 2, 3, 4} — no effect, already exists
 
s.update([5, 6], {7, 8})        # add multiple from multiple iterables
# {1, 2, 3, 4, 5, 6, 7, 8}
 
# ================================================================
# REMOVING ELEMENTS
# ================================================================
s = {1, 2, 3, 4, 5}
 
s.remove(3)                     # removes 3; ⚠️ KeyError if 3 not present!
s.discard(99)                   # ✅ no error even if 99 not in set
x = s.pop()                     # removes and returns ARBITRARY element
s.clear()                       # empties the set
 
# ================================================================
# SET OPERATIONS
# ================================================================
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
 
# Union — all elements from both
a | b                           # {1, 2, 3, 4, 5, 6}
a.union(b)                      # same result
 
# Intersection — common elements only
a & b                           # {3, 4}
a.intersection(b)               # same result
 
# Difference — in a but NOT in b
a - b                           # {1, 2}
a.difference(b)                 # same result
 
# Symmetric difference — in one but NOT both
a ^ b                           # {1, 2, 5, 6}
a.symmetric_difference(b)       # same result
 
# ================================================================
# SUBSET / SUPERSET CHECKS
# ================================================================
{1, 2} <= {1, 2, 3}             # True  — is subset
{1, 2} < {1, 2, 3}             # True  — is PROPER subset (not equal)
{1, 2, 3} >= {1, 2}            # True  — is superset
{1, 2, 3}.isdisjoint({4, 5})   # True  — no common elements
 
# ================================================================
# IN-PLACE OPERATIONS (modifies the set directly)
# ================================================================
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
a |= b                          # a = {1, 2, 3, 4, 5, 6}
a &= b                          # a = intersection
a -= b                          # a = difference
a ^= b                          # a = symmetric difference

# frozenset is an IMMUTABLE set
# → Can be used as dictionary key or element of another set
 
fs = frozenset([1, 2, 3])
# fs.add(4)               ← AttributeError: can't modify frozenset
 
# Use case 1: set of sets
set_of_sets = {frozenset([1, 2]), frozenset([3, 4])}
 
# Use case 2: dict key
cache = {frozenset(['a', 'b', 'c']): "result"}
 
# Use case 3: caching a set argument in memoization
@functools.cache
def compute(items: frozenset):          # frozenset is hashable!
    return sum(items)
 
# frozenset supports all read operations:
fs1 = frozenset([1, 2, 3])
fs2 = frozenset([3, 4, 5])
fs1 & fs2                               # frozenset({3})
fs1 | fs2                               # frozenset({1, 2, 3, 4, 5})
fs1 - fs2                               # frozenset({1, 2})

# ================================================================
# PATTERN 1: Remove duplicates PRESERVING order
# ================================================================
lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
seen = set()
unique = []
for x in lst:
    if x not in seen:           # O(1) lookup
        seen.add(x)
        unique.append(x)
# unique = [3, 1, 4, 5, 9, 2, 6]
 
# One-liner (tricky but useful in interviews):
seen = set()
unique = [x for x in lst if not (x in seen or seen.add(x))]
# Explanation: seen.add(x) returns None (falsy)
# So: "x in seen or None" → if x not in seen → add it → include in result
 
# If order doesn't matter (simplest):
unique = list(set(lst))         # ⚠️ ORDER IS LOST
 
# ================================================================
# PATTERN 2: Find duplicates in a list
# ================================================================
lst = [1, 2, 3, 2, 4, 3, 5]
seen = set()
duplicates = set()
for x in lst:
    if x in seen:
        duplicates.add(x)
    seen.add(x)
# duplicates = {2, 3}
 
# ================================================================
# PATTERN 3: BFS/DFS visited tracking
# ================================================================
visited = set()
def dfs(node, graph):
    if node in visited:          # O(1) check
        return
    visited.add(node)            # O(1) add
    for neighbor in graph[node]:
        dfs(neighbor, graph)
 
# ================================================================
# PATTERN 4: Find common elements across multiple lists
# ================================================================
def common_elements(*lists):
    result = set(lists[0])      # start with first list's elements
    for lst in lists[1:]:
        result &= set(lst)      # intersect with each subsequent list
    return result
 
common_elements([1,2,3,4], [2,3,4,5], [3,4,5,6])   # {3, 4}

# ================================================================
# TRAP 1: Empty set — MUST use set(), not {}
# ================================================================
not_a_set = {}                  # ❌ empty DICT!
type(not_a_set)                 # <class 'dict'>
empty_set = set()               # ✅ empty set
 
# ================================================================
# TRAP 2: Sets are UNORDERED
# ================================================================
s = {3, 1, 4, 1, 5}
# Don't rely on iteration order — it's NOT guaranteed
# {1, 3, 4, 5} — order depends on hash values
 
# ================================================================
# TRAP 3: Mutable objects cannot be in sets
# ================================================================
# s = {[1, 2]}        ← TypeError: unhashable type: 'list'
# s = {{1, 2}}        ← TypeError: unhashable type: 'set'
s = {(1, 2)}                    # ✅ tuple is hashable
s = {frozenset([1, 2])}         # ✅ frozenset is hashable
 
# ================================================================
# TRAP 4: set.pop() is ARBITRARY (not FIFO, not LIFO)
# ================================================================
s = {10, 20, 30}
s.pop()                         # could return ANY element — unpredictable!

def longest_consecutive(nums: list) -> int:
    """
    Problem: Find length of longest consecutive sequence.
    Example: [100, 4, 200, 1, 3, 2] → 4  (sequence: 1,2,3,4)
    Must run in O(n) time.
 
    Key insight: Only start counting from the BEGINNING of a sequence.
    A number n is a sequence start if (n-1) is NOT in the set.
    """
    num_set = set(nums)                     # O(n) build, O(1) lookups
    max_length = 0
 
    for num in num_set:
        if num - 1 not in num_set:          # num is start of a sequence
            current = num
            length = 1
            while current + 1 in num_set:  # extend the sequence
                current += 1
                length += 1
            max_length = max(max_length, length)
 
    return max_length
    # Time: O(n) — each number visited at most twice
    # Space: O(n) — hash set

set()                            # empty set (NOT {})
s.add(x)                         # add element O(1)
s.discard(x)                     # remove — no error if missing
s.remove(x)                      # remove — KeyError if missing
x in s                           # O(1) membership test
s1 & s2                          # intersection
s1 | s2                          # union
s1 - s2                          # difference (in s1 not s2)
s1 ^ s2                          # symmetric difference
s1 <= s2                         # is s1 subset of s2?
s1.isdisjoint(s2)                # no common elements?
list(set(lst))                   # remove duplicates (loses order)
frozenset(s)                     # immutable set (hashable)
len(s)                           # count — O(1)

# ================================================================
# CREATION
# ================================================================
d = {}                                          # empty dict
d = {'a': 1, 'b': 2}                           # literal syntax
d = dict(a=1, b=2)                             # keyword arguments
d = dict([('a', 1), ('b', 2)])                 # from list of pairs
d = dict.fromkeys(['x', 'y', 'z'], 0)          # {'x':0, 'y':0, 'z':0}
d = {k: v for k, v in [('a',1),('b',2)]}       # dict comprehension
 
# ================================================================
# ACCESS
# ================================================================
d = {'a': 1, 'b': 2, 'c': 3}
 
d['a']                          # 1 — direct access; ⚠️ KeyError if missing!
d.get('a')                      # 1 — safe access; returns None if missing
d.get('z', -1)                  # -1 — returns default if key missing
d.get('z')                      # None — default default is None
 
# ================================================================
# MODIFICATION
# ================================================================
d['d'] = 4                      # add new key or update existing
d.update({'e': 5, 'f': 6})     # merge dict (updates existing keys)
d.update(g=7, h=8)             # keyword argument form
 
# setdefault — get OR set if missing (returns value)
d.setdefault('count', 0)        # if 'count' not in d, set it to 0
d.setdefault('count', 99)       # already exists → keeps 0, returns 0
 
# Common pattern: group items
groups = {}
for item in ['apple', 'banana', 'avocado', 'blueberry']:
    key = item[0]                               # first letter
    groups.setdefault(key, []).append(item)
# {'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry']}
 
# ================================================================
# REMOVAL
# ================================================================
val = d.pop('a')                # removes 'a', returns its value; ⚠️ KeyError if missing
val = d.pop('z', None)          # ✅ safe: returns None instead of KeyError
key, val = d.popitem()          # removes and returns LAST inserted pair (Python 3.7+)
del d['b']                      # delete key — statement, not method; ⚠️ KeyError if missing
d.clear()                       # remove ALL items, dict becomes {}
 
# ================================================================
# VIEWS — Dynamic, Reflect Changes to Dict
# ================================================================
d = {'a': 1, 'b': 2, 'c': 3}
keys = d.keys()                 # dict_keys(['a', 'b', 'c'])   — view
vals = d.values()               # dict_values([1, 2, 3])       — view
items = d.items()               # dict_items([('a',1),('b',2),('c',3)]) — view
 
# Views are LIVE — they reflect changes:
d['d'] = 4
print(keys)                     # dict_keys(['a', 'b', 'c', 'd']) — updated!
 
# Convert to static list if you need to modify dict while using:
list(d.keys())                  # ['a', 'b', 'c', 'd']

# Basic
squares = {x: x**2 for x in range(6)}              # {0:0, 1:1, 2:4, 3:9, 4:16, 5:25}
 
# With condition
even_sq = {x: x**2 for x in range(10) if x % 2 == 0}
 
# Invert dict (swap keys and values)
d = {'a': 1, 'b': 2, 'c': 3}
inverted = {v: k for k, v in d.items()}            # {1:'a', 2:'b', 3:'c'}
# ⚠️ Only works if values are unique and hashable!
 
# From two parallel lists
keys = ['name', 'age', 'city']
values = ['Alice', 30, 'NYC']
d = dict(zip(keys, values))                         # {'name':'Alice','age':30,'city':'NYC'}
# OR:
d = {k: v for k, v in zip(keys, values)}
 
# Filter dict
scores = {'Alice': 90, 'Bob': 55, 'Charlie': 75}
passing = {name: score for name, score in scores.items() if score >= 60}
# {'Alice': 90, 'Charlie': 75}

d1 = {'a': 1, 'b': 2}
d2 = {'b': 3, 'c': 4}
 
# Method 1: ** unpacking (Python 3.5+)
merged = {**d1, **d2}           # {'a':1, 'b':3, 'c':4} — d2 wins conflicts
 
# Method 2: | operator (Python 3.9+)
merged = d1 | d2                # {'a':1, 'b':3, 'c':4}
 
# Method 3: update (modifies d1 in place)
d1.update(d2)                   # d1 = {'a':1, 'b':3, 'c':4}
 
# Method 4: |= in place (Python 3.9+)
d1 |= d2                        # same as d1.update(d2)

from collections import defaultdict, OrderedDict, Counter
 
# ================================================================
# defaultdict — auto-creates default value for missing keys
# ================================================================
 
# defaultdict(int) — missing keys default to 0
freq = defaultdict(int)
for char in "abracadabra":
    freq[char] += 1             # no need to check if key exists!
# defaultdict(int, {'a':5, 'b':2, 'r':2, 'c':1, 'd':1})
 
# defaultdict(list) — missing keys default to []
adj = defaultdict(list)         # perfect for graph adjacency lists!
edges = [(1,2), (1,3), (2,4)]
for u, v in edges:
    adj[u].append(v)            # no need for setdefault or if-check
    adj[v].append(u)            # undirected graph
 
# defaultdict(set) — missing keys default to set()
groups = defaultdict(set)
for word in ["eat", "tea", "tan", "ate"]:
    key = ''.join(sorted(word)) # anagram key
    groups[key].add(word)
# {'aet': {'eat', 'tea', 'ate'}, 'ant': {'tan'}}
 
# ================================================================
# Counter — specialized dict for counting hashable objects
# ================================================================
c = Counter("abracadabra")
# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
 
c.most_common(2)                # [('a', 5), ('b', 2)] — top 2
c['a']                          # 5 — count of 'a'
c['z']                          # 0 — ✅ missing keys return 0, NOT KeyError!
 
# Counter arithmetic
c1 = Counter("aab")             # {'a':2, 'b':1}
c2 = Counter("abb")             # {'a':1, 'b':2}
c1 + c2                         # Counter({'a':3, 'b':3}) — add
c1 - c2                         # Counter({'a':1}) — subtract (keep positive only)
c1 & c2                         # Counter({'a':1, 'b':1}) — min of each
c1 | c2                         # Counter({'a':2, 'b':2}) — max of each
 
list(Counter(a=2, b=3).elements())  # ['a','a','b','b','b'] — with multiplicity
 
# Anagram check:
def is_anagram(s1: str, s2: str) -> bool:
    return Counter(s1) == Counter(s2)   # O(n)
 
# ================================================================
# OrderedDict — dict with extra order-manipulation methods
# ================================================================
od = OrderedDict()
od['a'] = 1
od['b'] = 2
od['c'] = 3
 
od.move_to_end('a')             # move 'a' to end → [b, c, a]
od.move_to_end('c', last=False) # move 'c' to beginning → [c, b, a]
od.popitem(last=True)           # pop last item: ('a', 1)
od.popitem(last=False)          # pop first item: ('c', 3)
 
# LRU Cache pattern with OrderedDict (classic interview question!):
from collections import OrderedDict
 
class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.cap = capacity
 
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)         # mark as recently used
        return self.cache[key]
 
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # evict LEAST recently used

# ================================================================
# TRAP 1: Modifying dict while iterating
# ================================================================
d = {'a': 1, 'b': 2, 'c': 3}
# for k in d:
#     if d[k] > 1: del d[k]   # ❌ RuntimeError: changed size during iteration
 
# ✅ FIX: iterate over copy of keys
for k in list(d.keys()):
    if d[k] > 1:
        del d[k]
 
# ✅ BETTER: dict comprehension
d = {k: v for k, v in d.items() if v <= 1}
 
# ================================================================
# TRAP 2: What CAN and CANNOT be a dict key
# ================================================================
# Keys must be HASHABLE (immutable):
{1: 'int', 'a': 'str', (1,2): 'tuple', True: 'bool'}  # ✅ all valid
 
# {[1,2]: 'list'}             # ❌ TypeError: unhashable type: 'list'
# {{1}: 'set'}                # ❌ TypeError: unhashable type: 'set'
 
# ================================================================
# TRAP 3: True, False, 1, 0 as dict keys
# ================================================================
d = {True: 'true', 1: 'one'}
# True == 1 is True AND hash(True) == hash(1)
# So they are the SAME KEY!
print(d)                        # {True: 'one'} — 1 overwrote True!
 
d = {False: 'false', 0: 'zero'}
print(d)                        # {False: 'zero'} — 0 overwrote False!
 
# ================================================================
# TRAP 4: dict ordering guarantee
# ================================================================
# Python 3.7+: insertion order GUARANTEED by language spec
# Python 3.6: CPython implementation detail (not guaranteed by spec)
# Python < 3.6: NO ordering guarantee at all

from collections import defaultdict
 
def group_anagrams(strs: list) -> list:
    """
    Problem: Group strings that are anagrams of each other.
    Example: ["eat","tea","tan","ate","nat","bat"]
           → [["eat","tea","ate"], ["tan","nat"], ["bat"]]
 
    Key insight: anagrams share the same sorted form.
    "eat", "tea", "ate" all sort to "aet"
    """
    groups = defaultdict(list)
 
    for s in strs:
        key = ''.join(sorted(s))            # "eat" → "aet" — same for all anagrams
        groups[key].append(s)               # group by sorted key
 
    return list(groups.values())
    # Time: O(n × k log k) — n strings, k = max length
    # Space: O(n × k)

def subarray_sum(nums: list, k: int) -> int:
    """
    Problem: Count subarrays that sum to exactly k.
    Example: nums = [1,1,1], k = 2 → 2
 
    Key insight: if prefix[j] - prefix[i] = k,
                 then subarray nums[i..j-1] sums to k.
    We need: how many times has (current_prefix - k) appeared before?
    """
    count = 0
    prefix_sum = 0
    freq = {0: 1}                           # empty prefix has sum 0, seen once
 
    for num in nums:
        prefix_sum += num                   # running prefix sum
        # If (prefix_sum - k) appeared before, those subarrays sum to k
        count += freq.get(prefix_sum - k, 0)
        freq[prefix_sum] = freq.get(prefix_sum, 0) + 1
 
    return count
    # Time: O(n), Space: O(n)

d.get(k, default)                    # safe access — no KeyError
d.setdefault(k, []).append(v)        # get-or-create then use
d.pop(k, None)                       # remove safely — no KeyError
Counter(lst).most_common(k)          # top k frequent elements
defaultdict(list)                    # auto-create [] for missing keys
defaultdict(int)                     # auto-create 0 for missing keys
{**d1, **d2}                         # merge (d2 wins on conflicts)
d1 | d2                              # merge (Python 3.9+)
{v: k for k, v in d.items()}         # invert dict
sorted(d, key=d.get, reverse=True)   # sort keys by value descending
{k: v for k,v in d.items() if v>0}  # filter dict entries
k in d                               # key membership — O(1)

lst = [10, 20, 30]
 
# What you write:
for x in lst:
    print(x)
 
# What Python actually does:
_iterator = iter(lst)           # Step 1: calls lst.__iter__() → returns iterator
while True:
    try:
        x = next(_iterator)     # Step 2: calls _iterator.__next__()
        print(x)
    except StopIteration:       # Step 3: caught → loop ends cleanly
        break
 
# iter() built-in = calls __iter__()
# next() built-in = calls __next__()

# ================================================================
# ITERABLES — can create multiple independent iterators
# ================================================================
lst = [1, 2, 3]
 
iter1 = iter(lst)               # fresh iterator
iter2 = iter(lst)               # another fresh iterator — independent!
 
next(iter1)                     # 1
next(iter1)                     # 2
next(iter2)                     # 1  ← starts from beginning, independent!
 
# ================================================================
# ITERATORS — return themselves from iter()
# ================================================================
it = iter(lst)                  # iterator object
iter(it) is it                  # True! iter(iterator) returns same object
 
next(it)                        # 1
next(it)                        # 2
next(it)                        # 3
# next(it)                      # ⚠️ StopIteration — exhausted!
 
# next() with default — no error on exhaustion:
next(it, 'DONE')                # 'DONE' — returns default instead of error
 
# ================================================================
# WHICH IS WHICH? Quick test:
# ================================================================
lst = [1, 2, 3]
print(hasattr(lst, '__iter__'))     # True  — it's iterable
print(hasattr(lst, '__next__'))     # False — it's NOT an iterator
 
it = iter(lst)
print(hasattr(it, '__iter__'))      # True  — iterators are also iterable
print(hasattr(it, '__next__'))      # True  — it has __next__ → it's an iterator

# ================================================================
# CUSTOM ITERABLE — separate class for iterator
# ================================================================
class CountDown:
    """Iterable: can be looped multiple times."""
    def __init__(self, n):
        self.n = n
 
    def __iter__(self):
        return CountDownIterator(self.n)    # returns NEW iterator each call
 
class CountDownIterator:
    """Iterator: tracks state, single-use."""
    def __init__(self, n):
        self.current = n
 
    def __iter__(self):
        return self                         # iterator returns itself
 
    def __next__(self):
        if self.current <= 0:
            raise StopIteration             # signal end of iteration
        value = self.current
        self.current -= 1                   # advance state
        return value
 
cd = CountDown(3)
for x in cd: print(x)                      # 3 2 1
for x in cd: print(x)                      # 3 2 1 again! (fresh iterator)
 
# ================================================================
# COMBINED ITERABLE+ITERATOR — single class (one-time use)
# ================================================================
class InfiniteCounter:
    """Iterator that also IS its own iterable."""
    def __init__(self, start=0):
        self.current = start
 
    def __iter__(self):
        return self                         # returns itself
 
    def __next__(self):
        value = self.current
        self.current += 1
        return value                        # infinite — never raises StopIteration
 
counter = InfiniteCounter(10)
import itertools
list(itertools.islice(counter, 5))          # [10, 11, 12, 13, 14]

# ================================================================
# enumerate — index + value
# ================================================================
fruits = ['apple', 'banana', 'cherry']
 
for i, fruit in enumerate(fruits):
    print(f"{i}: {fruit}")              # 0: apple, 1: banana, 2: cherry
 
for i, fruit in enumerate(fruits, start=1):  # custom start
    print(f"{i}: {fruit}")              # 1: apple, 2: banana, 3: cherry
 
# Common use: find index while iterating
idx = next((i for i, v in enumerate(lst) if v == target), -1)
 
# ================================================================
# zip — iterate parallel sequences
# ================================================================
names = ['Alice', 'Bob', 'Charlie']
scores = [95, 87, 92]
 
for name, score in zip(names, scores):
    print(f"{name}: {score}")           # Alice: 95, etc.
 
# ⚠️ zip stops at SHORTEST sequence:
list(zip([1,2,3], [10,20]))             # [(1,10), (2,20)] — 3 is dropped!
 
# zip_longest — pads shorter with fillvalue
from itertools import zip_longest
list(zip_longest([1,2,3], [10,20], fillvalue=0))
# [(1,10), (2,20), (3,0)]
 
# Unzip (transpose list of tuples):
pairs = [(1,'a'), (2,'b'), (3,'c')]
nums, chars = zip(*pairs)               # nums=(1,2,3), chars=('a','b','c')
 
# ================================================================
# map — apply function to each element
# ================================================================
nums = [1, 2, 3, 4]
squared = list(map(lambda x: x**2, nums))       # [1, 4, 9, 16]
# ← Usually prefer list comprehension: [x**2 for x in nums]
 
# map with multiple iterables:
list(map(lambda a, b: a+b, [1,2,3], [10,20,30]))  # [11, 22, 33]
 
# ================================================================
# filter — keep elements where function returns True
# ================================================================
nums = [1, 2, 3, 4, 5, 6]
evens = list(filter(lambda x: x % 2 == 0, nums))   # [2, 4, 6]
# ← Usually prefer: [x for x in nums if x % 2 == 0]
 
# ================================================================
# sorted — flexible, powerful
# ================================================================
words = ['banana', 'apple', 'Cherry', 'date']
 
sorted(words)                           # ['Cherry', 'apple', 'banana', 'date']
sorted(words, key=str.lower)            # ['apple', 'banana', 'Cherry', 'date']
sorted(words, key=len)                  # ['date', 'apple', 'banana', 'Cherry']
sorted(words, key=len, reverse=True)    # longest first
 
# Multi-key sort (tuple key):
students = [('Alice', 90), ('Bob', 85), ('Charlie', 90)]
sorted(students, key=lambda s: (-s[1], s[0]))
# sort by score DESC, then name ASC
# [('Alice', 90), ('Charlie', 90), ('Bob', 85)]
 
# ================================================================
# reversed — iterate backwards (returns iterator)
# ================================================================
for x in reversed([1, 2, 3]):
    print(x)                            # 3, 2, 1
# reversed() is lazy — doesn't create new list
 
# ================================================================
# any / all — short-circuit boolean checks
# ================================================================
nums = [1, -2, 3, -4, 5]
 
any(x > 0 for x in nums)               # True  — stops at first True
all(x > 0 for x in nums)               # False — stops at first False
 
any([])                                 # False — no elements = no True found
all([])                                 # True  — vacuously true (no False found)
 
# Practical use:
has_even = any(x % 2 == 0 for x in nums)
all_unique = len(nums) == len(set(nums))

# ================================================================
# LIST COMPREHENSION
# Syntax: [expression for item in iterable if condition]
# ================================================================
squares = [x**2 for x in range(10)]                    # [0,1,4,9,...,81]
evens   = [x for x in range(20) if x % 2 == 0]        # [0,2,4,...,18]
upper   = [c.upper() for c in "hello"]                 # ['H','E','L','L','O']
 
# If-else in expression (not at the end):
labels = ["even" if x%2==0 else "odd" for x in range(5)]
# ['even','odd','even','odd','even']
 
# ================================================================
# NESTED LIST COMPREHENSION
# ================================================================
# Flatten nested list:
nested = [[1, 2, 3], [4, 5], [6]]
flat = [x for sublist in nested for x in sublist]      # [1,2,3,4,5,6]
# Rule: outer loop comes FIRST, inner loop comes SECOND
 
# Matrix creation:
rows, cols = 3, 4
matrix = [[0] * cols for _ in range(rows)]             # 3×4 zero matrix
 
# All pairs where i != j:
pairs = [(i,j) for i in range(3) for j in range(3) if i != j]
# [(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)]
 
# Transpose matrix:
matrix = [[1,2,3],[4,5,6],[7,8,9]]
transposed = [[row[i] for row in matrix] for i in range(len(matrix[0]))]
# [[1,4,7],[2,5,8],[3,6,9]]
 
# ================================================================
# SET COMPREHENSION
# ================================================================
unique_lengths = {len(word) for word in ["hi","hello","hey","hi"]}  # {2, 5, 3}
 
# ================================================================
# DICT COMPREHENSION
# ================================================================
word_lengths = {word: len(word) for word in ["hi","hello","hey"]}
# {'hi': 2, 'hello': 5, 'hey': 3}
 
squares_map = {x: x**2 for x in range(6)}
# {0:0, 1:1, 2:4, 3:9, 4:16, 5:25}
 
# ================================================================
# GENERATOR EXPRESSION
# ================================================================
# Same syntax as list comprehension but with () — produces values LAZILY
 
gen = (x**2 for x in range(1_000_000))     # No memory used yet!
next(gen)                                   # 0  — compute on demand
next(gen)                                   # 1
 
# Use directly in functions (no extra parentheses needed):
total = sum(x**2 for x in range(100))       # sum of squares, memory efficient
any(x > 50 for x in data)                  # short-circuits at first True
max(len(word) for word in words)            # longest word length
 
# Memory comparison:
import sys
list_comp = [x**2 for x in range(10000)]   # stores 10000 integers
gen_exp   = (x**2 for x in range(10000))   # stores only generator object
 
sys.getsizeof(list_comp)        # ~87,624 bytes
sys.getsizeof(gen_exp)          # ~112 bytes (just the generator!)

# ================================================================
# Basic generator function
# ================================================================
def count_up(n: int):
    """Yields numbers from 1 to n."""
    i = 1
    while i <= n:
        yield i                 # PAUSE here, return i to caller
        i += 1                  # RESUME here on next call to next()
    # Falling off the end raises StopIteration automatically
 
gen = count_up(3)
print(type(gen))                # <class 'generator'>
 
next(gen)                       # 1 — runs until first yield
next(gen)                       # 2 — resumes, runs until second yield
next(gen)                       # 3
# next(gen)                     # StopIteration!
 
for x in count_up(5):           # for loop handles StopIteration automatically
    print(x)                    # 1 2 3 4 5
 
# ================================================================
# Generator for infinite sequence (Fibonacci)
# ================================================================
def fibonacci():
    a, b = 0, 1
    while True:                 # infinite — never stops on its own
        yield a
        a, b = b, a + b         # next Fibonacci number
 
fib = fibonacci()
[next(fib) for _ in range(10)]  # [0,1,1,2,3,5,8,13,21,34]
 
# ================================================================
# Generator for reading large files — memory efficient
# ================================================================
def read_large_file(filepath: str):
    """
    Process file line by line.
    Uses O(1) memory regardless of file size!
    Can process a 10GB file with constant memory.
    """
    with open(filepath, 'r') as f:
        for line in f:          # file object is itself an iterator
            yield line.strip()  # yield one line at a time
 
# Process 10GB log file with constant memory:
for line in read_large_file('huge_log.txt'):
    if 'ERROR' in line:
        print(line)             # process one line, discard, next line
 
# ================================================================
# yield from — delegate to sub-generator
# ================================================================
def flatten(nested):
    """Recursively flatten any nested iterable."""
    for item in nested:
        if isinstance(item, (list, tuple)):
            yield from flatten(item)        # delegate recursively
        else:
            yield item                      # yield the leaf value
 
list(flatten([1, [2, [3, 4], 5], [6, [7]]]))   # [1,2,3,4,5,6,7]
 
# Without yield from, you'd need:
# for val in flatten(item):
#     yield val
 
# ================================================================
# Generator send() — two-way communication
# ================================================================
def running_average():
    """Generator that computes running average as values are sent."""
    total = 0
    count = 0
    average = None
    while True:
        value = yield average               # yield current avg, receive new value
        if value is None:
            break
        total += value
        count += 1
        average = total / count
 
gen = running_average()
next(gen)                       # None  — initialize (prime the generator)
gen.send(10)                    # 10.0  — running avg: 10/1
gen.send(20)                    # 15.0  — running avg: 30/2
gen.send(30)                    # 20.0  — running avg: 60/3
 
# ================================================================
# Generator Pipeline — real-world data processing
# ================================================================
def read_logs(filename):
    """Stage 1: Read lines."""
    with open(filename) as f:
        for line in f:
            yield line.strip()
 
def parse_json_lines(lines):
    """Stage 2: Parse each line."""
    import json
    for line in lines:
        try:
            yield json.loads(line)
        except:
            continue                        # skip malformed
 
def filter_errors(records):
    """Stage 3: Keep only error records."""
    for record in records:
        if record.get('level') == 'ERROR':
            yield record
 
def add_metadata(records):
    """Stage 4: Enrich records."""
    for record in records:
        record['processed'] = True
        yield record
 
# Build pipeline — no data loaded yet!
lines   = read_logs('app.log')
records = parse_json_lines(lines)
errors  = filter_errors(records)
enriched = add_metadata(errors)
 
# Data flows through ONE record at a time — constant memory!
for record in enriched:
    save_to_db(record)

import itertools
 
# ================================================================
# combinations — choose r items (order doesn't matter, no repetition)
# ================================================================
list(itertools.combinations([1,2,3,4], 2))
# [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)] — C(4,2) = 6
 
# DSA use: generate all pairs, all subsets of size k
 
# ================================================================
# permutations — all orderings of r items
# ================================================================
list(itertools.permutations([1,2,3], 2))
# [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)] — P(3,2) = 6
 
list(itertools.permutations([1,2,3]))
# [(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)] — 3! = 6
 
# ================================================================
# combinations_with_replacement — choose r with repetition allowed
# ================================================================
list(itertools.combinations_with_replacement([1,2,3], 2))
# [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
 
# ================================================================
# product — cartesian product (like nested for loops)
# ================================================================
list(itertools.product([1,2], ['a','b']))
# [(1,'a'),(1,'b'),(2,'a'),(2,'b')]
 
# product with repeat:
list(itertools.product([0,1], repeat=3))    # all 3-bit binary numbers
# [(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)]
 
# DSA use: brute-force all combinations
 
# ================================================================
# chain — concatenate multiple iterables lazily
# ================================================================
list(itertools.chain([1,2],[3,4],[5]))       # [1,2,3,4,5]
 
# chain.from_iterable — flatten one level of nesting
list(itertools.chain.from_iterable([[1,2],[3,4],[5]]))  # [1,2,3,4,5]
 
# ================================================================
# islice — slice a generator (can't use [a:b] on iterators!)
# ================================================================
gen = (x**2 for x in range(100))
list(itertools.islice(gen, 5))              # [0,1,4,9,16] — first 5
 
list(itertools.islice(range(100), 10, 20)) # [10,11,...,19] — slice by indices
 
# Backend use: pagination!
def get_page(iterable, page_size, page_num):
    """Get specific page from any iterable."""
    start = page_size * (page_num - 1)
    return list(itertools.islice(iterable, start, start + page_size))
 
# ================================================================
# takewhile / dropwhile
# ================================================================
list(itertools.takewhile(lambda x: x < 5, [1,3,5,2,1]))
# [1,3] — stops at FIRST element >= 5 (even though 2,1 come after!)
 
list(itertools.dropwhile(lambda x: x < 5, [1,3,5,2,1]))
# [5,2,1] — drops while condition True, then yields ALL remaining
 
# ================================================================
# groupby — group CONSECUTIVE elements (⚠️ MUST SORT FIRST!)
# ================================================================
data = [('A',1),('A',2),('B',3),('B',4),('A',5)]
 
# Without sorting — 'A' appears in two separate groups:
for key, group in itertools.groupby(data, key=lambda x: x[0]):
    print(key, list(group))
# A [('A',1),('A',2)]
# B [('B',3),('B',4)]
# A [('A',5)]   ← separate group!
 
# With sorting — all same-key items grouped:
for key, group in itertools.groupby(sorted(data, key=lambda x: x[0]),
                                     key=lambda x: x[0]):
    print(key, list(group))
# A [('A',1),('A',2),('A',5)]
# B [('B',3),('B',4)]
 
# ================================================================
# accumulate — running accumulation (prefix sums!)
# ================================================================
list(itertools.accumulate([1,2,3,4,5]))             # [1,3,6,10,15] — prefix sums
import operator
list(itertools.accumulate([1,2,3,4,5], operator.mul))  # [1,2,6,24,120] — prefix products
list(itertools.accumulate([3,1,4,1,5], max))        # [3,3,4,4,5] — running max
 
# ================================================================
# count / cycle / repeat — infinite iterators
# ================================================================
counter = itertools.count(start=10, step=2)
[next(counter) for _ in range(4)]          # [10, 12, 14, 16]
 
cycler = itertools.cycle(['R','G','B'])
[next(cycler) for _ in range(7)]           # ['R','G','B','R','G','B','R']
 
list(itertools.repeat(0, 5))               # [0,0,0,0,0]

import itertools
 
def subsets(nums: list) -> list:
    """
    Generate all subsets (power set) of nums.
    Example: [1,2,3] → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
    """
    result = []
    for r in range(len(nums) + 1):          # for each subset size 0..n
        for combo in itertools.combinations(nums, r):
            result.append(list(combo))
    return result
 
# Alternative using bitmask (no itertools):
def subsets_bits(nums: list) -> list:
    n = len(nums)
    result = []
    for mask in range(1 << n):              # 2^n possible masks (0 to 2^n - 1)
        subset = []
        for i in range(n):
            if mask & (1 << i):             # if i-th bit is set
                subset.append(nums[i])      # include nums[i]
        result.append(subset)
    return result
    # Time: O(n × 2^n), Space: O(n × 2^n)

import itertools
 
def paginate(data_generator, page_size: int, page_num: int) -> dict:
    """
    Paginate any iterable (works with generators — memory efficient!).
    page_num is 1-indexed.
 
    Real-world use: paginate database cursor results without
    loading entire result set into memory.
    """
    start = page_size * (page_num - 1)
    page_items = list(itertools.islice(data_generator, start, start + page_size))
 
    return {
        "page": page_num,
        "page_size": page_size,
        "items": page_items,
        "has_more": len(page_items) == page_size,   # might have more
    }
 
# Usage with generator (memory efficient):
def stream_users():
    for i in range(1, 10001):
        yield {"id": i, "name": f"User_{i}"}
 
# Get page 3, 20 items per page:
result = paginate(stream_users(), page_size=20, page_num=3)
# → {"page": 3, "items": [user41..user60], "has_more": True}

# Iterable vs Iterator
iter(lst)                        # get iterator from iterable
next(it)                         # get next value from iterator
next(it, default)               # get next or return default (no error)
 
# Generator function
def gen(): yield value           # pauses and resumes
yield from sub_gen()             # delegate to another generator
 
# Generator expression (lazy, memory efficient)
(x**2 for x in lst)             # vs [x**2 for x in lst] (eager)
 
# itertools essentials
itertools.combinations(lst, r)   # C(n,r) — order doesn't matter
itertools.permutations(lst, r)   # P(n,r) — order matters
itertools.product(a, b)          # cartesian product
itertools.chain(*lists)          # concatenate iterables lazily
itertools.chain.from_iterable(nested)   # flatten one level
itertools.accumulate(lst)        # prefix sums
itertools.islice(gen, start, stop)      # slice any iterator
itertools.groupby(sorted_data, key)     # group (SORT FIRST!)
itertools.takewhile(pred, it)    # take while condition True
itertools.dropwhile(pred, it)    # drop while condition True
 
# Common patterns
sum(x**2 for x in lst)          # generator in function call
list(map(fn, lst))               # apply fn to each element
list(filter(fn, lst))            # keep elements where fn is True
[x for sub in nested for x in sub]     # flatten nested list

# ================================================================
# Functions can be assigned to variables
# ================================================================
def greet(name: str) -> str:
    return f"Hello, {name}!"
 
say_hi = greet              # NO parentheses = reference to function object
                            # With parentheses greet() = CALL the function
print(say_hi)               # <function greet at 0x...>
say_hi("Alice")             # "Hello, Alice!" — calling via new name
 
# ================================================================
# Functions can be passed as arguments
# ================================================================
def apply(func, value):
    """Accepts a function and calls it with value."""
    return func(value)
 
apply(len, "hello")         # 5  — passed built-in len
apply(str.upper, "hello")   # "HELLO" — passed method
apply(greet, "Bob")         # "Hello, Bob!" — passed custom function
 
# ================================================================
# Functions can be returned from functions
# ================================================================
def make_multiplier(n: int):
    """Factory function — returns a customized function."""
    def multiplier(x):          # inner function defined inside outer
        return x * n            # 'n' is captured from enclosing scope
    return multiplier           # return the function OBJECT (no parentheses)
 
double = make_multiplier(2)     # double is now a function
triple = make_multiplier(3)
 
double(5)                       # 10
triple(5)                       # 15
double(triple(4))               # double(12) = 24
 
# ================================================================
# Closures — inner function remembers enclosing scope
# ================================================================
def make_counter(start: int = 0):
    """Returns a counter function that remembers its count."""
    count = start               # enclosed variable — lives in closure
 
    def increment(by: int = 1):
        nonlocal count          # ← tells Python: modify the ENCLOSING count
        count += by             # without nonlocal, this would be UnboundLocalError!
        return count
 
    return increment
 
counter_a = make_counter(0)
counter_b = make_counter(100)   # independent closure!
 
counter_a()                     # 1
counter_a()                     # 2
counter_a(5)                    # 7
counter_b()                     # 101 — completely independent!
 
# ================================================================
# nonlocal vs global
# ================================================================
x = 10                          # module-level variable
 
def outer():
    x = 20                      # outer local variable
 
    def inner():
        nonlocal x              # refers to outer()'s x, NOT module x
        x += 5
        print(x)                # 25
 
    inner()
    print(x)                    # 25 — modified by inner!
 
# global keyword (rarely needed, usually bad practice):
def bad_practice():
    global x                    # refers to module-level x
    x += 1                      # modifies global state — avoid!
 
# ================================================================
# Functions stored in data structures
# ================================================================
operations = {
    'add':      lambda a, b: a + b,
    'subtract': lambda a, b: a - b,
    'multiply': lambda a, b: a * b,
    'divide':   lambda a, b: a / b if b != 0 else None
}
 
operations['add'](3, 4)         # 7
operations['multiply'](3, 4)    # 12
 
# Dispatch table pattern (replaces long if-elif chains):
def process(op: str, a: int, b: int):
    handler = operations.get(op)
    if not handler:
        raise ValueError(f"Unknown operation: {op}")
    return handler(a, b)