Google 면접 질문

Google 면접의 초점

일반적인 Google 면접 질문

• 정수 배열이 주어졌을 때, 두 수의 합이 특정 타겟이 되는 인덱스를 반환하세요. (고전적인 두 수의 합 문제이지만, 여러 해결책을 요구하고 복잡성을 논의합니다.)
  좋은 답변이 다루는 것

  • 해시맵 O(n) 시간 O(n) 공간
  • 브루트 포스 O(n^2) 시간 O(1) 공간
  • 정렬 후 투 포인터 O(n log n) 시간 O(1) 공간 (공간 추가 사용 가능)
  • 중복 값 처리와 인덱스 반환 주의

  샘플 답변 보기

  두 수의 합 문제는 여러 해결책이 있습니다. 가장 효율적인 방법은 해시맵을 사용하는 것으로, O(n) 시간과 O(n) 공간이 소요됩니다. 배열을 한 번 순회하면서 각 요소의 보완값(target - nums[i])이 해시맵에 있는지 확인하고, 없으면 현재 값을 인덱스와 함께 저장합니다. 이 방법은 모든 테스트 케이스에서 안정적입니다. 브루트 포스는 이중 루프를 사용해 O(n^2) 시간이 들며 공간은 O(1)입니다. 정렬 후 투 포인터 방식은 O(n log n) 정렬 시간이 필요하고, 인덱스를 반환해야 하므로 원래 인덱스를 기억해야 하는 번거로움이 있습니다. 면접에서는 먼저 해시맵 솔루션을 제시하고, 추가 메모리를 사용할 수 없는 경우 정렬 후 투 포인터를 논의하는 것이 좋습니다. 중복 값이 있을 경우 인덱스가 유일함을 보장해야 합니다.

  def twoSum(nums, target):
      # 해시맵을 사용하여 O(n) 시간 해결
      seen = {}  # 값 -> 인덱스 매핑
      for i, num in enumerate(nums):
          complement = target - num
          if complement in seen:
              return [seen[complement], i]
          seen[num] = i
      return []  # 문제에서 항상 해가 있다고 가정

• bit.ly와 같은 URL 단축기를 설계하세요 – 데이터베이스 스키마, 해싱, 확장, 리디렉션 처리에 대해 논의하세요.
  좋은 답변이 다루는 것

  • 해싱: MD5, base62, 7자 고유 ID
  • 데이터베이스: long_url -> short_id 매핑, 인덱스
  • 리디렉션: 301 vs 302, 캐싱 (Redis)
  • 확장: 읽기/쓰기 분리, 샤딩 (ID 기준)

  샘플 답변 보기

  URL 단축기는 긴 URL을 짧은 고유 문자열로 변환하는 시스템입니다. 설계 시 고려할 핵심 요소는 해싱, 데이터베이스 스키마, 리디렉션 처리, 확장성입니다. 먼저 고유 ID를 생성하는 방법이 중요합니다. MD5와 같은 해시 함수를 사용한 후 base62 인코딩으로 7자 문자열을 만드는 것이 일반적입니다. 충돌을 방지하기 위해 데이터베이스에 존재 여부를 확인하거나, 중복 시 다른 해시를 적용하는 방법(예: salt 추가)이 필요합니다. 데이터베이스 스키마는 간단합니다: id (기본키), short_id (고유 인덱스), long_url (텍스트), created_at 등입니다. 리디렉션은 HTTP 301(영구 이동)을 사용하여 브라우저 캐싱을 유도하거나, 클릭 통계가 필요하면 302(임시 이동)를 사용합니다. 캐싱 계층(예: Redis)을 도입하여 읽기 성능을 높입니다. 확장을 위해 short_id를 기준으로 데이터베이스를 샤딩하고, 쓰기 부하가 크면 메시지 큐를 통해 비동기 처리합니다. 가용성을 위해 마스터-슬레이브 복제도 고려합니다.

