코딩 면접 문제 모음

패턴: 투 포인터·복잡도: 시간 O(n), 공간 O(1)

정렬된 배열의 양 끝에서 포인터를 시작하세요. 합이 너무 작으면 왼쪽 포인터를 앞으로, 너무 크면 오른쪽 포인터를 뒤로 옮겨요. 정렬되어 있기 때문에 유효한 쌍을 절대 건너뛰지 않아요. 면접관은 바로 이 불변식을 소리 내어 말하길 원해요.

패턴: 해시 맵 / 카운팅·복잡도: 시간 O(n), 고정된 알파벳이면 공간 O(1)

첫 번째 문자열의 문자 빈도를 세고, 두 번째 문자열을 훑으며 하나씩 빼서 모든 카운트가 0으로 돌아오는지 확인하세요. 묻기 전에 후속 질문을 먼저 언급하세요. 유니코드 전체를 다루면 고정된 26칸 배열은 더 이상 통하지 않으니 해시 맵을 써야 해요.

패턴: 플로이드의 느린/빠른 포인터·복잡도: 시간 O(n), 공간 O(1)

포인터 하나는 한 노드씩, 다른 하나는 두 노드씩 전진시키세요. 둘이 만나면 사이클이 있어요. 전형적인 후속 질문인 사이클 시작점 찾기에도 대비하세요. 포인터 하나를 head로 되돌린 뒤 둘 다 한 칸씩 전진시켜 다시 만나는 곳이 시작점이에요.

패턴: 보이어-무어 과반수 투표·복잡도: 시간 O(n), 공간 O(1)

후보 하나와 카운터를 두세요. 같으면 증가, 다르면 감소, 카운터가 0이 되면 후보를 바꿔요. 과반수 원소는 n/2번보다 많이 등장하므로 항상 살아남아요. 왜 살아남는지 설명하는 것이 면접의 핵심이에요.

패턴: 한 번 순회, 최솟값 유지·복잡도: 시간 O(n), 공간 O(1)

지금까지 본 최저가와, 오늘 판다면 얻을 최고 수익을 추적하세요. 한 번 순회에 변수 두 개면 돼요. 이 문제는 나중에 카데인 알고리즘에서도 나오는 "가장 좋은 접두 상태를 들고 가기" 아이디어의 가장 작은 예예요. 그 연결을 짚으면 점수를 얻어요.

패턴: 정렬 + 선형 스윕·복잡도: 시간 O(n log n), 공간 O(n)

구간을 시작점으로 정렬한 다음 훑으세요. 현재 구간이 마지막으로 병합한 구간이 끝난 뒤에 시작하면 추가하고, 아니면 병합된 끝점을 둘 중 큰 값으로 늘려요. 실제 일은 정렬이 해요. 그렇다고 말하고, 비교 기준의 경계 사례(맞닿은 구간)를 정확히 처리하세요.

패턴: 해시 셋 + 수열 시작점·복잡도: 시간 O(n), 공간 O(n)

모든 수를 셋에 넣고, 바로 앞의 수가 없는 수(수열의 시작점)에서만 세기 시작해 앞으로 걸어가세요. 각 원소는 최대 두 번만 방문하므로, "중첩 루프가 있는데요?"라는 반론에 맞서 O(n)을 방어하는 근거가 돼요.

패턴: 접두/접미 곱·복잡도: 시간 O(n), 출력 외 추가 공간 O(1)

나눗셈 없이 두 번 순회하세요. 먼저 각 칸을 그 왼쪽 원소들의 곱으로 채우고, 오른쪽에서부터 훑으며 오른쪽 원소들의 곱을 곱해 넣어요. 나눗셈 기반 답은 0이 있는 경우에 실패해요. 면접관은 보통 나눗셈을 명시적으로 금지해요.

패턴: 보조 스택 불변식·복잡도: 연산당 O(1), 공간 O(n)

값 스택과 함께, 맨 위가 항상 그 아래 전체의 최솟값인 최소 스택을 두세요. min(새 값, 현재 맨 위)를 push하고, pop은 함께 하세요. 이건 설계 문제예요. 채점되는 건 코드 양이 아니라 불변식이에요.

