A **data structure** is a way to store data so you can **use it efficiently**.
  
  If you choose the right structure:
  - your code becomes faster
  - your logic becomes simpler
  - your programs scale better
  
  If you choose the wrong structure:
  - you get slow apps
  - messy code
  - hard bugs
  
  ## What you will learn in this playlist
  We will go step by step from beginner to advanced:
  - Lists, tuples, sets, dictionaries
  - Stacks, queues, heaps
  - Trees, graphs (intro level)
  - How to pick the right structure for the job
  - Time complexity (in simple words)
  
  ## A simple example
  Imagine you store student names.
  - If you use a **list**, searching a name can be slow for large data.
  - If you use a **set**, checking if a name exists is fast.
  
  That is the power of picking the right structure.
  
  ## Core idea: operations you do most
  When you choose a data structure, ask:
  - Do I add items often?
  - Do I search often?
  - Do I need ordering?
  - Do I need uniqueness?
  - Do I need key-value lookup?
  
  ## Graph: how to choose quickly
  ```mermaid
  flowchart TD
    A[Need to store many items] --> B{Need order?}
    B -->|Yes| C[List / Tuple]
    B -->|No| D{Need uniqueness?}
    D -->|Yes| E[Set]
    D -->|No| F{Need key->value?}
    F -->|Yes| G[Dict]
    F -->|No| H[List]
  ```
  
  ## Key terms (student-friendly)
  - **Ordered**: items keep position (like list)
  - **Unordered**: no fixed position (like set)
  - **Mutable**: you can change it (list, dict)
  - **Immutable**: you cannot change it (tuple)
  - **Key-Value**: look up using keys (dict)
  
  ## Remember
  - Data structure choice decides speed and simplicity
  - Python gives powerful built-in containers
  - We'll build your concepts so you don’t need to read elsewhere
  

Build a clear foundation: what a data structure is, why it matters, how to choose one, and how Python stores and works with common containers.

Data Structures Intro

Big O tells you how time grows when your data grows.
  
  You do not need heavy math here.
  You only need this simple idea:
  
  ✅ If data becomes 10x larger, how much slower does your code get?
  
  ## Common Big O types (in human words)
  
  - **O(1)**: constant time, stays fast
  - **O(log n)**: grows slowly
  - **O(n)**: grows linearly
  - **O(n log n)**: common in sorting
  - **O(n²)**: becomes slow quickly
  
  ## Example: O(n) vs O(1)
  
  ### O(n): search in a list
  ```python
  names = ["Tom", "Sarah", "Mike", "Ahsan"]
  
  # worst case: it checks many items
  print("Ahsan" in names)
  ```
  
  ### O(1) average: search in a set
  ```python
  names = {"Tom", "Sarah", "Mike", "Ahsan"}
  print("Ahsan" in names)
  ```
  
  ## Why sets are faster for membership
  A list checks one by one.
  A set uses hashing to jump to the right place (average case).
  
  ## Visual intuition
  ```mermaid
  flowchart LR
    A[List membership] --> B[Check item1]
    B --> C[Check item2]
    C --> D[Check item3...]
    E[Set membership] --> F[Hash -> direct bucket]
  ```
  
  ## Practical cheat sheet (Python built-ins)
  - list append: usually fast
  - list membership: slow for large lists
  - dict get: fast average
  - set membership: fast average
  - sorting: n log n
  
  ## Remember
  - Big O helps you pick the right structure
  - You don’t need math, focus on growth behavior
  - Use set/dict for fast lookups
  

Understand time complexity with simple intuition: why some code is fast and some becomes slow as data grows, plus a practical cheat sheet for Python structures.

Big O Basics

A **list** stores multiple items in an ordered sequence.
  
  ### When to use a list
  Use a list when:
  - you care about order (first, second, third)
  - you need duplicates
  - you add/remove items often
  
  ## Creating lists
  ```python
  numbers = [10, 20, 30]
  names = ["Tom", "Sarah", "Mike"]
  mixed = ["Tom", 25, True]
  ```
  
  ## Indexing (most important)
  Index starts from 0.
  
  ```python
  names = ["Tom", "Sarah", "Mike"]
  print(names[0])  # Tom
  print(names[1])  # Sarah
  ```
  
  ## Negative indexing
  ```python
  print(names[-1])  # Mike (last item)
  ```
  
  ## Slicing (get a part)
  ```python
  nums = [1, 2, 3, 4, 5]
  print(nums[1:4])  # [2, 3, 4]
  ```
  
  ## Add and remove
  ```python
  fruits = ["apple", "banana"]
  fruits.append("orange")     # add at end
  fruits.insert(1, "grape")   # add at position
  print(fruits)
  
  fruits.remove("banana")     # remove by value
  last = fruits.pop()         # remove last and return it
  print(last)
  ```
  
  ## Beginner mistakes
  1) IndexError: accessing out of range
  ```python
  # names[10]  # error
  ```
  
  2) Confusing copy with reference
  ```python
  a = [1, 2]
  b = a
  b.append(3)
  print(a)  # [1,2,3] because both point to same list
  ```
  
  Fix:
  ```python
  a = [1, 2]
  b = a.copy()
  b.append(3)
  print(a)  # [1,2]
  ```
  
  ## Graph: list mental model
  ```mermaid
  flowchart LR
    A[List] --> B[Index 0]
    A --> C[Index 1]
    A --> D[Index 2]
  ```
  
  ## Remember
  - List is ordered and mutable
  - Index starts at 0
  - Use copy() when you want a real copy
  

Learn lists like a teacher would: what they are, when to use them, how indexing works, and how to avoid beginner mistakes with examples and visuals.

List Fundamentals

A **tuple** is like a list, but **immutable** (cannot be changed).
  
  ### When to use tuples
  Use tuples when:
  - data should not change (like coordinates)
  - you want safer code (no accidental edits)
  - you want to return multiple values from a function
  
  ## Create tuples
  ```python
  point = (10, 20)
  user = ("Tom", 25, "Austin")
  ```
  
  ## Single-item tuple (common beginner confusion)
  ```python
  x = (5)     # this is int, not tuple
  y = (5,)    # this is tuple
  ```
  
  ## Access items
  ```python
  point = (10, 20)
  print(point[0])  # 10
  ```
  
  ## Tuple unpacking (very important)
  ```python
  person = ("Sarah", 28)
  name, age = person
  print(name, age)
  ```
  
  ## Why immutability is useful
  If you store config settings, you don’t want changes by mistake.
  
  ```python
  CONFIG = ("localhost", 5432)
  # CONFIG[0] = "prod"  # error, cannot change
  ```
  
  ## Graph: list vs tuple
  ```mermaid
  flowchart LR
    A[List] --> B[Mutable: can change]
    C[Tuple] --> D[Immutable: cannot change]
  ```
  
  ## Remember
  - Tuples are ordered but immutable
  - Great for fixed data
  - Unpacking is a powerful Python skill
  

Understand tuples clearly: why immutability matters, where tuples are better than lists, and how packing/unpacking works with real examples.

Tuple Essentials

A **set** stores **unique items** and is usually **unordered**.
  
  ### Why sets matter
  Sets are extremely useful when you want:
  - remove duplicates
  - check membership fast
  - compare groups (common vs missing)
  
  ## Create a set
  ```python
  nums = {1, 2, 3, 3, 3}
  print(nums)  # {1,2,3} duplicates removed
  ```
  
  ## Add and remove
  ```python
  s = {"a", "b"}
  s.add("c")
  s.remove("b")  # error if missing
  s.discard("x") # safe if missing
  ```
  
  ## Fast membership
  ```python
  users = {"Tom", "Sarah", "Mike"}
  print("Sarah" in users)  # fast
  ```
  
  ## Common set operations (very useful)
  ```python
  a = {"Tom", "Sarah", "Mike"}
  b = {"Sarah", "Ahsan"}
  
  print(a & b)  # intersection -> common
  print(a | b)  # union -> all
  print(a - b)  # difference -> in a not in b
  ```
  
  ## Real example: find new applicants
  ```python
  applied = {"Tom", "Sarah"}
  all_users = {"Tom", "Sarah", "Mike", "Ahsan"}
  not_applied = all_users - applied
  print(not_applied)
  ```
  
  ## Graph: set uniqueness
  ```mermaid
  flowchart LR
    A[Input: a,a,b,c] --> B[Set]
    B --> C[Output: a,b,c]
  ```
  
  ## Remember
  - Sets remove duplicates automatically
  - Use sets for fast membership
  - Set operations solve many real problems
  

