Google 코딩 인터뷰 실제 진행 과정 총정리: 리크루터 스크린부터 온사이트까지 단계별 가이드

Google 코딩 인터뷰는 실제로 어떻게 진행되는가? (모의 문제 풀이 포함)

사람들이 ‘Google 코딩 인터뷰’라고 말할 때 떠올리는 장면은 대체로 비슷하다. 흰 보드 앞에서 복잡한 그래프를 그리고, 몇 줄의 코드로 천재성을 증명해야 하는… 그런 이미지다. 하지만 실제 과정은 그보다 훨씬 구조적이며, 동시에 훨씬 인간적이다. 정답만 던져서 끝나는 시험이 아니라, 문제를 어떻게 이해하고, 어떤 순서로 생각을 정리하고, 막혔을 때 어떻게 회복하며, 코드와 설명을 얼마나 신뢰 가능하게 제시하는지를 종합적으로 본다.

이 글은 Google 코딩 인터뷰가 일반적으로 어떤 단계로 진행되는지부터 시작해, 실제로 자주 등장하는 “0/1 행렬에서 최대 정사각형 면적을 구하는 문제”를 어떻게 풀어야 하는지까지, 영상 스크립트의 모든 내용을 빠짐없이 길고 촘촘하게 정리한 롱폼 가이드다. 특히 문제 풀이 파트는 ‘처음 문제를 받았을 때’의 자연스러운 사고 흐름(질문 → 예시 확인 → 브루트포스 → 더 나은 해법 탐색 → DP 점화식 도출 → 구현 → 디버깅 → 복잡도 → 최적화) 자체가 중요한 학습 자료이므로, 그 과정의 뉘앙스까지 최대한 보존해 서술한다.

 

Google 코딩 인터뷰: 전체 프로세스의 큰 그림

 

---

1) Google 코딩 인터뷰: 전체 프로세스의 큰 그림

Google의 채용 프로세스는 대체로 몇 개의 단계로 구성된다. 첫 단계는 리크루터 스크린(Recruiter Screen)이다. 이는 흔히 ‘지원자 적합성’을 빠르게 확인하는 기본 대화로 이해할 수 있다. 지원자의 배경, 지원 동기, 역할 적합성 등을 가볍게 확인한 뒤 다음 단계로 진행할지 판단하는 관문에 가깝다.

리크루터 스크린 이후에는 1~2회의 폰 스크린(Phone Screen)이 이어질 수 있다. 이 단계는 원격으로 진행되며, 기술 질문과 행동 면접(Behavioral)이 섞여 나올 수 있다. 즉, 기술적으로 풀어내는 능력뿐 아니라 협업 방식이나 문제 상황에서의 판단을 확인하기도 한다.

폰 스크린을 통과하면 온사이트(On-site)로 초대되는 경우가 많다. 온사이트는 보통 하루 동안 4~5개의 인터뷰가 연속으로 진행되는 구조다. 말 그대로 백투백(back-to-back)으로 이어지며, 한 번의 긴 하루 안에 여러 라운드를 연달아 치르는 형태이기 때문에 집중력과 페이스 관리가 중요해진다.

 

 

 

---

2) 코딩 인터뷰의 ‘진짜 평가 포인트’: 정답만이 아니다

Google 코딩 인터뷰에서 자주 언급되는 기본 포맷은 45분이다. 보통 1~2개의 알고리즘 문제가 주어지고, 지원자는 제한된 시간 안에 다음을 동시에 수행해야 한다.

• 사고 과정을 말로 설명한다.
• 깔끔하고 읽기 쉬운 코드(clean code)를 작성한다.
• 시간/공간 복잡도(time/space complexity)를 분석한다.

 

여기서 가장 흔한 오해는 ‘정답만 맞히면 된다’는 생각이다. 실제로는 정답 여부만 보지 않는다. 어떤 방식으로 생각하는지, 어떻게 소통하는지, 막혔을 때 어떻게 접근을 수정하는지까지 평가한다. 면접관은 지원자가 ‘무엇을 알고 있는지’보다 ‘어떻게 풀어내는지’를 세밀하게 본다.

이 점이 특히 중요해지는 이유 중 하나가 Google이 구조화된 평가 방식(Structured Interviewing)을 사용한다는 설명과 맞닿아 있다. 구조화 면접은 모든 후보자가 동일한 기준(루브릭)으로 평가되도록 설계된 방식이다. 흔히 언급되는 루브릭 항목으로는 다음이 있다.

• 일반 인지 능력(General Cognitive Ability)
• 리더십(Leadership)
• 직무 관련 지식(Role-related Knowledge)
• 구글리니스(Googliness)

 

