Data Structures and Algorithms (DSA)

┌─────────────────────────────────────────────────────────────────────┐
│                     TWO SUM PATTERN WORKFLOW                        │
├─────────────────────────────────────────────────────────────────────┤
│                                                                     │
│  INPUT: nums = [2, 7, 11, 15], target = 9                          │
│                                                                     │
│  APPROACH 1: HASH MAP (O(n) TIME, O(n) SPACE)                      │
│  ┌───────────────────────────────────────────────────────────────┐ │
│  │  i=0: num=2, complement=7, seen={} → add 2 to seen            │ │
│  │  i=1: num=7, complement=2, seen={2:0} → FOUND! return [0,1]   │ │
│  └───────────────────────────────────────────────────────────────┘ │
│                                                                     │
│  APPROACH 2: TWO POINTERS (O(n log n) TIME, O(1) SPACE)            │
│  ┌───────────────────────────────────────────────────────────────┐ │
│  │  Sort: [2, 7, 11, 15]                                          │ │
│  │  L=0, R=3: sum=17 > 9 → R--                                    │ │
│  │  L=0, R=2: sum=13 > 9 → R--                                    │ │
│  │  L=0, R=1: sum=9 == 9 → FOUND! return [0,1]                   │ │
│  └───────────────────────────────────────────────────────────────┘ │
│                                                                     │
└─────────────────────────────────────────────────────────────────────┘

import numpy as np
from typing import List, Dict, Tuple, Optional
from dataclasses import dataclass
from enum import Enum
import time

class TwoSumStrategy(Enum):
    """Strategy for solving Two Sum problem"""
    HASH_MAP = "hash_map"
    TWO_POINTERS = "two_pointers"
    BRUTE_FORCE = "brute_force"

@dataclass
class TwoSumResult:
    """Result from Two Sum computation"""
    indices: Optional[Tuple[int, int]]
    values: Optional[Tuple[int, int]]
    time_ms: float
    strategy: TwoSumStrategy
    found: bool

class TwoSumSolver:
    """
    Production-quality Two Sum solver with multiple strategies.
    Used by Google for pair matching in distributed systems.
    """

    def __init__(self, strategy: TwoSumStrategy = TwoSumStrategy.HASH_MAP):
        self.strategy = strategy
        self.call_count = 0

    def solve(self, nums: List[int], target: int) -> TwoSumResult:
        """
        Find two numbers that sum to target.

        Args:
            nums: List of integers
            target: Target sum

        Returns:
            TwoSumResult with indices, values, timing
        """
        start = time.perf_counter()
        self.call_count += 1

        if self.strategy == TwoSumStrategy.HASH_MAP:
            indices = self._hash_map_approach(nums, target)
        elif self.strategy == TwoSumStrategy.TWO_POINTERS:
            indices = self._two_pointers_approach(nums, target)
        else:
            indices = self._brute_force_approach(nums, target)

        elapsed_ms = (time.perf_counter() - start) * 1000

        found = indices is not None
        values = (nums[indices[0]], nums[indices[1]]) if found else None

        return TwoSumResult(
            indices=indices,
            values=values,
            time_ms=elapsed_ms,
            strategy=self.strategy,
            found=found
        )

    def _hash_map_approach(self, nums: List[int], target: int) -> Optional[Tuple[int, int]]:
        """O(n) time, O(n) space - Industry standard"""
        seen: Dict[int, int] = {}

        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return (seen[complement], i)
            seen[num] = i

        return None

    def _two_pointers_approach(self, nums: List[int], target: int) -> Optional[Tuple[int, int]]:
        """O(n log n) time, O(n) space - For sorted or memory-constrained"""
        indexed_nums = [(num, i) for i, num in enumerate(nums)]
        indexed_nums.sort(key=lambda x: x[0])

        left, right = 0, len(indexed_nums) - 1

        while left < right:
            curr_sum = indexed_nums[left][0] + indexed_nums[right][0]
            if curr_sum == target:
                return (indexed_nums[left][1], indexed_nums[right][1])
            elif curr_sum < target:
                left += 1
            else:
                right -= 1

        return None

    def _brute_force_approach(self, nums: List[int], target: int) -> Optional[Tuple[int, int]]:
        """O(n²) time, O(1) space - For very small arrays"""
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return (i, j)
        return None

    def solve_all_pairs(self, nums: List[int], target: int) -> List[Tuple[int, int]]:
        """Find ALL pairs that sum to target (not just first one)"""
        seen: Dict[int, List[int]] = {}
        pairs = []

        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                for j in seen[complement]:
                    pairs.append((j, i))

            if num not in seen:
                seen[num] = []
            seen[num].append(i)

        return pairs

# Example 1: Google Search - Document Pair Matching
print("="*70)
print("GOOGLE - DOCUMENT SIMILARITY PAIR MATCHING")
print("="*70)
print("Scenario: Find pairs of documents with combined relevance score")
print()

# Document relevance scores
doc_scores = [23, 45, 12, 67, 34, 55, 78, 11]
target_relevance = 100

solver = TwoSumSolver(TwoSumStrategy.HASH_MAP)
result = solver.solve(doc_scores, target_relevance)

if result.found:
    print(f"✓ Found pair: Doc#{result.indices[0]} + Doc#{result.indices[1]}")
    print(f"  Scores: {result.values[0]} + {result.values[1]} = {target_relevance}")
    print(f"  Time: {result.time_ms:.4f}ms")
else:
    print("✗ No valid document pair found")

# Example 2: Amazon Inventory - Price Matching
print("\n" + "="*70)
print("AMAZON - PRICE PAIR MATCHING FOR DEALS")
print("="*70)
print("Scenario: Find two items that match customer's budget exactly")
print()

item_prices = [15, 25, 35, 45, 55, 65, 75, 85, 95]
budget = 100

result2 = solver.solve(item_prices, budget)