Learn sets from scratch: uniqueness, fast membership checks, and practical use cases like removing duplicates and comparing groups of data.

Set Basics

A **dictionary (dict)** stores data as **key -> value**.
  
  You use dict when you want:
  - fast lookup by key
  - mapping IDs to objects
  - configuration settings
  - counting occurrences
  
  ## Create a dict
  ```python
  person = {"name": "Tom", "age": 25, "city": "Austin"}
  ```
  
  ## Get values (safe vs unsafe)
  Unsafe (can crash if key missing):
  ```python
  # print(person["email"])  # KeyError
  ```
  
  Safe:
  ```python
  print(person.get("email", "N/A"))
  ```
  
  ## Add/update
  ```python
  person["age"] = 26
  person["email"] = "tom@example.com"
  ```
  
  ## Loop patterns
  ```python
  for key in person:
      print(key, person[key])
  
  for k, v in person.items():
      print(k, v)
  ```
  
  ## Real use case: counting
  ```python
  text = "banana"
  count = {}
  
  for ch in text:
      count[ch] = count.get(ch, 0) + 1
  
  print(count)  # {'b':1,'a':3,'n':2}
  ```
  
  ## Graph: dict mental model
  ```mermaid
  flowchart LR
    A[key: name] --> B[value: Tom]
    C[key: age] --> D[value: 25]
  ```
  
  ## Remember
  - dict gives fast key lookups
  - use get() to avoid KeyError
  - items() is best for looping key+value
  

Master dictionaries as key-value maps: safe lookups, updating values, looping patterns, and real-world use cases like configs and counters.

Dict Fundamentals

A string is also a **sequence data structure**.
  
  Key idea:
  - string is **ordered**
  - string is **immutable**
  - you can index and slice it like lists/tuples
  
  ## Indexing and slicing
  ```python
  s = "Python"
  print(s[0])    # P
  print(s[-1])   # n
  print(s[1:4])  # yth
  ```
  
  ## Looping
  ```python
  for ch in "abc":
      print(ch)
  ```
  
  ## Why immutability matters
  You cannot modify a character directly:
  ```python
  s = "cat"
  # s[0] = "b"  # error
  ```
  
  Instead, you create a new string:
  ```python
  s = "b" + s[1:]
  print(s)  # bat
  ```
  
  ## Common beginner need: building strings efficiently
  If you are joining many parts:
  ```python
  parts = ["Hello", "from", "Python"]
  result = " ".join(parts)
  print(result)
  ```
  
  ## Graph: string immutability
  ```mermaid
  flowchart LR
    A[Old string] --> B[Cannot change in place]
    B --> C[Create new string]
  ```
  
  ## Remember
  - strings behave like sequences
  - immutable means safe but you must rebuild for changes
  - join() is best for combining many parts
  

Treat strings like sequences: indexing, slicing, iteration, and why immutability matters when you build text processing and parsing logic.

Strings as Structures

Indexing and slicing are core skills for working with sequences:
  - list
  - tuple
  - string
  
  ## Indexing recap
  ```python
  data = ["a", "b", "c", "d"]
  print(data[0])   # a
  print(data[-1])  # d
  ```
  
  ## Slicing format
  `data[start:end]` includes start but excludes end.
  
  ```python
  data = ["a", "b", "c", "d", "e"]
  print(data[1:4])  # ['b','c','d']
  ```
  
  ## Slice with step
  `data[start:end:step]`
  
  ```python
  nums = [0,1,2,3,4,5,6,7,8,9]
  print(nums[0:10:2])  # [0,2,4,6,8]
  ```
  
  ## Reverse a sequence
  ```python
  print(nums[::-1])
  ```
  
  ## Common beginner mistakes
  - forgetting end is exclusive
  - mixing up negative indexes
  
  ## Graph: slicing mental model
  ```mermaid
  flowchart LR
    A[Sequence] --> B[start at index]
    B --> C[stop before end]
    C --> D[optional step]
  ```
  
  ## Remember
  - end index is not included
  - step helps skip and reverse
  - slicing works across list/tuple/string
  

Learn indexing, slicing, and step slicing for lists/tuples/strings with strong intuition, so you stop guessing and start slicing confidently.

Indexing and Slicing

Mutability means: can this object change after creation?
  
  ## Mutable structures
  - list
  - dict
  - set
  - most class objects
  
  ## Immutable structures
  - tuple
  - string
  - int, float, bool
  
  ## Why it matters
  Because it affects:
  - copying
  - passing to functions
  - unexpected bugs
  
  ## Example: mutable reference bug
  ```python
  a = [1, 2]
  b = a
  b.append(3)
  print(a)  # [1, 2, 3]
  ```
  
  ## Fix: copy
  ```python
  a = [1, 2]
  b = a.copy()
  b.append(3)
  print(a)  # [1, 2]
  ```
  
  ## Example: immutable is safe
  ```python
  x = "cat"
  y = x
  y = "bat"
  print(x)  # cat
  ```
  
  ## Graph: reference vs copy
  ```mermaid
  flowchart LR
    A[a] --> C[Same list object]
    B[b] --> C
    D[a.copy()] --> E[New list object]
  ```
  
  ## Remember
  - Most “surprising” bugs come from mutability
  - Use copy() when needed
  - Immutable data prevents accidental changes
  

Understand the #1 beginner confusion: why some structures change in place and others don’t, and how this affects copying, functions, and bugs.

Mutability Explained

Copying is easy when data is flat, but tricky when nested.
  
  ## Shallow copy vs deep copy
  - Shallow copy copies the outer container only
  - Deep copy copies everything inside (nested items too)
  
  ## Shallow copy example (problem)
  ```python
  a = [[1, 2], [3, 4]]
  b = a.copy()
  b[0].append(99)
  
  print(a)  # [[1,2,99],[3,4]] <-- changed!
  print(b)
  ```
  
  Why?
  Because inner lists are still shared.
  
  ## Deep copy (solution)
  ```python
  import copy
  
  a = [[1, 2], [3, 4]]
  b = copy.deepcopy(a)
  b[0].append(99)
  
  print(a)  # [[1,2],[3,4]]
  print(b)  # [[1,2,99],[3,4]]
  ```
  
  ## Graph: shallow vs deep
  ```mermaid
  flowchart LR
    A[Outer list] --> B[Inner list 1]
    A --> C[Inner list 2]
    D[Shallow copy] --> B
    D --> C
    E[Deep copy] --> F[New inner list 1]
    E --> G[New inner list 2]
  ```
  
  ## Remember
  - Shallow copy is fine for flat structures
  - Nested structures often need deepcopy
  - Know this to avoid hidden bugs
  

Learn shallow vs deep copying with nested structures, why shallow copy breaks in nested lists/dicts, and the correct fixes with examples.

Copy vs Deep Copy

Most beginners ask: “Which one should I use?”
  
  Here is the simple decision system.
  
  ## Use list when
  - order matters
  - you need duplicates
  - you need indexing
  
  ## Use tuple when
  - order matters
  - you want data to be fixed (no changes)
  
  ## Use set when
  - uniqueness matters
  - you need fast membership tests
  
  ## Use dict when
  - you need key -> value lookup
  
  ## Examples
  ### Task: store user order list
  Use list:
  ```python
  queue = ["Tom", "Sarah", "Mike"]
  ```
  
  ### Task: store unique user emails
  Use set:
  ```python
  emails = {"a@x.com", "b@x.com"}
  ```
  
  ### Task: store user profile by id
  Use dict:
  ```python
  users = {101: {"name":"Tom"}, 102: {"name":"Sarah"}}
  ```
  
  ## Graph: quick decision
  ```mermaid
  flowchart TD
    A[Need a container] --> B{Need key->value?}
    B -->|Yes| C[dict]
    B -->|No| D{Need uniqueness?}
    D -->|Yes| E[set]
    D -->|No| F{Need fixed/unchangeable?}
    F -->|Yes| G[tuple]
    F -->|No| H[list]
  ```
  
  ## Remember
  - Choose based on operations, not personal preference
  - Correct structure makes code simpler and faster
  

A practical decision guide: list vs tuple vs set vs dict, with real tasks like membership, ordering, uniqueness, and key-based access.

Choosing the Right Structure