‘구글리니스’는 표현 자체가 다소 모호하게 느껴질 수 있으나, 맥락상 문화 적합성과 협업 역량에 가까운 의미로 설명된다. 팀 안에서 어떻게 협력하고, 어떤 태도로 문제를 풀며, 구성원으로서 어떻게 함께 일할 수 있는지를 본다는 관점이다.

 

 

---

3) Google 코딩 인터뷰가 까다롭게 느껴지는 이유

대형 테크 기업들의 면접 구조는 전반적으로 비슷한 면이 있다. 그러나 Google이 특히 까다롭게 느껴지는 이유는, 단순히 ‘맞는 답’을 원하지 않기 때문이다. Google은 보통 다음 세 가지를 동시에 높은 수준으로 요구하는 것으로 설명된다.

1. 최적 해법(optimal solution)
2. 깔끔한 코드
3. 명확한 커뮤니케이션

 

게다가 이 세 가지를 ‘그럭저럭’ 수준으로만 해서는 부족하고, 경쟁자들보다 더 잘해야 하는 형태로 바(bar)가 설정되어 있다는 인식이 있다. 즉, 정답을 맞히는 것만으로는 통과하기 어렵고, 해결 과정 전체의 품질이 평가 대상이 된다.

참고로 Google에는 시스템 디자인(System Design) 인터뷰도 존재하지만, 여기서는 그 부분을 다루지 않는다. 초점은 자료구조/알고리즘 기반의 문제 해결(problem solving) 유형에 맞춰져 있다.

 

 

 

---

4) 공개된 모의 코딩 인터뷰 영상: ‘입구를 보여주는 지도’

많은 사람이 놓치는 사실 중 하나로, Google이 코딩 인터뷰가 어떻게 진행되는지 보여주는 영상을 자사 YouTube 채널에 공개해 두었다는 점이 언급된다. 이는 ‘비밀’이 아니라 누구나 볼 수 있는 공개 자료이며, 실제로 어떤 흐름으로 질문이 주어지고, 어떤 식으로 질문을 되묻고, 코드가 어떻게 작성되고, 테스트와 최적화가 어떻게 이어지는지 전체 과정을 관찰할 수 있는 리소스로 소개된다.

그 영상에서는 한 Google 엔지니어가 지원자 역할을 하고, 다른 엔지니어가 면접관 역할을 맡아 모의 진행을 한다. 다만, ‘지원자 역할’이 Google 엔지니어라는 점에서 현실의 일반 지원자와는 거리감이 있을 수 있다. 그래서 동일한 문제를 ‘사전 준비 없이’ 풀어내는 과정을 보여 주는 것이 더 현실적인 학습 경험이 될 수 있다는 문제의식이 제시된다.

 

 

 

---

5) 실제 문제: 0/1 행렬에서 “좋은 땅만으로 된 최대 정사각형 면적” 찾기

5.1 문제 요약

문제는 다음과 같은 상황으로 제시된다.

• 땅은 0과 1로 이루어진 행렬(matrix)로 표현된다.
• 1은 좋은 땅, 0은 나쁜 땅이다.
• 좋은 땅이 있는 구역에서 최대 면적으로 농사를 짓고 싶다.
• 단, 농사를 짓는 구역은 ‘정사각형(square)’이어야 한다.
• 정사각형은 오직 1로만 구성되어야 한다.
• 구해야 하는 출력은 정사각형의 위치가 아니라 ‘최대 면적’이다.
• 문제에는 예시 행렬이 함께 제공된다.

 

5.2 시작부터 푸는 대신, 먼저 해야 할 일: уточ(Clarifying) 질문

코딩 테스트처럼 바로 풀이로 뛰어드는 것이 아니라, 문제를 받은 직후에는 먼저 이해를 맞추기 위한 질문이 필요하다는 흐름이 강조된다. 실제로는 다음과 같은 질문을 순서대로 던지는 형태가 자연스럽다.

• 정사각형 내부에 0이 포함될 수 있는가, 아니면 오직 1만 가능한가.
  • 답은 ‘오직 좋은 땅(1)만’이라는 조건으로 확정된다.
•  도형은 직사각형이 가능한가, 반드시 정사각형인가.
  • 답은 ‘정사각형만’으로 확정된다.
• 입력 형식은 무엇인가.
  • 2차원 배열(파이썬의 2D 리스트)로 받는다고 정리된다.
• 값의 범위는 0/1로 고정되는가.
  • 답은 ‘0과 1만’이라고 가정한다.
