Håndtering af kanttilfælde og kommunikation som interviewperson

# Example: explicitly stated assumptions in code comments
def longest_palindrome(s):
    # Assumptions:
    # - s consists of lowercase English letters only
    # - 1 <= len(s) <= 1000
    # - Return the first palindrome if multiple exist with same max length
    # - If s is empty (not per constraints but defensive): return ''
    if not s:
        return ''

    start = end = 0

    def expand(l, r):
        nonlocal start, end
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if r - l > end - start:
                start, end = l, r
            l -= 1; r += 1

    for i in range(len(s)):
        expand(i, i)       # odd-length palindromes
        expand(i, i + 1)   # even-length palindromes
    return s[start:end + 1]

print(longest_palindrome('babad'))   # 'bab' or 'aba'
print(longest_palindrome('cbbd'))    # 'bb'
print(longest_palindrome('a'))       # 'a'

# Example narration script for Two Sum problem
narration = [
    'I see this asks for indices of two numbers that sum to target.',
    'Brute force would be O(n^2) — check all pairs. I can do better.',
    'I will use a hash map to store each number and its index.',
    'For each number, I compute target - number and check if it is in the map.',
    'This gives O(n) time and O(n) space — one pass through the array.',
    "Edge case: what if the same element is used twice? The problem says 'exactly two different indices', so I check the current index is not the stored one.",
    'Let me write it...',
]
for step in narration:
    print(f'[NARRATE] {step}')

print()
def two_sum(nums, target):
    seen = {}   # value -> index
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen and seen[complement] != i:  # different index
            return [seen[complement], i]
        seen[n] = i
    return []

print('Result:', two_sum([2, 7, 11, 15], 9))   # [0, 1]

# Responses to common interviewer hints
hint_responses = [
    {
        'hint': 'What if the array were sorted?',
        'bad_response': 'Oh, it is not sorted in this problem.',
        'good_response': 'Great point! If sorted, I could use two pointers. Let me sort first in O(n log n), then apply two pointers for O(n). Total O(n log n) which might be acceptable.',
    },
    {
        'hint': 'Can you reduce the space?',
        'bad_response': 'My solution is already O(n), that seems fine.',
        'good_response': 'Yes! Currently O(n) for the hash map. For an O(1) space solution, I could modify the array in-place as a visited marker, or use Floyd cycle detection...',
    },
    {
        'hint': 'What data structure could give you O(1) lookup here?',
        'bad_response': '...a list?',
        'good_response': 'A hash set or hash map! Instead of scanning O(n) each time, I can build a set upfront and check membership in O(1). Let me redesign...',
    },
]
for h in hint_responses:
    print(f'Hint: "{h["hint"]}"')
    print(f'  Bad:  {h["bad_response"]}')
    print(f'  Good: {h["good_response"]}')
    print()

# Manual trace of Two Sum for demonstrating testing
def trace_two_sum(nums, target):
    seen = {}
    print(f'Input: {nums}, target={target}')
    for i, n in enumerate(nums):
        complement = target - n
        print(f'  i={i}, n={n}, complement={complement}, seen={seen}', end=' => ')
        if complement in seen:
            print(f'FOUND! indices [{seen[complement]}, {i}]')
            return [seen[complement], i]
        print('not found, adding to seen')
        seen[n] = i
    print('No solution found')
    return []

# Demonstrating the testing workflow
print('=== Testing valid case ===')
trace_two_sum([2, 7, 11, 15], 9)
print()
print('=== Testing no solution ===')
trace_two_sum([1, 2, 3], 10)
print()
print('=== Testing with duplicates ===')
trace_two_sum([3, 3], 6)

def validate_solution_coverage(fn, problem_name):
    print(f'Edge case checklist for: {problem_name}')
    edge_categories = [
        ('Empty input',      '[] or ""'),
        ('Single element',   '[x] or "x"'),
        ('All same',         '[5,5,5,5] or "aaaa"'),
        ('Negative/zero',    '[-1, 0, 1] or negative target'),
        ('Already optimal',  'sorted input, already max, no change needed'),
    ]
    for category, example in edge_categories:
        print(f'  [ ] {category}: test with {example}')

# Example problem being tested
def max_subarray(nums):
    if not nums: return 0  # edge: empty
    max_sum = cur_sum = nums[0]  # edge: single element handled by init
    for n in nums[1:]:
        cur_sum = max(n, cur_sum + n)
        max_sum = max(max_sum, cur_sum)
    return max_sum