Real data is often nested.
  
  Examples:
  - API JSON
  - database records
  - configuration files
  
  ## Nested list (2D list)
  ```python
  matrix = [
    [1, 2, 3],
    [4, 5, 6]
  ]
  print(matrix[0][1])  # 2
  ```
  
  ## Nested dict (JSON style)
  ```python
  user = {
    "id": 101,
    "profile": {"name": "Tom", "city": "Austin"}
  }
  
  print(user["profile"]["name"])
  ```
  
  ## Safe access pattern
  Use get() to avoid KeyError:
  
  ```python
  city = user.get("profile", {}).get("city", "Unknown")
  print(city)
  ```
  
  ## Loop through nested structures
  ```python
  for row in matrix:
      for value in row:
          print(value)
  ```
  
  ## Graph: nested access
  ```mermaid
  flowchart LR
    A[user] --> B[profile]
    B --> C[name]
    B --> D[city]
  ```
  
  ## Remember
  - Nested data is normal in real apps
  - Use get() for safe access
  - Understand references when nested lists are copied
  

Work confidently with nested lists/dicts: reading and writing deeply, loops, safe access patterns, and a strong mental model with diagrams.

Nested Structures

This lesson teaches list patterns you will use in real projects.
  
  ## 1) Build a list from data
  ```python
  nums = []
  for i in range(5):
      nums.append(i*i)
  print(nums)
  ```
  
  Better with comprehension:
  ```python
  nums = [i*i for i in range(5)]
  ```
  
  ## 2) Flatten a list of lists
  ```python
  data = [[1,2], [3,4], [5]]
  flat = [x for row in data for x in row]
  print(flat)
  ```
  
  ## 3) Chunk a list (split into parts)
  ```python
  items = list(range(10))
  size = 3
  
  chunks = [items[i:i+size] for i in range(0, len(items), size)]
  print(chunks)
  ```
  
  ## 4) Remove items safely while looping (important)
  Wrong way:
  ```python
  # can skip items
  ```
  
  Right way:
  ```python
  nums = [1,2,3,4,5,6]
  nums = [n for n in nums if n % 2 == 1]
  print(nums)
  ```
  
  ## Graph: chunking
  ```mermaid
  flowchart LR
    A[0..9] --> B[0..2]
    A --> C[3..5]
    A --> D[6..8]
    A --> E[9]
  ```
  
  ## Remember
  - Comprehensions are powerful and readable
  - Avoid modifying list while iterating
  - Chunking and flattening are common tasks
  

Learn essential list patterns: building lists, flattening, chunking, searching, and removing items safely, using clean beginner-friendly techniques.

List Patterns

Dictionaries are the backbone of most Python applications.
  
  ## 1) Counting (classic)
  ```python
  text = "mississippi"
  count = {}
  
  for ch in text:
      count[ch] = count.get(ch, 0) + 1
  
  print(count)
  ```
  
  ## 2) Grouping values by key
  ```python
  students = [
    ("Tom", "A"),
    ("Sarah", "A"),
    ("Mike", "B"),
  ]
  
  groups = {}
  for name, grade in students:
      groups.setdefault(grade, []).append(name)
  
  print(groups)  # {'A': ['Tom','Sarah'], 'B': ['Mike']}
  ```
  
  ## 3) Merge dicts
  ```python
  a = {"x": 1, "y": 2}
  b = {"y": 99, "z": 3}
  merged = {**a, **b}
  print(merged)
  ```
  
  ## 4) Invert a dict (careful with duplicates)
  ```python
  d = {"a": 1, "b": 2}
  inv = {v: k for k, v in d.items()}
  print(inv)
  ```
  
  ## Graph: grouping
  ```mermaid
  flowchart TD
    A[("Tom","A")] --> B[A group]
    C[("Sarah","A")] --> B
    D[("Mike","B")] --> E[B group]
  ```
  
  ## Remember
  - get() and setdefault() are your friends
  - dict is best for fast lookup and grouping
  - careful when inverting if values repeat
  

Practical dictionary patterns: grouping, counting, merging, default values, and building maps for fast lookups in real-world data.

Dict Patterns

Python's `collections` module gives extra data structures.
  
  ## 1) Counter (count items easily)
  ```python
  from collections import Counter
  
  fruits = ["apple", "banana", "apple", "orange", "banana", "apple"]
  c = Counter(fruits)
  
  print(c)
  print(c.most_common(2))
  ```
  
  ## 2) defaultdict (avoid KeyError)
  ```python
  from collections import defaultdict
  
  scores = defaultdict(int)
  scores["Tom"] += 10
  print(scores)
  ```
  
  ## 3) deque (fast queue)
  ```python
  from collections import deque
  
  q = deque(["Tom", "Sarah"])
  q.append("Mike")
  q.appendleft("Ahsan")
  print(q)
  
  left = q.popleft()
  print(left)
  ```
  
  ## 4) namedtuple (lightweight objects)
  ```python
  from collections import namedtuple
  
  Point = namedtuple("Point", ["x", "y"])
  p = Point(10, 20)
  print(p.x, p.y)
  ```
  
  ## Graph: deque queue
  ```mermaid
  flowchart LR
    A[Left] --> B[deque] --> C[Right]
  ```
  
  ## Remember
  - Counter for counting
  - defaultdict for grouping and safe defaults
  - deque for queues and stacks
  - namedtuple for readable tuple-like objects
  

Learn collections module structures that feel like “super-powered” lists and dicts: Counter, defaultdict, deque, and namedtuple with real examples.

Collections Toolkit

A **stack** follows LIFO:
  Last In, First Out.
  
  Real examples:
  - undo/redo
  - browser back button
  - function call stack
  
  ## Implement stack with list (simple)
  ```python
  stack = []
  stack.append("A")  # push
  stack.append("B")
  print(stack)
  
  top = stack.pop()  # pop
  print(top)
  print(stack)
  ```
  
  ## Stack example: bracket matching
  Goal: check if parentheses are balanced.
  
  ```python
  def is_balanced(s: str) -> bool:
      stack = []
      pairs = {")": "(", "]": "[", "}": "{"}
  
      for ch in s:
          if ch in "([{":
              stack.append(ch)
          elif ch in ")]}":
              if not stack or stack[-1] != pairs[ch]:
                  return False
              stack.pop()
  
      return len(stack) == 0
  
  print(is_balanced("(a[b]{c})"))  # True
  print(is_balanced("(a[b]{c}"))   # False
  ```
  
  ## Graph: stack LIFO
  ```mermaid
  flowchart TD
    A[Push A] --> B[Stack: A]
    B --> C[Push B]
    C --> D[Stack: A,B]
    D --> E[Pop -> B]
  ```
  
  ## Remember
  - stack = append + pop
  - stack[-1] is the top
  - used in parsing and “undo” logic
  

Learn stack (LIFO) using lists and deque, why stacks matter, and real examples like undo operations and bracket matching.

Stack in Python

A **queue** follows FIFO:
  First In, First Out.
  
  Real examples:
  - ticketing systems
  - print queues
  - job scheduling
  - message processing
  
  ## Why not use list for queue?
  Removing from front of list can be slow.
  `collections.deque` is designed for fast ends.
  
  ## Queue with deque
  ```python
  from collections import deque
  
  q = deque()
  q.append("Task1")     # enqueue
  q.append("Task2")
  print(q)
  
  first = q.popleft()   # dequeue
  print(first)
  print(q)
  ```
  
  ## Example: task processing simulation
  ```python
  from collections import deque
  
  tasks = deque(["email", "report", "backup"])
  
  while tasks:
      task = tasks.popleft()
      print("Processing:", task)
  ```
  
  ## Graph: queue FIFO
  ```mermaid
  flowchart LR
    A[Enqueue] --> B[Queue] --> C[Dequeue]
  ```
  
  ## Remember
  - Use deque for queues
  - append + popleft
  - queues are everywhere in systems
  

Understand queue (FIFO) using deque, why lists are not ideal for queues, and build a simple task queue like real apps.

Queue in Python

A priority queue returns items by priority, not by insertion time.
  
  Example:
  - urgent tasks first
  - shortest job first
  - routing algorithms
  
  In Python, we use `heapq`.
  
  ## Basic heap (min-heap)
  ```python
  import heapq
  
  heap = []
  heapq.heappush(heap, 5)
  heapq.heappush(heap, 1)
  heapq.heappush(heap, 3)
  
  print(heapq.heappop(heap))  # 1
  print(heapq.heappop(heap))  # 3
  ```
  
  ## Store (priority, value)
  ```python
  import heapq
  
  pq = []
  heapq.heappush(pq, (1, "urgent"))
  heapq.heappush(pq, (5, "low"))
  heapq.heappush(pq, (2, "medium"))
  
  while pq:
      priority, task = heapq.heappop(pq)
      print(priority, task)
  ```
  
  ## Max-heap trick
  heapq is min-heap. To simulate max-heap, store negative priorities.
  
  ```python
  import heapq
  
  pq = []
  heapq.heappush(pq, (-10, "high"))
  heapq.heappush(pq, (-1, "low"))
  
  print(heapq.heappop(pq))  # (-10, 'high')
  ```
  
  ## Graph: heap property (intuition)
  ```mermaid
  flowchart TD
    A[Min heap] --> B[Smallest item at top]
    B --> C[Pop gives smallest first]
  ```
  
  ## Remember
  - Use heapq for priority queues
  - Great for scheduling and shortest-first problems
  - Store (priority, item) for clean logic
  

