Interview Excellence

from typing import List, Dict, Any
import time

# Problem: Two Sum - Multiple approaches with trade-off analysis

def two_sum_brute_force(nums: List[int], target: int) -> List[int]:
    """Approach 1: Brute Force - O(n²) time, O(1) space"""
    # "Let me start with the most straightforward approach..."
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

def two_sum_hash_map(nums: List[int], target: int) -> List[int]:
    """Approach 2: Hash Map - O(n) time, O(n) space"""
    # "Now let me optimize using a hash map for better time complexity..."
    num_map = {}
    
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    return []

def two_sum_two_pointers(nums: List[int], target: int) -> List[int]:
    """Approach 3: Two Pointers (if sorted) - O(n log n) time, O(1) space"""
    # "If we're allowed to sort, we can use two pointers..."
    indexed = [(num, i) for i, num in enumerate(nums)]
    indexed.sort()
    
    left, right = 0, len(indexed) - 1
    
    while left < right:
        current_sum = indexed[left][0] + indexed[right][0]
        if current_sum == target:
            return sorted([indexed[left][1], indexed[right][1]])
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

class SolutionAnalyzer:
    """Demonstrates professional solution analysis"""
    
    @staticmethod
    def compare_approaches():
        return """
        Approach Comparison:
        
        1. Brute Force:
           ✅ Pros: Simple, O(1) space, no preprocessing
           ❌ Cons: O(n²) time complexity, slow for large inputs
           
        2. Hash Map:
           ✅ Pros: O(n) time, single pass
           ❌ Cons: O(n) extra space, hash collisions possible
           
        3. Two Pointers:
           ✅ Pros: O(1) space after sorting
           ❌ Cons: O(n log n) time due to sorting, loses original indices
           
        Recommendation: Hash map for most cases, two pointers if space is critical.
        """
    
    @staticmethod
    def benchmark_solutions(nums: List[int], target: int):
        """Show practical performance differences"""
        approaches = [
            ("Brute Force", two_sum_brute_force),
            ("Hash Map", two_sum_hash_map),
            ("Two Pointers", two_sum_two_pointers)
        ]
        
        results = {}
        for name, func in approaches:
            start = time.time()
            result = func(nums.copy(), target)
            end = time.time()
            results[name] = {
                'result': result,
                'time': (end - start) * 1000,  # ms
                'correct': len(result) == 2
            }
        
        return results

class InterviewEvolution:
    """Demonstrates how to evolve solutions during interview"""
    
    def solve_longest_substring(self, s: str):
        """Show step-by-step solution evolution"""
        
        print("Let me think through this step by step...")
        
        # Step 1: Understand the problem
        print("\n1. Problem Understanding:")
        print("   Find longest substring without repeating characters")
        print(f"   Example: '{s}' -> need to find longest unique substring")
        
        # Step 2: Brute Force
        print("\n2. Brute Force Approach:")
        print("   - Check all possible substrings")
        print("   - For each, verify if characters are unique")
        print("   - Time: O(n³), Space: O(min(m,n))")
        
        def brute_force(s: str) -> int:
            max_length = 0
            for i in range(len(s)):
                seen = set()
                for j in range(i, len(s)):
                    if s[j] in seen:
                        break
                    seen.add(s[j])
                    max_length = max(max_length, j - i + 1)
            return max_length
        
        bf_result = brute_force(s)
        print(f"   Brute force result: {bf_result}")
        
        # Step 3: Optimize
        print("\n3. Optimization - Sliding Window:")
        print("   - Use two pointers (left, right)")
        print("   - Expand right, shrink left when needed")
        print("   - Time: O(n), Space: O(min(m,n))")
        
        def sliding_window(s: str) -> int:
            char_map = {}
            left = max_length = 0
            
            for right, char in enumerate(s):
                if char in char_map and char_map[char] >= left:
                    left = char_map[char] + 1
                char_map[char] = right
                max_length = max(max_length, right - left + 1)
            
            return max_length
        
        sw_result = sliding_window(s)
        print(f"   Sliding window result: {sw_result}")
        
        # Step 4: Analysis
        print("\n4. Solution Analysis:")
        print("   - Improved from O(n³) to O(n)")
        print("   - Space complexity remains optimal")
        print("   - Single pass through string")
        
        return {
            'brute_force': bf_result,
            'optimized': sw_result,
            'improvement': 'O(n³) → O(n)'
        }

# Interview Communication Examples
class InterviewCommunication:
    """Examples of professional interview communication"""
    
    @staticmethod
    def problem_clarification():
        return [
            "Let me clarify the requirements...",
            "Should I assume the input is always valid?",
            "Are there any constraints on the input size?",
            "Do you want me to handle edge cases like empty input?",
            "Should I optimize for time or space complexity?"
        ]
    
    @staticmethod
    def solution_presentation():
        return [
            "I'll start with a brute force approach and then optimize...",
            "Let me trace through an example to verify my logic...",
            "The time complexity is O(n) and space complexity is O(1)...",
            "This solution handles edge cases like...",
            "Would you like me to implement this or move to optimization?"
        ]
    
    @staticmethod
    def testing_approach():
        return [
            "Let me test with a few examples...",
            "Edge cases to consider: empty input, single element, all same elements",
            "I'll trace through the algorithm step by step...",
            "This should work for the given constraints because...",
            "Are there any specific test cases you'd like me to consider?"
        ]