Python Data Structures: Algorithms and Implementation

# This approach gets slower as your user base grows
user_emails = ['[email protected]', '[email protected]', ...]
if new_email in user_emails:  # Potentially checks every email
    return "Email already exists"

# This approach stays fast regardless of size
user_emails = {'[email protected]', '[email protected]', ...}
if new_email in user_emails:  # Direct hash lookup
    return "Email already exists"

# Gets slower as more users log in
logged_in_users = []
if user_id in logged_in_users:  # Linear search through every user
    show_dashboard()

# Stays fast regardless of user count
logged_in_users = set()
if user_id in logged_in_users:  # Direct hash lookup
    show_dashboard()

# Dangerous - can skip items
items = [1, 2, 3, 4, 5]
for item in items:
    if item % 2 == 0:
        items.remove(item)  # Changes list size during loop

# Safe approach
items = [1, 2, 3, 4, 5]
items = [item for item in items if item % 2 != 0]

# These point to the same list object
original = [1, 2, 3]
reference = original
copy = original[:]  # This creates a new list

original.append(4)
print(f"Original: {original}")    # [1, 2, 3, 4]
print(f"Reference: {reference}")  # [1, 2, 3, 4] - same object!
print(f"Copy: {copy}")           # [1, 2, 3] - different object

# This creates three references to the same inner list
matrix = [[0] * 3] * 3
matrix[0][0] = 1
print(matrix)  # [[1, 0, 0], [1, 0, 0], [1, 0, 0]] - all rows changed!

# This creates three separate inner lists
matrix = [[0] * 3 for _ in range(3)]
matrix[0][0] = 1
print(matrix)  # [[1, 0, 0], [0, 0, 0], [0, 0, 0]] - only first row changed

# Fast operations - happen instantly
my_list = [1, 2, 3, 4, 5]
item = my_list[2]        # Direct memory access
my_list.append(6)        # Add to pre-allocated space

# Slow operations - get slower with more data
my_list.insert(0, 0)     # Must shift all elements right
found = 4 in my_list     # Must search through elements

# Traditional approach
squares = []
for i in range(10):
    if i % 2 == 0:
        squares.append(i ** 2)

# List comprehension - cleaner and faster
squares = [i ** 2 for i in range(10) if i % 2 == 0]

users = ['[email protected]', '[email protected]', '[email protected]']
domains = [email.split('@')[1] for email in users]
# Result: ['gmail.com', 'yahoo.com', 'company.com']

data = list(range(100))

first_ten = data[:10]      # First 10 elements
last_ten = data[-10:]      # Last 10 elements
every_other = data[::2]    # Every second element
reversed_data = data[::-1] # Reverse the entire list

def rotate_left(lst, n):
    return lst[n:] + lst[:n]

numbers = [1, 2, 3, 4, 5]
rotated = rotate_left(numbers, 2)  # [3, 4, 5, 1, 2]

# Memory-hungry - creates entire list in memory
large_squares = [x**2 for x in range(1000000)]

# Memory-efficient - processes one item at a time
large_squares_gen = (x**2 for x in range(1000000))

# Use the generator to find what you need
for square in large_squares_gen:
    if square > 1000:
        print(f"First square > 1000: {square}")
        break

# Slow for membership testing
valid_ids = [1, 5, 10, 15, 20, 25, 30]
if user_id in valid_ids:  # Must check each ID until found
    process_user()

# Fast for membership testing
valid_ids = {1, 5, 10, 15, 20, 25, 30}
if user_id in valid_ids:  # Direct hash lookup
    process_user()

# Tuples can't be modified after creation
coordinates = (10, 20)
# coordinates[0] = 15  # TypeError: 'tuple' object does not support item assignment

# But they can contain mutable objects
data = ([1, 2, 3], {'name': 'Alice'})
data[0].append(4)  # This works - we're modifying the list inside the tuple
print(data)  # ([1, 2, 3, 4], {'name': 'Alice'})

# The tuple itself hasn't changed - it still contains the same objects
print(id(data[0]))  # Same memory address before and after append

# Truly immutable tuple (contains only immutable objects)
point = (10, 20)
config = ('localhost', 8080, True)

# Partially mutable tuple (contains mutable objects)
user_data = ('john', [25, 'engineer'], {'active': True})

# For hashability (dictionary keys), all elements must be immutable
try:
    cache = {user_data: 'some_value'}  # TypeError: unhashable type: 'list'
except TypeError as e:
    print(f"Error: {e}")

# This works because all elements are immutable
cache = {('john', 25, 'engineer'): 'some_value'}

# Parentheses are optional but recommended for clarity
point1 = 10, 20
point2 = (10, 20)

# Empty tuple
empty = ()
empty2 = tuple()

# Single-element tuple - comma is required!
single = (42,)  # Without comma, it's just parentheses around an integer
not_tuple = (42)  # This is just the integer 42

print(type(single))    # <class 'tuple'>
print(type(not_tuple)) # <class 'int'>

# Creating from iterables
list_data = [1, 2, 3, 4]
tuple_data = tuple(list_data)
print(tuple_data)  # (1, 2, 3, 4)

# Packing - multiple values into a tuple
person = 'Alice', 25, 'Engineer'  # Tuple packing

# Unpacking - tuple values into variables
name, age, job = person  # Tuple unpacking
print(f"{name} is {age} years old and works as an {job}")

# Partial unpacking with *
numbers = (1, 2, 3, 4, 5)
first, *middle, last = numbers
print(f"First: {first}, Middle: {middle}, Last: {last}")
# Output: First: 1, Middle: [2, 3, 4], Last: 5

# Swapping variables elegantly
a, b = 10, 20
a, b = b, a  # Swap using tuple unpacking
print(f"a: {a}, b: {b}")  # a: 20, b: 10

# Unpacking in function calls
def calculate_distance(x1, y1, x2, y2):
    return ((x2 - x1)**2 + (y2 - y1)**2)**0.5

point1 = (0, 0)
point2 = (3, 4)
distance = calculate_distance(*point1, *point2)
print(f"Distance: {distance}")  # Distance: 5.0