Learn priority queues with heapq: always pull the smallest or highest priority item first, used in scheduling, shortest path, and job systems.

Priority Queue

dict and set are fast because they use **hashing**.
  
  ## What is hashing?
  A hash function converts a value into a number (hash).
  That hash helps decide where the item belongs.
  
  ## Basic idea (not math-heavy)
  - compute hash(key)
  - go to bucket
  - store/retrieve quickly
  
  ## Example: dict lookup
  ```python
  users = {"tom": 101, "sarah": 102}
  print(users["tom"])
  ```
  
  This feels instant even if dict is large (average case).
  
  ## Collisions (simple)
  Sometimes two keys produce same bucket.
  Python handles this internally.
  
  ## Keys must be hashable
  Hashable means: value does not change.
  Good keys:
  - str, int, tuple (if inner values are hashable)
  
  Bad keys:
  - list, dict, set (mutable)
  
  ```python
  good = {("a", 1): "ok"}  # tuple key works
  # bad = {[1,2]: "no"}     # list key fails
  ```
  
  ## Graph: hashing mental model
  ```mermaid
  flowchart LR
    A[key] --> B[hash()]
    B --> C[bucket]
    C --> D[value stored]
  ```
  
  ## Remember
  - dict/set are fast due to hashing (average case)
  - keys must be immutable (hashable)
  - collisions exist but Python manages them
  

Understand how dict and set feel 'instant': hashing basics, collisions, and practical rules for safe keys and good performance.

Hashing and Lookups

Sorting is a core operation in data structures.
  
  Python provides:
  - `sorted()` (returns new list)
  - `list.sort()` (sorts in place)
  
  ## Sort numbers
  ```python
  nums = [5, 2, 8, 1]
  print(sorted(nums))
  ```
  
  ## Sort strings
  ```python
  words = ["banana", "apple", "kiwi"]
  words.sort()
  print(words)
  ```
  
  ## Sort by custom key (very important)
  Sort by length:
  ```python
  words = ["apple", "hi", "banana", "kiwi"]
  words.sort(key=len)
  print(words)
  ```
  
  ## Sort dicts in a list
  ```python
  students = [
    {"name": "Tom", "grade": 85},
    {"name": "Sarah", "grade": 92},
    {"name": "Mike", "grade": 78},
  ]
  students.sort(key=lambda s: s["grade"], reverse=True)
  print(students)
  ```
  
  ## Multiple keys
  Sort by grade then name:
  ```python
  data = [("Tom", 25), ("Sarah", 25), ("Mike", 30)]
  data.sort(key=lambda x: (x[1], x[0]))
  print(data)
  ```
  
  ## Graph: sorting pipeline
  ```mermaid
  flowchart LR
    A[Unsorted list] --> B[key function]
    B --> C[Order by key]
    C --> D[Sorted list]
  ```
  
  ## Remember
  - sorted() makes a new list, sort() changes existing list
  - key= is the power tool
  - Python sorting is stable (keeps relative order when keys tie)
  

Sort lists of numbers, strings, tuples, and dictionaries correctly using key functions, multiple keys, and stable sorting with real examples.

Sorting Structures

Searching is common: find an item in your data.
  
  ## 1) Linear search (simple)
  ```python
  nums = [10, 20, 30, 40]
  target = 30
  found = target in nums
  print(found)
  ```
  
  ## 2) Binary search (fast but requires sorted list)
  Binary search is like: keep cutting the list in half.
  
  Use `bisect`:
  ```python
  import bisect
  
  nums = [10, 20, 30, 40, 50]
  i = bisect.bisect_left(nums, 30)
  print(i)  # 2
  ```
  
  ## 3) Best trick: use set/dict when you do many searches
  ```python
  nums = list(range(1000000))
  nums_set = set(nums)
  
  print(999999 in nums_set)  # fast
  ```
  
  ## Graph: linear vs binary
  ```mermaid
  flowchart LR
    A[Linear search] --> B[Check 1 by 1]
    C[Binary search] --> D[Half -> half -> half]
  ```
  
  ## Remember
  - Linear search is simple but slower for big data
  - Binary search is fast but requires sorted data
  - For repeated lookups, use set/dict
  

Learn practical searching: linear search, binary search with bisect, and when to use set/dict instead of searching lists.

Searching Patterns

Two pointers is a technique used with lists (often sorted).
  
  Idea:
  - you keep two indexes moving
  - you avoid nested loops
  - you make code faster
  
  ## Example: find pair with sum in sorted list
  ```python
  def has_pair(nums, target):
      left, right = 0, len(nums) - 1
  
      while left < right:
          s = nums[left] + nums[right]
          if s == target:
              return True
          if s < target:
              left += 1
          else:
              right -= 1
  
      return False
  
  print(has_pair([1,2,3,4,6,8], 10))  # True (2+8)
  ```
  
  ## Why this is powerful
  Instead of checking all pairs (slow), you move pointers smartly.
  
  ## Graph: pointer movement
  ```mermaid
  flowchart LR
    A[left] --> B[move right if sum too small]
    C[right] --> D[move left if sum too big]
  ```
  
  ## Remember
  - Works best on sorted lists
  - Often replaces O(n²) with O(n)
  - Very common in interviews and real code
  

Solve array/list problems efficiently using two pointers: pairs, removing duplicates in sorted data, and sliding comparisons with clear visuals.

Two Pointer Technique

Sliding window is used when you need continuous chunks of data.
  
  Example:
  - max sum of 3 consecutive days
  - longest substring without repeating
  - windowed averages
  
  ## Example: max sum of k consecutive items
  ```python
  def max_sum_k(nums, k):
      window_sum = sum(nums[:k])
      best = window_sum
  
      for i in range(k, len(nums)):
          window_sum += nums[i] - nums[i-k]
          best = max(best, window_sum)
  
      return best
  
  print(max_sum_k([2,1,5,1,3,2], 3))  # 9
  ```
  
  ## Why this is efficient
  Instead of summing each window from scratch,
  you update by removing left item and adding right item.
  
  ## Graph: window movement
  ```mermaid
  flowchart LR
    A[Window start] --> B[Shift right]
    B --> C[Drop left]
    C --> D[Add new right]
  ```
  
  ## Remember
  - Great for consecutive subarray/substrings
  - Converts repeated work into one-pass logic
  - Often changes O(n*k) into O(n)
  

Learn the sliding window technique to process subarrays efficiently, like max sum of k items, longest substring problems, and stream-like processing.

Sliding Window

Recursion means a function calls itself.
  
  It is useful for:
  - nested structures
  - trees
  - divide-and-conquer logic
  
  ## The two rules
  1) Base case (stop condition)
  2) Recursive step (smaller problem)
  
  ## Example: sum nested list
  ```python
  def deep_sum(data):
      total = 0
      for item in data:
          if isinstance(item, list):
              total += deep_sum(item)
          else:
              total += item
      return total
  
  print(deep_sum([1, [2, 3], [4, [5]]]))  # 15
  ```
  
  ## Graph: recursion idea
  ```mermaid
  flowchart TD
    A[Problem] --> B[Smaller problem]
    B --> C[Smaller problem]
    C --> D[Base case]
    D --> E[Return up]
  ```
  
  ## Remember
  - Always define a base case
  - Each call must reduce the problem
  - Recursion is common in tree/graph processing
  

Understand recursion as a tool for nested data, trees, and parsing. Learn base case, recursive step, and how to avoid infinite recursion.

Recursion for Structures

Most APIs return JSON, which becomes nested dict/list in Python.
  
  ## Example JSON-like structure
  ```python
  data = {
    "users": [
      {"id": 1, "profile": {"name": "Tom"}},
      {"id": 2, "profile": {"name": "Sarah"}},
    ]
  }
  ```
  
  ## Read nested data safely
  ```python
  users = data.get("users", [])
  for u in users:
      name = u.get("profile", {}).get("name", "Unknown")
      print(name)
  ```
  
  ## Transform: build id -> name map
  ```python
  id_to_name = {}
  for u in data.get("users", []):
      uid = u.get("id")
      name = u.get("profile", {}).get("name")
      if uid is not None and name is not None:
          id_to_name[uid] = name
  
  print(id_to_name)
  ```
  
  ## Graph: JSON mapping
  ```mermaid
  flowchart LR
    A[users list] --> B[loop]
    B --> C[id]
    B --> D[name]
    C --> E[dict map]
    D --> E
  ```
  
  ## Remember
  - JSON becomes dict + list
  - Use get() to avoid KeyError
  - Building maps is a common real-world pattern
  

