Practice Focus

# Problem Decomposition Example: Island Problems
# Shows how similar problems can be solved with pattern recognition

class IslandProblemSolver:
    """Demonstrates decomposition of various island-related problems"""
    
    def __init__(self):
        self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    # Problem 1: Number of Islands
    def num_islands(self, grid):
        """Count number of islands in grid"""
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        visited = [[False] * cols for _ in range(rows)]
        count = 0
        
        def dfs(r, c):
            if (r < 0 or r >= rows or c < 0 or c >= cols or
                visited[r][c] or grid[r][c] == '0'):
                return
            
            visited[r][c] = True
            for dr, dc in self.directions:
                dfs(r + dr, c + dc)
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1' and not visited[r][c]:
                    dfs(r, c)
                    count += 1
        
        return count
    
    # Problem 2: Max Area of Island
    def max_area_of_island(self, grid):
        """Find maximum area of any island"""
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        max_area = 0
        
        def dfs(r, c):
            if (r < 0 or r >= rows or c < 0 or c >= cols or
                grid[r][c] == 0):
                return 0
            
            grid[r][c] = 0  # Mark visited
            area = 1
            
            for dr, dc in self.directions:
                area += dfs(r + dr, c + dc)
            
            return area
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    max_area = max(max_area, dfs(r, c))
        
        return max_area
    
    # Problem 3: Island Perimeter
    def island_perimeter(self, grid):
        """Calculate perimeter of the island"""
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        perimeter = 0
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    # Check all 4 sides
                    for dr, dc in self.directions:
                        nr, nc = r + dr, c + dc
                        # Add to perimeter if edge or water
                        if (nr < 0 or nr >= rows or nc < 0 or nc >= cols or
                            grid[nr][nc] == 0):
                            perimeter += 1
        
        return perimeter
    
    # Problem 4: Surrounded Regions (capture problem)
    def solve_surrounded_regions(self, board):
        """Capture regions surrounded by 'X'"""
        if not board or not board[0]:
            return
        
        rows, cols = len(board), len(board[0])
        
        def dfs(r, c):
            if (r < 0 or r >= rows or c < 0 or c >= cols or
                board[r][c] != 'O'):
                return
            
            board[r][c] = 'E'  # Mark edge-connected
            
            for dr, dc in self.directions:
                dfs(r + dr, c + dc)
        
        # Mark edge-connected regions
        for r in range(rows):
            dfs(r, 0)
            dfs(r, cols - 1)
        
        for c in range(cols):
            dfs(0, c)
            dfs(rows - 1, c)
        
        # Capture surrounded regions
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
                elif board[r][c] == 'E':
                    board[r][c] = 'O'

# Complex Problem Decomposition: Meeting Scheduler
class MeetingScheduler:
    """Demonstrates decomposition of scheduling problems"""
    
    def find_meeting_time(self, calendars, meeting_duration):
        """
        Find common free time for meeting
        Decomposition:
        1. Merge individual calendars
        2. Find free slots
        3. Check duration constraint
        """
        # Step 1: Merge all busy times
        all_busy = []
        for calendar in calendars:
            all_busy.extend(calendar)
        
        # Step 2: Sort and merge overlapping intervals
        all_busy.sort()
        merged = []
        
        for start, end in all_busy:
            if not merged or merged[-1][1] < start:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)
        
        # Step 3: Find gaps of sufficient duration
        free_slots = []
        
        # Check before first meeting
        if merged and merged[0][0] >= meeting_duration:
            free_slots.append([0, merged[0][0]])
        
        # Check between meetings
        for i in range(1, len(merged)):
            gap_start = merged[i-1][1]
            gap_end = merged[i][0]
            if gap_end - gap_start >= meeting_duration:
                free_slots.append([gap_start, gap_end])
        
        # Check after last meeting (assuming day ends at 1440 minutes)
        if merged and 1440 - merged[-1][1] >= meeting_duration:
            free_slots.append([merged[-1][1], 1440])
        
        return free_slots
    
    def schedule_interviews(self, candidates, interviewers, duration):
        """
        Complex scheduling with multiple constraints
        Decomposition:
        1. Model as bipartite matching
        2. Apply constraints
        3. Optimize for preferences
        """
        from collections import defaultdict
        
        # Build availability graph
        graph = defaultdict(list)
        
        for candidate in candidates:
            for interviewer in interviewers:
                # Check if they have common available time
                common_slots = self.find_common_slots(
                    candidate['available'],
                    interviewer['available'],
                    duration
                )
                if common_slots:
                    graph[candidate['id']].append({
                        'interviewer': interviewer['id'],
                        'slots': common_slots,
                        'preference': candidate['preferences'].get(interviewer['id'], 0)
                    })
        
        # Use Hungarian algorithm or greedy matching
        assignments = self.match_interviews(graph, candidates, interviewers)
        
        return assignments
    
    def find_common_slots(self, slots1, slots2, duration):
        """Find overlapping time slots of sufficient duration"""
        common = []
        i = j = 0
        
        while i < len(slots1) and j < len(slots2):
            start = max(slots1[i][0], slots2[j][0])
            end = min(slots1[i][1], slots2[j][1])
            
            if end - start >= duration:
                common.append([start, end])
            
            if slots1[i][1] < slots2[j][1]:
                i += 1
            else:
                j += 1
        
        return common
                                

