Baidu 면접 질문

Baidu 면접의 초점

일반적인 Baidu 면접 질문

• 정수 배열이 주어졌을 때 가장 긴 증가하는 부분 수열을 찾으세요.
  좋은 답변이 다루는 것

  • 동적 계획법(DP)을 사용하여 O(n^2) 시간 복잡도로 해결 가능
  • 이진 탐색을 활용하여 O(n log n) 시간 복잡도로 최적화 가능
  • DP 배열 dp[i]는 i번째 원소를 마지막으로 하는 LIS의 길이를 저장
  • 이진 탐색 방식에서는 tails 배열을 유지하며 각 숫자가 들어갈 위치를 찾음
  • 증가하는 부분 수열이므로 같은 값은 허용되지 않음 (strictly increasing)

  샘플 답변 보기

  가장 긴 증가하는 부분 수열(LIS) 문제는 주어진 배열에서 원소의 순서를 유지하면서 증가하는 부분 수열 중 가장 긴 것을 찾는 문제입니다. 기본적인 해결책은 동적 계획법으로, 각 위치에서 끝나는 최장 증가 부분 수열의 길이를 저장한 후 이전 원소들을 검사하여 업데이트합니다. 시간 복잡도는 O(n^2)이며 공간 복잡도는 O(n)입니다. 더 효율적인 방법은 이진 탐색을 사용하는 것으로, tails 배열을 유지하며 각 숫자가 들어갈 위치를 이진 탐색으로 찾아 업데이트합니다. 이 방법은 O(n log n) 시간에 동작합니다. 주의할 점은 tails 배열이 실제 부분 수열을 저장하는 것이 아니라 길이 정보를 위한 보조 배열이라는 것입니다. 또한 문제가 '증가'의 정의를 어떻게 하는지 확인해야 하는데, 보통은 strict increasing을 의미합니다. 아래 코드는 O(n log n) 방식을 구현한 것입니다.

  # 가장 긴 증가하는 부분 수열 (LIS) - O(n log n)
  import bisect
  
  def lengthOfLIS(nums):
      tails = []  # tails[i]는 길이 i+1인 증가 부분 수열의 마지막 원소 중 최솟값
      for num in nums:
          pos = bisect.bisect_left(tails, num)  # num이 들어갈 위치를 이진 탐색
          if pos == len(tails):
              tails.append(num)  # num이 모든 tails 원소보다 크면 추가
          else:
              tails[pos] = num   # 그렇지 않으면 해당 위치를 num으로 교체
      return len(tails)  # tails의 길이가 LIS 길이
  
  # 시간 복잡도: O(n log n), 공간 복잡도: O(n)

• 방향 그래프에서 사이클을 감지하는 함수를 구현하세요.
  좋은 답변이 다루는 것

  • DFS를 사용하여 방문 중인 노드를 추적하는 재귀 스택 활용
  • 방향 그래프에서 사이클 감지는 백 엣지(back edge) 존재 여부 확인
  • 시간 복잡도는 O(V+E)이며 각 노드와 간선을 한 번씩 방문
  • BFS를 사용한 위상 정렬(Topological Sort)로도 사이클 감지 가능
  • 재귀 구현 시 스택 오버플로우에 주의 (큰 그래프에서는 반복적 DFS 권장)

  샘플 답변 보기

  방향 그래프에서 사이클을 감지하는 가장 일반적인 방법은 DFS를 사용하는 것입니다. DFS 탐색 중 현재 노드가 '방문 중' 상태인 노드로 다시 돌아오면 사이클이 존재합니다. 이를 위해 각 노드에 세 가지 상태(미방문, 방문 중, 방문 완료)를 할당합니다. DFS를 수행하면서 방문 중인 노드를 만나면 사이클이 있는 것입니다. 시간 복잡도는 O(V+E)이며 공간 복잡도는 O(V)입니다. 또 다른 방법은 위상 정렬을 활용하는 것으로, 모든 노드의 진입 차수를 계산하여 큐에서 처리하는 방식입니다. 만약 모든 노드를 처리하지 못했다면 사이클이 있는 것입니다. 아래 코드는 DFS 기반의 사이클 감지 함수입니다. 큰 그래프에서는 재귀 대신 명시적 스택을 사용하는 것이 좋습니다.

  # 방향 그래프에서 사이클 감지 - DFS
  from collections import defaultdict
  
  class Graph:
      def __init__(self, vertices):
          self.graph = defaultdict(list)
          self.V = vertices
  
      def add_edge(self, u, v):
          self.graph[u].append(v)
  
      def _dfs_cycle(self, v, visited, rec_stack):
          visited[v] = True
          rec_stack[v] = True
  
          for neighbor in self.graph[v]:
              if not visited[neighbor]:
                  if self._dfs_cycle(neighbor, visited, rec_stack):
                      return True
              elif rec_stack[neighbor]:  # 백 엣지 발견
                  return True
  
          rec_stack[v] = False
          return False
  
      def has_cycle(self):
          visited = [False] * self.V
          rec_stack = [False] * self.V
  
          for node in range(self.V):
              if not visited[node]:
                  if self._dfs_cycle(node, visited, rec_stack):
                      return True
          return False
  
  # 시간 복잡도: O(V+E), 공간 복잡도: O(V)

