Entrevista simulada cronometrada: problemas fáceis e médios

Como usar esta entrevista simulada

# Mock interview timer simulation
import time

class InterviewTimer:
    def __init__(self, total_minutes):
        self.total = total_minutes * 60
        self.start = None

    def begin(self, problem_name):
        self.start = time.time()
        print(f'TIMER STARTED: {problem_name}')
        print(f'You have {self.total//60} minutes. Go!')

    def checkpoint(self, label):
        if self.start:
            elapsed = time.time() - self.start
            remaining = self.total - elapsed
            print(f'[{label}] Elapsed: {elapsed:.0f}s, Remaining: {remaining:.0f}s')

# Usage in real practice:
timer = InterviewTimer(15)  # 15-minute easy problem
timer.begin('Two Sum')
time.sleep(1)
timer.checkpoint('Identified pattern')

Problema fácil 1: parênteses válidos

def is_valid(s):
    stack = []
    matching = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in '({[':
            stack.append(char)
        else:
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
    return len(stack) == 0

# Test cases
test_cases = [
    ('()', True),
    ('()[]{}'  , True),
    ('(]', False),
    ('([)]', False),
    ('{[]}', True),
    ('', True),        # empty string is valid
    ('(((', False),    # unmatched opens
    (')]', False),     # close without open
]
for s, expected in test_cases:
    result = is_valid(s)
    status = 'PASS' if result == expected else 'FAIL'
    print(f'{status}: is_valid({repr(s)}) = {result} (expected {expected})')

Problema fácil 2: melhor momento para comprar e vender ações

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})')

Problema médio 1: soma de três elementos

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]))           # []

Problema Médio 2: Subcadeia Mais Longa sem Caracteres Repetidos

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})')

Problema Médio 3: Troca de Moedas

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})')

Fluxo de Trabalho para Resolver Problemas sob Pressão de Tempo

# 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 []

Revisão da Sua Solução: Cinco Perguntas

# 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})')

Como Lidar com Perguntas de Acompanhamento

# 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')

Problema para Praticar: Agrupamento de Anagramas

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)])

Autoavaliação Após uma Simulação

# 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

Verificação Rápida

Recapitulação da Lição