패턴: 해시 맵 + 이중 연결 리스트·복잡도: get/put당 O(1), 공간 O(capacity)

해시 맵으로, 최근 사용 순서로 정렬된 이중 연결 리스트의 노드를 O(1)에 찾아요. 접근하면 노드를 head로 옮기고, 용량을 넘으면 tail에서 제거하세요. 센티널 head/tail 노드를 두면 null 체크 경계 사례가 모두 사라져요. 코딩을 시작하기 전에 언급하세요.

패턴: 격자 BFS/DFS 플러드 필·복잡도: 시간 O(rows × cols)

격자를 훑으며 방문하지 않은 땅 칸마다 플러드 필(DFS 또는 BFS)을 시작해 섬 전체를 방문 처리하고, 시작한 횟수를 세세요. 방문 표시 전략(제자리에서 지우기 대 별도 셋)과 거대한 격자에서의 재귀 깊이 위험을 말하세요. 그게 시니어다운 신호예요.

패턴: 위상 정렬 / 사이클 탐지·복잡도: 시간 O(V + E)

선수 과목을 방향 그래프로 모델링하세요. '모두 이수할 수 있는가'라는 질문은 정확히 '그래프에 사이클이 없는가'예요. Kahn 알고리즘(진입 차수가 0인 노드를 반복해서 제거)이나 DFS 3색 표시 모두 통해요. 하나를 골라, 남는 노드가 왜 사이클을 뜻하는지 설명하세요.

패턴: 레벨별 스냅샷 BFS·복잡도: 시간 O(n), 공간 O(width)

큐로 BFS를 하되, 단계마다 큐 길이를 스냅샷해 레벨마다 리스트를 하나씩 내보내세요. 이 길이 스냅샷 기법이 재사용 가능한 핵심이에요. 지그재그 순회와 오른쪽에서 본 뷰도 수집 단계만 다른 같은 루프예요.

패턴: 범위 전파 / 중위 순회·복잡도: 시간 O(n), 공간 O(height)

단계마다 좁혀지는 허용 범위 (min, max)를 들고 재귀하거나, 중위 순회를 해서 엄격하게 증가하는지 확인하세요. 전형적인 함정은 자식을 부모하고만 비교하는 거예요. 면접관보다 먼저 반례를 직접 만들어 보이세요.

패턴: 양방향 해시 매핑 (전단사)·복잡도: 시간 O(n), 공간 O(n)

패턴 문자를 단어로, 그리고 단어를 다시 문자로 매핑하세요. 한 방향만 보면 "dog dog"에 대해 패턴 "ab"를 받아들이고 말아요. 양방향으로 전단사를 확인하는 것이 핵심 전부예요. "전단사"라는 말을 쓰고, 코딩 전에 길이가 다른 경우를 처리하세요.

패턴: 숨은 수열에서의 사이클 탐지·복잡도: 단계당 O(log n), 플로이드를 쓰면 공간 O(1)

수를 각 자릿수 제곱의 합으로 계속 바꾸면 1에 도달하거나 루프에 빠져요. 그러니 이건 모습을 바꾼 Linked List Cycle이에요. 본 적 있는 수의 셋으로 루프를 찾거나, 공간 O(1)을 위해 플로이드의 느린/빠른 포인터로 깊은 인상을 남기세요. 사이클 탐지로 환원된다는 걸 짚는 것이 시니어다운 한 수예요.

패턴: 증명이 필요한 그리디·복잡도: 시간 O(n), 공간 O(1)

전체 연료 ≥ 전체 비용이면 답이 존재하고 유일해요. 누적 연료량을 추적하며 한 번 훑다가 음수가 되면, 실패한 구간의 어떤 주유소도 출발점이 될 수 없으니 다음 주유소에서 다시 시작하세요. 면접의 핵심은 루프 자체가 아니라 그 건너뛰기의 정당화예요.

패턴: 그리디 / 암묵적 BFS 레이어·복잡도: 시간 O(n), 공간 O(1)

