from collections import OrderedDict

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

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # mark as recently used
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)    # evict least recently used

cache = LRUCache(2)
cache.put("p1", "Phone"); cache.put("p2", "Laptop"); cache.get("p1"); cache.put("p3", "Watch")
print(list(cache.data))   # ['p1', 'p3'] — p2 was evicted

seen = set()
incoming = ["ORD1", "ORD2", "ORD1", "ORD3", "ORD2"]
for order_id in incoming:
    if order_id in seen:
        print("skip duplicate", order_id)
        continue
    seen.add(order_id)
    print("process", order_id)

import heapq

tickets = []
# (priority, arrival order, title) — lower number = more urgent
heapq.heappush(tickets, (2, 1, "Password reset"))
heapq.heappush(tickets, (1, 2, "Payment failing for all users"))
heapq.heappush(tickets, (3, 3, "Typo on About page"))

while tickets:
    priority, _, title = heapq.heappop(tickets)
    print(f"P{priority}: {title}")
# P1 first, then P2, then P3

history = []
text = ""
for action in ["Hello", " world", "!"]:
    history.append(text)
    text += action
print(text)            # Hello world!
text = history.pop()   # undo
print(text)            # Hello world

from collections import deque
jobs = deque(["email", "invoice", "report"])
print(jobs.popleft())  # email — first in, first out

import heapq

roads = {  # minutes between areas
    "Sector 18": {"Sector 62": 20, "Sector 15": 8},
    "Sector 15": {"Sector 62": 18, "Sector 18": 8},
    "Sector 62": {"Sector 18": 20, "Sector 15": 18},
}

def shortest(graph, start, goal):
    pq, best = [(0, start)], {start: 0}
    while pq:
        cost, node = heapq.heappop(pq)
        if node == goal:
            return cost
        for nxt, w in graph[node].items():
            new = cost + w
            if new < best.get(nxt, float("inf")):
                best[nxt] = new
                heapq.heappush(pq, (new, nxt))
    return None

print(shortest(roads, "Sector 18", "Sector 62"))   # 20

menu = {
    "Electronics": {"Mobiles": {}, "Laptops": {"Gaming": {}, "Office": {}}},
    "Books": {"Fiction": {}, "Programming": {}},
}

def walk(tree, depth=0):
    for name, children in tree.items():
        print("  " * depth + "- " + name)
        walk(children, depth + 1)

walk(menu)

Which data structure?
Need fast lookup by key            → hash map / dict
Need to check 'seen before?'       → set
Process in arrival order           → queue (deque)
Undo / backtracking                → stack
Always take the most urgent        → heap
Keep items sorted, range queries   → balanced tree / sorted structure / DB index
Model connections                  → graph

Explain a structure with a real example (interview)
1. The problem: 'We need the top 10 products by sales every hour.'
2. The structure: 'A min-heap of size 10.'
3. Why: 'Each insert is O(log 10); we never sort all products.'
4. Trade-off: 'Exact top 10 for one machine's data; at scale we'd aggregate first.'

DSA practice plan with real-world framing
Week A: arrays, strings, hash maps (dedup, counting, caching)
Week B: stacks and queues (undo, job processing)
Week C: heaps (top K, scheduling)
Week D: trees (traversals, BST)
Week E: graphs (BFS, Dijkstra)
For each problem, write one sentence: 'Where is this used in real software?'