Company-Specific Interview Patterns

# Google-Style Problem: Find All Valid Parentheses Expressions
# Tests mathematical thinking and optimization

class GoogleParenthesesSolver:
    def generate_parentheses(self, n: int) -> list[str]:
        """Generate all valid parentheses combinations - classic Google problem"""
        result = []
        
        def backtrack(current: str, open_count: int, close_count: int):
            # Base case: completed valid expression
            if len(current) == 2 * n:
                result.append(current)
                return
            
            # Add opening parenthesis if we haven't used all
            if open_count < n:
                backtrack(current + "(", open_count + 1, close_count)
            
            # Add closing parenthesis if it would create valid expression
            if close_count < open_count:
                backtrack(current + ")", open_count, close_count + 1)
        
        backtrack("", 0, 0)
        return result
    
    def is_valid_expression(self, s: str) -> bool:
        """Validate parentheses expression - often used as follow-up"""
        balance = 0
        for char in s:
            if char == '(':
                balance += 1
            elif char == ')':
                balance -= 1
                if balance < 0:  # More closing than opening so far
                    return False
        return balance == 0
    
    def min_additions_to_make_valid(self, s: str) -> int:
        """Google follow-up: minimum additions to make expression valid"""
        open_needed = 0  # Opening parentheses needed
        close_needed = 0  # Closing parentheses needed
        
        for char in s:
            if char == '(':
                open_needed += 1
            elif char == ')':
                if open_needed > 0:
                    open_needed -= 1  # Match with previous opening
                else:
                    close_needed += 1  # Need opening for this closing
        
        return open_needed + close_needed

# Google Example 3: Advanced Graph Problem - Course Scheduling with Prerequisites
from collections import defaultdict, deque
from typing import List, Dict, Set

class CourseScheduler:
    def can_finish_all_courses(self, num_courses: int, prerequisites: List[List[int]]) -> bool:
        """Topological sort to detect cycles - Google loves graph problems"""
        # Build adjacency list and in-degree count
        graph = defaultdict(list)
        in_degree = [0] * num_courses
        
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1
        
        # Initialize queue with courses that have no prerequisites
        queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
        completed_courses = 0
        
        while queue:
            course = queue.popleft()
            completed_courses += 1
            
            # Process all courses that depend on this course
            for dependent_course in graph[course]:
                in_degree[dependent_course] -= 1
                if in_degree[dependent_course] == 0:
                    queue.append(dependent_course)
        
        return completed_courses == num_courses
    
    def find_course_order(self, num_courses: int, prerequisites: List[List[int]]) -> List[int]:
        """Google follow-up: return the actual ordering"""
        graph = defaultdict(list)
        in_degree = [0] * num_courses
        
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1
        
        queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
        result = []
        
        while queue:
            course = queue.popleft()
            result.append(course)
            
            for dependent_course in graph[course]:
                in_degree[dependent_course] -= 1
                if in_degree[dependent_course] == 0:
                    queue.append(dependent_course)
        
        return result if len(result) == num_courses else []
    
    def min_semesters_to_graduate(self, num_courses: int, prerequisites: List[List[int]]) -> int:
        """Google optimization follow-up: minimum time to complete all courses"""
        graph = defaultdict(list)
        in_degree = [0] * num_courses
        
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1
        
        queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
        semesters = 0
        completed = 0
        
        while queue:
            semesters += 1
            semester_size = len(queue)
            
            # Process all courses available this semester
            for _ in range(semester_size):
                course = queue.popleft()
                completed += 1
                
                for dependent_course in graph[course]:
                    in_degree[dependent_course] -= 1
                    if in_degree[dependent_course] == 0:
                        queue.append(dependent_course)
        
        return semesters if completed == num_courses else -1

# Demonstration
def demonstrate_google_patterns():
    print("=== Google Algorithm Patterns Demo ===\n")
    
    # Pathfinding with optimization
    pathfinder = GridPathfinder()
    grid = [
        [0, 0, 0, 0],
        [0, 1, 1, 0],
        [0, 0, 0, 0],
        [1, 1, 0, 0]
    ]
    result = pathfinder.minStepsToTarget(grid, [0, 0], [3, 3])
    print(f"Minimum steps in grid: {result}")
    
    # Parentheses generation
    paren_solver = GoogleParenthesesSolver()
    expressions = paren_solver.generate_parentheses(3)
    print(f"Valid parentheses for n=3: {expressions}")
    
    # Course scheduling
    scheduler = CourseScheduler()
    prerequisites = [[1, 0], [2, 1], [3, 2]]
    can_finish = scheduler.can_finish_all_courses(4, prerequisites)
    print(f"Can finish all courses: {can_finish}")
    
    min_semesters = scheduler.min_semesters_to_graduate(4, prerequisites)
    print(f"Minimum semesters needed: {min_semesters}")