Next.js 리드·아키텍트 코딩·알고리즘 면접
새 면접Q. Next.js App Router에서 수백만 개의 동적 라우트를 처리하는 대규모 서비스를 설계한다고 가정합니다. 각 페이지는 ISR로 빌드되며, 메모리 제약으로 인해 모든 캐시를 보관할 수 없습니다. LRU(Least Recently Used) 캐시 알고리즘을 직접 구현한다면 어떤 자료구조를 선택하고, 시간 복잡도는 어떻게 최적화하시겠습니까? 또한 멀티 인스턴스 환경에서 캐시 일관성을 유지하기 위한 전략도 함께 설명해주세요.
O(1) 접근을 위해서는 해시맵과 양방향 연결 리스트의 조합을 고려해보세요.
LRU 캐시는 HashMap과 Doubly Linked List를 조합하여 구현합니다. HashMap은 키-노드 매핑으로 O(1) 조회를 보장하고, Doubly Linked List는 최근 사용 순서를 유지하며 head에 최신, tail에 가장 오래된 항목을 배치합니다. get 연산 시 해당 노드를 리스트에서 제거 후 head로 이동시키고, put 연산 시 용량 초과면 tail 노드를 제거합니다. 모든 연산이 O(1) 시간 복잡도를 가지며 공간 복잡도는 O(n)입니다. 멀티 인스턴스 환경에서는 Redis를 중앙 캐시 저장소로 사용하고, 각 인스턴스는 로컬 L1 캐시를 두며 Redis Pub/Sub으로 캐시 무효화 이벤트를 브로드캐스트합니다. Stale-While-Revalidate 패턴을 적용해 캐시 미스 시에도 이전 데이터를 제공하면서 백그라운드에서 갱신하여 사용자 경험을 개선합니다.
- • HashMap과 Doubly Linked List 조합으로 O(1) 시간 복잡도 달성
- • get/put 모두 상수 시간에 처리되는 구현 전략
- • Redis 기반 중앙 캐시와 로컬 L1 캐시의 2-tier 아키텍처
- • Pub/Sub을 통한 분산 캐시 무효화 메커니즘
대규모 커머스 사이트에서 수백만 개의 상품 페이지를 ISR로 제공하면서 메모리 효율을 유지해야 할 때 사용됩니다.
LRU 대신 LFU(Least Frequently Used)를 선택해야 하는 시나리오는 무엇이며, 구현 복잡도는 어떻게 달라지나요?
Q. Next.js 프로젝트에서 복잡한 다단계 네비게이션 메뉴 구조를 렌더링해야 합니다. 메뉴 데이터는 부모-자식 관계를 가진 플랫한 배열로 API에서 제공되며, 이를 트리 구조로 변환한 후 권한에 따라 특정 노드를 필터링하고 breadcrumb를 생성해야 합니다. 이 과정에서 사용할 알고리즘 접근법과 각 단계의 시간 복잡도를 설명하고, 메모이제이션을 통한 최적화 전략을 제시해주세요.
HashMap을 활용한 O(n) 트리 구축과 DFS/BFS 선택 기준을 고려해보세요.
먼저 플랫 배열을 트리로 변환할 때 HashMap을 사용해 O(n) 시간에 처리합니다. 각 노드를 id를 키로 HashMap에 저장하고, 두 번째 순회에서 parentId를 참조해 자식 배열에 추가합니다. 권한 필터링은 DFS(깊이 우선 탐색)로 수행하며, 후위 순회로 리프부터 검사해 권한 없는 자식만 있는 부모도 제거합니다. Breadcrumb 생성은 목표 노드에서 루트까지 역방향 탐색하며 O(h) 시간이 소요됩니다(h는 트리 높이). 메모이제이션은 React.useMemo로 트리 구조를 캐싱하고, 권한이나 현재 경로가 변경될 때만 재계산합니다. 대규모 메뉴의 경우 Virtual Scrolling과 결합해 렌더링 성능을 개선하며, 서버 컴포넌트에서 초기 트리 구축을 수행해 클라이언트 부담을 줄입니다.
- • HashMap 기반 O(n) 트리 구축 알고리즘
- • 후위 순회 DFS를 통한 권한 기반 필터링
- • useMemo와 의존성 배열을 활용한 메모이제이션 전략
- • 서버 컴포넌트 활용으로 초기 연산 오프로드
대기업 ERP 시스템이나 CMS에서 수백 개의 메뉴 항목을 권한별로 동적 렌더링할 때 필수적입니다.
메뉴 구조가 실시간으로 자주 변경되는 환경에서는 어떤 데이터 구조와 알고리즘을 선택하시겠습니까?
Q. Next.js 기반 검색 기능에서 사용자가 입력하는 실시간 자동완성을 구현해야 합니다. 수만 개의 검색어 후보 중에서 prefix 매칭을 수행하는데, 단순 배열 필터링은 성능이 부족합니다. Trie 자료구조를 사용한 접근법의 시간/공간 복잡도를 분석하고, 한글 검색의 특수성(초성 검색, 자모 분리)을 어떻게 처리할지 설명해주세요.
Trie는 prefix 검색에 최적화되어 있으며, 한글은 유니코드 분해를 고려해야 합니다.
Trie 자료구조는 각 문자를 노드로 표현하며, 삽입과 검색 모두 O(m) 시간 복잡도를 가집니다(m은 검색어 길이). n개의 단어를 저장할 때 공간 복잡도는 최악의 경우 O(ALPHABET_SIZE * m * n)이지만, 공통 prefix를 공유해 실제로는 훨씬 효율적입니다. 한글 처리를 위해 입력 문자열을 Hangul.js 같은 라이브러리로 자모 단위로 분해하고, 초성 검색은 별도 Trie에 초성만 추출해 인덱싱합니다. 예를 들어 '카카오'는 'ㅋㅏㅋㅏㅇㅗ'로 분해되고, 초성 Trie에는 'ㅋㅋㅇ'으로 저장됩니다. 클라이언트에서는 debounce로 입력을 제어하고, 서버에서는 Trie 기반 검색 결과를 Redis에 캐싱해 반복 쿼리를 최적화합니다. 대용량 데이터는 Elasticsearch의 n-gram 토크나이저를 병행 사용해 퍼지 매칭도 지원합니다.
- • Trie의 O(m) 검색 시간 복잡도와 prefix 공유의 공간 효율성
- • 한글 자모 분해와 초성 검색을 위한 별도 인덱스 구축
- • debounce와 Redis 캐싱을 통한 실시간 검색 최적화
- • Elasticsearch n-gram과의 하이브리드 접근
쿠팡이나 네이버 쇼핑 같은 검색 중심 서비스에서 실시간 자동완성 기능을 구현할 때 사용됩니다.
Trie 대신 Ternary Search Tree를 사용하면 어떤 장단점이 있나요?
Q. Next.js 대시보드에서 수십만 건의 실시간 이벤트 로그를 처리하며, 사용자는 다양한 기준(시간, 우선순위, 심각도)으로 정렬하고 상위 N개만 표시합니다. 전체 데이터를 정렬하면 비효율적이므로 Top-K 문제로 접근하려 합니다. Min Heap을 사용한 알고리즘의 시간 복잡도를 분석하고, 정렬 기준이 동적으로 변경될 때의 처리 전략과 Virtual Scrolling 통합 방안을 제시해주세요.
Min Heap을 사용하면 전체 정렬 없이 Top-K를 O(n log k)에 찾을 수 있습니다.
Top-K 문제는 크기 k의 Min Heap을 유지하며 O(n log k) 시간 복잡도로 해결합니다. 각 이벤트를 순회하며 힙 크기가 k 미만이면 삽입하고, k에 도달한 후에는 현재 원소가 힙의 최솟값보다 크면 최솟값을 제거하고 삽입합니다. 이는 O(n log n) 전체 정렬보다 효율적이며 공간 복잡도는 O(k)입니다. 정렬 기준 변경 시 기존 힙을 폐기하고 새로운 비교 함수로 힙을 재구성하며, 이때 이미 필터링된 데이터셋에 대해서만 수행해 비용을 줄입니다. Virtual Scrolling과 통합할 때는 초기 k개를 렌더링하고, 스크롤 이벤트로 추가 배치를 lazy load하되 IntersectionObserver로 뷰포트 진입을 감지합니다. 서버에서는 Streaming SSR로 초기 k개를 우선 전송하고, 나머지는 클라이언트에서 점진적으로 fetch합니다. Redis Sorted Set을 활용하면 서버 측에서도 효율적인 Top-K 쿼리가 가능합니다.
- • Min Heap 기반 O(n log k) Top-K 알고리즘
- • 동적 정렬 기준 변경 시 필터링된 데이터셋 재활용
- • Virtual Scrolling과 IntersectionObserver 통합
- • Streaming SSR과 Redis Sorted Set 활용
모니터링 대시보드에서 수백만 개의 로그 중 심각도 높은 상위 100개만 실시간으로 표시할 때 필수적입니다.
실시간 스트리밍 데이터에서 Top-K를 유지하려면 어떤 알고리즘을 사용해야 하나요?
Q. Next.js 프로젝트의 빌드 최적화를 위해 모듈 간 의존성 그래프를 분석하려 합니다. 순환 의존성을 탐지하고, 빌드 순서를 결정하며, 병렬 빌드 가능한 모듈 그룹을 식별해야 합니다. 이 문제를 해결하기 위한 그래프 알고리즘 접근법(순환 탐지, 위상 정렬, 병렬화)을 설명하고, 각각의 시간 복잡도와 구현 시 주의할 점을 제시해주세요.
DFS로 순환을 탐지하고, 위상 정렬로 빌드 순서를 결정하며, 레벨별 그룹화로 병렬화합니다.
순환 의존성 탐지는 DFS에 방문 상태(unvisited, visiting, visited)를 추가해 O(V+E) 시간에 수행합니다. visiting 상태 노드를 재방문하면 순환으로 판단하며, 백엣지를 추적해 순환 경로를 추출합니다. 빌드 순서는 Kahn's Algorithm이나 DFS 기반 위상 정렬로 O(V+E)에 결정되며, 진입 차수가 0인 노드부터 큐에 넣고 처리하면서 후속 노드의 진입 차수를 감소시킵니다. 병렬 빌드는 위상 정렬 결과를 레벨별로 그룹화하며, 같은 레벨의 노드들은 의존성이 없어 동시 빌드 가능합니다. 구현 시 주의점은 동적 import로 인한 런타임 의존성은 정적 분석으로 감지 어려우므로 webpack/Turbopack의 dependency graph API를 활용하고, pnpm workspace나 turborepo의 task scheduling과 통합해 실제 빌드 파이프라인에 적용합니다. 대규모 모노레포에서는 affected graph만 추출해 증분 빌드를 최적화합니다.
- • DFS 기반 O(V+E) 순환 의존성 탐지와 백엣지 추적
- • Kahn's Algorithm을 활용한 위상 정렬과 빌드 순서 결정
- • 레벨별 그룹화를 통한 병렬 빌드 모듈 식별
- • webpack/Turbopack API와 turborepo 통합 전략
대규모 모노레포에서 수백 개의 패키지 빌드 순서를 최적화하고 CI/CD 시간을 단축할 때 사용됩니다.
동적 import가 많은 프로젝트에서 정적 분석의 한계를 어떻게 보완하시겠습니까?
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!