Work with JSON-like dict/list structures: safe reading, transformations, and building clean nested data for APIs and real applications.

Data in JSON Style

Python uses dynamic arrays for lists, but linked lists are still important to understand.
  
  ## What is a linked list?
  A chain of nodes:
  - each node holds a value
  - each node points to the next node
  
  ## Why learn it?
  - helps you understand pointers and memory ideas
  - useful in interviews and some system designs
  
  ## Node and list implementation
  ```python
  class Node:
      def __init__(self, value, next=None):
          self.value = value
          self.next = next
  
  class LinkedList:
      def __init__(self):
          self.head = None
  
      def add_front(self, value):
          self.head = Node(value, self.head)
  
      def to_list(self):
          out = []
          cur = self.head
          while cur:
              out.append(cur.value)
              cur = cur.next
          return out
  
  ll = LinkedList()
  ll.add_front(3)
  ll.add_front(2)
  ll.add_front(1)
  print(ll.to_list())  # [1,2,3]
  ```
  
  ## Graph: linked list
  ```mermaid
  flowchart LR
    A[Node 1] --> B[Node 2]
    B --> C[Node 3]
    C --> D[None]
  ```
  
  ## Remember
  - Linked lists excel at insert/remove at head
  - Random access (indexing) is slow
  - Python list is usually better in real Python apps
  

Understand linked lists conceptually in Python: nodes, pointers, and when linked lists help or hurt, with a clean implementation and diagrams.

Linked List Concept

A tree is a hierarchical structure.
  
  Real examples:
  - file system folders
  - HTML DOM
  - organization charts
  
  ## Tree vocabulary
  - root: top node
  - child: below a node
  - leaf: node with no children
  
  ## Simple binary tree node
  ```python
  class Node:
      def __init__(self, value, left=None, right=None):
          self.value = value
          self.left = left
          self.right = right
  ```
  
  ## Build a small tree
  ```python
  root = Node(1, Node(2), Node(3))
  ```
  
  ## DFS traversal (in-order)
  ```python
  def inorder(node):
      if not node:
          return
      inorder(node.left)
      print(node.value)
      inorder(node.right)
  
  inorder(root)  # 2,1,3
  ```
  
  ## BFS traversal (level order)
  ```python
  from collections import deque
  
  def bfs(root):
      q = deque([root])
      while q:
          node = q.popleft()
          print(node.value)
          if node.left:
              q.append(node.left)
          if node.right:
              q.append(node.right)
  
  bfs(root)  # 1,2,3
  ```
  
  ## Graph: tree structure
  ```mermaid
  flowchart TD
    A[1] --> B[2]
    A --> C[3]
  ```
  
  ## Remember
  - Trees model hierarchy
  - DFS uses recursion or stack
  - BFS uses queue
  

Learn trees as hierarchical structures: nodes, children, traversal (DFS/BFS), and why trees appear in file systems, UI, and search problems.

Binary Tree Intro

This lesson takes heaps from basic to real problem solving.
  
  ## Heapify (turn list into heap)
  ```python
  import heapq
  
  nums = [5, 2, 9, 1, 7]
  heapq.heapify(nums)
  print(nums)  # now heap structure
  ```
  
  ## Get k smallest
  ```python
  import heapq
  
  nums = [10, 4, 7, 1, 9, 2]
  print(heapq.nsmallest(3, nums))  # [1,2,4]
  ```
  
  ## Get k largest
  ```python
  import heapq
  print(heapq.nlargest(2, nums))  # [10,9]
  ```
  
  ## Merge sorted lists efficiently
  ```python
  import heapq
  
  a = [1,4,7]
  b = [2,5,8]
  c = [3,6,9]
  
  print(list(heapq.merge(a, b, c)))
  ```
  
  ## Graph: heap use cases
  ```mermaid
  flowchart TD
    A[Heap] --> B[Scheduling]
    A --> C[Top K]
    A --> D[Merging sorted streams]
  ```
  
  ## Remember
  - heapify is fast for building heap
  - nsmallest/nlargest solve top-k problems
  - merge is great for sorted streams
  

Go deeper with heaps: heapify, k largest/smallest problems, merging sorted streams, and building efficient scheduling logic.

Heap Deep Dive

A graph represents connections between things.
  
  Examples:
  - roads between cities
  - followers on social media
  - dependencies in projects
  
  ## Adjacency list (best common representation)
  ```python
  graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": []
  }
  ```
  
  ## DFS traversal
  ```python
  def dfs(graph, start):
      visited = set()
  
      def visit(node):
          if node in visited:
              return
          visited.add(node)
          print(node)
          for nxt in graph.get(node, []):
              visit(nxt)
  
      visit(start)
  
  dfs(graph, "A")
  ```
  
  ## BFS traversal
  ```python
  from collections import deque
  
  def bfs(graph, start):
      visited = set([start])
      q = deque([start])
  
      while q:
          node = q.popleft()
          print(node)
          for nxt in graph.get(node, []):
              if nxt not in visited:
                  visited.add(nxt)
                  q.append(nxt)
  
  bfs(graph, "A")
  ```
  
  ## Graph diagram
  ```mermaid
  flowchart LR
    A --> B
    A --> C
    B --> D
    C --> D
  ```
  
  ## Remember
  - Graph = nodes + edges
  - adjacency list is common in Python
  - DFS and BFS are core traversal tools
  

Understand graphs as networks: adjacency lists, BFS/DFS traversal, and why graphs appear in maps, social networks, and recommendation systems.

Graph Intro

A trie (prefix tree) is great for prefix searching.
  
  Real examples:
  - autocomplete
  - dictionary word search
  - spam filters (prefix rules)
  
  ## Trie node structure
  ```python
  class TrieNode:
      def __init__(self):
          self.children = {}
          self.is_end = False
  
  class Trie:
      def __init__(self):
          self.root = TrieNode()
  
      def insert(self, word: str) -> None:
          node = self.root
          for ch in word:
              node = node.children.setdefault(ch, TrieNode())
          node.is_end = True
  
      def starts_with(self, prefix: str) -> bool:
          node = self.root
          for ch in prefix:
              if ch not in node.children:
                  return False
              node = node.children[ch]
          return True
  
  trie = Trie()
  trie.insert("cat")
  trie.insert("car")
  print(trie.starts_with("ca"))  # True
  print(trie.starts_with("cb"))  # False
  ```
  
  ## Graph: trie prefix idea
  ```mermaid
  flowchart TD
    A[root] --> B[c]
    B --> C[a]
    C --> D[t]
    C --> E[r]
  ```
  
  ## Remember
  - trie is built for prefixes
  - great for many words and frequent prefix queries
  - not always needed in normal apps, but powerful in search features
  

Learn trie (prefix tree) for fast prefix searches like autocomplete. Build a simple trie and understand why it beats scanning lists for prefixes.

Trie Concept

Immutability helps when data should never change.
  
  ## frozenset
  A frozenset is an immutable set.
  Useful when you want a set as a dict key.
  
  ```python
  a = frozenset([1,2,3])
  b = frozenset([2,3,4])
  
  print(a & b)
  ```
  
  ## Use immutable keys safely
  ```python
  cache = {}
  key = ("user", 101)  # tuple key
  cache[key] = {"name": "Tom"}
  print(cache[key])
  ```
  
  ## Why immutability helps
  - safer sharing across functions
  - safe keys in dict/set
  - fewer accidental mutations
  
  ## Graph: shared state safety
  ```mermaid
  flowchart LR
    A[Mutable object] --> B[Can change unexpectedly]
    C[Immutable object] --> D[Safe to share]
  ```
  
  ## Remember
  - tuples and frozenset help create safe keys
  - immutability reduces bugs in shared code
  

Learn when immutability is a feature: using tuples, frozenset, and safe keys in dicts, plus how immutability prevents bugs in shared state.

Immutable Collections

