NestJS 리드·아키텍트 코딩·알고리즘 면접
새 면접Q. 마이크로서비스 환경에서 10만 건 이상의 이벤트가 동시에 발생할 때, 순서 보장이 필요한 이벤트 처리 시스템을 설계해야 합니다. 어떤 알고리즘적 접근법을 사용하시겠습니까? 시간 복잡도와 공간 복잡도, 그리고 트레이드오프를 설명해주세요.
이벤트의 파티셔닝 전략과 각 파티션 내에서의 순서 보장 메커니즘을 함께 고려해보세요.
파티션 키 기반 샤딩과 시퀀스 넘버를 결합한 접근법을 사용합니다. 각 엔티티별로 파티션 키를 할당하여 O(1)로 라우팅하고, 파티션 내에서는 우선순위 큐(힙)를 사용해 O(log n)으로 순서를 관리합니다. 공간 복잡도는 O(n*p) (n은 이벤트 수, p는 파티션 수)입니다. 벡터 클락이나 램포트 타임스탬프를 활용해 인과관계를 추적하며, 메모리 사용량과 처리 지연시간 사이의 트레이드오프가 발생합니다. 처리량 증가를 위해 파티션을 늘리면 메모리 오버헤드가 증가하고, 글로벌 순서 보장이 어려워지는 한계가 있습니다.
- • 파티션 키 기반 샤딩으로 O(1) 라우팅
- • 파티션 내 우선순위 큐로 O(log n) 순서 관리
- • 벡터 클락/램포트 타임스탬프로 인과관계 추적
- • 처리량과 메모리 사이의 트레이드오프 이해
대규모 주문 처리 시스템에서 동일 사용자의 주문 이벤트 순서를 보장하면서도 전체 시스템 처리량을 최대화할 때 사용됩니다.
파티션 리밸런싱이 필요한 상황에서 이벤트 손실 없이 마이그레이션하는 알고리즘은 어떻게 설계하시겠습니까?
Q. NestJS 애플리케이션에서 다층 캐시 전략(L1: 인메모리, L2: Redis, L3: DB)을 구현할 때, 캐시 무효화(invalidation)와 일관성 유지를 위한 최적의 알고리즘 접근법은 무엇입니까? 각 계층별 복잡도와 일관성 보장 수준을 설명해주세요.
Write-through, Write-back, Write-around 전략의 특성과 각 계층 간 동기화 타이밍을 고려해보세요.
Write-through 기반의 계층적 무효화 전략을 사용하되, 각 계층마다 TTL과 버전 태깅을 결합합니다. L1은 LRU 알고리즘으로 O(1) 접근과 무효화를 보장하고, L2는 pub/sub 패턴으로 O(m) (m은 구독자 수) 복잡도로 전파합니다. 버전 벡터를 사용해 각 엔트리에 타임스탬프와 버전을 부여하여 stale read를 방지합니다. Eventual consistency를 허용하되, critical path에서는 Cache-Aside 패턴으로 강한 일관성을 보장합니다. Bloom Filter를 추가해 존재하지 않는 키 조회를 O(k) (k는 해시 함수 수)로 필터링하여 캐시 관통을 방지합니다.
- • Write-through 기반 계층적 무효화와 버전 태깅
- • LRU O(1) + pub/sub O(m) 조합
- • 버전 벡터로 stale read 방지
- • Bloom Filter로 캐시 관통 방지 O(k)
전자상거래 상품 상세 페이지처럼 읽기 빈도가 높고 일관성이 중요한 데이터를 효율적으로 캐싱할 때 사용됩니다.
Thunder herd 문제가 발생할 때 캐시 워밍과 요청 코어레싱을 어떻게 구현하시겠습니까?
Q. NestJS에서 분산 락 없이 낙관적 동시성 제어(Optimistic Concurrency Control)를 구현할 때, 충돌 감지와 재시도 로직의 알고리즘을 어떻게 설계하시겠습니까? 최악의 경우 시간 복잡도와 기아(starvation) 방지 전략을 포함해 설명해주세요.
버전 번호나 타임스탬프를 활용한 CAS(Compare-And-Swap) 연산과 지수 백오프 전략을 생각해보세요.
버전 필드 기반 CAS 연산을 사용하며, 읽기는 O(1), 쓰기는 충돌 시 재시도로 최악 O(n*r) (n은 동시 요청 수, r은 재시도 횟수)입니다. Exponential backoff with jitter를 적용해 재시도 간격을 2^n * random(0, 1000)ms로 설정하여 충돌 확률을 낮춥니다. 최대 재시도 횟수를 제한하고 그 이후는 비관적 락으로 폴백하여 기아를 방지합니다. Monotonic increasing 버전 번호를 사용해 ABA 문제를 해결하고, WHERE version = :old_version 조건으로 원자적 업데이트를 보장합니다. 충돌률이 30%를 초과하면 자동으로 비관적 락 모드로 전환하는 적응형 전략을 사용합니다.
- • 버전 기반 CAS 연산으로 O(1) 읽기, O(n*r) 최악 쓰기
- • Exponential backoff with jitter로 충돌 감소
- • 최대 재시도 후 비관적 락 폴백으로 기아 방지
- • 충돌률 기반 적응형 전략 전환
재고 관리 시스템에서 동일 상품에 대한 동시 주문 처리 시 재고 차감의 정확성을 보장하면서도 높은 처리량을 유지할 때 사용됩니다.
동시 업데이트가 빈번한 핫 레코드에서 낙관적 락의 성능이 급격히 저하될 때 어떤 대안 알고리즘을 사용하시겠습니까?
Q. 실시간 로그 분석 시스템에서 슬라이딩 윈도우 기반으로 최근 5분간의 에러율을 계산해야 합니다. 메모리 효율적이면서도 정확한 집계를 위한 알고리즘과 자료구조를 제안하고, 시간/공간 복잡도를 설명해주세요.
고정 크기 버킷과 순환 버퍼를 활용하여 O(1) 삽입과 집계를 달성하는 방법을 고려해보세요.
Tumbling window를 10초 단위 30개 버킷으로 나눈 순환 버퍼를 사용합니다. 각 버킷은 {timestamp, success_count, error_count} 구조로 O(1) 공간만 사용하며, 새 이벤트 삽입은 현재 버킷 인덱스 계산 후 카운터 증가로 O(1)입니다. 에러율 조회는 30개 버킷을 순회하며 sum(error) / sum(total)을 계산하여 O(k) (k=30, 상수)입니다. 공간 복잡도는 O(k)로 고정되어 메모리 효율적입니다. Count-Min Sketch를 추가로 사용하면 에러 타입별 빈도를 O(d) (d는 해시 함수 수) 공간으로 근사 추정할 수 있습니다. 만료된 버킷은 자동으로 덮어쓰기되어 별도 가비지 컬렉션이 불필요합니다.
- • 10초 단위 30개 버킷의 순환 버퍼로 O(1) 삽입
- • 에러율 조회는 O(k) 상수 시간
- • 공간 복잡도 O(k) 고정으로 메모리 효율적
- • Count-Min Sketch로 타입별 빈도 근사 추정
API 게이트웨이에서 실시간 에러율 모니터링과 자동 알림 트리거를 위해 지속적으로 메트릭을 집계할 때 사용됩니다.
정확도를 희생하지 않고 윈도우 크기를 1시간으로 확장할 때 메모리 사용량을 최소화하는 방법은 무엇입니까?
Q. 조직도 기반 권한 관리 시스템에서 특정 사용자가 접근 가능한 모든 하위 조직과 리소스를 조회해야 합니다. 계층이 깊고 순환 참조 가능성이 있는 그래프에서 효율적인 탐색 알고리즘과 순환 감지 방법을 설명해주세요.
DFS 기반 탐색에 방문 상태를 세 가지로 구분하여 순환을 감지하는 방법을 생각해보세요.
DFS 기반 탐색에 삼색 마킹(white, gray, black)을 사용합니다. white는 미방문, gray는 탐색 중, black은 완료를 의미하며, gray 노드를 재방문하면 순환으로 감지합니다. 시간 복잡도는 O(V+E) (V는 조직 수, E는 관계 수)이며, 공간 복잡도는 재귀 스택과 방문 맵으로 O(V)입니다. 인접 리스트로 그래프를 표현하여 메모리 효율성을 높이고, 메모이제이션으로 중복 서브트리 탐색을 O(1)로 스킵합니다. Materialized Path나 Closure Table을 사전 계산하면 조회를 O(1)로 개선할 수 있으나, 쓰기 시 O(V)의 업데이트 비용이 발생하는 트레이드오프가 있습니다. 읽기/쓰기 비율에 따라 전략을 선택합니다.
- • DFS + 삼색 마킹으로 O(V+E) 탐색과 순환 감지
- • 인접 리스트와 메모이제이션으로 효율성 향상
- • Materialized Path로 O(1) 조회 vs O(V) 업데이트 트레이드오프
- • 읽기/쓰기 비율에 따른 전략 선택
기업 ERP 시스템에서 부서 계층 구조를 기반으로 문서 접근 권한을 실시간으로 계산하고 검증할 때 사용됩니다.
수천 개의 조직이 실시간으로 변경될 때 증분 업데이트(incremental update) 알고리즘은 어떻게 설계하시겠습니까?
Q. 자동완성 기능 구현 시 수백만 개의 키워드에서 prefix 매칭을 실시간으로 수행해야 합니다. Trie 자료구조 기반 구현의 시간/공간 복잡도를 분석하고, 메모리 최적화 방법을 제시해주세요.
Trie의 기본 복잡도와 함께 압축 기법(Radix Tree, Ternary Search Tree)을 비교해보세요.
표준 Trie는 삽입/검색이 O(m) (m은 키 길이)이며, 공간 복잡도는 O(ALPHABET_SIZE * N * M) (N은 키워드 수)로 메모리 비효율적입니다. Radix Tree(Patricia Trie)로 압축하면 단일 자식 노드 체인을 압축해 공간을 O(N*M)으로 개선하되, 구현 복잡도가 증가합니다. Ternary Search Tree는 각 노드를 3방향(작음, 같음, 큼)으로 분기하여 공간을 O(N*M)으로 유지하면서 캐시 지역성을 높입니다. 빈도 기반 정렬을 위해 각 노드에 카운터를 추가하고, Top-K 조회 시 힙을 사용해 O(N + K log K) 복잡도로 인기 검색어를 추출합니다. 메모리 절약을 위해 Succinct Trie나 Double Array Trie를 사용하면 공간을 90% 이상 줄일 수 있습니다.
- • 표준 Trie O(m) 검색, O(ALPHABET_SIZE*N*M) 공간
- • Radix Tree로 O(N*M) 공간 압축
- • Ternary Search Tree로 캐시 지역성 향상
- • Succinct Trie로 90% 메모리 절약
검색 엔진이나 전자상거래 사이트의 검색창에서 사용자가 타이핑할 때마다 실시간으로 추천 키워드를 제공할 때 사용됩니다.
다국어 지원 시 유니코드 문자의 ALPHABET_SIZE가 커지는 문제를 어떻게 해결하시겠습니까?
Q. 실시간 리더보드 시스템에서 수백만 명의 사용자 점수를 관리하며, 특정 사용자의 순위를 빠르게 조회하고 점수 업데이트를 처리해야 합니다. Redis Sorted Set을 사용할 때와 자체 구현할 때의 알고리즘 복잡도를 비교 분석해주세요.
Skip List와 균형 이진 탐색 트리의 특성을 비교하고, 각각의 삽입/조회/순위 계산 복잡도를 고려해보세요.
Redis Sorted Set은 내부적으로 Skip List와 Hash Table을 결합하여 삽입/삭제/업데이트를 O(log n), 점수로 조회를 O(log n), 순위 조회를 O(log n)에 처리합니다. 자체 구현 시 AVL Tree나 Red-Black Tree를 사용하면 동일한 O(log n) 보장이 가능하나, 각 노드에 서브트리 크기를 저장해야 순위 계산이 가능합니다. Skip List는 평균 O(log n)이지만 최악 O(n)이며, 확률적 균형으로 구현이 단순합니다. Order Statistic Tree를 사용하면 k번째 요소 조회도 O(log n)으로 가능합니다. 공간 복잡도는 모두 O(n)이며, Skip List는 평균 2n 포인터, BST는 정확히 2n 포인터를 사용합니다. 동시성 환경에서는 Skip List가 Lock-free 구현에 유리합니다.
- • Redis Sorted Set: Skip List + Hash로 모든 연산 O(log n)
- • 자체 구현: AVL/Red-Black Tree + 서브트리 크기 저장
- • Skip List는 확률적 균형, Lock-free 구현 용이
- • Order Statistic Tree로 k번째 조회 O(log n)
게임 서버에서 실시간 랭킹을 표시하고 사용자가 본인의 순위를 즉시 확인할 수 있도록 할 때 사용됩니다.
점수 동점자가 많을 때 보조 정렬 기준(타임스탬프 등)을 추가하면 복잡도가 어떻게 변하나요?
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!