# Unpacking in loops
data = [('Alice', 25), ('Bob', 30), ('Charlie', 35)]
for name, age in data:
    print(f"{name}: {age}")

# Nested unpacking
nested_data = (('Alice', 'Engineer'), (25, 30))
(name, job), (current_age, target_age) = nested_data
print(f"{name} the {job} is {current_age}, wants to be promoted by {target_age}")

def analyze_text(text):
    words = text.split()
    word_count = len(words)
    char_count = len(text)
    avg_word_length = sum(len(word) for word in words) / word_count if words else 0
    
    return word_count, char_count, avg_word_length

# Clean unpacking of results
text = "Python is a powerful programming language"
word_count, char_count, avg_length = analyze_text(text)
print(f"Words: {word_count}, Characters: {char_count}, Avg length: {avg_length:.1f}")

# Or use as a single tuple
stats = analyze_text(text)
print(f"Text statistics: {stats}")

def get_user_stats(user_id):
    # Simulate database query
    return user_id, 'Alice', 150, 4.8  # id, name, posts, rating

def process_user(user_id):
    user_id, name, post_count, rating = get_user_stats(user_id)
    
    if post_count > 100 and rating > 4.5:
        return f"{name} is a power user!"
    elif post_count > 50:
        return f"{name} is an active user"
    else:
        return f"{name} is a new user"

print(process_user(123))

from collections import namedtuple

# Define a named tuple
Point = namedtuple('Point', ['x', 'y'])
Person = namedtuple('Person', ['name', 'age', 'email'])

# Create instances
origin = Point(0, 0)
user = Person('Alice', 25, '[email protected]')

# Access by name (more readable)
print(f"Point coordinates: ({origin.x}, {origin.y})")
print(f"User: {user.name}, Age: {user.age}")

# Access by index (still works)
print(f"First coordinate: {origin[0]}")

# Unpacking still works
x, y = origin
name, age, email = user

Person = namedtuple('Person', ['name', 'age', 'city'])
alice = Person('Alice', 25, 'New York')

# _replace() - create a new instance with some fields changed
older_alice = alice._replace(age=26)
print(older_alice)  # Person(name='Alice', age=26, city='New York')

# _asdict() - convert to dictionary
alice_dict = alice._asdict()
print(alice_dict)  # {'name': 'Alice', 'age': 25, 'city': 'New York'}

# _fields - get field names
print(Person._fields)  # ('name', 'age', 'city')

# _make() - create from iterable
data = ['Bob', 30, 'San Francisco']
bob = Person._make(data)
print(bob)  # Person(name='Bob', age=30, city='San Francisco')

Config = namedtuple('Config', ['host', 'port', 'debug', 'max_connections'])

# Immutable configuration
app_config = Config(
    host='localhost',
    port=8080,
    debug=True,
    max_connections=100
)

def start_server(config):
    print(f"Starting server on {config.host}:{config.port}")
    print(f"Debug mode: {config.debug}")
    print(f"Max connections: {config.max_connections}")

start_server(app_config)

Record = namedtuple('Record', ['timestamp', 'user_id', 'action', 'value'])

def process_logs(log_entries):
    records = []
    for entry in log_entries:
        # Parse log entry into structured data
        parts = entry.split(',')
        record = Record(
            timestamp=parts[0],
            user_id=int(parts[1]),
            action=parts[2],
            value=float(parts[3])
        )
        records.append(record)
    return records

# Sample log data
logs = [
    "2023-01-01T10:00:00,123,login,1.0",
    "2023-01-01T10:05:00,123,purchase,29.99",
    "2023-01-01T10:10:00,456,login,1.0"
]

records = process_logs(logs)
for record in records:
    print(f"User {record.user_id} performed {record.action} at {record.timestamp}")

import sys
import timeit

# Memory usage comparison
list_data = [1, 2, 3, 4, 5]
tuple_data = (1, 2, 3, 4, 5)

print(f"List size: {sys.getsizeof(list_data)} bytes")
print(f"Tuple size: {sys.getsizeof(tuple_data)} bytes")

# Creation time comparison
def create_list():
    return [1, 2, 3, 4, 5]

def create_tuple():
    return (1, 2, 3, 4, 5)

list_time = timeit.timeit(create_list, number=1000000)
tuple_time = timeit.timeit(create_tuple, number=1000000)

print(f"List creation: {list_time:.4f} seconds")
print(f"Tuple creation: {tuple_time:.4f} seconds")
print(f"Tuple creation is {list_time/tuple_time:.1f}x faster")

# Good tuple use cases
RGB_RED = (255, 0, 0)  # Color constants
ORIGIN = (0, 0)        # Fixed point
DATABASE_CONFIG = ('localhost', 5432, 'mydb')  # Configuration

# Good list use cases
shopping_cart = []     # Items will be added/removed
user_scores = [85, 92, 78]  # Scores might be updated
task_queue = []        # Tasks added and removed dynamically

# Cache function results based on multiple parameters
cache = {}

def expensive_calculation(x, y, z):
    key = (x, y, z)  # Tuple as cache key
    
    if key in cache:
        print(f"Cache hit for {key}")
        return cache[key]
    
    # Simulate expensive calculation
    result = x * y + z
    cache[key] = result
    print(f"Calculated {key} = {result}")
    return result

# Test caching
print(expensive_calculation(2, 3, 4))  # Calculated (2, 3, 4) = 10
print(expensive_calculation(2, 3, 4))  # Cache hit for (2, 3, 4)

# Simple state machine using tuples
State = namedtuple('State', ['name', 'allowed_transitions'])

# Define states
IDLE = State('idle', ['running', 'error'])
RUNNING = State('running', ['idle', 'paused', 'error'])
PAUSED = State('paused', ['running', 'idle'])
ERROR = State('error', ['idle'])

class StateMachine:
    def __init__(self, initial_state):
        self.current_state = initial_state
    
    def transition(self, new_state_name):
        if new_state_name in self.current_state.allowed_transitions:
            # Find the new state (in real code, you'd use a lookup dict)
            states = {'idle': IDLE, 'running': RUNNING, 'paused': PAUSED, 'error': ERROR}
            self.current_state = states[new_state_name]
            print(f"Transitioned to {new_state_name}")
        else:
            print(f"Invalid transition from {self.current_state.name} to {new_state_name}")