• 행렬 크기 및 제약은 무엇인가.
  • 정사각형인지 직사각형인지, 비어 있을 수 있는지, 크기 제한이 있는지 등을 확인한다.
  • 크기는 알 수 없고(unknown), 비어 있을 수 있다는 취지로 정리된다.
• 출력은 무엇인가.
  • 위치(좌표)가 아니라 ‘최대 면적 값’을 반환해야 한다.

 

이러한 질문은 단지 예의가 아니라, 풀이 자체를 안전하게 만드는 장치다. 요구사항을 잘못 가정하면 이후의 모든 계산과 구현이 무의미해질 수 있기 때문이다.

 

 

 

---

6) 예시로 정답을 먼저 ‘확인’하는 습관

질문이 끝났다면, 다음으로 중요한 것은 예시를 통해 문제 이해를 검증하는 단계다. 예시 행렬을 화이트보드에 직접 그려보며, 가장 큰 정사각형이 어디인지 눈으로 확인한다. 이 과정에서 예시에서는 3×3 정사각형이 가장 크며, 면적이 9라는 결론이 도출된다.

그리고 여기서 한 번 더 확인한다. 만약 더 많은 1이 모여 직사각형 형태로 더 넓은 면적이 가능해 보이더라도, 정사각형이 아니라면 정답이 될 수 없다. 즉, 문제의 핵심 제약(정사각형)을 다시 고정시키는 단계가 된다.

 

 

 

---

7) 가장 먼저 떠오르는 해법: 브루트포스, 왜 버려야 하는가

문제를 보자마자 떠올릴 수 있는 가장 단순한 방법은 완전 탐색이다. 예를 들어 행렬의 크기에서 가능한 최대 정사각형 크기를 기준으로 5×5, 4×4, 3×3 … 순서대로 가능한 모든 정사각형을 생성하고, 내부가 전부 1인지 검사하는 방식이다. 크기가 줄어들수록 후보의 수는 더 늘어나며, 각 후보를 검사하는 비용도 크다.

또 다른 방식으로는 각 칸에서 시작해, 해당 칸이 1이면 정사각형을 바깥으로 확장하며 0을 만날 때까지 검사하는 방법도 있다. 그러나 이 또한 반복 계산이 많아지고, 동일 영역을 여러 번 보게 되며 시간이 과도하게 소요된다.

이런 접근들은 ‘가능은 하지만 비효율적’이며, 더 나은 접근이 필요하다는 결론으로 이어진다.

 

 

 

---

8) DP로 전환되는 순간: “이미 계산한 것으로 더 큰 정사각형을 만든다”

8.1 0과 1의 기본 의미

• 어떤 칸이 0이면, 그 칸은 ‘전부 1로만 이루어진 정사각형’에 포함될 수 없으므로 즉시 배제된다.
• 어떤 칸이 1이면, 최소한 1×1 정사각형은 가능하므로 ‘최소 크기 1’의 기반이 된다.

 

8.2 중복 계산을 피하려면, 방향을 바꿔야 한다

정사각형을 직접 확장해서 검사하면, 한 번 확인한 영역을 다른 시작점에서 또 확인하게 된다. 그래서 더 효율적인 방식은 ‘지금까지 계산한 결과를 재사용’하는 것이다. 정사각형의 성질상, 작은 정사각형들이 먼저 성립해야 큰 정사각형이 성립한다.

 

8.3 핵심 규칙: 우하단 기준 3방향 최소값 + 1

각 칸을 “정사각형의 우하단(bottom-right) 꼭짓점”이라고 생각하면, 그 칸에서 만들 수 있는 최대 정사각형의 한 변 길이는 다음 세 방향 값에 의해 결정된다.

• 바로 위(Up): dp[i-1][j]
• 바로 왼쪽(Left): dp[i][j-1]
• 좌상단 대각선(Top-left diagonal): dp[i-1][j-1]

 

세 값 중 하나라도 작으면 더 큰 정사각형을 만들 수 없으므로 최소값을 취한다. 그리고 현재 칸이 1일 때 그 최소값에 1을 더하면 현재 칸을 우하단으로 하는 최대 정사각형의 변 길이가 된다.

• 현재 칸이 1이면:

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

 

• 현재 칸이 0이면:

dp[i][j] = 0

 

화이트보드에 실제로 값을 채워 넣으면, 특정 지점에서 2가 나타나고, 그 다음 단계에서 3이 나타난다. 그 결과 최대 변 길이가 3이 되고, 면적은 3²=9로 결정된다.

 

 

 

---

9) 구현으로 옮기는 과정: 파이썬 코드, 그리고 실제 디버깅의 흐름