• 동료와 갈등이 있었던 경험에 대해 말씀해 주세요. 어떻게 해결하셨나요? (행동 질문 – 협업과 결과에 중점을 둡니다.)
  좋은 답변이 다루는 것

  • 구체적인 상황 설명 (STAR)
  • 갈등 원인: 설계 접근 방식 차이
  • 해결: 적극적 경청, 타협, 데이터 기반 논의
  • 결과: 더 나은 설계 도출, 관계 개선

  샘플 답변 보기

  제가 이전 회사에서 새 마이크로서비스를 설계할 때 동료와 갈등을 겪은 경험이 있습니다. 상황은 모놀리식 아키텍처에서 전환하는 프로젝트였고, 동료는 점진적 리팩토링을 주장한 반면 저는 새로운 서비스를 별도로 구축하자고 제안했습니다. 제 역할은 마이크로서비스 경험이 적은 팀을 이끌어 올바른 방향을 결정하는 것이었습니다. 갈등을 해결하기 위해 먼저 동료의 우려를 경청했습니다. 그는 기존 시스템에 대한 깊은 이해와 위험 최소화를 강조했습니다. 이후 양측 접근법의 장단점을 비교하는 문서를 작성하고, 데이터 기반으로 논의했습니다. 결국 타협안을 도출했습니다: 핵심 기능은 새 서비스로 분리하되, 데이터베이스는 기존과 공유하고 API 게이트웨이를 통해 점진적으로 전환하기로 했습니다. 결과적으로 시스템 전환 위험을 줄이면서도 마이크로서비스 이점을 얻을 수 있었고, 동료와의 신뢰 관계도 강화되었습니다.

• 이진 트리를 직렬화 및 역직렬화하는 함수를 구현하세요. (null 처리, 재귀 및 반복 테스트)
  좋은 답변이 다루는 것

  • 직렬화: null 마커 사용 (예: '#')
  • 재귀적 전위 순회
  • 역직렬화: 큐 또는 인덱스 사용
  • 시간 O(n), 공간 O(n) (재귀 스택)

  샘플 답변 보기

  이진 트리 직렬화는 트리를 문자열로 변환하고, 역직렬화는 문자열을 다시 트리로 복원하는 과정입니다. null 처리를 위해 특별한 마커(예: '#')를 사용합니다. 직렬화는 재귀적 전위 순회로 구현합니다: 현재 노드의 값을 문자열에 추가하고, 왼쪽 자식과 오른쪽 자식을 재귀적으로 직렬화합니다. null 노드는 '#'으로 표시합니다. 역직렬화는 입력 문자열을 전처리하여 큐에 저장한 후, 같은 전위 순서로 재귀적으로 노드를 복원합니다. 큐에서 값을 꺼내 '#'이면 null을 반환하고, 아니면 새 노드를 생성하여 왼쪽과 오른쪽 자식을 재귀적으로 설정합니다. 시간 복잡도는 O(n)이고, 공간 복잡도는 재귀 스택 깊이로 인해 최악 O(n)입니다. 반복적 방법(스택 사용)으로도 구현 가능하지만 재귀가 더 간결합니다.

  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right
  
  class Codec:
      def serialize(self, root):
          def dfs(node):
              if not node:
                  return '#'
              # 전위 순회: 현재, 왼쪽, 오른쪽
              return str(node.val) + ',' + dfs(node.left) + ',' + dfs(node.right)
          return dfs(root)
  
      def deserialize(self, data):
          def dfs(queue):
              val = queue.popleft()
              if val == '#':
                  return None
              node = TreeNode(int(val))
              node.left = dfs(queue)
              node.right = dfs(queue)
              return node
          from collections import deque
          q = deque(data.split(','))
          return dfs(q)