Custom iterables let your structure work like a list in a for loop.
  
  ## Why this matters
  In real code you may build:
  - stream readers
  - custom collections
  - data pipelines
  
  ## Example: custom range-like structure
  ```python
  class MyRange:
      def __init__(self, start, end):
          self.start = start
          self.end = end
  
      def __iter__(self):
          self.cur = self.start
          return self
  
      def __next__(self):
          if self.cur >= self.end:
              raise StopIteration
          val = self.cur
          self.cur += 1
          return val
  
  for x in MyRange(3, 7):
      print(x)
  ```
  
  ## Graph: iterator lifecycle
  ```mermaid
  flowchart LR
    A[__iter__] --> B[__next__]
    B --> C[Yield value]
    C --> B
    B --> D[StopIteration]
  ```
  
  ## Remember
  - __iter__ returns iterator object
  - __next__ returns next item
  - StopIteration ends the loop
  

Build your own iterable data structures with __iter__ and __next__, so you can create clean custom containers that work with for-loops naturally.

Custom Iterable Structures

Memory matters when data becomes big.
  
  ## Common memory mistake
  Building huge lists:
  ```python
  nums = [i for i in range(10_000_000)]
  ```
  
  Better: generator
  ```python
  nums = (i for i in range(10_000_000))
  print(next(nums))
  ```
  
  ## Streaming file lines (classic real-world)
  ```python
  def read_lines(path):
      with open(path, "r") as f:
          for line in f:
              yield line.strip()
  ```
  
  ## __slots__ (reduce per-object memory)
  ```python
  class Person:
      __slots__ = ["name", "age"]
  
      def __init__(self, name, age):
          self.name = name
          self.age = age
  ```
  
  ## Graph: list vs generator
  ```mermaid
  flowchart LR
    A[List] --> B[Allocates all values]
    C[Generator] --> D[Produces one value at a time]
  ```
  
  ## Remember
  - generators are best for large sequences
  - streaming avoids memory spikes
  - __slots__ helps when creating many objects
  

Learn how to reduce memory usage with generators, iterators, __slots__, and streaming patterns so your data handling stays fast and stable.

Memory Efficient Structures

This lesson is about mistakes that cause bugs in real projects.
  
  ## 1) Modifying a list while iterating
  Bad:
  ```python
  nums = [1,2,3,4]
  for n in nums:
      if n % 2 == 0:
          nums.remove(n)
  print(nums)  # can behave unexpectedly
  ```
  
  Good:
  ```python
  nums = [1,2,3,4]
  nums = [n for n in nums if n % 2 != 0]
  print(nums)
  ```
  
  ## 2) Shallow copy with nested structures
  ```python
  a = [[1],[2]]
  b = a.copy()
  b[0].append(99)
  print(a)  # changed
  ```
  
  Fix:
  ```python
  import copy
  b = copy.deepcopy(a)
  ```
  
  ## 3) Assuming set has stable order
  Sets are not designed for “index order”.
  If you need order, use list.
  
  ## 4) KeyError in dict
  Use get() for safe reads:
  ```python
  d = {"a": 1}
  print(d.get("x", 0))
  ```
  
  ## Graph: pitfalls map
  ```mermaid
  flowchart TD
    A[Bug] --> B[Mutation during loop]
    A --> C[Shallow copy]
    A --> D[Wrong structure assumption]
    A --> E[Unsafe dict access]
  ```
  
  ## Remember
  - Use get(), copy(), deepcopy()
  - Don’t mutate while iterating
  - Choose structure that matches your needs
  

Avoid common mistakes: modifying lists during iteration, shallow-copy bugs, dict key errors, set ordering assumptions, and performance traps.

Data Structure Pitfalls

This is the final lesson where you stop thinking:
    “list or set? dict or list?”
    and start thinking like a problem solver.
    
    A beginner usually chooses structures by habit.
    A good programmer chooses by **operations** (what you do most).
    
    ## The decision rule (the simplest one)
    Ask yourself these questions in order:
    
    1) Do I need **key -> value** lookup?
    2) Do I need **uniqueness** (no duplicates)?
    3) Do I need **order** (sequence matters)?
    4) Do I need **FIFO / LIFO / Priority** behavior?
    
    If you answer these correctly, your structure becomes obvious.
    
    ## Quick decision map (visual)
    ```mermaid
    flowchart TD
      A[What do you need?] --> B{Key -> value lookup?}
      B -->|Yes| C[dict]
      B -->|No| D{Need uniqueness?}
      D -->|Yes| E[set]
      D -->|No| F{Need order + indexing?}
      F -->|Yes| G[list]
      F -->|No| H{Fixed, unchangeable data?}
      H -->|Yes| I[tuple]
      H -->|No| J{Need FIFO (first in first out)?}
      J -->|Yes| K[deque queue]
      J -->|No| L{Need LIFO (last in first out)?}
      L -->|Yes| M[stack (list/deque)]
      L -->|No| N{Need highest/lowest priority first?}
      N -->|Yes| O[heapq priority queue]
    ```
    
    ---
    
    # 1) Scenario Decisions (Real-world style)
    
    ## Scenario 1: “Keep events in order (timeline / logs)”
    ### Problem
    You are storing events as they happen, and later you display them in the same order.
    
    ### Best structure: list
    Because:
    - order matters
    - you append a lot
    - you read in order
    
    ```python
    events = []
    events.append({"t": "10:00", "msg": "login"})
    events.append({"t": "10:02", "msg": "viewed profile"})
    print(events[0]["msg"])  # login
    ```
    
    **Benefit:** simple, readable, keeps natural order.
    
    ---
    
    ## Scenario 2: “Track unique users online”
    ### Problem
    Same user may ping your server many times, but you want unique online users.
    
    ### Best structure: set
    Because:
    - duplicates should be removed automatically
    - membership check should be fast
    
    ```python
    online = set()
    online.add("Tom")
    online.add("Tom")  # duplicate ignored
    online.add("Sarah")
    print(online)  # {'Tom', 'Sarah'} (order not guaranteed)
    print("Tom" in online)  # fast
    ```
    
    **Benefit:** prevents duplicates, super fast membership.
    
    ---
    
    ## Scenario 3: “Lookup user profile by id (fast)”
    ### Problem
    You have an id, you want the user data instantly.
    
    ### Best structure: dict
    Because:
    - key -> value lookup
    - fast average reads
    
    ```python
    users = {
      101: {"name": "Tom", "city": "Austin"},
      102: {"name": "Sarah", "city": "Miami"},
    }
    print(users[101]["name"])  # Tom
    ```
    
    Safe read:
    ```python
    print(users.get(999, {"name": "Unknown"}))
    ```
    
    **Benefit:** avoids slow searching in lists.
    
    ---
    
    ## Scenario 4: “Undo feature (editor, form, user actions)”
    ### Problem
    You want to undo the latest action first.
    
    ### Best structure: stack (LIFO)
    Because:
    - last action should come out first
    
    ```python
    history = []
    history.append("state1")
    history.append("state2")
    last = history.pop()
    print(last)  # state2
    ```
    
    **Benefit:** perfect natural match for undo.
    
    ---
    
    ## Scenario 5: “Task processing (jobs in order)”
    ### Problem
    First task added should be processed first.
    
    ### Best structure: queue (FIFO) using deque
    Because:
    - FIFO behavior
    - efficient popleft()
    
    ```python
    from collections import deque
    
    q = deque()
    q.append("task1")
    q.append("task2")
    
    print(q.popleft())  # task1
    ```
    
    **Benefit:** real-world job systems use this idea.
    
    ---
    
    ## Scenario 6: “Urgent job first (priority scheduling)”
    ### Problem
    You don’t want FIFO, you want highest/lowest priority first.
    
    ### Best structure: heapq (priority queue)
    Because:
    - always pops smallest priority item first (or use negative for max)
    
    ```python
    import heapq
    
    pq = []
    heapq.heappush(pq, (1, "urgent"))
    heapq.heappush(pq, (5, "low"))
    heapq.heappush(pq, (2, "medium"))
    
    while pq:
        p, task = heapq.heappop(pq)
        print(p, task)
    ```
    
    **Benefit:** used in scheduling, routing, “top-k” problems.
    
    ---
    
    # 2) The “Wrong Structure” Mistakes (and why they hurt)
    
    ## Mistake A: Using list for membership-heavy checks
    ```python
    nums = list(range(1_000_000))
    print(999_999 in nums)  # slow compared to set
    ```
    
    Fix:
    ```python
    nums_set = set(nums)
    print(999_999 in nums_set)  # fast
    ```
    
    ## Mistake B: Using set when you need stable ordering
    Sets don’t guarantee order for your logic.  
    If order matters, use list (or sort).
    
    ---
    
    # 3) A “One Minute Cheat Sheet”
    - **list**: ordered, duplicates allowed, indexing needed
    - **tuple**: ordered, fixed data (immutable)
    - **set**: unique items, fast membership
    - **dict**: key -> value mapping, fastest lookup style
    - **deque**: queue/stack optimized ends
    - **heapq**: priority-based retrieval
    
    ---
    
    # Final takeaway (the mindset)
    Data structures are not “topics”.
    They are “tools”.
    
    Pick the tool based on the job:
    - order? list/tuple
    - uniqueness? set
    - lookup? dict
    - FIFO? deque
    - LIFO? stack
    - priority? heapq
    
    ## Congratulations
    You completed the intermediate level Data Structures playlist (35 tutorials).