이제 개념이 정리되었으니 코드로 옮긴다. 실전에서는 대략 45분 중 15~20분 정도를 개념 정리와 커뮤니케이션에 쓰고, 15분 정도에 구현을 마치고, 남은 5~10분을 최종 설명/검증/질문에 쓰는 흐름이 목표로 제시된다. 물론 이는 ‘빠르게 타이핑한다’는 의미가 아니라, 라인마다 의도를 설명하며 깔끔하게 작성하는 것을 뜻한다.

 

 

9.1 먼저 처리하는 엣지 케이스

입력이 비어 있을 수 있고, 행 또는 열 크기가 1 이하일 수 있다. 이런 경우에는 최대 정사각형 크기가 입력 크기 자체로 제한되므로, 빠르게 반환하는 로직을 둔다.

• 행 길이가 2 미만이면(0 또는 1행) 그대로 처리한다.
• 열 길이가 2 미만이면(0 또는 1열) 동일하게 처리한다.

 

구현 중에는 “len(land) < 2이면 len(land)를 반환” 같은 형태로 단순 처리하려는 시도가 등장한다. 다만 실제로는 면적 기준인지, 변 길이 기준인지에 따라 반환값을 조심해야 한다는 뉘앙스가 뒤따른다.

 

 

9.2 DP 저장 구조를 두고 벌어지는 선택: 전체 테이블 vs 2행 최적화

처음에는 공간을 줄이기 위해 “왼쪽 값 1개 + 위쪽 행 1개만 저장하면 되지 않나”라는 생각이 나온다. 그러나 구현을 진행하며, 인덱스와 갱신 순서를 고려했을 때 단순히 ‘왼쪽 하나’만으로는 충분하지 않다는 판단으로 전환된다.

그 결과 초기 구현은 DP 테이블 전체를 저장하는 방식으로 진행된다. 즉, 입력 크기 H×W에 대해 dp도 같은 크기의 2차원 배열로 만든다. 이 방식은 구현이 명확하고 디버깅이 쉬운 장점이 있다.

 

 

9.3 중간에 발생하는 ‘손코딩 감각’ 이슈와 교훈

실제 구현 과정에서는 다음과 같은 현실적인 장면이 드러난다.

• 평소 AI를 많이 쓰다 보니 손으로 코드를 타이핑하는 감각이 예전보다 무뎌진 느낌이 들 수 있다.
• 변수를 잘못 참조하거나(정의되지 않은 변수), 인덱스 조건을 약간 틀리는 작은 실수가 생길 수 있다.

 

이때 중요한 것은 ‘작은 실수가 나오는 것 자체’가 아니라, 그 실수를 어떻게 빠르게 진단하고 수정하는지다. 실제로는 실행 결과를 보며 “어떤 변수가 정의되지 않았다”는 오류를 수정하거나, 예상 출력(예: 9, 16)과 비교해 로직을 점검하는 흐름이 이어진다.

 

 

9.4 핵심 구현 로직의 형태

기본 흐름은 다음과 같다.

• 모든 칸을 순회한다.
• 현재 칸이 0이면 dp[i][j]=0으로 둔다.
• 현재 칸이 1이면, 첫 행/첫 열인지 확인한다.
  • 첫 행 또는 첫 열이면 dp[i][j]=1이다(확장할 수 없으므로 1×1만 가능).
  • 그 외에는 dp[i][j]=1+min(위, 왼쪽, 좌상단)을 적용한다.
• max_size_found(최대 변 길이)를 갱신한다.
• 최종 반환은 max_size_found * max_size_found로 면적을 반환한다.

 

구현 중에는 “세 방향 값을 리스트로 모아 min을 구한 뒤 1을 더해 현재 dp에 넣고, max를 갱신”하는 형태가 등장한다. 이후 면적이 필요하므로 마지막에 제곱 처리로 마무리한다.

 

 

9.5 테스트: 9가 나와야 하는데, 정말 9가 나오나

예시 입력으로 실행했을 때 출력이 9가 나오면, 기본 로직이 맞다는 신호가 된다. 이후 테스트를 약간 바꿔 더 큰 정사각형이 가능하도록 만든 뒤 출력이 16(4×4)으로 늘어나는지 확인한다. 다시 1을 하나 제거해 최대 정사각형이 줄어드는 상황을 만들고, 출력이 9로 되돌아오는지도 확인한다.

이런 테스트는 ‘정확성’뿐 아니라, 구현이 특정 패턴에만 맞춘 것이 아니라 일반적으로 작동한다는 신뢰를 준다.

 

 

 

---

10) 복잡도 분석: 무엇이 얼마나 걸리는가

10.1 시간 복잡도