# Usage
machine = StateMachine(IDLE)
machine.transition('running')  # Valid
machine.transition('paused')   # Valid
machine.transition('idle')     # Valid
machine.transition('error')    # Valid from any state

# This lookup is nearly instant, regardless of dictionary size
user_ages = {'alice': 25, 'bob': 30, 'charlie': 35}
age = user_ages['alice']  # Direct hash lookup

# Compare with searching through a list of tuples
user_list = [('alice', 25), ('bob', 30), ('charlie', 35)]
for name, age in user_list:  # Must check each item
    if name == 'alice':
        break

# Literal syntax - clear and direct
config = {'host': 'localhost', 'port': 8080, 'debug': True}

# Dictionary comprehension - great for transforming data
squares = {x: x**2 for x in range(5)}  # {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

user_data = {'name': 'Alice', 'age': 25}

# Dangerous - raises KeyError if key doesn't exist
# email = user_data['email']  # KeyError!

# Safe - returns default value if key missing
email = user_data.get('email', '[email protected]')

# Transform a list of names to name lengths
names = ['Alice', 'Bob', 'Charlie']
name_lengths = {name: len(name) for name in names}
# Result: {'Alice': 5, 'Bob': 3, 'Charlie': 7}

# Filter and transform simultaneously
numbers = range(10)
even_squares = {x: x**2 for x in numbers if x % 2 == 0}
# Result: {0: 0, 2: 4, 4: 16, 6: 36, 8: 64}

from collections import defaultdict

# Traditional approach - verbose and error-prone
students = {}
for name, subject, grade in [('Alice', 'Math', 'A'), ('Alice', 'Science', 'B')]:
    if name not in students:
        students[name] = {}
    students[name][subject] = grade

# Cleaner with defaultdict
students = defaultdict(dict)
for name, subject, grade in [('Alice', 'Math', 'A'), ('Alice', 'Science', 'B')]:
    students[name][subject] = grade

def fibonacci_cached():
    cache = {}
    
    def fib(n):
        if n in cache:
            return cache[n]
        
        if n <= 1:
            result = n
        else:
            result = fib(n-1) + fib(n-2)
        
        cache[n] = result
        return result
    
    return fib

# This version is much faster for large numbers
fib = fibonacci_cached()
print(fib(10))  # Fast after first calculation

class Config:
    def __init__(self):
        self._config = {
            'database': {'host': 'localhost', 'port': 5432},
            'api': {'host': '0.0.0.0', 'port': 8080, 'debug': False}
        }
    
    def get(self, path, default=None):
        """Get config value using dot notation: 'database.host'"""
        keys = path.split('.')
        value = self._config
        
        for key in keys:
            if isinstance(value, dict) and key in value:
                value = value[key]
            else:
                return default
        return value

config = Config()
print(config.get('database.host'))  # 'localhost'

from collections import defaultdict, Counter

# defaultdict eliminates key existence checks
word_count = defaultdict(int)
for word in "the quick brown fox".split():
    word_count[word] += 1  # No need to check if key exists

# Counter makes frequency analysis trivial
text = "hello world"
char_count = Counter(text)
print(char_count.most_common(3))  # [('l', 3), ('o', 2), ('h', 1)]

# Dangerous - dictionary size changes during iteration
data = {'a': 1, 'b': 2, 'c': 3, 'd': 4}
# for key in data:  # Don't do this!
#     if data[key] % 2 == 0:
#         del data[key]

# Safe - iterate over copy of keys
for key in list(data.keys()):
    if data[key] % 2 == 0:
        del data[key]

# Creating sets is straightforward
fruits = {'apple', 'banana', 'orange'}
numbers = {1, 2, 3, 4, 5}

# Empty set requires set() - {} creates a dictionary!
empty_set = set()

# Convert any iterable to remove duplicates
list_data = [1, 2, 2, 3, 3, 3, 4]
unique_numbers = set(list_data)  # {1, 2, 3, 4} - duplicates gone

# With large datasets, the difference is dramatic
large_list = list(range(100000))
large_set = set(large_list)

# List: might check all 100,000 items
found = 99999 in large_list  # Slow

# Set: direct hash lookup
found = 99999 in large_set   # Fast

frontend_devs = {'alice', 'bob', 'charlie'}
backend_devs = {'bob', 'diana', 'eve'}

# All developers (no duplicates)
all_devs = frontend_devs | backend_devs
# Result: {'alice', 'bob', 'charlie', 'diana', 'eve'}

# Who works on both frontend and backend?
fullstack_devs = frontend_devs & backend_devs
# Result: {'bob'} - only bob appears in both sets

# Who only does frontend?
frontend_only = frontend_devs - backend_devs
# Result: {'alice', 'charlie'}

def deduplicate_preserve_order(items):
    seen = set()
    result = []
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result

# Remove duplicate user actions while keeping order
user_actions = ['login', 'view_page', 'login', 'purchase', 'view_page', 'logout']
unique_actions = deduplicate_preserve_order(user_actions)
# Result: ['login', 'view_page', 'purchase', 'logout']

ALLOWED_STATUSES = {'active', 'inactive', 'pending', 'suspended'}
ADMIN_ROLES = {'admin', 'superuser', 'moderator'}

def validate_user_data(user_data):
    errors = []
    
    # Check if status is valid
    if user_data.get('status') not in ALLOWED_STATUSES:
        errors.append(f"Invalid status: {user_data.get('status')}")
    
    # Check for invalid roles using set difference
    user_roles = set(user_data.get('roles', []))
    invalid_roles = user_roles - ADMIN_ROLES
    if invalid_roles:
        errors.append(f"Invalid roles: {invalid_roles}")
    
    return errors

# Extract unique skills from user data
data = [
    {'name': 'Alice', 'skills': ['python', 'javascript']},
    {'name': 'Bob', 'skills': ['python', 'java', 'go']},
    {'name': 'Charlie', 'skills': ['javascript', 'react', 'python']}
]