• Google Maps의 실시간 교통 기능을 설계하세요 – 데이터 수집, 경로 업데이트, 수백만 사용자 처리는 어떻게 할 것인가?
  좋은 답변이 다루는 것

  • 데이터 소스: GPS, 센서, 타사 데이터
  • 데이터 수집: Kafka, 실시간 스트림 처리 (Spark/Flink)
  • 경로 업데이트: 동적 Dijkstra, 가중치 갱신
  • 확장: 캐싱, CDN, 지역별 서버, 로드 밸런싱

  샘플 답변 보기

  Google Maps 실시간 교통 기능은 대규모 데이터를 수집하고 처리하여 사용자에게 최적 경로를 제공합니다. 데이터 수집은 여러 소스에서 이루어집니다: 사용자 스마트폰의 GPS 위치 전송(익명화, 속도 추정), 도로 센서, 교통 카메라, 그리고 타사 데이터(예: 교통 당국). 이 데이터는 Kafka 같은 메시지 큐로 실시간 수집되고, Apache Flink나 Spark Streaming으로 처리됩니다. 처리 단계에서는 각 도로 세그먼트의 평균 속도와 교통 상태(원활/혼잡/정체)를 계산합니다. 경로 업데이트는 이 동적 가중치를 반영한 Dijkstra 알고리즘 변형으로 이루어집니다. 수백만 사용자를 처리하기 위해 지역별 서버 클러스터를 두고, CDN을 통해 정적 데이터를 캐싱합니다. 또한 자주 요청되는 경로는 Redis에 캐시하여 지연 시간을 줄입니다. 과부하 방지를 위해 로드 밸런서와 auto-scaling을 적용하고, 데이터 정확성을 위해 머신러닝 모델로 결측치를 보간합니다.

• 가장 자랑스러워하는 프로젝트에 대해 설명해 주세요. 당신의 역할, 도전 과제, 영향은 무엇인가요? (행동 질문 – 주인 의식과 영향력 평가)
  좋은 답변이 다루는 것

  • 구체적인 프로젝트 설명 (STAR)
  • 개인 기여: 아키텍처 설계, 핵심 모듈 구현
  • 도전 과제: 엄격한 성능 요구사항 (초당 1000 요청)
  • 영향: 사용자 대기 시간 50% 감소, 팀 생산성 향상

  샘플 답변 보기

  제가 가장 자랑스러워하는 프로젝트는 전자상거래 플랫폼의 주문 처리 시스템 재설계 프로젝트입니다. 기존 시스템은 모놀리식 구조로 확장성과 성능에 한계가 있었습니다. 제 역할은 새로운 마이크로서비스 아키텍처를 설계하고 주문 서비스를 포함한 핵심 모듈을 구현하는 것이었습니다. 가장 큰 도전 과제는 초당 1000건 이상의 주문을 처리하면서도 지연 시간을 200ms 미만으로 유지하는 것이었습니다. 해결책으로 비동기 이벤트 기반 아키텍처를 도입하고, Apache Kafka로 메시지를 전달하며, 데이터베이스 샤딩을 적용했습니다. 또한 Redis를 사용해 인벤토리와 세션 데이터를 캐싱하여 DB 부하를 줄였습니다. 결과적으로 사용자 대기 시간이 50% 감소하고, 시스템 처리량이 3배 증가했습니다. 팀 내에서 이 아키텍처 패턴이 재사용되어 여러 서비스로 확장되었고, 제 설계 결정이 회사 전체의 엔지니어링 표준에 영향을 주었습니다.

• 정수 스트림이 주어졌을 때, 어떤 시점에서든 중앙값을 찾으세요. (두 개의 힙 사용 – 최대 힙과 최소 힙)
  좋은 답변이 다루는 것

  • 두 개의 힙: 최대 힙 (작은 절반), 최소 힙 (큰 절반)
  • 밸런스 조건: 최대 힙 size >= 최소 힙 size (1 이하 차이)
  • addNum: O(log n), findMedian: O(1)
  • 중복 값 처리: 두 힙 모두 수용

  샘플 답변 보기

  정수 스트림에서 중앙값을 효율적으로 찾기 위해 두 개의 힙을 사용합니다. 최대 힙(max-heap)은 작은 절반의 수를 저장하고, 최소 힙(min-heap)은 큰 절반의 수를 저장합니다. 두 힙의 크기 차이는 최대 1로 유지합니다. 새 숫자가 추가될 때, 먼저 최대 힙에 넣고(음수로 저장하여 파이썬 heapq를 최대 힙처럼 사용) 필요시 최대 힙의 최댓값을 최소 힙으로 이동시킵니다. 그 후 두 힙의 크기를 조정하여 균형을 맞춥니다. 중앙값은 두 힙의 크기가 같을 경우 두 루트의 평균, 다를 경우 최대 힙의 루트입니다. addNum 연산은 O(log n), findMedian은 O(1)입니다. 추가 메모리는 O(n)이 필요하며, 스트림이 매우 크면 메모리 문제가 발생할 수 있습니다. 이 경우, 근사 알고리즘(예: TDigest)을 고려할 수 있습니다.

  import heapq
  
  class MedianFinder:
      def __init__(self):
          # small: 최대 힙 (음수로 저장), large: 최소 힙
          self.small = []  # max-heap
          self.large = []  # min-heap
  
      def addNum(self, num: int) -> None:
          # 최대 힙에 추가 (음수 변환)
          heapq.heappush(self.small, -num)
          # small에서 가장 큰 값을 large로 이동 (균형 유지)
          if self.small and self.large and (-self.small[0] > self.large[0]):
              val = -heapq.heappop(self.small)
              heapq.heappush(self.large, val)
          # 크기 조정: small이 large보다 2개 이상 많으면
          if len(self.small) > len(self.large) + 1:
              val = -heapq.heappop(self.small)
              heapq.heappush(self.large, val)
          # large가 많으면 small로 이동
          if len(self.large) > len(self.small):
              val = heapq.heappop(self.large)
              heapq.heappush(self.small, -val)
  
      def findMedian(self) -> float:
          if len(self.small) > len(self.large):
              return -self.small[0]
          else:
              return (-self.small[0] + self.large[0]) / 2.0