# Optimization Techniques Examples

import bisect
from collections import deque
import heapq

class OptimizationTechniques:
    """Collection of optimization techniques for common problems"""
    
    # Technique 1: Binary Search Optimization
    def search_in_rotated_array(self, nums, target):
        """Find target in rotated sorted array - O(log n)"""
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            
            if nums[mid] == target:
                return mid
            
            # Determine which half is sorted
            if nums[left] <= nums[mid]:
                # Left half is sorted
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                # Right half is sorted
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1
    
    # Technique 2: Monotonic Stack Optimization
    def next_greater_elements(self, nums):
        """Find next greater element for each element - O(n)"""
        n = len(nums)
        result = [-1] * n
        stack = []  # Monotonic decreasing stack
        
        # Process array twice for circular array
        for i in range(2 * n):
            while stack and nums[stack[-1]] < nums[i % n]:
                result[stack.pop()] = nums[i % n]
            
            if i < n:
                stack.append(i)
        
        return result
    
    # Technique 3: Sliding Window with Deque
    def max_sliding_window(self, nums, k):
        """Maximum in sliding window - O(n)"""
        if not nums:
            return []
        
        dq = deque()  # Store indices
        result = []
        
        for i in range(len(nums)):
            # Remove elements outside window
            while dq and dq[0] <= i - k:
                dq.popleft()
            
            # Remove smaller elements
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()
            
            dq.append(i)
            
            # Add to result after first window
            if i >= k - 1:
                result.append(nums[dq[0]])
        
        return result
    
    # Technique 4: Bucket Sort Optimization
    def top_k_frequent_bucket(self, nums, k):
        """Top K frequent elements using buckets - O(n)"""
        from collections import Counter
        
        count = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]
        
        # Group by frequency
        for num, freq in count.items():
            buckets[freq].append(num)
        
        # Collect top k
        result = []
        for i in range(len(buckets) - 1, -1, -1):
            result.extend(buckets[i])
            if len(result) >= k:
                return result[:k]
        
        return result
    
    # Technique 5: Matrix Optimization
    def search_2d_matrix(self, matrix, target):
        """Search in row and column sorted matrix - O(m + n)"""
        if not matrix or not matrix[0]:
            return False
        
        rows, cols = len(matrix), len(matrix[0])
        row, col = 0, cols - 1  # Start from top-right
        
        while row < rows and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1
            else:
                row += 1
        
        return False

# Advanced Caching Techniques
class LRUCache:
    """Least Recently Used Cache with O(1) operations"""
    
    class Node:
        def __init__(self, key=0, value=0):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> node
        self.head = self.Node()  # Dummy head
        self.tail = self.Node()  # Dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _add_to_head(self, node):
        """Add node right after head"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        """Remove node from list"""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
    
    def get(self, key):
        if key not in self.cache:
            return -1
        
        # Move to head (mark as recently used)
        node = self.cache[key]
        self._remove_node(node)
        self._add_to_head(node)
        
        return node.value
    
    def put(self, key, value):
        if key in self.cache:
            # Update existing
            node = self.cache[key]
            node.value = value
            self._remove_node(node)
            self._add_to_head(node)
        else:
            # Add new
            node = self.Node(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            
            if len(self.cache) > self.capacity:
                # Remove LRU
                lru = self.tail.prev
                self._remove_node(lru)
                del self.cache[lru.key]