DSA 면접 질문

수백 문제를 풀었는데도 여전히 준비가 안 된 것 같다면, 대개는 연습의 잘못된 절반에 집중해왔다는 뜻입니다. 이 섹션에서는 실제로 무엇이 평가되는지를 짚어서, 연습 방향을 거기에 맞출 수 있도록 합니다.

라이브 자료구조 및 알고리즘 면접은 다음 네 가지를 동시에 측정합니다. 문제가 어떤 패턴에 속하는지 알아볼 수 있는가, 코드를 작성하기 전에 접근법을 말할 수 있는가, 경계 조건에서 구현이 올바른가, 그리고 복잡도를 말로 설명할 수 있는가입니다. 지원자들은 세 번째에만 집중하고 두 번째를 소홀히 한 뒤, 설명 없이 나온 정답 때문에 감점을 받곤 합니다.

이 인식 단계가 바로 패턴 연습이 문제 양보다 중요한 이유입니다. 문제는 완전히 새로운 경우가 드물고, 대개 기존 패턴의 재조합입니다. 처음 일 분 안에 이건 빈도 맵 위에서의 슬라이딩 윈도우다라고 말할 수 있게 되면, 나머지는 구현일 뿐입니다. 언어와 직무별 관련 문제 모음은 면접 질문 허브에 있습니다.

이 패턴들이 출제되는 문제의 대부분을 차지합니다. 각 패턴을 가리키는 신호를 알아보는 법을 익히세요.

• 투 포인터. 정렬된 입력, 두 수의 합, 제자리 분할, 회문 판별.
• 슬라이딩 윈도우. 제약 조건 아래에서 가장 길거나 짧은 연속 부분 배열.
• 해시맵 카운팅. 애너그램, 중복, 빈도 비교, 첫 번째 고유 원소.
• 이진 탐색. 정렬된 배열, 그리고 배열이 정렬되지 않았을 때 답의 공간에서 하는 탐색.
• 너비 우선 탐색과 깊이 우선 탐색. 트리, 그리드, 연결 요소, 가중치 없는 최단 경로.
• 힙과 우선순위 큐. 상위 k개 문제, 정렬된 스트림 병합, 실시간 중앙값 계산.
• 구간. 시작점 기준으로 정렬한 뒤 병합, 삽입, 겹침 감지.
• 동적 계획법. 중첩되는 부분 문제: 계단 오르기, 동전 교환, 편집 거리, 부분 수열.
• 백트래킹. 순열, 조합, 부분집합, 제약 조건 퍼즐.
• 그래프 알고리즘. 위상 정렬, 유니온 파인드, 가중치 최단 경로.

면접관이 실제로 사용하는 표현으로 옮긴 대표적인 문제들입니다:

• 배열에서 합이 목표값이 되는 두 수를 찾고, 이어서 추가 공간 없이 구현한다.
• 반복되는 문자가 없는 가장 긴 부분 문자열의 길이를 반환한다.
• 회전된 정렬 배열이 주어졌을 때, 로그 시간 안에 목표값을 찾는다.
• 겹치는 구간을 병합하고, 정렬 비용이 왜 그만한 가치가 있는지 설명한다.
• 이진 트리를 뒤집고, 이어서 최대 깊이를 구한다.
• 이진 탐색 트리를 검증하고, 단순한 검사 방식이 놓치는 부분을 설명한다.
• 그리드에서 섬의 개수를 세고, 메모리에 다 담을 수 없을 만큼 큰 그리드는 어떻게 처리할지 설명한다.
• 빈도가 가장 높은 상위 k개 원소를 찾고, 선택한 자료구조의 이유를 설명한다.
• 주어진 금액에 대한 최소 동전 개수를 계산하고, 점화식을 말한다.
• 연결 리스트에서 사이클을 감지하고, 이어서 사이클이 시작되는 노드를 반환한다.
• 이진 트리를 직렬화하고 역직렬화한다.
• 수강 선수 조건이 주어졌을 때, 그 일정이 가능한지 판단한다.

백엔드 직무에 지원한 신입 지원자가 부분 문자열 문제를 받고 곧바로 타이핑을 시작합니다. 코드는 거의 맞지만, 면접관은 면접 시간 내내 그 코드가 무엇을 하는지 묻는 데 쓰고, 평가에는 버그가 아니라 그 침묵이 반영됩니다. 반면 사십 초를 들여 문자 맵 위의 윈도우이고, 오른쪽을 넓히다가 중복이 나오면 왼쪽을 좁히고, 최댓값을 추적한다라고 말한 지원자는 가장 만회하기 어려운 부분을 이미 통과한 것입니다.

조용히 문제를 푸는 연습은 잘못된 반사 신경을 만듭니다. 라이브 면접은 설명과 코딩을 동시에 요구하며, 이는 둘 중 하나만 잘하는 것과는 별개의 능력입니다.

바꿔야 할 것은 문제집이 아니라 연습 방식입니다. 무언가를 작성하기 전에 패턴, 접근법, 예상 복잡도를 소리 내어 말하세요. 계속 설명하면서 코드를 작성합니다. 다 끝나면 복잡도를 다시 말하고, 직접 처리한 엣지 케이스 하나와 물어보고 싶은 엣지 케이스 하나를 언급하세요. 이런 방식으로 열 문제를 푸는 것이 조용히 쉰 문제를 푸는 것보다 면접 역량을 더 키워줍니다.

모의 면접 세션은 혼자서는 연습할 수 없는 후속 질문을 제공하고, 자신의 설명을 녹음해 나중에 다시 볼 수 있게 해줍니다. 여기에는 항상 적용되는 한 가지 솔직한 한계가 있습니다. 감독관이 있는 브라우저 내 타이핑 평가는 대화가 아니며, 어떤 라이브 어시스턴트도 거기에 속하지 않습니다. 어떤 코딩 형식이 라이브이고 어떤 것이 자동화되어 있는지는 면접 유형 허브에서 확인할 수 있습니다.