k번 점프로 닿을 수 있는 인덱스들을 하나의 BFS 레이어로 보세요. 현재 레이어의 오른쪽 끝과 지금까지 본 가장 먼 도달점을 추적하다가, 그 끝을 지나치면 점프 수를 늘리고 끝을 가장 먼 도달점으로 넓혀요. 큐 없는 BFS로 설명하면 여기서 왜 그리디가 최적인지가 드러나요.

패턴: 3단계 선형 병합·복잡도: 시간 O(n), 공간 O(n)

새 구간이 시작하기 전에 끝나는 구간들을 내보내고, 겹치는 구간을 모두 새 구간에 흡수한 다음(시작은 최솟값, 끝은 최댓값), 나머지를 내보내세요. 입력이 정렬되어 있으니 다시 정렬할 필요 없이 한 번이면 돼요. 왜 이게 더 쉬운지 물으면 Merge Intervals와 대비해 설명하세요.

패턴: 제자리(in-place) 행렬 변환·복잡도: 시간 O(n²), 공간 O(1)

시계 방향 90° 회전 = 전치한 뒤 각 행 뒤집기. 추가 공간 O(1)의 깔끔한 두 번의 순회가, 압박 속에서 네 칸 순환 교환을 손으로 유도하는 것보다 나아요. 다만 면접관이 이 요령 너머를 파고들면 좌표 매핑 (i,j) → (j, n−1−i)를 설명할 준비를 하세요.

패턴: 빌린 공간을 이용한 제자리 표시·복잡도: 시간 O(m×n), 공간 O(1)

첫 행과 첫 열을 어느 행/열을 0으로 만들지 표시하는 저장소로 쓰고, 그 행과 열 자신의 상태는 불리언 두 개로 기억하세요. 공간 사다리를 소리 내어 따라가세요. O(mn) 복사 → O(m+n) 셋 → O(1) 빌린 공간. 그 사다리 자체가 평가 대상이에요.

패턴: 정렬 / 카운팅 버킷·복잡도: 정렬하면 O(n log n), 버킷을 쓰면 O(n)

내림차순 정렬 후 citations[i] ≥ i+1인 가장 큰 i를 찾거나, n에서 상한을 둔 카운팅 버킷으로 정렬 없이 O(n)에 풀 수 있어요. 코딩 전에 정의를 정확히 말하세요. 이 문제의 실패는 대부분 알고리즘이 아니라 "인용이 h번 이상인 논문이 h편"을 잘못 읽는 데서 나와요.

패턴: 위상 정렬, 순서 출력·복잡도: 시간 O(V + E)

Course Schedule과 같은 그래프지만, 이번에는 Kahn 알고리즘이 제값을 해요. 진입 차수가 0인 노드가 큐에서 나오는 순서가 곧 유효한 수강 순서예요. 출력된 순서가 과목 수보다 짧으면 사이클이 있는 것이니 빈 배열을 반환하세요. 대안으로 DFS 후위 순서를 뒤집는 방법도 언급하세요.

패턴: 충족 카운터를 쓰는 슬라이딩 윈도우·복잡도: 시간 O(n), 공간 O(alphabet)

윈도우가 필요한 문자를 모두 포함할 때까지 오른쪽 끝을 넓히고(단계마다 전체 맵을 비교하지 말고 "충족 수 대 필요 수" 카운터를 추적하세요), 여전히 유효한 동안 왼쪽 끝을 최소로 줄이며 최적값을 기록하세요. 충족 카운터 최적화가 O(n)을 지켜 줘요. 명시적으로 설명하세요.

패턴: 누적 최댓값 위의 투 포인터·복잡도: 시간 O(n), 공간 O(1)

각 막대 위의 물은 min(왼쪽 최댓값, 오른쪽 최댓값) − 높이예요. 양 끝에서 안쪽으로 움직이는 두 포인터로, 누적 최댓값이 더 낮은 쪽을 먼저 확정할 수 있어요. 그쪽의 경계는 이미 최종값이기 때문이에요. 그 확실성이 왜 성립하는지 짚어 가세요. 그게 이 질문의 전부예요.