時間制限付き模擬面接：EasyとMediumの問題

この模擬面接の進め方

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

簡単な問題1：有効な括弧

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

簡単な問題2：株式の売買に最適なタイミング

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

中程度の問題1：3Sum

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

中級問題 2：繰り返し文字のない最長部分文字列

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

中級問題 3：コインチェンジ

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

解答のレビュー：5つの質問

# 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

クイックチェック

レッスンのまとめ