행렬의 모든 칸을 한 번씩 본다. 각 칸에서 수행하는 작업은 상수 시간에 가깝다(세 값의 min과 max 갱신 등). 따라서 시간 복잡도는 다음으로 정리된다.

• 시간 복잡도: O(H*W)

 

또한 모든 칸을 적어도 한 번은 확인해야 하므로, 이보다 더 낮게(예: O(H+W) 같은 형태로) 일반적으로 개선하기는 어렵다는 직관도 함께 제시된다.

 

 

10.2 공간 복잡도

초기 구현이 H×W 크기의 DP 테이블을 만들면 공간 복잡도는 다음과 같다.

• 공간 복잡도: O(H*W)

 

다만 실제로는 현재 행을 계산할 때 필요한 정보가 ‘이전 행’과 ‘현재 행의 왼쪽 값’뿐이므로, 전체 DP를 저장하지 않고 2행만 유지하는 방식으로 줄일 수 있다.

• 최적화 후 공간 복잡도: O(W)

 

 

 

---

11) 공간 최적화(2행 DP): 시도, 실패, 수정, 그리고 복구

2행 최적화는 개념적으로는 간단하다. dp_prev(이전 행)와 dp_curr(현재 행)만 있으면 된다. 행을 하나 처리하고 나면 dp_curr을 dp_prev로 넘기고, 새로운 dp_curr을 0으로 초기화해 다음 행을 계산한다.

그러나 실제 구현에서는 작은 실수가 결과를 크게 망가뜨릴 수 있다.

• 처음 시도에서는 예상 결과(9 또는 16)가 아니라 1 같은 값이 나오는 문제가 발생한다.
• 이는 대개 “어느 행이 prev이고 어느 행이 curr인지” 또는 “좌상단/왼쪽 참조가 어느 배열에서 와야 하는지”가 섞였을 때 나타난다.

 

수정 과정에서는 다음이 핵심 체크포인트로 떠오른다.

• up은 이전 행의 같은 열(dp_prev[j])이어야 한다.
• left는 현재 행의 이전 열(dp_curr[j-1])이어야 한다.
• diag(좌상단)은 이전 행의 이전 열(dp_prev[j-1])이어야 한다.

 

이 참조 관계가 정확히 복구되면, 출력은 다시 16과 9처럼 기대값으로 돌아온다. 이 과정은 면접에서 “최적화를 무리하게 하다가 코드가 흔들릴 수 있다”는 현실을 보여 주면서도, 동시에 “원인 추적과 수정 능력”이 얼마나 중요한지 드러내는 사례가 된다.

또한 최적화 리팩터링 과정에서 인덱스 실수(예: 0과 1의 의미를 뒤섞거나, 참조 대상 행을 잘못 잡는 문제)가 발생할 수 있음을 인정하는 흐름이 있으며, 최종적으로는 정상 동작을 회복해 공간을 줄인 버전까지 제시하는 방향으로 정리된다.

 

 

 

---

12) 면접에서 실제로 ‘좋게 보이는’ 흐름은 무엇인가

여기까지의 전체 흐름은 단지 알고리즘을 설명하는 글이 아니라, 평가자가 보고 싶어 하는 문제 해결의 순서를 담고 있다.

• 요구사항을 명확히 하기 위한 질문을 한다.
• 예시로 이해를 검증한다.
• 단순한 해법을 떠올리되 비효율성을 설명하고 버린다.
• 더 나은 해법을 탐색하며, 중복 계산을 제거한다.
• DP 점화식을 도출한다.
• 구현하고, 테스트하고, 디버깅한다.
• 복잡도를 분석하고, 가능하면 최적화까지 논의한다.

 

이 과정에서 ‘정답’은 결과물일 뿐이며, 핵심은 사고 과정의 설계와 전달이다. 특히 “막혔을 때의 대처”가 평가에 포함된다는 점은, 디버깅과 리팩터링 과정이 단순한 실수의 기록이 아니라 실전 역량의 일부라는 메시지로 이어진다.

 

 

 

---

13) 요약: 기억해야 할 한 문장

Google 코딩 인터뷰는 “정답을 맞히는 시험”이 아니라 “문제를 이해하고 풀어내는 과정을 설득력 있게 보여주는 평가”이다.

그리고 그 과정은 크게 다르지 않다. 질문으로 출발해, 예시로 확인하고, 비효율을 걷어내고, DP로 압축한 뒤, 코드로 구현해 검증하며, 마지막에 복잡도를 설명한다. 이 흐름을 반복 연습하면, 새로운 문제도 ‘낯선 문제’가 아니라 ‘익숙한 패턴의 변주’로 보이기 시작한다.