Next.js 리드·아키텍트 코딩·알고리즘 면접
새 면접Q. Next.js 기반 콘텐츠 관리 시스템에서 사용자가 작성한 마크다운 문서 간의 유사도를 측정하여 중복 콘텐츠를 탐지해야 합니다. 수천 개의 문서가 있고, 각 문서는 수 KB의 텍스트를 포함합니다. Levenshtein Distance를 사용하면 O(n*m)의 시간 복잡도로 인해 비효율적입니다. 대규모 문서 비교를 위한 효율적인 알고리즘 접근법(MinHash, SimHash, N-gram 기반)을 설명하고, 각 방법의 시간/공간 복잡도와 정확도 트레이드오프를 비교한 후, 실시간 중복 탐지를 위한 구현 전략을 제시해주세요.
정확한 문자열 매칭 대신 해시 기반 근사 알고리즘을 고려하고, 차원 축소를 통한 비교 효율화 방법을 생각해보세요.
MinHash는 Jaccard 유사도를 추정하는 방법으로 문서를 N-gram으로 분해한 후 여러 해시 함수로 시그니처를 생성하며, O(n*k) 복잡도로 비교가 가능합니다. SimHash는 문서를 고정 길이 비트 벡터로 변환하여 Hamming Distance로 유사도를 측정하며, O(1) 공간에 시그니처를 저장할 수 있습니다. N-gram 기반 접근은 토큰화 후 집합 연산으로 유사도를 계산하며, 인덱싱을 통해 후보군을 먼저 필터링할 수 있습니다. 실시간 탐지를 위해서는 LSH(Locality Sensitive Hashing)를 활용하여 유사한 문서를 같은 버킷에 매핑함으로써 전체 비교 없이 O(1)에 가까운 조회가 가능합니다. 구현 시 문서 길이에 따른 N-gram 크기 조정, 해시 함수 개수와 정확도의 균형, 그리고 증분 업데이트를 위한 인덱스 구조 설계가 핵심입니다.
- • MinHash는 Jaccard 유사도 추정으로 O(n*k) 복잡도를 가지며 확률적 정확도를 제공
- • SimHash는 고정 길이 비트 벡터로 변환하여 Hamming Distance 기반 비교 가능
- • LSH를 활용하면 유사 문서를 같은 버킷에 매핑하여 전수 비교 없이 후보군 필터링
- • N-gram 크기, 해시 함수 개수, 버킷 수는 정확도와 성능의 트레이드오프 결정
대규모 콘텐츠 플랫폼에서 표절 탐지, 유사 문서 추천, 중복 제거 시스템 구축에 활용됩니다.
LSH의 버킷 수와 해시 함수 개수를 결정하는 이론적 근거와, False Positive Rate를 낮추기 위한 Multi-Probe LSH 전략을 설명해주세요.
Q. Next.js 기반 동영상 스트리밍 플랫폼에서 사용자의 네트워크 대역폭에 따라 최적의 비디오 청크 품질 조합을 선택해야 합니다. 각 청크는 여러 품질(해상도)로 인코딩되어 있으며, 품질마다 파일 크기와 사용자 만족도가 다릅니다. 전체 재생 시간 동안 버퍼링 없이 최대 만족도를 달성하는 품질 조합을 찾는 문제입니다. 이를 Knapsack Problem의 변형으로 접근할 때, 0/1 Knapsack과 Unbounded Knapsack의 차이를 설명하고, 동적 계획법을 사용한 해결 방법의 시간/공간 복잡도를 분석한 후, 실시간 스트리밍 환경에서 적용 가능한 최적화 전략을 제시해주세요.
각 청크는 한 번만 선택되며, 대역폭 제약은 배낭의 용량으로, 만족도는 가치로 모델링할 수 있습니다.
이 문제는 각 청크를 정확히 한 번씩 선택해야 하므로 0/1 Knapsack 변형에 해당하며, Unbounded Knapsack(아이템을 무한히 선택 가능)과 달리 각 청크의 품질은 중복 선택이 불가능합니다. 동적 계획법으로 dp[i][w]를 i번째 청크까지 고려했을 때 대역폭 w 이하에서의 최대 만족도로 정의하면, O(n*W) 시간 복잡도와 O(n*W) 공간 복잡도를 가집니다. 공간 최적화를 위해 1차원 배열로 축소하면 O(W) 공간으로 줄일 수 있습니다. 실시간 스트리밍에서는 미래 대역폭 예측의 불확실성 때문에 Sliding Window 방식으로 다음 N개 청크만 고려하고, 대역폭 변화를 실시간 모니터링하여 재계산하는 Adaptive Bitrate 전략이 필요합니다. 또한 Greedy 휴리스틱(현재 대역폭에서 가능한 최고 품질 선택)과 DP를 결합하여 계산 비용을 줄이면서도 준최적 해를 빠르게 찾을 수 있습니다.
- • 0/1 Knapsack은 각 아이템을 한 번만 선택하며, O(n*W) 시간/공간 복잡도
- • 공간 최적화를 통해 1차원 배열로 O(W) 공간으로 축소 가능
- • 실시간 환경에서는 Sliding Window로 계산 범위를 제한하고 대역폭 변화에 적응
- • Greedy 휴리스틱과 DP 결합으로 준최적 해를 빠르게 계산
Netflix, YouTube 등의 적응형 비트레이트 스트리밍(ABR) 알고리즘 구현에 활용됩니다.
대역폭 예측이 부정확할 때 발생하는 버퍼링 리스크를 최소화하기 위한 확률적 DP 접근법과, Look-ahead 전략의 효과를 설명해주세요.
Q. Next.js 기반 소셜 네트워크 서비스에서 사용자 A와 B 사이의 관계 강도를 측정하여 친구 추천 기능을 구현해야 합니다. 사용자는 노드, 관계는 가중치가 있는 간선으로 표현되며, 수백만 명의 사용자가 있습니다. 단순 BFS로 최단 경로를 찾으면 O(V+E)이지만, 가중치를 고려해야 하므로 Dijkstra를 사용하면 O((V+E)logV)입니다. 대규모 그래프에서 모든 사용자 쌍에 대해 계산하는 것은 비현실적입니다. 이 문제를 해결하기 위한 알고리즘 접근법(양방향 BFS, Landmark 기반 근사, Graph Embedding)을 비교하고, 각 방법의 시간 복잡도와 정확도 트레이드오프를 설명한 후, 실시간 추천을 위한 사전 계산 및 증분 업데이트 전략을 제시해주세요.
전체 그래프 탐색 대신 지역적 탐색, 사전 계산된 랜드마크 거리, 또는 저차원 임베딩을 활용하는 방법을 고려하세요.
양방향 BFS는 시작점과 목표점에서 동시에 탐색하여 탐색 공간을 O(b^(d/2))로 줄이며, 가중치가 없거나 균일한 경우 효과적입니다. Landmark 기반 접근은 그래프에서 k개의 랜드마크 노드를 선정하고 모든 노드와의 거리를 사전 계산하여 삼각 부등식으로 근사 거리를 O(k)에 추정하며, 정확도는 랜드마크 선택에 의존합니다. Graph Embedding(Node2Vec, DeepWalk)은 노드를 저차원 벡터 공간에 매핑하여 유사도를 벡터 거리로 계산하며, 학습은 O(|walks|*length)이지만 추론은 O(1)로 매우 빠릅니다. 실시간 추천을 위해서는 주기적으로 Embedding을 재학습하고, 새로운 관계 추가 시 영향받는 노드만 증분 업데이트하는 전략이 필요합니다. 또한 2-hop 이웃으로 탐색 범위를 제한하고 관계 강도로 우선순위를 두어 계산량을 줄일 수 있습니다.
- • 양방향 BFS는 탐색 공간을 O(b^(d/2))로 줄이지만 가중치 그래프에는 부적합
- • Landmark 기반 방법은 O(k) 시간에 근사 거리 계산 가능하나 정확도는 랜드마크 선택에 의존
- • Graph Embedding은 학습 후 O(1) 추론이 가능하며 대규모 그래프에 적합
- • 증분 업데이트와 탐색 범위 제한으로 실시간 처리 가능
LinkedIn의 People You May Know, Facebook의 친구 추천 시스템에서 활용됩니다.
Graph Embedding의 Random Walk 기반 학습에서 walk length와 context window 크기가 임베딩 품질에 미치는 영향을 설명하고, Skip-gram 모델의 역할을 설명해주세요.
Q. Next.js 기반 전자책 플랫폼에서 수십만 권의 책을 사용자 선호도, 평점, 출판일 등 복합 기준으로 정렬해야 합니다. 정렬 기준은 사용자가 동적으로 변경할 수 있으며, 결과는 페이지네이션되어 제공됩니다. QuickSort, MergeSort, HeapSort의 시간/공간 복잡도와 안정성을 비교하고, 복합 정렬 기준을 효율적으로 처리하는 Comparator 설계 원칙을 설명해주세요. 또한 부분 정렬만 필요한 경우(Top 100 결과만 표시) Partial Sorting 최적화 전략과, 정렬 결과를 캐싱할 때 무효화 조건을 어떻게 설정할지 제시해주세요.
전체 정렬이 아닌 부분 정렬 알고리즘과, 정렬 기준의 우선순위 처리 방법을 고려하세요.
QuickSort는 평균 O(nlogn), 최악 O(n^2)이며 불안정 정렬이고 O(logn) 스택 공간을 사용합니다. MergeSort는 항상 O(nlogn)이며 안정 정렬이지만 O(n) 추가 공간이 필요합니다. HeapSort는 O(nlogn) 보장에 O(1) 공간이지만 불안정하고 캐시 지역성이 낮습니다. 복합 정렬을 위한 Comparator는 우선순위가 높은 기준부터 비교하고, 같을 경우 다음 기준으로 진행하는 체이닝 방식으로 설계합니다. Top-K 문제는 Min Heap을 사용하여 O(nlogk) 복잡도로 해결하거나, QuickSelect로 O(n) 평균 시간에 k번째 요소를 찾은 후 부분 정렬할 수 있습니다. 캐싱 시에는 정렬 기준 조합을 키로 사용하고, 책 데이터 변경(평점 업데이트, 신규 출판) 시 영향받는 캐시만 선택적으로 무효화하며, TTL을 설정하여 시간 기반 만료도 적용합니다.
- • QuickSort는 평균 O(nlogn)이나 최악 O(n^2), MergeSort는 O(nlogn) 보장과 안정성 제공
- • 복합 정렬은 Comparator 체이닝으로 우선순위 기준 순차 비교
- • Top-K는 Min Heap O(nlogk) 또는 QuickSelect O(n)로 최적화
- • 캐시 무효화는 데이터 변경 영향 범위와 TTL 기반으로 설정
Amazon, 교보문고 등 전자상거래 플랫폼의 상품 정렬 및 필터링 기능에 활용됩니다.
JavaScript의 Array.sort()가 V8 엔진에서 TimSort를 사용하는 이유와, TimSort가 실제 데이터에서 O(nlogn)보다 빠른 성능을 보이는 원리를 설명해주세요.
Q. Next.js 기반 지도 서비스에서 사용자 주변의 가장 가까운 K개 매장을 찾아야 합니다. 수백만 개의 매장 좌표가 있으며, 사용자 위치는 실시간으로 변경됩니다. 단순 선형 탐색은 O(n)으로 비효율적이며, 모든 거리를 계산 후 정렬하면 O(nlogn)입니다. K-D Tree를 사용한 최근접 이웃 탐색의 평균/최악 시간 복잡도를 분석하고, 2차원 공간에서 트리 구축과 탐색 알고리즘을 설명해주세요. 또한 고차원에서 K-D Tree의 성능 저하(Curse of Dimensionality) 문제와, 대안으로 Ball Tree나 Locality Sensitive Hashing을 사용하는 경우의 트레이드오프를 비교해주세요.
공간을 재귀적으로 분할하는 자료구조와, 차원이 증가할 때 탐색 효율이 변하는 이유를 고려하세요.
K-D Tree는 공간을 축 기준으로 재귀적으로 분할하여 평균 O(logn) 시간에 최근접 이웃을 탐색하지만, 최악의 경우(불균형 트리) O(n)이 될 수 있습니다. 트리 구축은 중앙값을 기준으로 분할하여 O(nlogn) 시간이 소요되며, 탐색 시 현재 노드와 거리를 계산하고 분할 평면과의 거리를 비교하여 가지치기를 수행합니다. K개 최근접 이웃은 Max Heap을 유지하며 탐색하여 O(klogn) 복잡도로 찾을 수 있습니다. 고차원(d>20)에서는 분할 효율이 떨어져 거의 모든 노드를 방문하게 되어 O(n)에 가까워지는 Curse of Dimensionality가 발생합니다. Ball Tree는 하이퍼스피어로 공간을 분할하여 고차원에서 더 나은 성능을 보이며, LSH는 근사 탐색으로 O(1)에 가까운 조회가 가능하나 정확도를 일부 희생합니다. 실무에서는 2D 좌표이므로 K-D Tree가 적합하며, 매장 위치 변경 시 증분 업데이트 전략이 필요합니다.
- • K-D Tree는 평균 O(logn) 탐색이나 불균형 시 O(n), 구축은 O(nlogn)
- • 분할 평면 거리 비교로 가지치기하여 탐색 공간 축소
- • 고차원에서는 Curse of Dimensionality로 성능 저하, Ball Tree나 LSH가 대안
- • 2D 공간에서는 K-D Tree가 효율적이며 Max Heap으로 K개 유지
배달의민족, 카카오맵 등 위치 기반 서비스에서 주변 매장 검색에 활용됩니다.
R-Tree와 K-D Tree의 차이점을 설명하고, 범위 쿼리(특정 반경 내 모든 매장 검색)에서 어느 자료구조가 더 적합한지 비교해주세요.
Q. Next.js 기반 일정 관리 시스템에서 N명의 참석자가 모두 참석 가능한 회의 시간을 찾아야 합니다. 각 참석자는 여러 개의 불가능한 시간대를 가지며, 회의는 연속된 M시간이 필요합니다. 가능한 모든 시간대를 찾는 문제를 백트래킹으로 접근할 때, 탐색 공간을 줄이기 위한 가지치기 전략과 제약 조건 전파(Constraint Propagation) 기법을 설명해주세요. 또한 이 문제의 시간 복잡도를 분석하고, 참석자 수와 시간 슬롯 수가 증가할 때 현실적으로 해결 가능한 범위와 휴리스틱 최적화 방안을 제시해주세요.
모든 조합을 시도하기 전에 명백히 불가능한 경우를 먼저 제거하고, 제약이 가장 강한 참석자부터 고려하세요.
백트래킹은 가능한 시간대를 순차적으로 시도하며 제약 위반 시 즉시 되돌아가는 방식으로, 최악의 경우 O(T^M) 시간 복잡도를 가집니다(T는 전체 시간 슬롯 수). 가지치기 전략으로는 먼저 모든 참석자의 불가능 시간대를 합집합하여 후보군을 필터링하고, 연속 M시간을 만족하지 못하는 구간은 조기에 제외합니다. 제약 조건 전파는 한 시간 슬롯이 선택되면 연관된 제약을 즉시 업데이트하여 탐색 공간을 동적으로 축소하는 기법입니다. 참석자 수가 10명 이상, 시간 슬롯이 수백 개를 넘으면 완전 탐색은 비현실적이므로, 가장 제약이 많은 참석자(불가능 시간이 많은)부터 우선 고려하는 MRV(Minimum Remaining Values) 휴리스틱을 적용합니다. 또한 탐욕적 접근으로 가장 많은 참석자가 가능한 시간대를 우선 선택하거나, 시간을 블록 단위로 그룹화하여 탐색 공간을 줄일 수 있습니다.
- • 백트래킹은 제약 위반 시 조기 되돌아가며 최악 O(T^M) 복잡도
- • 불가능 시간 합집합 필터링과 연속성 검사로 가지치기
- • 제약 조건 전파로 선택 즉시 관련 제약 업데이트하여 탐색 공간 축소
- • MRV 휴리스틱으로 제약 많은 참석자 우선 고려, 탐욕적 접근으로 최적화
Google Calendar, Outlook의 회의 시간 자동 제안 기능에 활용됩니다.
CSP(Constraint Satisfaction Problem)의 관점에서 Arc Consistency 알고리즘이 탐색 전 제약을 사전 처리하는 원리와, Forward Checking과의 차이를 설명해주세요.
Q. Next.js 기반 실시간 모니터링 대시보드에서 최근 N초 동안의 API 요청 수를 카운트하여 Rate Limiting을 구현해야 합니다. 요청은 밀리초 단위 타임스탬프와 함께 도착하며, 매 요청마다 현재 윈도우 내 요청 수를 O(1) 시간에 계산해야 합니다. 고정 윈도우(Fixed Window)와 슬라이딩 윈도우(Sliding Window) 방식의 차이를 설명하고, 슬라이딩 윈도우를 효율적으로 구현하기 위한 자료구조(Circular Buffer, Deque)와 알고리즘을 제시해주세요. 또한 메모리 사용량을 제한하면서도 정확도를 유지하기 위한 근사 알고리즘(Sliding Window Log vs Counter) 트레이드오프를 비교해주세요.
시간에 따라 만료되는 데이터를 효율적으로 제거하고, 윈도우 경계를 동적으로 관리하는 자료구조를 고려하세요.
고정 윈도우는 시간을 고정된 구간으로 나누어 각 구간의 카운트를 저장하며 O(1) 공간과 시간이지만, 윈도우 경계에서 버스트 트래픽을 정확히 감지하지 못합니다. 슬라이딩 윈도우는 현재 시점 기준 정확히 N초 이전까지의 요청을 카운트하여 더 정확하지만, 모든 타임스탬프를 저장하면 O(k) 공간이 필요합니다(k는 윈도우 내 요청 수). Deque를 사용하면 윈도우 밖으로 나간 요청을 앞에서 제거하고 새 요청을 뒤에 추가하여 O(1) 상각 시간에 처리할 수 있습니다. Sliding Window Counter는 시간을 작은 버킷으로 나누고 가중 평균으로 근사하여 O(1) 공간으로 줄이지만, 버킷 크기에 따라 정확도가 달라집니다. Circular Buffer는 고정 크기 배열로 메모리를 제한하며, 오래된 데이터를 덮어쓰는 방식으로 구현할 수 있습니다. 실무에서는 정확도 요구사항에 따라 Sliding Window Log(정확하지만 메모리 많음)와 Counter(근사이지만 메모리 적음)를 선택합니다.
- • 고정 윈도우는 O(1) 공간/시간이나 경계 버스트 미감지, 슬라이딩은 정확하나 O(k) 공간
- • Deque로 만료 요청 제거와 신규 추가를 O(1) 상각 시간에 처리
- • Sliding Window Counter는 버킷 가중 평균으로 O(1) 공간에 근사
- • 정확도와 메모리 트레이드오프에 따라 Log 방식과 Counter 방식 선택
API Gateway의 Rate Limiting, DDoS 방어, 사용자별 요청 제한 기능에 활용됩니다.
Token Bucket과 Leaky Bucket 알고리즘을 Rate Limiting에 적용할 때의 차이점과, 각각이 버스트 트래픽을 처리하는 방식을 설명해주세요.
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!