if result2.found:
    print(f"✓ Perfect deal found:")
    print(f"  Item A (${result2.values[0]}) + Item B (${result2.values[1]}) = ${budget}")
    print(f"  Indices: [{result2.indices[0]}, {result2.indices[1]}]")

# Example 3: All pairs scenario
print("\n" + "="*70)
print("META - FIND ALL USER PAIRS WITH TARGET CONNECTION STRENGTH")
print("="*70)

connection_scores = [10, 20, 30, 40, 50, 10, 40]
target_connection = 50

all_pairs = solver.solve_all_pairs(connection_scores, target_connection)
print(f"Target connection strength: {target_connection}")
print(f"Found {len(all_pairs)} pairs:")
for i, (idx1, idx2) in enumerate(all_pairs, 1):
    print(f"  Pair {i}: User#{idx1} ({connection_scores[idx1]}) + "
          f"User#{idx2} ({connection_scores[idx2]})")

┌──────────────────────────────────────────────────────────────────────┐
│              LINKED LIST REVERSAL PROCESS                            │
├──────────────────────────────────────────────────────────────────────┤
│                                                                      │
│  ORIGINAL:  1 → 2 → 3 → 4 → None                                    │
│                                                                      │
│  STEP 1: prev=None, curr=1                                           │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  None ← 1   2 → 3 → 4 → None                                   │ │
│  │         ↑   ↑                                                   │ │
│  │       prev curr                                                 │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                          ↓                                           │
│  STEP 2: prev=1, curr=2                                              │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  None ← 1 ← 2   3 → 4 → None                                   │ │
│  │             ↑   ↑                                               │ │
│  │           prev curr                                             │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                          ↓                                           │
│  STEP 3: prev=2, curr=3                                              │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  None ← 1 ← 2 ← 3   4 → None                                   │ │
│  │                 ↑   ↑                                           │ │
│  │               prev curr                                         │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                          ↓                                           │
│  FINAL:  None ← 1 ← 2 ← 3 ← 4                                       │
│                             ↑                                        │
│                           prev (new head)                           │
│                                                                      │
└──────────────────────────────────────────────────────────────────────┘

from typing import Optional, List, Tuple
from dataclasses import dataclass
import time

class ListNode:
    """Singly linked list node"""
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
        self.val = val
        self.next = next

    def __repr__(self) -> str:
        return f"Node({self.val})"

@dataclass
class ReversalMetrics:
    """Metrics from linked list reversal"""
    nodes_reversed: int
    time_ns: int
    approach: str
    memory_used: str