Purpose: make you confident in choosing the right data structure without guessing. Benefit: your code becomes faster, cleaner, and easier to maintain by matching the structure to the job (order, uniqueness, lookup, FIFO/LIFO, priority).

Structure Decision Mastery

Sometimes an operation looks slow once, but overall it is fast across many runs.

This idea is called **amortized analysis**.

## Why this matters
Beginners often think:
“append() sometimes resizes list, so it must be slow”.

But in reality:
- resizing happens rarely
- most appends are O(1)
- overall cost stays low

## Example: list append
```python
nums = []
for i in range(100000):
    nums.append(i)
```

Most appends are fast.
Occasionally Python resizes internal array.

## Intuition
Instead of asking:
“How slow is one operation?”
We ask:
“How slow is it on average over many operations?”

## Visual idea
```mermaid
flowchart LR
  A[Many cheap appends] --> B[One expensive resize]
  B --> C[Overall still fast]
```

## Key takeaway
- append() is amortized O(1)
- occasional slow step doesn’t break overall speed

## Remember
- Amortized = average over time
- Python lists are optimized for growth


Understand why some operations look expensive but are cheap on average, using list resizing and append behavior as your main intuition.

Amortized Analysis

Disjoint Set Union (DSU) helps manage groups.

It answers:
- Are two items connected?
- Can we merge two groups?

## Real examples
- friend networks
- computer networks
- clustering

## Basic structure
```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa != pb:
            self.parent[pb] = pa
```

## Usage
```python
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
print(dsu.find(0) == dsu.find(2))  # True
```

## Graph: groups merging
```mermaid
flowchart LR
  A[0] --> B[1]
  B --> C[2]
  D[3] --> E[4]
```

## Remember
- find() locates group leader
- union() merges groups
- path compression makes it fast


Learn Union-Find (DSU) to manage connected components efficiently, with path compression and real examples like grouping networks.

Disjoint Set Union

LRU means **Least Recently Used**.

When cache is full:
remove the item not used for longest time.

## Where used
- web servers
- databases
- API clients

## Simple LRU using OrderedDict
```python
from collections import OrderedDict

class LRUCache:
    def __init__(self, cap):
        self.cap = cap
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.cap:
            self.data.popitem(last=False)
```

## Example
```python
c = LRUCache(2)
c.put(1, "A")
c.put(2, "B")
c.get(1)
c.put(3, "C")  # removes key 2
```

## Graph: LRU idea
```mermaid
flowchart LR
  A[Oldest] --> B[Cache] --> C[Newest]
```

## Remember
- caches trade memory for speed
- LRU keeps recent items


Build an LRU cache using dict and deque ideas, and understand why caches are essential for performance in real systems.

LRU Cache

Segment tree helps answer range queries fast.

Example questions:
- sum from index 2 to 7?
- minimum in range?

## Why needed
Without it:
each query scans range (slow).
With tree:
logarithmic time.

## Build simple sum tree
```python
class SegTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.t = [0] * (4*self.n)
        self._build(arr, 1, 0, self.n-1)

    def _build(self, arr, v, l, r):
        if l == r:
            self.t[v] = arr[l]
        else:
            m = (l+r)//2
            self._build(arr, v*2, l, m)
            self._build(arr, v*2+1, m+1, r)
            self.t[v] = self.t[v*2] + self.t[v*2+1]
```

## Graph: segment ranges
```mermaid
flowchart TD
  A[0..7]
  A --> B[0..3]
  A --> C[4..7]
```

## Remember
- segment tree = divide ranges
- good for many queries + updates


Understand segment trees for fast range queries like sum and minimum, and build a simple tree from scratch.

Segment Tree Intro

Fenwick Tree supports:
- prefix sum queries
- point updates
in log time with simple code.

## Implementation
```python
class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)

    def add(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
```

## Usage
```python
fw = Fenwick(5)
fw.add(1, 5)
fw.add(3, 2)
print(fw.sum(3))  # 7
```

## Graph: prefix accumulation
```mermaid
flowchart LR
  A[Index] --> B[Jump using lowbit]
  B --> C[Accumulate]
```

## Remember
- simpler than segment tree
- great for prefix sums


Learn Fenwick Tree (Binary Indexed Tree) as a simpler structure for prefix sums and updates.

Fenwick Tree

In unweighted graphs, BFS gives shortest path.

## Example graph
```python
graph = {
  "A": ["B", "C"],
  "B": ["D"],
  "C": ["D"],
  "D": []
}
```

## BFS shortest path
```python
from collections import deque

def shortest(graph, start):
    q = deque([(start, 0)])
    seen = {start}
    while q:
        node, dist = q.popleft()
        if node == "D":
            return dist
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                q.append((nxt, dist+1))

print(shortest(graph, "A"))  # 2
```

## Graph
```mermaid
flowchart LR
  A --> B
  A --> C
  B --> D
  C --> D
```

## Remember
- BFS = shortest in unweighted graphs
- uses queue


Use BFS on graphs to find shortest paths in unweighted networks like grids, maps, and connections.

Shortest Path BFS

When edges have weights, use Dijkstra.

## Example graph
```python
graph = {
  "A": [("B", 1), ("C", 4)],
  "B": [("C", 2), ("D", 5)],
  "C": [("D", 1)],
  "D": []
}
```

## Dijkstra with heap
```python
import heapq

def dijkstra(g, start):
    dist = {start: 0}
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in g[u]:
            nd = d + w
            if v not in dist or nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

print(dijkstra(graph, "A"))
```

## Graph
```mermaid
flowchart LR
  A --1--> B
  A --4--> C
  B --2--> C
  C --1--> D
```

## Remember
- use heap for min distance
- works only with non-negative weights


Find shortest paths in weighted graphs using heaps, and understand why this powers GPS and routing systems.

Dijkstra Algorithm

Topological sort orders nodes so dependencies come first.

## Example: course prerequisites
```python
graph = {
  "A": ["C"],
  "B": ["C"],
  "C": ["D"],
  "D": []
}
```

## Kahn's algorithm
```python
from collections import deque, defaultdict

def topo(g):
    indeg = defaultdict(int)
    for u in g:
        for v in g[u]:
            indeg[v] += 1

    q = deque([u for u in g if indeg[u] == 0])
    order = []

    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order

print(topo(graph))
```

## Graph
```mermaid
flowchart LR
  A --> C
  B --> C
  C --> D
```

## Remember
- only for DAG (no cycles)
- used in scheduling and builds


Order tasks with dependencies using topological sort, useful for builds, courses, and workflows.

Topological Sort

Dynamic Programming (DP) = solve once, reuse many times.

## Fibonacci naive
```python
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
```

This repeats work.

## Memoized version
```python
def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]
```

## Graph
```mermaid
flowchart TD
  A[fib(5)] --> B[fib(4)]
  A --> C[fib(3)]
  B --> D[fib(3)]
  B --> E[fib(2)]
```

## Remember
- DP avoids recomputation
- memo = cache
- huge speedups


Understand dynamic programming as saving repeated work, with memoization and classic examples like Fibonacci.

Dynamic Programming Intro

Backtracking = try, explore, undo.

## Example: permutations
```python
def perm(nums):
    res = []

    def dfs(path, used):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            dfs(path, used)
            path.pop()
            used[i] = False

    dfs([], [False]*len(nums))
    return res

print(perm([1,2,3]))
```

## Graph
```mermaid
flowchart TD
  A[Start] --> B[Choose 1]
  B --> C[Choose 2]
  C --> D[Choose 3]
```

## Remember
- explore all paths
- undo after each try
- used in puzzles and search


Explore backtracking to try all possibilities safely, used in puzzles like permutations, subsets, and path finding.

Backtracking

Monotonic stack keeps elements in increasing or decreasing order.

## Problem: next greater element
```python
def next_greater(nums):
    st = []
    res = [-1]*len(nums)
    for i in range(len(nums)):
        while st and nums[i] > nums[st[-1]]:
            j = st.pop()
            res[j] = nums[i]
        st.append(i)
    return res

print(next_greater([2,1,2,4,3]))
```

