Python 리드·아키텍트 코딩·알고리즘 면접

Min Heap을 사용한 스트리밍 알고리즘이 최적입니다. K 크기의 Min Heap을 유지하면서 파일을 순차적으로 읽어 현재 원소가 힙의 최솟값보다 크면 교체합니다. 시간 복잡도는 O(N log K)이며, 공간 복잡도는 O(K)로 메모리 제약을 만족합니다. 대안으로 파일을 청크 단위로 나눠 각각 정렬 후 병합하는 External Sort 방식도 가능하나 O(N log N) 시간이 소요됩니다. 프로덕션 구현 시 파일 I/O 버퍼링, 예외 처리, 진행률 모니터링, 그리고 중단 후 재시작 가능한 체크포인트 메커니즘을 고려해야 합니다. 또한 멀티프로세싱으로 파일을 분할 처리 후 결과를 병합하면 처리 속도를 개선할 수 있습니다.

기본 해싱(hash(key) mod N)은 노드 수 N이 변경되면 대부분의 키가 재배치되어 캐시 미스가 급증합니다. Consistent Hashing은 해시 링 구조를 사용해 키와 노드를 동일한 해시 공간에 배치하고, 키는 시계방향으로 가장 가까운 노드에 할당됩니다. 노드 추가/삭제 시 평균 K/N개의 키만 재배치되어 O(1/N) 비율의 영향만 받습니다. 키 검색은 이진 탐색으로 O(log N) 시간 복잡도를 가집니다. Virtual Node는 각 물리 노드를 여러 가상 노드로 매핑해 데이터 분산의 균등성을 개선하지만, 가상 노드 수가 많을수록 메모리 사용량과 검색 시간이 증가하는 트레이드오프가 있습니다. 실무에서는 물리 노드당 100-200개의 가상 노드가 적절하며, 노드별 가중치 설정, 복제 전략, 그리고 점진적 데이터 마이그레이션 메커니즘도 함께 고려해야 합니다.

Token Bucket은 고정 속도로 토큰을 생성하고 요청마다 토큰을 소비하는 방식으로 버스트를 자연스럽게 허용하며 O(1) 시간과 사용자당 O(1) 공간 복잡도를 가집니다. Leaky Bucket은 요청을 큐에 담고 고정 속도로 처리해 평탄화하지만 버스트 대응이 약하고 O(1) 시간, O(queue_size) 공간이 필요합니다. Sliding Window는 타임스탬프 기반으로 정확한 제한을 제공하나 O(N) 공간과 윈도우 계산 시 O(N) 시간이 소요됩니다. 분산 환경에서는 Redis 같은 중앙 저장소를 사용해 상태를 공유하되, Lua 스크립트로 원자성을 보장하고 네트워크 지연을 고려한 로컬 캐싱을 병행해야 합니다. Token Bucket이 구현 복잡도와 성능, 사용자 경험 측면에서 가장 균형잡힌 선택이며, Sliding Window Log의 근사 버전인 Sliding Window Counter는 메모리 효율성을 개선한 대안입니다.