• 왜 Google인가요? Google 문화에 적합한 이유는 무엇인가요? (행동 질문 – 개인 가치를 Google의 사명과 연결)
  좋은 답변이 다루는 것

  • Google 사명: '세계의 정보를 체계화하여 모두가 접근하고 유용하게 사용할 수 있게 하는 것'
  • 개인 가치: 데이터 기반 문제 해결, 사용자 중심 디자인
  • Google 문화: 혁신, 협업, 실패로부터 배우기
  • 구체적 적합성: 이전 프로젝트에서의 경험 연결

  샘플 답변 보기

  Google에 지원하는 이유는 제 개인 가치와 Google의 사명이 일치하기 때문입니다. Google은 '세계의 정보를 체계화하여 모두가 접근하고 유용하게 사용할 수 있게 한다'는 사명을 가지고 있으며, 저는 항상 데이터와 기술을 통해 사람들의 삶을 개선하는 프로젝트에 열정을 가지고 있습니다. 예를 들어, 이전에 개발한 개방형 API는 소규모 비즈니스가 더 많은 고객에게 도달할 수 있도록 도왔습니다. 또한 Google의 문화는 혁신과 협업을 중시하며, 실패를 학습의 기회로 보는 점이 인상적입니다. 저는 제가 만든 시스템의 성능을 분석하고 반복적으로 개선하는 것을 즐깁니다. 이는 Google의 데이터 중심 접근 방식과 잘 맞습니다. 또한 대규모 분산 시스템과 머신러닝에 대한 전문성을 가지고 있어 Google의 복잡한 문제를 해결하는 데 기여할 수 있다고 믿습니다. Google에서 일하면서 더 많은 사람들에게 긍정적인 영향을 미치는 제품을 만들고 싶습니다.

준비 팁

• 화이트보드나 IDE 없이 코딩 연습: Google 면접은 종종 손으로 코드를 작성해야 하므로 평평한 표면에서 생각하고 쓰는 것에 익숙해지세요.
• 항상 소리 내어 생각하세요: 면접관은 문제 해결 과정을 보고 싶어하므로 접근 방식, 트레이드오프, 디버깅 단계를 설명하세요.
• 핵심 자료 구조를 마스터하세요: 배열, 문자열, 트리, 그래프, 해시 테이블에 집중하세요 – 대부분의 코딩 문제에 등장합니다. 시간 및 공간 복잡성에 대해 논의할 준비를 하세요.
• 확장성을 공부하여 시스템 디자인을 준비하세요: 캐싱, 로드 밸런싱, 샤딩, CAP 이론을 이해하세요. YouTube, Twitter 또는 채팅 서비스와 같은 시스템 설계를 연습하세요.
• STAR 방법으로 행동 이야기를 검토하세요: 상황, 과제, 행동, 결과를 중심으로 답변을 구성하고 Google의 리더십 원칙(예: '소신을 가지고 의견을 제시하고 헌신하라')에 맞게 조정하세요.

자주 묻는 질문