all_skills = {skill for person in data for skill in person['skills']}
# Result: {'python', 'javascript', 'java', 'go', 'react'}

# Use skill combinations as cache keys
job_cache = {
    frozenset(['python', 'web']): 'web_developer',
    frozenset(['python', 'data']): 'data_scientist',
    frozenset(['javascript', 'react']): 'frontend_developer'
}

# Look up job title by skills
skills = frozenset(['python', 'web'])
job_title = job_cache.get(skills, 'unknown')

from collections import deque

# Creating and using deques
queue = deque([1, 2, 3, 4, 5])

# Fast operations at both ends
queue.appendleft(0)    # Add to left
queue.append(6)        # Add to right
left_item = queue.popleft()   # Remove from left
right_item = queue.pop()      # Remove from right

def sliding_window_average(data, window_size):
    """Calculate moving average using deque's maxlen feature"""
    window = deque(maxlen=window_size)  # Automatically maintains size
    averages = []
    
    for value in data:
        window.append(value)
        if len(window) == window_size:
            averages.append(sum(window) / window_size)
    
    return averages

# Stock price moving average
prices = [100, 102, 98, 105, 107, 103, 99, 101, 104, 106]
moving_avg = sliding_window_average(prices, 3)
print(f"3-day moving averages: {moving_avg}")

def bfs_shortest_path(graph, start, end):
    """Find shortest path using BFS with deque"""
    queue = deque([(start, [start])])  # (node, path)
    visited = {start}
    
    while queue:
        node, path = queue.popleft()
        
        if node == end:
            return path
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # No path found

from collections import Counter

# Basic counting
text = "hello world"
char_count = Counter(text)
print(char_count.most_common(3))  # [('l', 3), ('o', 2), ('h', 1)]

# Count from any iterable
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
word_count = Counter(words)
print(word_count)  # Counter({'apple': 3, 'banana': 2, 'cherry': 1})

# Compare sales between quarters
sales_q1 = Counter({'laptops': 50, 'phones': 80, 'tablets': 30})
sales_q2 = Counter({'laptops': 60, 'phones': 70, 'tablets': 40, 'watches': 20})

# What's the total sales?
total_sales = sales_q1 + sales_q2

# How did sales change?
growth = sales_q2 - sales_q1
print(f"Growth Q1 to Q2: {growth}")

def analyze_web_logs(log_entries):
    """Analyze web server logs for patterns"""
    status_codes = Counter()
    ip_addresses = Counter()
    
    for entry in log_entries:
        # Simple parsing (in reality, you'd use regex)
        parts = entry.split(' ')
        if len(parts) > 8:
            ip = parts[0]
            status_code = parts[8]
            
            status_codes[status_code] += 1
            ip_addresses[ip] += 1
    
    return {
        'status_codes': status_codes,
        'top_ips': ip_addresses.most_common(5)
    }

# Sample log analysis
logs = [
    '192.168.1.1 - - [01/Jan/2023:12:00:00] "GET /" 200 1234',
    '192.168.1.2 - - [01/Jan/2023:12:01:00] "GET /api" 404 567',
    '192.168.1.1 - - [01/Jan/2023:12:02:00] "POST /login" 200 890'
]

analysis = analyze_web_logs(logs)
print("Most common status codes:", analysis['status_codes'].most_common())

from collections import defaultdict

# Traditional approach - verbose
regular_dict = {}
items = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']

for item in items:
    if item not in regular_dict:
        regular_dict[item] = 0
    regular_dict[item] += 1

# defaultdict approach - clean
count_dict = defaultdict(int)  # int() returns 0
for item in items:
    count_dict[item] += 1  # No need to check if key exists

# Group students by grade
students_by_grade = defaultdict(list)
students = [('Alice', 'A'), ('Bob', 'B'), ('Alice', 'A'), ('Charlie', 'B')]

for name, grade in students:
    students_by_grade[grade].append(name)

print(dict(students_by_grade))  # {'A': ['Alice', 'Alice'], 'B': ['Bob', 'Charlie']}

# Sales data by region and product
sales = defaultdict(lambda: defaultdict(int))

data = [
    ('North', 'laptops', 100),
    ('South', 'phones', 150),
    ('North', 'phones', 120),
    ('East', 'laptops', 80),
]

for region, product, amount in data:
    sales[region][product] += amount

# Convert to regular dict for display
result = {region: dict(products) for region, products in sales.items()}
print("Sales by region:", result)

from collections import OrderedDict

ordered = OrderedDict([('first', 1), ('second', 2), ('third', 3)])

# Move items around
ordered.move_to_end('first')  # Move to end
print(list(ordered.keys()))  # ['second', 'third', 'first']

# Pop items from specific ends
last_key, last_value = ordered.popitem(last=True)   # Remove from end
first_key, first_value = ordered.popitem(last=False) # Remove from beginning

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()
    
    def get(self, key):
        if key in self.cache:
            # Move to end (most recently used)
            self.cache.move_to_end(key)
            return self.cache[key]
        return None
    
    def put(self, key, value):
        if key in self.cache:
            self.cache[key] = value
            self.cache.move_to_end(key)
        else:
            if len(self.cache) >= self.capacity:
                # Remove least recently used
                self.cache.popitem(last=False)
            self.cache[key] = value

cache = LRUCache(3)
cache.put('a', 1)
cache.put('b', 2)
cache.put('c', 3)
cache.get('a')  # 'a' becomes most recently used
cache.put('d', 4)  # 'b' gets evicted (least recently used)

from collections import ChainMap

# Configuration with fallbacks
user_config = {'theme': 'dark', 'language': 'en'}
app_defaults = {'theme': 'light', 'language': 'en', 'debug': False, 'timeout': 30}

# ChainMap searches in order
config = ChainMap(user_config, app_defaults)
print(config['theme'])    # 'dark' - from user_config
print(config['timeout'])  # 30 - from app_defaults

# Updates go to first mapping
config['new_setting'] = 'value'
print(user_config)  # Now contains 'new_setting'