## Graph
```mermaid
flowchart LR
  A[Stack] --> B[Keep order]
  B --> C[Pop when broken]
```

## Remember
- stack keeps monotonic order
- solves many range problems in O(n)


Use monotonic stacks to solve next greater/smaller problems efficiently in linear time.

Monotonic Stack

Sparse table answers range min queries fast after preprocessing.

## Idea
Precompute answers for ranges of length 2^k.

## Graph
```mermaid
flowchart TD
  A[Range 0..7]
  A --> B[0..3]
  A --> C[4..7]
```

## Remember
- preprocess once
- query in O(1)
- data must be static


Learn sparse tables for fast static range queries like RMQ when data never changes.

Sparse Table Concept

Bloom filter tells:
- item is definitely NOT present
- or MAYBE present

## Why useful
- huge datasets
- save memory

## Graph
```mermaid
flowchart LR
  A[Item] --> B[Hash1]
  A --> C[Hash2]
  B --> D[Bit array]
  C --> D
```

## Remember
- no false negatives
- possible false positives
- used in databases and caches


Understand bloom filters for memory-efficient membership checks with possible false positives.

Bloom Filter Concept

Intervals appear in:
- meetings
- bookings
- time ranges

## Merge intervals
```python
def merge(ints):
    ints.sort()
    res = [ints[0]]
    for s, e in ints[1:]:
        last = res[-1]
        if s <= last[1]:
            last[1] = max(last[1], e)
        else:
            res.append([s, e])
    return res

print(merge([[1,3],[2,6],[8,10]]))
```

## Graph
```mermaid
flowchart LR
  A[1-3] --> B[2-6]
  B --> C[Merged 1-6]
```

## Remember
- sort first
- then merge overlaps


Handle overlapping intervals using sorting and merging patterns, common in scheduling and timelines.

Interval Structures

You’ve now seen advanced structures and techniques.

## What you learned
- performance thinking
- trees, heaps, graphs
- caching and DP
- advanced patterns

## Big decision idea
```mermaid
flowchart TD
  A[Problem] --> B{Need speed?}
  B --> C[Heap / Cache]
  B --> D{Need ranges?}
  D --> E[Segment / Fenwick]
  D --> F{Need relations?}
  F --> G[Graph / DSU]
```

## Final advice
- start simple
- only use advanced tools when needed
- clarity beats cleverness

## Congratulations
You now understand **advanced data structures** and how to think like a problem solver.

Bring everything together: how to think about advanced data structures, trade-offs, and when to actually use them in real projects.

Advanced Structures Wrap-Up

This comprehensive guide covers 50 essential Data Structures interview questions that every developer should know. These questions cover fundamental data structures, their operations, time/space complexity, and when to use each structure commonly asked in technical interviews.

## Arrays & Lists

Arrays are fundamental data structures. These questions test your knowledge of array operations, dynamic arrays, and list implementations.

## Linked Lists

Linked lists provide dynamic memory allocation. Master these questions to demonstrate your understanding of singly/doubly linked lists, operations, and trade-offs.

## Stacks & Queues

Stacks and queues are linear data structures with specific access patterns. These questions cover LIFO/FIFO principles, implementations, and use cases.

## Trees & Binary Trees

Trees are hierarchical data structures. These questions cover binary trees, BST, AVL trees, traversals, and tree operations.

## Graphs & Hash Tables

Graphs represent relationships, hash tables provide fast lookups. These questions cover graph representations, traversal algorithms, and hash table implementations.

Comprehensive collection of 50 essential Data Structures interview questions covering arrays, linked lists, trees, graphs, hash tables, and algorithm complexity.

Data Structures Interview Questions: 50 Essential Questions for Developers

Arrays and linked lists are the foundation of data structures. Understanding them deeply helps you understand everything else. Let's learn when to use each and why it matters.

## Arrays Explained

Arrays store elements in contiguous memory. Accessing any element is instant (O(1)), but inserting or deleting in the middle is slow (O(n)). Arrays are perfect when you need fast random access.

## Linked Lists Explained

Linked lists store elements as nodes connected by pointers. Inserting or deleting is fast (O(1) at known position), but accessing elements is slow (O(n)). Linked lists are perfect when you do lots of insertions and deletions.

## When to Use Which?

Use arrays when you need fast access by index, know the size in advance, or need cache-friendly memory layout. Use linked lists when you do lots of insertions/deletions, size is unknown, or memory is fragmented.

## Time Complexity Comparison

I'll show you the time complexities for common operations - access, search, insertion, deletion. Understanding these helps you choose the right structure for your problem.

## Implementation Examples

I'll walk you through implementing both from scratch. Seeing how they work internally makes everything click.

Understand arrays and linked lists - the most fundamental data structures. Learn when to use arrays vs linked lists, their time complexities, and practical implementations. Essential knowledge for every developer.

Arrays and Linked Lists: Choosing the Right Structure

Stacks and queues are simple but powerful data structures. They restrict how you can access data, which makes them perfect for specific problems. Understanding them opens up many algorithm solutions.

## What is a Stack?

A stack follows LIFO (Last In First Out) - like a stack of plates. You add to the top and remove from the top. Think of the undo feature in editors - that's a stack.

## What is a Queue?

A queue follows FIFO (First In First Out) - like a line at a store. You add to the back and remove from the front. Think of print jobs or task scheduling - that's a queue.

## Common Operations

Both have simple operations: push/pop for stacks, enqueue/dequeue for queues. All operations are O(1) when implemented correctly. I'll show you how.

## Real-World Applications

Stacks are used for expression evaluation, undo/redo, function calls, and backtracking. Queues are used for task scheduling, BFS algorithms, and buffering. I'll show you practical examples.

## Implementation

I'll walk you through implementing both using arrays and linked lists. You'll see how simple they are and why they're so useful.

Master stacks and queues - two essential data structures. Learn LIFO (Last In First Out) and FIFO (First In First Out) principles, when to use each, and real-world applications. Used in countless algorithms.

Stacks and Queues: LIFO and FIFO Data Structures

Trees are everywhere in computer science - file systems, databases, decision trees, and more. Binary trees are the simplest and most important type. Understanding them is crucial for many algorithms.

## What is a Binary Tree?

A binary tree is a tree where each node has at most two children (left and right). It's hierarchical - perfect for representing relationships, decisions, or sorted data.

## Tree Traversal

There are three main ways to traverse a tree: in-order (left, root, right), pre-order (root, left, right), and post-order (left, right, root). Each has different uses. I'll show you when to use each.

## Binary Search Trees

BSTs are binary trees where left child < parent < right child. This makes searching, insertion, and deletion efficient (O(log n) in balanced trees). They're the foundation of many data structures.

## Real-World Applications

Trees are used in file systems, databases (B-trees), expression parsing, decision trees in ML, and hierarchical data. Understanding trees helps you understand these systems.

## Implementation

I'll walk you through building a binary tree and BST from scratch. You'll implement insertion, search, deletion, and traversal. This hands-on experience makes everything clear.

Master binary trees - one of the most important data structures. Learn tree traversal, binary search trees, and when to use trees. Essential for understanding databases, file systems, and many algorithms.

Binary Trees: Hierarchical Data Structures

Hash tables give you O(1) average time for insertions, deletions, and lookups. They're the fastest way to store and retrieve data by key. Understanding them is essential for building fast applications.

## What is a Hash Table?

A hash table stores key-value pairs. It uses a hash function to convert keys into array indices. This lets you access values instantly by key, without searching through the entire structure.

## How Hashing Works

A hash function takes a key and returns an index. Good hash functions distribute keys evenly and are fast to compute. I'll show you common hash functions and how to choose one.

## Handling Collisions

When two keys hash to the same index, you have a collision. Common solutions are chaining (linked list at each index) or open addressing (find next available slot). I'll explain both approaches.

## Time Complexity

Average case: O(1) for all operations. Worst case: O(n) if all keys hash to same index. Good hash functions and load factor management keep it close to O(1).

## Real-World Applications

Hash tables are used in databases (indexing), caches (Redis, Memcached), dictionaries, sets, and anywhere you need fast lookups. They're one of the most used data structures.

Master hash tables - the fastest data structure for lookups. Learn how hashing works, handle collisions, and when to use hash tables. Essential for understanding databases, caches, and high-performance systems.

Hash Tables: Fast Lookups and Key-Value Storage

Master fundamental data structures and their implementations.

Data Structures Resources

Browse Data Structures Content

Tutorials

Interview Questions

Practice Problems

Articles & Blog