• Baidu와 같은 실시간 검색 자동 완성 시스템을 설계하세요.
  좋은 답변이 다루는 것

  • 트라이트(Trie) 자료구조를 사용하여 접두사 기반 검색어 저장 및 빠른 자동 완성 제공
  • 실시간 업데이트를 위해 분산 시스템 필요 (예: Apache Kafka로 로그 수집 후 배치 처리)
  • 검색어 빈도수를 기반으로 상위 k개 추천 (예: 힙 자료구조 사용)
  • 캐싱 계층 (Redis 등)을 도입하여 인기 검색어 빠르게 제공
  • 샤딩(Sharding)을 통해 트라이를 여러 서버에 분산하여 확장성 확보

  샘플 답변 보기

  실시간 검색 자동 완성 시스템은 사용자가 입력하는 각 문자에 대해 검색어를 예측하여 보여줍니다. 핵심 요구사항은 매우 낮은 지연 시간 (수 밀리초)과 높은 가용성, 그리고 실시간 업데이트입니다. 데이터 저장소로는 트라이(Trie) 자료구조를 사용하여 접두사 기반의 빠른 검색이 가능하게 합니다. 각 노드는 문자와 함께 인기 검색어 목록을 저장할 수 있습니다. 분산 환경에서는 트라이를 여러 서버에 샤딩하여 부하를 분산합니다. 예를 들어, 첫 글자나 첫 두 글자를 기준으로 파티셔닝할 수 있습니다. 인기 검색어 순위를 유지하기 위해 각 서버는 로컬 힙을 사용하여 상위 k개를 관리하고, 주기적으로 글로벌 힙에 병합합니다. 실시간 업데이트는 사용자 검색 로그를 Kafka 같은 메시지 큐로 수집한 후, 배치 처리 또는 스트림 처리(예: Apache Flink)로 빈도수를 업데이트합니다. 또한 Redis와 같은 인메모리 캐시를 도입하여 가장 인기 있는 검색어를 빠르게 제공할 수 있습니다. 확장성을 위해 로드 밸런서를 앞에 두고, 각 서버는 독립적으로 트라이를 관리하지만 일관성 해시를 사용하여 키를 분산합니다. 장애 대비로 데이터를 복제하고, CDN을 통해 정적 콘텐츠를 캐싱합니다. 성능 최적화를 위해 자주 사용되는 접두사 결과를 캐싱하고, 트라이 노드를 압축하여 메모리 사용을 줄입니다.

• 트래픽이 많은 웹사이트를 위한 분산 캐시를 설계하세요.
  좋은 답변이 다루는 것

  • 캐시 데이터를 여러 노드에 분산 저장하기 위해 일관성 해시(Consistent Hashing) 사용
  • 데이터 복제를 통해 가용성과 내구성 확보 (예: 각 데이터를 여러 노드에 복제)
  • 캐시 미스 시 데이터베이스에서 원본 데이터를 가져와 캐시에 저장 (Cache-aside 패턴)
  • TTL(Time-To-Live)을 설정하여 오래된 데이터 자동 만료
  • 캐시 노드 추가/제거 시 데이터 재분배 최소화를 위해 가상 노드 사용

  샘플 답변 보기

  트래픽이 많은 웹사이트를 위한 분산 캐시 시스템은 데이터베이스 부하를 줄이고 응답 시간을 단축하는 것이 목적입니다. 핵심 요구사항은 높은 처리량, 낮은 지연 시간, 확장성, 그리고 일관성입니다. 일반적인 아키텍처는 클라이언트가 캐시에 데이터를 요청하고, 캐시에 없으면 데이터베이스에서 읽어와 캐시에 저장하는 Cache-aside 패턴을 사용합니다. 데이터 분산을 위해 일관성 해시(Consistent Hashing)를 사용하여 캐시 키를 여러 노드에 균등하게 분배하고, 노드 추가/제거 시 재분배되는 데이터를 최소화합니다. 가상 노드를 도입하면 더 균일한 분산이 가능합니다. 내결함성을 위해 각 데이터를 여러 캐시 노드에 복제하고, 주 복제본이 실패하면 보조 복제본이 서비스합니다. 캐시 노드는 Redis나 Memcached와 같은 인메모리 저장소를 사용하며, 필요에 따라 지속성(Persistence)을 설정할 수 있습니다. TTL을 설정하여 오래된 데이터를 자동으로 만료시키고, 만료된 데이터는 데이터베이스에서 다시 로드합니다. 또한 캐시 미스가 급증하는 Thundering Herd 문제를 방지하기 위해 Mutex나 분산 락을 사용할 수 있습니다. 모니터링을 위해 각 노드의 메모리 사용량, 히트율, 지연 시간을 수집하고, 오토스케일링을 통해 트래픽 변화에 대응합니다. 데이터베이스와 캐시 간 일관성 문제는 쓰기 시 캐시를 무효화(Invalidation)하거나 업데이트하는 전략을 사용합니다.

