Published on

구글 엔지니어 코딩 인터뷰 문제 JavaScript로 풀어보기

출처 : Youtube - Google Student

최근에 Google의 엔지니어 채용 과정을 보여주는 흥미로운 코딩 인터뷰 영상을 시청했습니다.

제목은 How to: Work at Google — Example Coding/Engineering Interview 인데요. 7년 전 영상이지만 구글의 소프트웨어 엔지니어 채용 과정이라는 점과 '코딩 인터뷰'라는 채용 방식이 인상깊었습니다.

제가 주로 사용하는 언어인 JavaScript로 코딩 인터뷰 문제를 풀어보며 정리한 내용과 느낀 점을 기록해봅니다.

영상 소개

이 영상은 Google 엔지니어들이 모의 면접 질문을 시연하고 Google 면접에서의 모범 사례를 강조하는 내용을 담고 있습니다.

두 명의 Google 엔지니어가 지원자 / 면접관 역할을 맡고 대화하며 화이트보드에 문제를 풀어갑니다. 문제는 아래와 같습니다.

정수 배열과 하나의 특정 정수 값 sum이 주어집니다. 정수 배열에서 합이 sum이 되는 두 수의 쌍을 찾아주세요.

지원자는 먼저 문제에 대한 명확한 이해를 위해 질문을 합니다. 그리고 면접관과 대화하며 여러 가지 접근 방식을 고려하고 화이트보드에 코드를 작성합니다.

문제 해결 과정

영상에서는 두 수의 쌍이 존재하는지 여부를 리턴하는 함수를 작성합니다. 동일하게 boolean을 리턴하도록 풀어봤습니다.

Solution 1. 배열의 모든 요소에 대해 쌍을 비교 O(n^2)

처음으로 생각해볼 수 있는 가장 간단한 접근법입니다. 비효율적이지만 직관적인 방법입니다.

function hasPairWithSum(arr, targetSum) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i; j < arr.length; j++) {
      if (arr[i] + arr[j] === targetSum) {
        return true
      }
    }
  }
  return false
}

// 테스트
console.log(hasPairWithSum([1, 2, 3, 9], 8)) // false
console.log(hasPairWithSum([1, 2, 4, 4], 8)) // true

Solution 2. 이진 탐색 O(n log n)

다음으로는 이진 탐색을 사용합니다. 배열을 순회하며 요소의 값을 sum에서 뺀 값이 배열 안에 있는지 이진 탐색으로 찾는 방법입니다.

이진 탐색은 정렬이 되어 있을 때 유효한 알고리즘이기 때문에 sort() 메서드가 선행되어야 합니다.

시간복잡도를 계산하면

  • 정렬 + (for 문 * 이진 탐색)
  • O(n log n) + (n * O(log n)) = O(n log n)

O(n log n) 입니다.

function binarySearch(arr, target, start, end) {
  while (start <= end) {
    const mid = Math.floor((start + end) / 2)
    if (arr[mid] === target) return true
    if (arr[mid] < target) start = mid + 1
    else end = mid - 1
  }
  return false
}

function findPairWithSumBinary(arr, targetSum) {
  arr.sort((a, b) => a - b)

  for (let i = 0; i < arr.length; i++) {
    const complement = targetSum - arr[i]
    if (binarySearch(arr, complement, i + 1, arr.length - 1)) {
      return true
    }
  }
  return false
}

// 테스트
console.log(findPairWithSumBinary([1, 2, 3, 9], 8)) // false
console.log(findPairWithSumBinary([1, 2, 4, 4], 8)) // true

Solution 3. 해시 셋 O(n)

해시 셋을 이용한 접근입니다. 시간복잡도 O(n)을 가지는 가장 시간 효율이 좋은 알고리즘입니다. 정렬되지 않은 배열에서도 효율적으로 작동하며, 단 한 번의 순회로 문제를 해결할 수 있습니다.

코드를 미리 설명하자면 아래와 같습니다.

  1. 배열을 한 번 순회하면서 각 숫자의 보수(targetSum - 현재 숫자)를 Set에 저장합니다.
  2. 현재 숫자가 이전에 저장된 보수 중 하나와 일치하면, 합이 targetSum이 되는 쌍을 찾은 것입니다.
function findPairWithSum(arr, targetSum) {
  const complements = new Set()

  for (const num of arr) {
    if (complements.has(num)) {
      return true
    }
    complements.add(targetSum - num)
  }

  return false
}

// 테스트
console.log(findPairWithSum([1, 2, 3, 9], 8)) // false
console.log(findPairWithSum([1, 2, 4, 4], 8)) // true

최종적으로 해시 셋을 이용한 Solution 3을 모범 답안으로 볼 수 있겠습니다.

느낀 점

  1. 문제 정의의 중요성

    문제를 완전히 이해하기 위해 명확한 질문을 하는 것이 중요함을 느꼈습니다. 실무에서도 업무를 진행하다보면 '내가 어떤 문제를 해결하려고 이걸 알아보고 있지?'하고 다른 길로 빠지는 경우가 있는데 문제 정의를 명확히하여 필요한 요구사항/문제를 빠르게 해결하는 습관을 길러야겠다고 느꼈습니다.

  2. 생각하는 과정을 말로 표현하기

    영상에서 지원자는 생각하는 과정을 계속해서 말로 표현합니다. 러버덕 디버깅과 같은 방법론도 있듯이 말로 표현하는 것이 중요하다는 것을 한 번 더 생각하게 되었습니다.

  3. 다양한 해결책을 고려하고 각각의 장단점을 설명하기

    실무에서도 업무의 해결책은 다양합니다. 상황에 따라 좋은 해결책과 비효율적이지만 일단 '되는' 해결책 등 다양한 해결책이 존재하고 우리는 여기서 최대한 좋은 선택을 해야 합니다. 장단점을 설명할 수 있을 정도로 파악하는 것이 중요하다는 것을 깨달았습니다.

  4. 예외 상황과 edge case 고려하기

    지원자도 edge case에 대해 고려하고 면접관도 아주 예리하게 edge case와 예외 상황에 대해 질문합니다. 엔지니어로서의 역량에서 매우 중요한 부분임을 알 수 있습니다.

  5. 대규모 데이터에 대한 해결책 고려하기

    결국 알고리즘 효율을 고려하는 것은 데이터 양이 많아졌을 때입니다. 실무에서도 요즘 성능 문제로 고민이 많은데, 그 동안 크게 신경쓰지 않았던 알고리즘 효율을 이제는 신경쓰며 개발해야겠다고 느꼈습니다.