class LinkedListReverser:
    """
    Production linked list reversal with multiple approaches.
    Used by Amazon for order processing queue reversal.
    """

    def __init__(self):
        self.operations = 0

    def reverse_iterative(self, head: Optional[ListNode]) -> Tuple[Optional[ListNode], ReversalMetrics]:
        """
        Reverse linked list iteratively - O(n) time, O(1) space.
        Industry standard approach for production systems.

        Args:
            head: Head of linked list

        Returns:
            Tuple of (new_head, metrics)
        """
        start = time.perf_counter_ns()

        prev = None
        current = head
        nodes = 0

        while current:
            # Save next before we overwrite it
            next_node = current.next

            # Reverse the pointer
            current.next = prev

            # Move pointers forward
            prev = current
            current = next_node
            nodes += 1
            self.operations += 1

        elapsed = time.perf_counter_ns() - start

        metrics = ReversalMetrics(
            nodes_reversed=nodes,
            time_ns=elapsed,
            approach="iterative",
            memory_used="O(1) - constant space"
        )

        return prev, metrics

    def reverse_recursive(self, head: Optional[ListNode]) -> Tuple[Optional[ListNode], ReversalMetrics]:
        """
        Reverse linked list recursively - O(n) time, O(n) space.
        Elegant but uses call stack.

        Args:
            head: Head of linked list

        Returns:
            Tuple of (new_head, metrics)
        """
        start = time.perf_counter_ns()

        nodes_count = [0]  # Mutable to capture in nested function

        def reverse_helper(node: Optional[ListNode]) -> Optional[ListNode]:
            # Base case: empty list or last node
            if not node or not node.next:
                if node:
                    nodes_count[0] += 1
                return node

            # Recursively reverse rest of list
            new_head = reverse_helper(node.next)

            # Reverse the link
            node.next.next = node
            node.next = None
            nodes_count[0] += 1
            self.operations += 1

            return new_head

        result = reverse_helper(head)
        elapsed = time.perf_counter_ns() - start

        metrics = ReversalMetrics(
            nodes_reversed=nodes_count[0],
            time_ns=elapsed,
            approach="recursive",
            memory_used="O(n) - call stack"
        )

        return result, metrics

    def reverse_between(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        """
        Reverse linked list from position left to right (1-indexed).
        Advanced variant asked by Meta.
        """
        if not head or left == right:
            return head

        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        # Move to node before reversal start
        for _ in range(left - 1):
            prev = prev.next

        # Reverse from left to right
        current = prev.next
        for _ in range(right - left):
            next_node = current.next
            current.next = next_node.next
            next_node.next = prev.next
            prev.next = next_node

        return dummy.next

def create_linked_list(values: List[int]) -> Optional[ListNode]:
    """Helper to create linked list from array"""
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

def print_linked_list(head: Optional[ListNode]) -> str:
    """Helper to print linked list"""
    values = []
    while head:
        values.append(str(head.val))
        head = head.next
    return " → ".join(values) + " → None"

# Example 1: Amazon Order Processing Queue
print("="*70)
print("AMAZON - REVERSE ORDER PROCESSING QUEUE")
print("="*70)
print("Scenario: Reverse priority queue for LIFO processing\n")

orders = create_linked_list([101, 102, 103, 104, 105])
reverser = LinkedListReverser()

print(f"Original order queue: {print_linked_list(orders)}")

reversed_orders, metrics = reverser.reverse_iterative(orders)

print(f"Reversed queue: {print_linked_list(reversed_orders)}")
print(f"✓ Reversed {metrics.nodes_reversed} orders in {metrics.time_ns:,}ns")
print(f"  Approach: {metrics.approach}")
print(f"  Memory: {metrics.memory_used}")

# Example 2: Meta - Undo Operation Stack
print("\n" + "="*70)
print("META - UNDO OPERATION HISTORY REVERSAL")
print("="*70)
print("Scenario: Reverse user action history for undo functionality\n")

actions = create_linked_list([1, 2, 3, 4, 5, 6])
print(f"Action history: {print_linked_list(actions)}")

# Using recursive approach
reversed_actions, metrics2 = reverser.reverse_recursive(actions)

print(f"Reversed history: {print_linked_list(reversed_actions)}")
print(f"✓ Reversed {metrics2.nodes_reversed} actions in {metrics2.time_ns:,}ns")
print(f"  Memory overhead: {metrics2.memory_used}")

# Example 3: Google - Partial Reversal
print("\n" + "="*70)
print("GOOGLE - REVERSE SUBLIST (POSITIONS 2-5)")
print("="*70)

data = create_linked_list([1, 2, 3, 4, 5, 6, 7])
print(f"Original: {print_linked_list(data)}")

result = reverser.reverse_between(data, 2, 5)
print(f"After reversing positions 2-5: {print_linked_list(result)}")
print("Expected: 1 → 5 → 4 → 3 → 2 → 6 → 7 → None")

┌──────────────────────────────────────────────────────────────────────┐
│                  PARENTHESES VALIDATION WITH STACK                   │
├──────────────────────────────────────────────────────────────────────┤
│                                                                      │
│  INPUT: "{[()]}"                                                     │
│                                                                      │
│  STEP 1: char='{', opening → push to stack                           │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  Stack: ['{']                                                   │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                          ↓                                           │
│  STEP 2: char='[', opening → push to stack                           │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  Stack: ['{', '[']                                              │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                          ↓                                           │
│  STEP 3: char='(', opening → push to stack                           │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  Stack: ['{', '[', '(']                                         │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                          ↓                                           │
│  STEP 4: char=')', closing → matches '(' → pop                      │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  Stack: ['{', '[']                                              │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                          ↓                                           │
│  STEP 5: char=']', closing → matches '[' → pop                      │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  Stack: ['{']                                                   │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                          ↓                                           │
│  STEP 6: char='}', closing → matches '{' → pop                      │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  Stack: []  ✓ VALID (empty stack at end)                       │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                                                                      │
└──────────────────────────────────────────────────────────────────────┘

from typing import Dict, List, Optional, Set
from dataclasses import dataclass
import time

@dataclass
class ValidationResult:
    """Result from bracket validation"""
    is_valid: bool
    error_position: Optional[int]
    error_char: Optional[str]
    unmatched_stack: List[str]
    time_ns: int

class ParenthesesValidator:
    """
    Production bracket validation system.
    Used by Google's code parsers and Amazon's JSON validators.
    """

    def __init__(self, allow_angle_brackets: bool = False):
        self.bracket_pairs = {
            ')': '(',
            ']': '[',
            '}': '{'
        }
        if allow_angle_brackets:
            self.bracket_pairs['>'] = '<'

        self.opening_brackets = set(self.bracket_pairs.values())
        self.closing_brackets = set(self.bracket_pairs.keys())
        self.validations = 0

    def is_valid(self, s: str) -> ValidationResult:
        """
        Validate if bracket string is properly balanced.

        Args:
            s: String containing brackets

        Returns:
            ValidationResult with validation details
        """
        start = time.perf_counter_ns()
        self.validations += 1

        stack = []

        for i, char in enumerate(s):
            if char in self.opening_brackets:
                # Opening bracket - push to stack
                stack.append(char)

            elif char in self.closing_brackets:
                # Closing bracket - must match top of stack
                if not stack:
                    # Closing bracket with no opening
                    elapsed = time.perf_counter_ns() - start
                    return ValidationResult(
                        is_valid=False,
                        error_position=i,
                        error_char=char,
                        unmatched_stack=[],
                        time_ns=elapsed
                    )

                if stack[-1] != self.bracket_pairs[char]:
                    # Mismatched brackets
                    elapsed = time.perf_counter_ns() - start
                    return ValidationResult(
                        is_valid=False,
                        error_position=i,
                        error_char=char,
                        unmatched_stack=stack.copy(),
                        time_ns=elapsed
                    )

                stack.pop()

        elapsed = time.perf_counter_ns() - start

        # Valid only if stack is empty
        return ValidationResult(
            is_valid=len(stack) == 0,
            error_position=None if len(stack) == 0 else len(s),
            error_char=None,
            unmatched_stack=stack.copy(),
            time_ns=elapsed
        )

    def longest_valid_parentheses(self, s: str) -> int:
        """
        Find length of longest valid parentheses substring.
        Advanced variant asked by Meta.
        """
        stack = [-1]  # Initialize with -1 for edge case
        max_length = 0

        for i, char in enumerate(s):
            if char == '(':
                stack.append(i)
            else:  # char == ')'
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_length = max(max_length, i - stack[-1])

        return max_length

    def min_remove_to_make_valid(self, s: str) -> str:
        """
        Remove minimum brackets to make valid.
        Asked by Amazon for string processing.
        """
        stack = []
        to_remove = set()

        # Find all invalid brackets
        for i, char in enumerate(s):
            if char == '(':
                stack.append(i)
            elif char == ')':
                if stack:
                    stack.pop()
                else:
                    to_remove.add(i)

        # Remaining opening brackets are also invalid
        to_remove.update(stack)

        # Build result without invalid brackets
        return ''.join(char for i, char in enumerate(s) if i not in to_remove)

# Example 1: Google - Code Parser Validation
print("="*70)
print("GOOGLE - CODE SYNTAX VALIDATION")
print("="*70)
print("Scenario: Validate bracket syntax in code compilation\n")

validator = ParenthesesValidator()

test_cases = [
    ("()[]{}",  "Valid nested brackets"),
    ("([)]",    "Interleaved invalid"),
    ("{[]}",    "Properly nested"),
    ("((()))",  "Multiple nesting"),
    ("({[",     "Unclosed brackets"),
]

for code, description in test_cases:
    result = validator.is_valid(code)
    status = "✓ VALID" if result.is_valid else "✗ INVALID"
    print(f"{status}: '{code}' - {description}")
    if not result.is_valid:
        print(f"  Error at position {result.error_position}")
        if result.unmatched_stack:
            print(f"  Unmatched: {result.unmatched_stack}")
    print(f"  Validation time: {result.time_ns}ns\n")

# Example 2: Amazon - JSON Validation
print("="*70)
print("AMAZON - JSON BRACKET VALIDATION")
print("="*70)
print("Scenario: Validate JSON structure for API responses\n")

json_samples = [
    ('{\"key\": [1, 2, {\"nested\": true}]}', True),
    ('{\"key\": [1, 2, 3}', False),  # Missing ]
    ('[[[{{{}}}]]]', True),
    ('{}[]', True),
]

for json_str, expected in json_samples:
    # Extract only brackets for validation
    brackets = ''.join(c for c in json_str if c in '()[]{}')
    result = validator.is_valid(brackets)
    match = "✓" if result.is_valid == expected else "✗"
    print(f"{match} JSON: {json_str}")
    print(f"  Brackets: {brackets} → {'Valid' if result.is_valid else 'Invalid'}\n")

# Example 3: Meta - Longest Valid Substring
print("="*70)
print("META - LONGEST VALID PARENTHESES SUBSTRING")
print("="*70)

test_strings = [
    "(()",
    ")()())",
    "()(())",
    "((())())"
]

for s in test_strings:
    length = validator.longest_valid_parentheses(s)
    print(f"String: '{s}' → Longest valid length: {length}")

# Example 4: Amazon - Minimum Removals
print("\n" + "="*70)
print("AMAZON - MINIMUM BRACKET REMOVAL")
print("="*70)

invalid_strings = [
    "lee(t(c)o)de)",
    "a)b(c)d",
    "))((",
    "(a(b(c)d)"
]

for s in invalid_strings:
    fixed = validator.min_remove_to_make_valid(s)
    print(f"Original: '{s}'")
    print(f"Fixed:    '{fixed}'\n")

┌──────────────────────────────────────────────────────────────────────┐
│                   BINARY SEARCH DIVIDE & CONQUER                     │
├──────────────────────────────────────────────────────────────────────┤
│                                                                      │
│  INPUT: nums = [1, 3, 5, 7, 9, 11, 13, 15], target = 9              │
│                                                                      │
│  ITERATION 1:                                                        │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  L=0, R=7, mid=3 → nums[3]=7 < 9                               │ │
│  │  [1, 3, 5, 7 | 9, 11, 13, 15]  → Search right half             │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                          ↓                                           │
│  ITERATION 2:                                                        │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  L=4, R=7, mid=5 → nums[5]=11 > 9                              │ │
│  │  [9 | 11, 13, 15]  → Search left half                          │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                          ↓                                           │
│  ITERATION 3:                                                        │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  L=4, R=4, mid=4 → nums[4]=9 == 9  ✓ FOUND!                    │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                                                                      │
│  TIME: O(log n) - cuts search space in half each iteration          │
│                                                                      │
└──────────────────────────────────────────────────────────────────────┘

import numpy as np
from typing import List, Optional, Tuple, Callable
from dataclasses import dataclass
from enum import Enum
import time

class SearchVariant(Enum):
    """Binary search variants"""
    EXACT = "exact"           # Find exact match
    LOWER_BOUND = "lower"     # First element >= target
    UPPER_BOUND = "upper"     # Last element <= target
    LEFTMOST = "leftmost"     # Leftmost occurrence
    RIGHTMOST = "rightmost"   # Rightmost occurrence

@dataclass
class SearchResult:
    """Result from binary search"""
    index: int
    found: bool
    comparisons: int
    time_ns: int
    variant: SearchVariant

class BinarySearchEngine:
    """
    Production binary search with all variants.
    Used by Google for searching 100B+ sorted documents.
    """

    def __init__(self):
        self.total_searches = 0
        self.total_comparisons = 0

    def search(self, nums: List[int], target: int, 
              variant: SearchVariant = SearchVariant.EXACT) -> SearchResult:
        """
        Universal binary search supporting all variants.

        Args:
            nums: Sorted array
            target: Element to find
            variant: Type of search (exact, bounds, etc.)

        Returns:
            SearchResult with index, found status, metrics
        """
        start = time.perf_counter_ns()
        self.total_searches += 1

        if variant == SearchVariant.EXACT:
            idx, comps = self._exact_search(nums, target)
            found = idx != -1
        elif variant == SearchVariant.LOWER_BOUND:
            idx, comps = self._lower_bound(nums, target)
            found = idx < len(nums) and nums[idx] >= target
        elif variant == SearchVariant.UPPER_BOUND:
            idx, comps = self._upper_bound(nums, target)
            found = idx >= 0 and nums[idx] <= target
        elif variant == SearchVariant.LEFTMOST:
            idx, comps = self._leftmost_occurrence(nums, target)
            found = idx != -1
        else:  # RIGHTMOST
            idx, comps = self._rightmost_occurrence(nums, target)
            found = idx != -1

        elapsed_ns = time.perf_counter_ns() - start
        self.total_comparisons += comps

        return SearchResult(
            index=idx,
            found=found,
            comparisons=comps,
            time_ns=elapsed_ns,
            variant=variant
        )

    def _exact_search(self, nums: List[int], target: int) -> Tuple[int, int]:
        """Standard binary search - O(log n)"""
        left, right = 0, len(nums) - 1
        comparisons = 0

        while left <= right:
            mid = left + (right - left) // 2  # Avoid overflow
            comparisons += 1

            if nums[mid] == target:
                return mid, comparisons
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1, comparisons

    def _lower_bound(self, nums: List[int], target: int) -> Tuple[int, int]:
        """First element >= target (insertion point)"""
        left, right = 0, len(nums)
        comparisons = 0

        while left < right:
            mid = left + (right - left) // 2
            comparisons += 1

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid

        return left, comparisons

    def _upper_bound(self, nums: List[int], target: int) -> Tuple[int, int]:
        """Last element <= target"""
        left, right = -1, len(nums) - 1
        comparisons = 0

        while left < right:
            mid = left + (right - left + 1) // 2
            comparisons += 1

            if nums[mid] <= target:
                left = mid
            else:
                right = mid - 1

        return left, comparisons

    def _leftmost_occurrence(self, nums: List[int], target: int) -> Tuple[int, int]:
        """Leftmost index where target occurs (handles duplicates)"""
        left, right = 0, len(nums) - 1
        result = -1
        comparisons = 0

        while left <= right:
            mid = left + (right - left) // 2
            comparisons += 1

            if nums[mid] == target:
                result = mid
                right = mid - 1  # Keep searching left
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return result, comparisons

    def _rightmost_occurrence(self, nums: List[int], target: int) -> Tuple[int, int]:
        """Rightmost index where target occurs"""
        left, right = 0, len(nums) - 1
        result = -1
        comparisons = 0

        while left <= right:
            mid = left + (right - left) // 2
            comparisons += 1

            if nums[mid] == target:
                result = mid
                left = mid + 1  # Keep searching right
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return result, comparisons

    def search_rotated(self, nums: List[int], target: int) -> int:
        """Binary search in rotated sorted array - O(log n)"""
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid

            # Determine which half is sorted
            if nums[left] <= nums[mid]:  # Left half sorted
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:  # Right half sorted
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

# Example 1: Google - Search in 100 billion sorted documents
print("="*70)
print("GOOGLE - DOCUMENT ID SEARCH IN SORTED INDEX")
print("="*70)
print("Scenario: Find document in sorted index of 100B documents")
print()

# Simulating billion-scale search with scaled example
doc_ids = list(range(0, 1000000, 7))  # 142,857 documents
target_doc = 700007

engine = BinarySearchEngine()
result = engine.search(doc_ids, target_doc, SearchVariant.EXACT)

print(f"Search for document ID: {target_doc}")
if result.found:
    print(f"✓ Found at index: {result.index}")
    print(f"  Comparisons: {result.comparisons} (log₂({len(doc_ids)}) ≈ {np.log2(len(doc_ids)):.1f})")
    print(f"  Time: {result.time_ns:,}ns = {result.time_ns/1000:.2f}μs")
    print(f"  Extrapolated for 100B docs: ~{27 * 40}ns = {27 * 40/1000:.1f}μs")
else:
    print(f"✗ Document not found (checked {result.comparisons} positions)")

# Example 2: Amazon - Price range queries for products
print("\n" + "="*70)
print("AMAZON - PRODUCT PRICE RANGE QUERIES")
print("="*70)
print("Scenario: Find products within budget using lower/upper bounds")
print()

product_prices = [10, 25, 25, 40, 40, 40, 55, 70, 70, 85, 100]
min_budget, max_budget = 40, 70

lower_result = engine.search(product_prices, min_budget, SearchVariant.LOWER_BOUND)
upper_result = engine.search(product_prices, max_budget, SearchVariant.UPPER_BOUND)

print(f"Budget range: ${min_budget} - ${max_budget}")
print(f"✓ Products in range: indices [{lower_result.index}:{upper_result.index + 1}]")
print(f"  Prices: {product_prices[lower_result.index:upper_result.index + 1]}")
print(f"  Total comparisons: {lower_result.comparisons + upper_result.comparisons}")

# Example 3: Netflix - Find viewing timestamp in sorted logs
print("\n" + "="*70)
print("NETFLIX - VIDEO PLAYBACK TIMESTAMP SEARCH")
print("="*70)
print("Scenario: Find first/last occurrence in duplicate timestamps")
print()

timestamps = [100, 150, 200, 200, 200, 250, 300, 350]
target_time = 200

left_result = engine.search(timestamps, target_time, SearchVariant.LEFTMOST)
right_result = engine.search(timestamps, target_time, SearchVariant.RIGHTMOST)

print(f"Target timestamp: {target_time}ms")
print(f"✓ First occurrence: index {left_result.index} ({left_result.comparisons} comparisons)")
print(f"✓ Last occurrence: index {right_result.index} ({right_result.comparisons} comparisons)")
print(f"✓ Total occurrences: {right_result.index - left_result.index + 1}")

# Example 4: Rotated array search
print("\n" + "="*70)
print("GOOGLE - SEARCH IN ROTATED SORTED ARRAY")
print("="*70)

rotated = [15, 18, 2, 3, 6, 12]
target = 6
idx = engine.search_rotated(rotated, target)
print(f"Rotated array: {rotated}")
print(f"Target {target} found at index: {idx}")

┌──────────────────────────────────────────────────────────────────────┐
│              KADANE'S ALGORITHM - EXTEND OR RESTART                  │
├──────────────────────────────────────────────────────────────────────┤
│                                                                      │
│  INPUT: [-2, 1, -3, 4, -1, 2, 1, -5, 4]                             │
│                                                                      │
│  KEY DECISION AT EACH ELEMENT:                                       │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  current_sum = max(nums[i], current_sum + nums[i])             │ │
│  │                     ↑              ↑                            │ │
│  │                  RESTART        EXTEND                          │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                                                                      │
│  ITERATION TRACE:                                                    │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  i=0: [-2]        curr=-2,  max=-2   (start)                   │ │
│  │  i=1: [1]         curr=1,   max=1    (restart better)          │ │
│  │  i=2: [1,-3]      curr=-2,  max=1    (extend, still negative)  │ │
│  │  i=3: [4]         curr=4,   max=4    (restart better)          │ │
│  │  i=4: [4,-1]      curr=3,   max=4    (extend, profit down)     │ │
│  │  i=5: [4,-1,2]    curr=5,   max=5    (extend, profit up!)      │ │
│  │  i=6: [4,-1,2,1]  curr=6,   max=6    (extend, profit up!)      │ │
│  │  i=7: [...,-5]    curr=1,   max=6    (extend, profit down)     │ │
│  │  i=8: [...,4]     curr=5,   max=6    (extend)                  │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                                                                      │
│  RESULT: max_sum = 6, subarray = [4, -1, 2, 1]                     │
│                                                                      │
└──────────────────────────────────────────────────────────────────────┘

import numpy as np
from typing import List, Tuple, Dict
from dataclasses import dataclass
from enum import Enum
import time

class SubarrayStrategy(Enum):
    """Strategy for finding maximum subarray"""
    KADANE = "kadane"
    DIVIDE_CONQUER = "divide_conquer"
    BRUTE_FORCE = "brute_force"

@dataclass
class SubarrayResult:
    """Result from maximum subarray computation"""
    max_sum: float
    start_index: int
    end_index: int
    subarray: List[int]
    time_ns: int
    strategy: SubarrayStrategy

class MaximumSubarrayFinder:
    """
    Production maximum subarray solver with multiple strategies.
    Used by Netflix for viewing pattern analysis.
    """

    def __init__(self):
        self.computations = 0

    def find_max_subarray(self, nums: List[int], 
                        strategy: SubarrayStrategy = SubarrayStrategy.KADANE) -> SubarrayResult:
        """
        Find maximum subarray using specified strategy.

        Args:
            nums: Input array
            strategy: Algorithm to use

        Returns:
            SubarrayResult with max sum, indices, timing
        """
        start = time.perf_counter_ns()
        self.computations += 1

        if strategy == SubarrayStrategy.KADANE:
            max_sum, start_idx, end_idx = self._kadane_algorithm(nums)
        elif strategy == SubarrayStrategy.DIVIDE_CONQUER:
            max_sum, start_idx, end_idx = self._divide_and_conquer(nums, 0, len(nums) - 1)
        else:
            max_sum, start_idx, end_idx = self._brute_force(nums)

        elapsed = time.perf_counter_ns() - start

        return SubarrayResult(
            max_sum=max_sum,
            start_index=start_idx,
            end_index=end_idx,
            subarray=nums[start_idx:end_idx + 1],
            time_ns=elapsed,
            strategy=strategy
        )

    def _kadane_algorithm(self, nums: List[int]) -> Tuple[float, int, int]:
        """
        Kadane's algorithm - O(n) time, O(1) space.
        Industry standard for production systems.
        """
        max_sum = current_sum = nums[0]
        start = end = temp_start = 0

        for i in range(1, len(nums)):
            # Key decision: extend or restart?
            if nums[i] > current_sum + nums[i]:
                current_sum = nums[i]
                temp_start = i
            else:
                current_sum += nums[i]

            # Update global maximum
            if current_sum > max_sum:
                max_sum = current_sum
                start = temp_start
                end = i

        return max_sum, start, end

    def _divide_and_conquer(self, nums: List[int], left: int, right: int) -> Tuple[float, int, int]:
        """
        Divide and conquer - O(n log n) time, O(log n) space.
        """
        if left == right:
            return nums[left], left, right

        mid = (left + right) // 2

        # Find max in left half
        left_max, left_start, left_end = self._divide_and_conquer(nums, left, mid)

        # Find max in right half
        right_max, right_start, right_end = self._divide_and_conquer(nums, mid + 1, right)

        # Find max crossing middle
        cross_max, cross_start, cross_end = self._max_crossing_subarray(nums, left, mid, right)

        # Return maximum of three
        if left_max >= right_max and left_max >= cross_max:
            return left_max, left_start, left_end
        elif right_max >= left_max and right_max >= cross_max:
            return right_max, right_start, right_end
        else:
            return cross_max, cross_start, cross_end

    def _max_crossing_subarray(self, nums: List[int], left: int, mid: int, right: int) -> Tuple[float, int, int]:
        """Helper for divide and conquer - find max crossing mid"""
        # Find max sum in left half ending at mid
        left_sum = float('-inf')
        current_sum = 0
        max_left = mid

        for i in range(mid, left - 1, -1):
            current_sum += nums[i]
            if current_sum > left_sum:
                left_sum = current_sum
                max_left = i

        # Find max sum in right half starting at mid+1
        right_sum = float('-inf')
        current_sum = 0
        max_right = mid + 1

        for i in range(mid + 1, right + 1):
            current_sum += nums[i]
            if current_sum > right_sum:
                right_sum = current_sum
                max_right = i

        return left_sum + right_sum, max_left, max_right

    def _brute_force(self, nums: List[int]) -> Tuple[float, int, int]:
        """Brute force - O(n²) time, O(1) space"""
        n = len(nums)
        max_sum = float('-inf')
        start = end = 0

        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += nums[j]
                if current_sum > max_sum:
                    max_sum = current_sum
                    start = i
                    end = j

        return max_sum, start, end

    def find_k_maximum_subarrays(self, nums: List[int], k: int) -> List[Tuple[float, int, int]]:
        """
        Find k non-overlapping maximum subarrays.
        Advanced variant for Netflix multi-segment analysis.
        """
        results = []
        remaining = nums.copy()

        for _ in range(k):
            if not remaining:
                break

            max_sum, start, end = self._kadane_algorithm(remaining)
            results.append((max_sum, start, end))

            # Remove found subarray (simplified approach)
            if max_sum <= 0:
                break

            # Mark used elements as very negative
            for i in range(start, end + 1):
                remaining[i] = float('-inf')

        return results

# Example 1: Netflix - Viewing Pattern Analysis
print("="*70)
print("NETFLIX - USER ENGAGEMENT PATTERN ANALYSIS")
print("="*70)
print("Scenario: Find period with highest viewer engagement\n")

# Daily engagement scores (positive = above average, negative = below)
engagement_scores = [-2, 1, -3, 4, -1, 2, 1, -5, 4, 3, -2, 5]

finder = MaximumSubarrayFinder()
result = finder.find_max_subarray(engagement_scores, SubarrayStrategy.KADANE)

print(f"Engagement scores: {engagement_scores}")
print(f"✓ Best engagement period: Days {result.start_index} to {result.end_index}")
print(f"  Subarray: {result.subarray}")
print(f"  Total engagement gain: {result.max_sum}")
print(f"  Computation time: {result.time_ns:,}ns")
print(f"  Strategy: {result.strategy.value}")

# Example 2: Google - Stock Price Analysis
print("\n" + "="*70)
print("GOOGLE - STOCK PRICE CHANGE ANALYSIS")
print("="*70)
print("Scenario: Find period with maximum cumulative price change\n")

# Daily price changes
price_changes = [3, -2, 5, -1, 2, -4, 3, 1, -2, 4]

result2 = finder.find_max_subarray(price_changes, SubarrayStrategy.KADANE)

print(f"Price changes: {price_changes}")
print(f"✓ Best trading period: Days {result2.start_index} to {result2.end_index}")
print(f"  Changes: {result2.subarray}")
print(f"  Maximum profit: ${result2.max_sum}")

# Example 3: Algorithm Comparison
print("\n" + "="*70)
print("ALGORITHM PERFORMANCE COMPARISON")
print("="*70)

test_array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

strategies = [
    SubarrayStrategy.KADANE,
    SubarrayStrategy.DIVIDE_CONQUER,
    SubarrayStrategy.BRUTE_FORCE
]

for strat in strategies:
    result = finder.find_max_subarray(test_array, strat)
    print(f"\n{strat.value.upper()}:")
    print(f"  Max sum: {result.max_sum}")
    print(f"  Subarray: {result.subarray}")
    print(f"  Time: {result.time_ns:,}ns")

# Example 4: Amazon - Warehouse Efficiency Analysis
print("\n" + "="*70)
print("AMAZON - WAREHOUSE EFFICIENCY ANALYSIS")
print("="*70)
print("Scenario: Find period with maximum operational efficiency\n")

# Efficiency scores (positive = efficient, negative = inefficient)
efficiency = [2, -1, 3, -4, 5, 1, -2, 6, -3, 2]

result3 = finder.find_max_subarray(efficiency, SubarrayStrategy.KADANE)

print(f"Efficiency scores: {efficiency}")
print(f"✓ Peak efficiency: Days {result3.start_index} to {result3.end_index}")
print(f"  Scores: {result3.subarray}")
print(f"  Total efficiency gain: {result3.max_sum}")

# Example 5: Find multiple non-overlapping segments
print("\n" + "="*70)
print("NETFLIX - TOP 3 ENGAGEMENT PERIODS")
print("="*70)

top_k = finder.find_k_maximum_subarrays(engagement_scores, 3)

for i, (sum_val, start, end) in enumerate(top_k, 1):
    print(f"Period {i}: Days {start}-{end}, Engagement: {sum_val}")

def merge_two_lists(l1, l2):
    """Merge two sorted linked lists"""
    dummy = ListNode(0)
    current = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # Attach remaining nodes
    current.next = l1 if l1 else l2

    return dummy.next

def merge_two_lists_recursive(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1

    if l1.val <= l2.val:
        l1.next = merge_two_lists_recursive(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_lists_recursive(l1, l2.next)
        return l2

┌──────────────────────────────────────────────────────────────────────┐
│                    LRU CACHE ARCHITECTURE                            │
├──────────────────────────────────────────────────────────────────────┤
│                                                                      │
│  HASH MAP + DOUBLY LINKED LIST = O(1) OPERATIONS                    │
│                                                                      │
│  Hash Map (key → node):                                              │
│  ┌────────────────────────────────────────────────────────────────┐ │
│  │  key1 → [Node*]    key2 → [Node*]    key3 → [Node*]           │ │
│  │           ↓                ↓                ↓                   │ │
│  └───────────┼────────────────┼────────────────┼─────────────────┘ │
│              │                │                │                     │
│  Doubly Linked List (LRU → MRU):                                    │
│  ┌──────────┼────────────────┼────────────────┼─────────────────┐ │
│  │         ↓                ↓                ↓                   │ │
│  │  HEAD ⇄ [Node1] ⇄ [Node2] ⇄ [Node3] ⇄ TAIL                   │ │
│  │         (LRU)                       (MRU)                      │ │
│  └────────────────────────────────────────────────────────────────┘ │
│                                                                      │
│  GET(key): Hash lookup O(1) + Move to end O(1) = O(1)               │
│  PUT(key): Hash insert O(1) + Add to end O(1) = O(1)                │
│  Evict: Remove from head O(1)                                        │
│                                                                      │
└──────────────────────────────────────────────────────────────────────┘

from typing import Optional, Dict, Any
from dataclasses import dataclass
from collections import OrderedDict
import time

class DLLNode:
    """Doubly Linked List Node for LRU Cache"""
    def __init__(self, key: int, value: Any):
        self.key = key
        self.value = value
        self.prev: Optional['DLLNode'] = None
        self.next: Optional['DLLNode'] = None

@dataclass
class CacheMetrics:
    """Metrics for cache performance"""
    hits: int = 0
    misses: int = 0
    evictions: int = 0
    total_gets: int = 0
    total_puts: int = 0

    @property
    def hit_rate(self) -> float:
        return self.hits / self.total_gets if self.total_gets > 0 else 0.0

class LRUCache:
    """
    Production LRU Cache with O(1) operations.
    Used by Redis, Memcached, CDN systems.
    """

    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("Capacity must be positive")

        self.capacity = capacity
        self.cache: Dict[int, DLLNode] = {}
        self.metrics = CacheMetrics()

        # Dummy head and tail for cleaner code
        self.head = DLLNode(0, 0)
        self.tail = DLLNode(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        """
        Get value from cache, move to most recently used.
        O(1) time complexity.
        """
        self.metrics.total_gets += 1

        if key not in self.cache:
            self.metrics.misses += 1
            return -1

        self.metrics.hits += 1
        node = self.cache[key]

        # Move accessed node to end (most recently used)
        self._remove(node)
        self._add_to_end(node)

        return node.value

    def put(self, key: int, value: Any) -> None:
        """
        Put key-value pair in cache.
        O(1) time complexity.
        """
        self.metrics.total_puts += 1

        # If key exists, remove old node
        if key in self.cache:
            self._remove(self.cache[key])

        # Create new node and add to end (MRU)
        node = DLLNode(key, value)
        self._add_to_end(node)
        self.cache[key] = node

        # Evict LRU if over capacity
        if len(self.cache) > self.capacity:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]
            self.metrics.evictions += 1

    def _remove(self, node: DLLNode) -> None:
        """Remove node from doubly linked list - O(1)"""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add_to_end(self, node: DLLNode) -> None:
        """Add node before tail (most recently used) - O(1)"""
        prev_node = self.tail.prev
        prev_node.next = node
        node.prev = prev_node
        node.next = self.tail
        self.tail.prev = node

    def size(self) -> int:
        """Current cache size"""
        return len(self.cache)

    def clear(self) -> None:
        """Clear all cache entries"""
        self.cache.clear()
        self.head.next = self.tail
        self.tail.prev = self.head

class LRUCacheOrderedDict:
    """
    Alternative implementation using OrderedDict.
    Simpler but less educational for interviews.
    """

    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = 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: Any) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # Remove oldest

# Example 1: Redis-style Web Cache
print("="*70)
print("REDIS - WEB PAGE CACHING SYSTEM")
print("="*70)
print("Scenario: Cache frequently accessed web pages\n")

cache = LRUCache(capacity=3)

# Simulate web page requests
print("PUT page1 (Homepage)")
cache.put(1, "Homepage Content")

print("PUT page2 (About)")
cache.put(2, "About Page Content")

print("PUT page3 (Products)")
cache.put(3, "Products Page Content")

print(f"\nCache size: {cache.size()}/{cache.capacity}")

print("\nGET page1:", "HIT" if cache.get(1) != -1 else "MISS")
print("GET page2:", "HIT" if cache.get(2) != -1 else "MISS")

print("\nPUT page4 (Contact) - triggers eviction of LRU")
cache.put(4, "Contact Page Content")

print("GET page3:", "HIT" if cache.get(3) != -1 else "MISS (evicted)")

print(f"\nCache Metrics:")
print(f"  Hits: {cache.metrics.hits}")
print(f"  Misses: {cache.metrics.misses}")
print(f"  Hit Rate: {cache.metrics.hit_rate:.1%}")
print(f"  Evictions: {cache.metrics.evictions}")

# Example 2: CDN Content Cache
print("\n" + "="*70)
print("CLOUDFLARE - CDN CONTENT DELIVERY CACHE")
print("="*70)
print("Scenario: Cache static assets with limited memory\n")

cdn_cache = LRUCache(capacity=5)

# Simulate asset requests
assets = [
    (101, "logo.png", 100),
    (102, "style.css", 150),
    (103, "app.js", 200),
    (104, "banner.jpg", 120),
    (105, "font.woff", 80),
]

for asset_id, name, size_kb in assets:
    cdn_cache.put(asset_id, (name, size_kb))
    print(f"Cached: {name} ({size_kb}KB)")

print("\nAccessing popular assets:")
popular = [101, 102, 101, 103, 102]  # logo and style accessed frequently
for asset_id in popular:
    result = cdn_cache.get(asset_id)
    if result != -1:
        name, size = result
        print(f"  GET {name}: HIT")

print(f"\nCDN Cache Stats:")
print(f"  Total Requests: {cdn_cache.metrics.total_gets}")
print(f"  Hit Rate: {cdn_cache.metrics.hit_rate:.1%}")
print(f"  Cache Efficiency: {'EXCELLENT' if cdn_cache.metrics.hit_rate > 0.8 else 'GOOD'}")

# Example 3: Database Query Cache
print("\n" + "="*70)
print("AMAZON - DATABASE QUERY RESULT CACHE")
print("="*70)
print("Scenario: Cache expensive database queries\n")

db_cache = LRUCache(capacity=4)

# Simulate query caching
queries = [
    ("SELECT * FROM users WHERE id=1", "User1 Data"),
    ("SELECT * FROM orders WHERE user_id=1", "Orders List"),
    ("SELECT * FROM products WHERE category='tech'", "Tech Products"),
    ("SELECT * FROM reviews WHERE product_id=5", "Product Reviews"),
]

for i, (query, result) in enumerate(queries, 1):
    db_cache.put(i, {"query": query, "result": result, "cached_at": time.time()})
    print(f"Cached Query {i}")

# Access pattern showing LRU in action
print("\nQuery Access Pattern:")
access_pattern = [1, 2, 3, 1, 4, 2, 5]  # Query 5 is new, will evict LRU

for query_id in access_pattern:
    if query_id <= 4:
        result = db_cache.get(query_id)
        print(f"  Query {query_id}: {'HIT' if result != -1 else 'MISS'}")
    else:
        print(f"  Query {query_id}: NEW (adding to cache)")
        db_cache.put(query_id, {"query": "New Query", "result": "New Result"})

print(f"\nDatabase Cache Performance:")
print(f"  Queries Cached: {db_cache.size()}")
print(f"  Evictions: {db_cache.metrics.evictions}")
print(f"  Hit Rate: {db_cache.metrics.hit_rate:.1%}")