• L1 및 L2 정규화의 차이점과 각각을 사용해야 하는 경우를 설명하세요.
  좋은 답변이 다루는 것

  • L1 정규화는 가중치 절대값의 합을 패널티로 추가하여 희소성을 유도
  • L2 정규화는 가중치 제곱합을 패널티로 추가하여 가중치를 균일하게 감소
  • L1은 특징 선택(Feature Selection)에 유용하며, L2는 다중 공선성 완화에 효과적
  • L1은 미분 불가능 지점이 있으므로 최적화에 주의 (서브그래디언트 또는 좌표 하강 사용)
  • 일반적으로 L2가 더 안정적이지만, 많은 특징 중 관련 있는 것만 선택해야 할 때 L1 사용

  샘플 답변 보기

  L1 정규화는 가중치의 절대값 합을 손실 함수에 추가하여 가중치를 0으로 만드는 특성이 있어 특징 선택 효과가 있습니다. L2 정규화는 가중치의 제곱합을 추가하여 가중치를 0에 가깝게 만들지만 완전히 0으로 만들지는 않습니다. L1은 희소 모델이 필요할 때, 예를 들어 많은 특징 중에서 중요한 특징만 골라내야 하는 고차원 데이터에서 유용합니다. L2는 모든 특징이 어느 정도 중요하다고 생각될 때 사용하며, 특히 다중 공선성이 있는 경우 가중치를 안정화시킵니다. L1은 미분이 불가능한 점이 있기 때문에 최적화 시 서브그래디언트나 좌표 하강법을 사용해야 합니다. 반면 L2는 매끄러운 함수여서 경사 하강법 적용이 쉽습니다. 실제로는 두 정규화를 결합한 Elastic Net도 많이 사용됩니다. 하이퍼파라미터 λ는 교차 검증을 통해 선택하며, L1은 λ 값을 크게 하면 더 많은 가중치가 0이 됩니다. L2는 λ가 클수록 가중치가 더 작아집니다.

• 분류 문제에서 클래스 불균형을 어떻게 처리하시겠습니까?
  좋은 답변이 다루는 것

  • 데이터 수준 접근법: 언더샘플링, 오버샘플링 (SMOTE), 또는 합성 데이터 생성
  • 알고리즘 수준 접근법: 비용 민감 학습 (Cost-sensitive learning)이나 클래스 가중치 조정
  • 평가 지표 변경: 정확도 대신 정밀도, 재현율, F1-score, AUC-ROC 사용
  • 앙상블 기법 (예: Balanced Random Forest, EasyEnsemble) 사용
  • 데이터 불균형이 심할 경우 이상 탐지(Anomaly Detection) 문제로 접근 가능

  샘플 답변 보기

  분류 문제에서 클래스 불균형은 한 클래스가 다른 클래스에 비해 훨씬 많은 데이터를 가질 때 발생하며, 모델이 다수 클래스에 편향될 수 있습니다. 이를 해결하기 위한 방법은 크게 데이터 수준, 알고리즘 수준, 평가 지표 변경으로 나뉩니다. 데이터 수준에서는 다수 클래스 샘플을 줄이는 언더샘플링이나 소수 클래스 샘플을 늘리는 오버샘플링을 사용합니다. SMOTE는 소수 클래스의 합성 샘플을 생성하는 인기 있는 기법입니다. 알고리즘 수준에서는 손실 함수나 가중치를 조정하여 소수 클래스 오분류에 더 높은 비용을 부여하는 비용 민감 학습을 사용합니다. 예를 들어 sklearn SVM이나 로지스틱 회귀에서 class_weight='balanced'를 설정할 수 있습니다. 평가 지표로는 정확도보다 정밀도, 재현율, F1-score, AUC-ROC를 사용하는 것이 좋습니다. 또한 앙상블 기법으로 다수 클래스에서 서브샘플링하여 여러 모델을 학습하고 결합하는 Balanced Random Forest 등을 사용할 수 있습니다. 매우 심한 불균형의 경우 문제를 이상 탐지로 재정의하는 것도 고려할 수 있습니다. 중요한 점은 항상 검증 세트에서도 실제 분포를 반영하도록 유지하고, 교차 검증 시 계층 샘플링을 사용해야 한다는 것입니다.