class SimpleContainer:
    def __init__(self, items=None):
        self._items = list(items) if items else []
    
    def __len__(self):
        return len(self._items)
    
    def __getitem__(self, index):
        return self._items[index]
    
    def __contains__(self, item):
        return item in self._items
    
    def __repr__(self):
        return f"SimpleContainer({self._items})"

# Usage - behaves like a built-in container
container = SimpleContainer([1, 2, 3, 4])
print(len(container))        # 4
print(container[1])          # 2
print(3 in container)        # True

class Stack:
    def __init__(self, max_size=None):
        self._items = []
        self._max_size = max_size
    
    def push(self, item):
        if self._max_size and len(self._items) >= self._max_size:
            raise OverflowError(f"Stack overflow: maximum size {self._max_size} reached")
        self._items.append(item)
    
    def pop(self):
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()
    
    def peek(self):
        if not self._items:
            raise IndexError("peek from empty stack")
        return self._items[-1]
    
    def is_empty(self):
        return len(self._items) == 0
    
    def __len__(self):
        return len(self._items)
    
    def __bool__(self):
        return bool(self._items)
    
    def __repr__(self):
        return f"Stack({self._items})"

# Usage
stack = Stack(max_size=3)
stack.push(1)
stack.push(2)
stack.push(3)
print(f"Top item: {stack.peek()}")  # 3
print(f"Stack size: {len(stack)}")  # 3

class NumberRange:
    """Custom range-like iterator with filtering"""
    
    def __init__(self, start, stop, step=1, filter_func=None):
        self.start = start
        self.stop = stop
        self.step = step
        self.filter_func = filter_func
    
    def __iter__(self):
        current = self.start
        while current < self.stop:
            if self.filter_func is None or self.filter_func(current):
                yield current
            current += self.step

# Usage
# Even numbers from 0 to 20
even_range = NumberRange(0, 21, 1, lambda x: x % 2 == 0)
print(list(even_range))  # [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

# Prime numbers (simple check)
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

prime_range = NumberRange(2, 30, 1, is_prime)
print(list(prime_range))  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word.lower():
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_word = True
    
    def search(self, word):
        node = self._find_node(word.lower())
        return node is not None and node.is_end_word
    
    def starts_with(self, prefix):
        return self._find_node(prefix.lower()) is not None
    
    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node
    
    def autocomplete(self, prefix, max_suggestions=10):
        node = self._find_node(prefix.lower())
        if node is None:
            return []
        
        suggestions = []
        self._collect_words(node, prefix.lower(), suggestions)
        return suggestions[:max_suggestions]
    
    def _collect_words(self, node, current_word, words):
        if node.is_end_word:
            words.append(current_word)
        
        for char, child_node in node.children.items():
            self._collect_words(child_node, current_word + char, words)

# Usage
trie = Trie()
words = ['apple', 'application', 'apply', 'appreciate', 'approach']
for word in words:
    trie.insert(word)

print(f"Contains 'apple': {'apple' in trie}")  # Need to implement __contains__
print(f"Starts with 'app': {trie.starts_with('app')}")
print(f"Autocomplete for 'app': {trie.autocomplete('app')}")

class Point:
    """Memory-efficient point class using __slots__"""
    __slots__ = ['x', 'y']
    
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def distance_to(self, other):
        return ((self.x - other.x)**2 + (self.y - other.y)**2)**0.5
    
    def __repr__(self):
        return f"Point({self.x}, {self.y})"

class PointCollection:
    """Memory-efficient collection of points"""
    
    def __init__(self):
        self._points = []
    
    def add_point(self, x, y):
        self._points.append(Point(x, y))
    
    def points_in_radius(self, center_x, center_y, radius):
        """Generator that yields points within radius"""
        center = Point(center_x, center_y)
        for point in self._points:
            if point.distance_to(center) <= radius:
                yield point
    
    def __len__(self):
        return len(self._points)
    
    def __iter__(self):
        return iter(self._points)

# Usage
collection = PointCollection()
collection.add_point(0, 0)
collection.add_point(3, 4)
collection.add_point(10, 10)

# Find points near origin
nearby_points = list(collection.points_in_radius(0, 0, 5))
print(f"Points within radius 5 of origin: {nearby_points}")

# Custom makes sense: specialized behavior
class BoundedList:
    """List that maintains a maximum size"""
    def __init__(self, max_size):
        self._items = []
        self._max_size = max_size
    
    def append(self, item):
        if len(self._items) >= self._max_size:
            self._items.pop(0)  # Remove oldest
        self._items.append(item)

# Built-in is better: standard behavior
def process_data(items):
    # Just use a regular list - no need for custom container
    return [item * 2 for item in items if item > 0]

# O(1) - Constant time: same speed regardless of data size
def get_first_item(data):
    return data[0] if data else None

# O(n) - Linear time: time increases proportionally with data size
def find_max(data):
    return max(data) if data else None

# O(n²) - Quadratic time: time increases exponentially with data size
def find_duplicates(data):
    duplicates = []
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] == data[j]:
                duplicates.append(data[i])
    return duplicates

import random

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    
    # Random pivot to avoid worst-case on sorted data
    pivot = arr[random.randint(0, len(arr) - 1)]
    
    # Partition around pivot
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    
    return quicksort(less) + equal + quicksort(greater)

# Test quicksort
test_data = [64, 34, 25, 12, 22, 11, 90]
print(f"Original: {test_data}")
print(f"Quicksort: {quicksort(test_data)}")

def insertion_sort(arr):
    arr = arr.copy()
    
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Move elements greater than key one position ahead
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr

# Test on nearly sorted data
nearly_sorted = [1, 2, 4, 3, 5, 6, 7, 8]
print(f"Nearly sorted insertion sort: {insertion_sort(nearly_sorted)}")

def counting_sort(arr, max_val=None):
    if not arr:
        return arr
    
    if max_val is None:
        max_val = max(arr)
    
    # Count occurrences
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    
    # Reconstruct sorted array
    result = []
    for i, freq in enumerate(count):
        result.extend([i] * freq)
    
    return result

# Perfect for sorting grades, ages, etc.
grades = [85, 92, 78, 96, 85, 88, 92, 79, 85, 90]
print(f"Sorted grades: {counting_sort(grades)}")

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # Not found