validate_solution_coverage(max_subarray, 'Maximum Subarray')
print()
for test in [[], [-1], [-2,-1], [0], [5,5,5], [-3,-1,-2]]:
    print(f'max_subarray({test}) = {max_subarray(test) if test else 0}')

# Complexity analysis template
def analyze_complexity(function_name, time_complexity, space_complexity, justification):
    print(f'Function: {function_name}')
    print(f'Time:  {time_complexity}')
    print(f'Space: {space_complexity}')
    print(f'Why:   {justification}')
    print()

# Examples of well-stated complexity analyses
analyze_complexity(
    'Two Sum (hash map)',
    'O(n)',
    'O(n)',
    'Single pass through n elements; hash map stores at most n entries'
)
analyze_complexity(
    'Binary Search',
    'O(log n)',
    'O(1)',
    'Halve the search space each step; no extra data structures'
)
analyze_complexity(
    'Merge Sort',
    'O(n log n)',
    'O(n)',
    'log n levels of recursion, O(n) work per level; O(n) aux space for merging'
)
analyze_complexity(
    'DFS on binary tree',
    'O(n)',
    'O(h) where h = tree height',
    'Visit each node once; call stack depth = height (O(log n) balanced, O(n) worst)'
)

# Recovery script when stuck in an interview
recovery_steps = [
    'Re-read problem: Did I miss a constraint? (sorted? unique? positive only?)',
    'Smallest example: trace through by hand for n=3 or n=4',
    'Brute force first: state the O(n^2) or O(2^n) solution, then look to optimise',
    'Data structure fit: what do I need to track? (freq, order, min/max?) => pick structure',
    'Pattern mapping: sorted+find = binary search? All combos = backtracking? Min cost = DP?',
    'Partial solution: solve a simpler version (ignore duplicates, only positive numbers)',
    'Ask for hint: "I can get to O(n^2) but am trying to see how to use a hash map here."',
]
print('When stuck, escalate through these steps:')
for i, step in enumerate(recovery_steps, 1):
    print(f'{i}. {step}')

print('\nWhat NOT to do when stuck:')
dont_do = [
    'Stay silent for > 2 minutes (raises red flags)',
    'Randomly try different code without reasoning',
    'Announce "I give up" (ask for a hint instead)',
]
for d in dont_do:
    print(f'  X {d}')

# Trade-off discussion examples
trade_offs = [
    {
        'approach': 'Hash Map (Two Sum)',
        'time': 'O(n)', 'space': 'O(n)',
        'alternative': 'Sort + Two Pointers',
        'alt_time': 'O(n log n)', 'alt_space': 'O(1)',
        'when_to_choose_alt': 'When input is already sorted or space is very constrained',
    },
    {
        'approach': 'BFS (shortest path)',
        'time': 'O(V+E)', 'space': 'O(width)',
        'alternative': 'DFS (any path)',
        'alt_time': 'O(V+E)', 'alt_space': 'O(height)',
        'when_to_choose_alt': 'When path existence matters more than shortest path',
    },
    {
        'approach': 'Recursive DFS',
        'time': 'O(n)', 'space': 'O(h) call stack',
        'alternative': 'Iterative DFS with explicit stack',
        'alt_time': 'O(n)', 'alt_space': 'O(h) explicit',
        'when_to_choose_alt': 'When recursion depth may hit Python limit (sys.setrecursionlimit needed)',
    },
]
for t in trade_offs:
    print(f'{t["approach"]}: {t["time"]} time, {t["space"]} space')
    print(f'  Alt: {t["alternative"]}: {t["alt_time"]} time, {t["alt_space"]} space')
    print(f'  Choose alt when: {t["when_to_choose_alt"]}\n')

# Questions to ask your interviewer (sorted by quality)
questions = [
    # High impact - shows genuine curiosity
    'What is the most interesting technical challenge you have worked on here?',
    'How does the team approach code review and technical decisions?',
    'What does the onboarding process look like for new engineers?',
    'What is the biggest technical challenge or debt the team is actively tackling?',
    # Medium impact - shows team awareness
    'How does your team balance new features with reliability work?',
    'What tools and infrastructure does the team use day-to-day?',
    # Lower impact (but still fine)
    'How many engineers are on the team and how is it structured?',
    'What does a typical day look like for someone in this role?',
]
print('Questions to ask your interviewer (ranked by impact):')
for i, q in enumerate(questions, 1):
    print(f'{i:2d}. {q}')