• 빡빡한 마감 기한 아래에서 프로젝트를 전달해야 했던 경험에 대해 말씀해 주세요.
  좋은 답변이 다루는 것

  • 상황: 회사의 주요 제품 출시를 앞두고 2주 만에 새로운 기능을 추가해야 했음
  • 과제: 기존 코드와의 호환성 유지 및 성능 요구사항 충족
  • 행동: 우선순위를 명확히 하고, 팀원들과 작업 분담, 핵심 기능에 집중
  • 결과: 마감일 하루 전에 테스트 완료하고 성공적으로 출시, 사용자 피드백 긍정적
  • 배운 점: 명확한 커뮤니케이션과 집중이 중요함

  샘플 답변 보기

  제가 참여한 프로젝트에서 중요한 제품 출시를 앞두고 갑자기 새로운 기능 요청이 들어왔고, 마감 기한은 2주밖에 없었습니다. 이 기능은 기존 시스템과의 통합이 복잡하고 성능 요구사항도 까다로웠습니다. 먼저 프로젝트 관리자와 협의하여 요구사항의 우선순위를 명확히 하고, MVP 범위를 정의했습니다. 가장 핵심적인 기능에 집중하고, 부차적인 기능은 다음 릴리스로 미루기로 했습니다. 팀원들과 역할을 분담하여 저는 백엔드 구현을, 동료는 테스트와 배포 준비를 맡았습니다. 또한 매일 15분 스탠드업 미팅을 통해 진행 상황을 공유하고 장애물을 해결했습니다. 결과적으로 마감일 하루 전에 모든 테스트를 통과하고 성공적으로 배포했습니다. 출시 후 사용자들로부터 기능이 유용하다는 긍정적인 피드백을 받았습니다. 이 경험을 통해 제한된 시간 안에 집중력과 협업의 중요성을 배웠습니다.

• 팀원과 의견이 달랐던 상황과 해결 방법을 설명하세요.
  좋은 답변이 다루는 것

  • 상황: 프로젝트에서 기술 스택 선택에 대해 팀원과 의견 차이가 발생
  • 과제: 팀원은 새로운 프레임워크를 제안했지만, 저는 안정성과 학습 곡선을 고려해 기존 기술을主張
  • 행동: 각 기술의 장단점을 분석하고, PoC(Proof of Concept)를 통해 실제 성능 비교
  • 결과: 데이터를 바탕으로 팀원을 설득하여 합의 도출, 프로젝트는 성공적으로 완료
  • 배운 점: 객관적인 데이터와 존중하는 태도가 갈등 해결에 중요

  샘플 답변 보기

  이전 프로젝트에서 웹 서버 프레임워크 선택에 대해 팀원과 의견이 갈렸습니다. 팀원은 최신 비동기 프레임워크를 도입하자고 주장했지만, 저는 팀의 경험과 프로젝트의 안정성을 고려해 기존의 동기식 프레임워크를 유지하는 것이 낫다고 생각했습니다. 저는 먼저 팀원의 의견을 경청하고, 그의 제안의 장점을 인정했습니다. 그런 다음 두 프레임워크의 학습 곡선, 성능, 커뮤니티 지원, 유지보수 용이성 등을 문서로 정리했습니다. 또한 간단한 PoC를 구현하여 성능 테스트를 진행했고, 그 결과 새로운 프레임워크가 약간 더 나은 성능을 보였지만, 우리 프로젝트의 요구사항에서는 그 차이가 미미하고 학습 비용이 더 크다는 데이터를 얻었습니다. 이 데이터를 팀원과 공유하고 논의한 결과, 기존 프레임워크를 사용하기로 합의했습니다. 프로젝트는 문제 없이 완료되었고, 팀원은 의사 결정 과정에 만족했습니다. 이 경험을 통해 데이터 기반의 의사 결정과 상대방을 존중하는 커뮤니케이션이 중요하다는 것을 배웠습니다.

준비 팁

• 자료 구조와 알고리즘을 마스터하세요. 특히 동적 프로그래밍, 트리, 그래프에 중점을 둡니다. Baidu 면접에서 자주 출제됩니다.
• 분산 시스템에 대한 시스템 설계를 연습하세요. 특히 검색, 추천, 대규모 데이터 처리 맥락에서 중요합니다.
• 핵심 ML 개념(지도/비지도 학습, 과적합, 특징 선택, 모델 평가 지표)을 복습하세요.
• 화이트보드나 공유 편집기에서 버그 없는 코드를 작성하고 사고 과정을 명확히 설명할 준비를 하세요.
• Baidu의 제품(예: Baidu 검색, Apollo, DuerOS)을 연구하여 그들이 직면한 기술적 과제를 이해하세요.

자주 묻는 질문