def find_insertion_point(arr, target):
    """Find where to insert target to maintain sorted order"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left

# Test binary search
sorted_data = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(f"Binary search for 7: index {binary_search(sorted_data, 7)}")
print(f"Insertion point for 8: index {find_insertion_point(sorted_data, 8)}")

from collections import deque

def bfs_shortest_path(graph, start, end):
    if start == end:
        return [start]
    
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        node, path = queue.popleft()
        
        for neighbor in graph.get(node, []):
            if neighbor == end:
                return path + [neighbor]
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # No path found

# Test graph algorithms
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

path = bfs_shortest_path(graph, 'A', 'F')
print(f"Shortest path A to F: {path}")

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    path = []
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            path.append(node)
            
            # Add neighbors to stack
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return path

print(f"DFS traversal: {dfs_iterative(graph, 'A')}")

def fibonacci_memoized():
    cache = {}
    
    def fib(n):
        if n in cache:
            return cache[n]
        
        if n <= 1:
            result = n
        else:
            result = fib(n - 1) + fib(n - 2)
        
        cache[n] = result
        return result
    
    return fib

# Compare performance
fib_memo = fibonacci_memoized()

# This is fast because we cache intermediate results
print(f"Fibonacci(35) = {fib_memo(35)}")

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []
        self.parent = None
    
    def add_child(self, child_node):
        child_node.parent = self
        self.children.append(child_node)
    
    def is_leaf(self):
        return len(self.children) == 0
    
    def get_level(self):
        level = 0
        current = self
        while current.parent:
            level += 1
            current = current.parent
        return level

# Build a simple organizational tree
root = TreeNode("CEO")
cto = TreeNode("CTO")
cfo = TreeNode("CFO")

root.add_child(cto)
root.add_child(cfo)

dev_manager = TreeNode("Dev Manager")
cto.add_child(dev_manager)

def traverse_preorder(node):
    """Visit root first, then children"""
    if node:
        print(node.value)
        for child in node.children:
            traverse_preorder(child)

def traverse_postorder(node):
    """Visit children first, then root"""
    if node:
        for child in node.children:
            traverse_postorder(child)
        print(node.value)

def traverse_level_order(root):
    """Visit nodes level by level"""
    from collections import deque
    if not root:
        return
    
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        queue.extend(node.children)

class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root_value=None):
        self.root = BinaryTreeNode(root_value) if root_value is not None else None
    
    def inorder_traversal(self, node=None):
        """Left -> Root -> Right"""
        if node is None:
            node = self.root
        
        result = []
        if node:
            result.extend(self.inorder_traversal(node.left))
            result.append(node.value)
            result.extend(self.inorder_traversal(node.right))
        
        return result
    
    def height(self, node=None):
        if node is None:
            node = self.root
        
        if not node:
            return -1
        
        left_height = self.height(node.left)
        right_height = self.height(node.right)
        
        return 1 + max(left_height, right_height)

# Build a binary tree
tree = BinaryTree(1)
tree.root.left = BinaryTreeNode(2)
tree.root.right = BinaryTreeNode(3)
tree.root.left.left = BinaryTreeNode(4)
tree.root.left.right = BinaryTreeNode(5)

print(f"Inorder: {tree.inorder_traversal()}")  # [4, 2, 5, 1, 3]
print(f"Height: {tree.height()}")              # 2

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if not self.root:
            self.root = BSTNode(value)
        else:
            self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = BSTNode(value)
            else:
                self._insert_recursive(node.left, value)
        elif value > node.value:
            if node.right is None:
                node.right = BSTNode(value)
            else:
                self._insert_recursive(node.right, value)
    
    def search(self, value):
        return self._search_recursive(self.root, value)
    
    def _search_recursive(self, node, value):
        if not node or node.value == value:
            return node
        
        if value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)
    
    def inorder(self):
        """Returns sorted list of values"""
        result = []
        self._inorder_recursive(self.root, result)
        return result
    
    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.value)
            self._inorder_recursive(node.right, result)

# Test BST
bst = BinarySearchTree()
values = [50, 30, 70, 20, 40, 60, 80]

for value in values:
    bst.insert(value)

print(f"Inorder traversal: {bst.inorder()}")  # [20, 30, 40, 50, 60, 70, 80] - sorted!
print(f"Search 40: {bst.search(40) is not None}")  # True

class FileSystemNode:
    def __init__(self, name, is_directory=False, size=0):
        self.name = name
        self.is_directory = is_directory
        self.children = [] if is_directory else None
        self.size = size
    
    def add_child(self, child):
        if not self.is_directory:
            raise ValueError("Cannot add child to file")
        self.children.append(child)
    
    def calculate_size(self):
        if not self.is_directory:
            return self.size
        
        return sum(child.calculate_size() for child in self.children)
    
    def find_files(self, pattern):
        import fnmatch
        results = []
        
        if not self.is_directory and fnmatch.fnmatch(self.name, pattern):
            results.append(self)
        
        if self.is_directory:
            for child in self.children:
                results.extend(child.find_files(pattern))
        
        return results

# Build file system
root = FileSystemNode("root", is_directory=True)
documents = FileSystemNode("documents", is_directory=True)
root.add_child(documents)

file1 = FileSystemNode("resume.pdf", size=1024)
file2 = FileSystemNode("notes.txt", size=512)
documents.add_child(file1)
documents.add_child(file2)

print(f"Total size: {root.calculate_size()} bytes")
pdf_files = root.find_files('*.pdf')
print(f"PDF files: {[f.name for f in pdf_files]}")

class DecisionNode:
    def __init__(self, question=None, true_branch=None, false_branch=None, result=None):
        self.question = question
        self.true_branch = true_branch
        self.false_branch = false_branch
        self.result = result  # For leaf nodes
    
    def is_leaf(self):
        return self.result is not None

def make_decision(node, data):
    if node.is_leaf():
        return node.result
    
    # Simple evaluation: check if data value meets condition
    if evaluate_condition(node.question, data):
        return make_decision(node.true_branch, data)
    else:
        return make_decision(node.false_branch, data)

def evaluate_condition(question, data):
    # Simplified: "income > 50000"
    parts = question.split()
    feature, operator, value = parts[0], parts[1], parts[2]
    
    if operator == '>':
        return data.get(feature, 0) > int(value)
    return False

# Build decision tree for loan approval
loan_tree = DecisionNode(
    question="income > 50000",
    true_branch=DecisionNode(result="Approved"),
    false_branch=DecisionNode(result="Rejected")
)

# Test decision
applicant = {"income": 60000, "credit_score": 750}
decision = make_decision(loan_tree, applicant)
print(f"Loan decision: {decision}")

class MinHeap:
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def peek(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        return self.heap[0]
    
    def size(self):
        return len(self.heap)

def insert(self, value):
    # Add to end of heap
    self.heap.append(value)
    # Bubble up to maintain heap property
    self._bubble_up(len(self.heap) - 1)

def _bubble_up(self, index):
    while (index > 0 and 
           self.heap[index] < self.heap[self.parent(index)]):
        self.swap(index, self.parent(index))
        index = self.parent(index)

# Add to MinHeap class
MinHeap.insert = insert
MinHeap._bubble_up = _bubble_up

def extract_min(self):
    if not self.heap:
        raise IndexError("Heap is empty")
    
    min_value = self.heap[0]
    # Move last element to root
    self.heap[0] = self.heap[-1]
    self.heap.pop()
    
    # Bubble down to maintain heap property
    if self.heap:
        self._bubble_down(0)
    
    return min_value

def _bubble_down(self, index):
    while self.left_child(index) < len(self.heap):
        smaller_child_index = self.left_child(index)
        
        # Find smaller child
        if (self.right_child(index) < len(self.heap) and 
            self.heap[self.right_child(index)] < self.heap[smaller_child_index]):
            smaller_child_index = self.right_child(index)
        
        # If heap property is satisfied, stop
        if self.heap[index] <= self.heap[smaller_child_index]:
            break
        
        self.swap(index, smaller_child_index)
        index = smaller_child_index

# Add to MinHeap class
MinHeap.extract_min = extract_min
MinHeap._bubble_down = _bubble_down

import heapq
from dataclasses import dataclass
from typing import Any

@dataclass
class PriorityItem:
    priority: int
    item: Any
    
    def __lt__(self, other):
        return self.priority < other.priority

class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._index = 0  # Tie-breaker for equal priorities
    
    def put(self, item, priority):
        heapq.heappush(self._heap, (priority, self._index, item))
        self._index += 1
    
    def get(self):
        if not self._heap:
            raise IndexError("Priority queue is empty")
        priority, index, item = heapq.heappop(self._heap)
        return item
    
    def empty(self):
        return len(self._heap) == 0

# Usage
pq = PriorityQueue()
pq.put("Low priority task", 10)
pq.put("High priority task", 1)
pq.put("Medium priority task", 5)

while not pq.empty():
    task = pq.get()
    print(f"Processing: {task}")

import time
from datetime import datetime, timedelta

@dataclass
class Task:
    name: str
    priority: int
    scheduled_time: datetime
    function: callable
    
    def __lt__(self, other):
        # First by scheduled time, then by priority
        if self.scheduled_time != other.scheduled_time:
            return self.scheduled_time < other.scheduled_time
        return self.priority < other.priority

class TaskScheduler:
    def __init__(self):
        self.task_heap = []
    
    def schedule_task(self, name, function, priority=5, delay_seconds=0):
        scheduled_time = datetime.now() + timedelta(seconds=delay_seconds)
        task = Task(name, priority, scheduled_time, function)
        heapq.heappush(self.task_heap, task)
    
    def run_pending_tasks(self):
        current_time = datetime.now()
        executed_tasks = []
        
        while (self.task_heap and 
               self.task_heap[0].scheduled_time <= current_time):
            task = heapq.heappop(self.task_heap)
            try:
                result = task.function()
                executed_tasks.append((task.name, result))
            except Exception as e:
                print(f"Error executing {task.name}: {e}")
        
        return executed_tasks

# Example usage
def send_email():
    return "Email sent"

def backup_database():
    return "Database backed up"

scheduler = TaskScheduler()
scheduler.schedule_task("Send email", send_email, priority=2, delay_seconds=1)
scheduler.schedule_task("Backup database", backup_database, priority=1, delay_seconds=2)

# Simulate running the scheduler
for i in range(3):
    executed = scheduler.run_pending_tasks()
    for task_name, result in executed:
        print(f"Completed: {task_name} -> {result}")
    time.sleep(1)

def find_k_largest(nums, k):
    """Find k largest elements using min-heap"""
    if k <= 0:
        return []
    
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[0]:  # num is larger than smallest in heap
            heapq.heapreplace(heap, num)
    
    return sorted(heap, reverse=True)

def find_k_smallest(nums, k):
    """Find k smallest elements using max-heap (negate values)"""
    if k <= 0:
        return []
    
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, -num)  # Negate for max-heap behavior
        elif num < -heap[0]:  # num is smaller than largest in heap
            heapq.heapreplace(heap, -num)
    
    return sorted([-x for x in heap])

# Test top K functions
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(f"3 largest: {find_k_largest(numbers, 3)}")
print(f"3 smallest: {find_k_smallest(numbers, 3)}")

def heap_sort(arr):
    """Sort array using heap sort algorithm"""
    def heapify(arr, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        if left < n and arr[left] > arr[largest]:
            largest = left
        
        if right < n and arr[right] > arr[largest]:
            largest = right
        
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)
    
    n = len(arr)
    
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements from heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # Move max to end
        heapify(arr, i, 0)  # Heapify reduced heap
    
    return arr

# Test heap sort
test_array = [64, 34, 25, 12, 22, 11, 90]
print(f"Original: {test_array}")
sorted_array = heap_sort(test_array.copy())
print(f"Heap sorted: {sorted_array}")

class Graph:
    def __init__(self, directed=False):
        self.directed = directed
        self.adjacency_list = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []
    
    def add_edge(self, vertex1, vertex2, weight=1):
        self.add_vertex(vertex1)
        self.add_vertex(vertex2)
        
        self.adjacency_list[vertex1].append((vertex2, weight))
        
        # If undirected, add reverse edge
        if not self.directed:
            self.adjacency_list[vertex2].append((vertex1, weight))
    
    def get_neighbors(self, vertex):
        return self.adjacency_list.get(vertex, [])

# Create a city network
graph = Graph(directed=False)
cities = ['New York', 'Los Angeles', 'Chicago', 'Houston']
connections = [
    ('New York', 'Chicago', 790),
    ('Los Angeles', 'Houston', 1550),
    ('Chicago', 'Houston', 1090)
]

for city in cities:
    graph.add_vertex(city)

for city1, city2, distance in connections:
    graph.add_edge(city1, city2, distance)

from collections import deque

def bfs_shortest_path(graph, start, end):
    if start == end:
        return [start]
    
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        node, path = queue.popleft()
        
        for neighbor, weight in graph.get_neighbors(node):
            if neighbor == end:
                return path + [neighbor]
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # No path found

def bfs_levels(graph, start_vertex):
    """BFS that returns vertices grouped by distance from start"""
    visited = set()
    queue = deque([(start_vertex, 0)])
    levels = {}
    
    while queue:
        vertex, level = queue.popleft()
        
        if vertex in visited:
            continue
        
        visited.add(vertex)
        
        if level not in levels:
            levels[level] = []
        levels[level].append(vertex)
        
        for neighbor, weight in graph.get_neighbors(vertex):
            if neighbor not in visited:
                queue.append((neighbor, level + 1))
    
    return levels

# Test BFS
path = bfs_shortest_path(graph, 'New York', 'Houston')
print(f"Shortest path: {path}")

levels = bfs_levels(graph, 'New York')
print(f"Vertices by distance: {levels}")

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    path = []
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            path.append(node)
            
            # Add neighbors to stack
            neighbors = [neighbor for neighbor, weight in graph.get_neighbors(node)]
            for neighbor in reversed(neighbors):  # Reverse for consistent order
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return path

def has_cycle_undirected(graph):
    """Detect cycle in undirected graph using DFS"""
    visited = set()
    
    def dfs_cycle_check(vertex, parent):
        visited.add(vertex)
        
        for neighbor, weight in graph.get_neighbors(vertex):
            if neighbor not in visited:
                if dfs_cycle_check(neighbor, vertex):
                    return True
            elif neighbor != parent:  # Back edge found
                return True
        
        return False
    
    for vertex in graph.adjacency_list:
        if vertex not in visited:
            if dfs_cycle_check(vertex, None):
                return True
    
    return False

print(f"DFS traversal: {dfs_iterative(graph, 'New York')}")
print(f"Graph has cycle: {has_cycle_undirected(graph)}")

import heapq

def dijkstra_shortest_path(graph, start_vertex):
    distances = {vertex: float('infinity') for vertex in graph.adjacency_list}
    previous = {vertex: None for vertex in graph.adjacency_list}
    distances[start_vertex] = 0
    
    # Priority queue: (distance, vertex)
    pq = [(0, start_vertex)]
    visited = set()
    
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        
        if current_vertex in visited:
            continue
        
        visited.add(current_vertex)
        
        for neighbor, weight in graph.get_neighbors(current_vertex):
            if neighbor not in visited:
                new_distance = current_distance + weight
                
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    previous[neighbor] = current_vertex
                    heapq.heappush(pq, (new_distance, neighbor))
    
    return distances, previous

def reconstruct_path(previous, start, end):
    path = []
    current = end
    
    while current is not None:
        path.append(current)
        current = previous[current]
    
    path.reverse()
    return path if path[0] == start else None

# Test Dijkstra's algorithm
distances, previous = dijkstra_shortest_path(graph, 'New York')

for city, distance in distances.items():
    if distance != float('infinity'):
        path = reconstruct_path(previous, 'New York', city)
        print(f"To {city}: {distance} miles, path: {' -> '.join(path)}")

class SocialNetwork:
    def __init__(self):
        self.graph = Graph(directed=False)
        self.user_data = {}
    
    def add_user(self, user_id, name, interests=None):
        self.graph.add_vertex(user_id)
        self.user_data[user_id] = {
            'name': name,
            'interests': interests or []
        }
    
    def add_friendship(self, user1, user2):
        self.graph.add_edge(user1, user2)
    
    def get_friends(self, user_id):
        return [friend for friend, weight in self.graph.get_neighbors(user_id)]
    
    def suggest_friends(self, user_id, max_suggestions=5):
        """Suggest friends based on mutual connections"""
        user_friends = set(self.get_friends(user_id))
        suggestions = {}
        
        # Look at friends of friends
        for friend in user_friends:
            for friend_of_friend, weight in self.graph.get_neighbors(friend):
                if (friend_of_friend != user_id and 
                    friend_of_friend not in user_friends):
                    
                    suggestions[friend_of_friend] = suggestions.get(friend_of_friend, 0) + 1
        
        # Sort by number of mutual connections
        sorted_suggestions = sorted(suggestions.items(), key=lambda x: x[1], reverse=True)
        return sorted_suggestions[:max_suggestions]
    
    def find_shortest_connection(self, user1, user2):
        return bfs_shortest_path(self.graph, user1, user2)

# Build social network
social_net = SocialNetwork()

users = [
    ('alice', 'Alice Johnson', ['reading', 'hiking']),
    ('bob', 'Bob Smith', ['gaming', 'programming']),
    ('charlie', 'Charlie Brown', ['music', 'hiking']),
    ('diana', 'Diana Prince', ['fitness', 'reading'])
]

for user_id, name, interests in users:
    social_net.add_user(user_id, name, interests)

friendships = [('alice', 'bob'), ('alice', 'charlie'), ('bob', 'diana')]
for user1, user2 in friendships:
    social_net.add_friendship(user1, user2)

print(f"Alice's friends: {social_net.get_friends('alice')}")
suggestions = social_net.suggest_friends('alice')
print(f"Friend suggestions for Alice: {suggestions}")