Tidsbegrænset prøveinterview: Nemme og mellemsvære problemer

def max_profit(prices):
    if not prices:
        return 0
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit

# Test cases
test_cases = [
    ([7, 1, 5, 3, 6, 4], 5),   # buy at 1, sell at 6
    ([7, 6, 4, 3, 1], 0),      # monotonically decreasing: no profit
    ([2, 4, 1], 2),             # buy at 2, sell at 4
    ([1], 0),                   # single price: no transaction possible
    ([3, 3, 3], 0),             # flat: no profit
]
for prices, expected in test_cases:
    result = max_profit(prices)
    status = 'PASS' if result == expected else 'FAIL'
    print(f'{status}: max_profit({prices}) = {result} (expected {expected})')

def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # Skip duplicate values for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1      # skip duplicate lefts
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1     # skip duplicate rights
                left += 1; right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2],[-1,0,1]]
print(three_sum([0, 0, 0, 0]))            # [[0,0,0]]
print(three_sum([]))                       # []
print(three_sum([1, 2, -2, -1]))           # []

def length_of_longest_substring(s):
    char_index = {}    # character -> last seen index
    left = 0
    max_len = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1  # shrink window past duplicate
        char_index[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len

# Test cases
test_cases = [
    ('abcabcbb', 3),   # 'abc'
    ('bbbbb', 1),       # 'b'
    ('pwwkew', 3),      # 'wke'
    ('', 0),            # empty string
    ('au', 2),          # full string
    ('dvdf', 3),        # 'vdf' (skip the first d)
]
for s, expected in test_cases:
    result = length_of_longest_substring(s)
    status = 'PASS' if result == expected else 'FAIL'
    print(f'{status}: len_longest({repr(s)}) = {result} (expected {expected})')

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0   # 0 coins to make amount 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1

    return dp[amount] if dp[amount] != float('inf') else -1

# Test cases
test_cases = [
    ([1, 5, 11], 15, 3),      # 11+1+1+1+1... wait: 11+1+1+1+1=5 coins? No: 5+5+5=3
    ([2], 3, -1),              # impossible (only even coins)
    ([1], 0, 0),               # 0 coins for amount 0
    ([1, 2, 5], 11, 3),        # 5+5+1
    ([186, 419, 83, 408], 6249, 20),  # stress test
]
for coins, amount, expected in test_cases:
    result = coin_change(coins, amount)
    status = 'PASS' if result == expected else 'FAIL'
    print(f'{status}: coin_change({coins}, {amount}) = {result} (expected {expected})')

# Priority order when time runs out
priority = [
    ('First priority',  'Correct brute-force that passes all test cases'),
    ('Second priority', 'Optimal solution with bugs is WORSE than suboptimal correct'),
    ('Third priority',  'Edge cases handled visibly (empty input, single element, negatives)'),
    ('Fourth priority', 'Clean variable names and readable code'),
    ('Fifth priority',  'Add complexity statement as a comment at the top'),
]
print('Under time pressure, prioritise:')
for priority_level, desc in priority:
    print(f'  {priority_level}: {desc}')

# Adding complexity as a comment
def two_sum_commented(nums, target):
    # Time: O(n), Space: O(n)
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

# The five edge-case categories with examples
edge_cases = {
    'Empty input':     ['[] empty array', '"" empty string', 'None / null'],
    'Single element':  ['[42]', 'single node tree', 'n=1'],
    'All same':        ['[3,3,3,3]', '"aaaa"', 'uniform grid'],
    'Extreme values':  ['[-10^9, 10^9]', 'INT_MAX + 1 overflow check', '0 as input'],
    'Already sorted':  ['ascending + descending', 'already optimal input'],
}
for category, examples in edge_cases.items():
    print(f'{category}:')
    for ex in examples:
        print(f'  - {ex}')
    print()

# Template for self-testing:
def test_my_solution(fn, test_cases):
    for inputs, expected in test_cases:
        result = fn(*inputs) if isinstance(inputs, tuple) else fn(inputs)
        status = 'PASS' if result == expected else 'FAIL'
        print(f'{status}: {inputs} => {result} (expected {expected})')

# Follow-up answers for classic problems
follow_ups = [
    {
        'problem': 'Find duplicate in array 1..n (space O(n) solution uses set)',
        'follow_up': 'Can you do it in O(1) space without modifying input?',
        'answer': 'Floyd cycle detection: treat array as linked list (slow/fast pointer)',
    },
    {
        'problem': 'Reverse a string (space O(n) with new array)',
        'follow_up': 'Can you do it in-place?',
        'answer': 'Two pointers from both ends, swap until they meet: O(n) time O(1) space',
    },
    {
        'problem': 'Find max in array: O(n) single pass',
        'follow_up': 'What if the array is streamed one element at a time?',
        'answer': 'Same algorithm works! Running maximum handles infinite streams',
    },
    {
        'problem': 'Merge sorted arrays O(n+m)',
        'follow_up': 'What if you have K sorted arrays?',
        'answer': 'Use a min-heap of (value, array_idx, element_idx): O(n log k)',
    },
]
for fu in follow_ups:
    print(f'Problem: {fu["problem"]}')
    print(f'Follow-up: {fu["follow_up"]}')
    print(f'Answer: {fu["answer"]}\n')

from collections import defaultdict

def group_anagrams(strs):
    # Method 1: sort each string as key
    groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))   # canonical form
        groups[key].append(s)
    return list(groups.values())

def group_anagrams_v2(strs):
    # Method 2: character count tuple as key (avoids sorting)
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        key = tuple(count)   # immutable, hashable
        groups[key].append(s)
    return list(groups.values())

test = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
result = [sorted(g) for g in group_anagrams(test)]
result.sort()
print('Groups:', result)
# [['ate','eat','tea'], ['bat'], ['nat','tan']]

print('V2:', [sorted(g) for g in sorted(group_anagrams_v2(test), key=len)])

# Self-assessment scoring template
def self_assess(pattern_speed, code_correctness, edge_cases,
                communication, complexity, recovery):
    scores = {
        'Pattern recognition (< 60s)': pattern_speed,
        'Code correctness (all tests pass)': code_correctness,
        'Edge case handling': edge_cases,
        'Communication (thinking aloud)': communication,
        'Complexity stated correctly': complexity,
        'Recovery when stuck': recovery,
    }
    total = sum(scores.values())
    max_total = len(scores) * 5
    print('Self-Assessment Results:')
    print('-'*50)
    for dim, score in scores.items():
        bar = '#' * score + '-' * (5 - score)
        print(f'{dim:45s} [{bar}] {score}/5')
    print(f'\nTotal: {total}/{max_total} ({total/max_total*100:.0f}%)')
    weak = min(scores, key=scores.get)
    print(f'Focus area: {weak}')

self_assess(4, 3, 4, 3, 5, 2)  # example scores