Medium - Solving Google’s 2020 Most Frequently Asked Whiteboarding Question

05 Feb 2020 in Trend

원문 - Joey Colon

Trend 파악을 위한 Medium 기고문 포스팅 - 2020년 구글 면접 질문 풀어보기; 구글 코딩 인터뷰에서 가장 흔하게 물어보는 문제를 깊게 파고들어 봅시다.

만약 여러분의 새해목표가 큰 테크 기업으로 가는 것이 목적이고 알고리즘 인터뷰를 해본적이 없다면 운이 좋으십니다. 이 포스트를 클릭 하셨으니까요, 기술 인터뷰는 보통 1~2개의 알고리즘 문제에 대해서 1시간 동안 풀게되며 구글에서는 45분간 인터뷰를 하게 됩니다. 이 포스트에서는 UMPIRE 방법을 활용한 2020년 구글 화이트 보드 질문에 가장 많이 나온 것을 다뤄볼 것입니다. 그럼 시작하겠습니다.

Problem Statement

정수 배열과 목표 숫자가 주어졌을 때 배열의 두개의 숫자를 합하여 목표 숫자를 만드는 인덱스를 리턴하십시오. 모든 입력값에 대해서 정확히 1개의 정답이 존재하며 같은 배열 원소를 두번 사용할 수 없습니다.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Understanding the Problem

문제는 꽤나 명백해 보입니다. layman의 관점에서 우리는 배열 안에서 2개를 골라서 합했을 때 목표 숫자가 나오는 원소들을 찾으려고 합니다. 그러나 같은 원소를 두개 쓸 수 없죠. UMPIRE 단계에서 테스트 케이스를 만들어보고 정답에 어떻게 접근 할 수 있는지 생각해봤습니다.

우리에게 주어진 예제를 생각해 보면 위의 예제도 괜찮은 것 같습니다. 그러나 예외의 케이스를 생각 해야합니다. 두개의 배열 모두가 오름차순으로 정렬되어 있기 때문에 정렬되어 있지 않을 때도 접근법이 참일지 고려해야 합니다. 이 질문이 제가 면접관에게 받았던 질문으로 정렬 순서에 따라 알고리즘의 복잡도가 급격하게 바뀌게 됩니다. 이 문제에서 면접관들은 우리에게 배열의 정렬을 장담할 수 없다고 알려줍니다. 우리의 예제를 한번 바꿔봅시다.

주어진 예제에 대하여 강조하고 싶은 또 하나의 포인트는 배열 안의 모든 요소가 중복되지 않는 다는 것입니다. 주어지는 배열의 원소가 모두 중복되지 않을까요? 다른 말로하면 [1,1,3,3]이 유효한 입력값일 까요? 결과 값으로 동일한 인덱스를 사용하지 않는다는 것은 알고있지만 질문에서는 원소가 중복되어 사용되어도 되는지는 명확하지 않습니다. 그럼 이런 것들을 고려해서 접근방법 들을 알아봅시다.

저에게 가장 먼저 떠오른 접근법은 i번째 인덱스를 가지고 나머지 모든 인덱스의 값들을 더하는 것이었습니다. arr[i] + arr[other_index] = target

이러한 접근법으로 0번째 인덱스에서는 다음과 같이 시행될 것입니다.

이 접근법은 잘 동작합니다. 각 인덱스에 대해서 값이 목표 숫자를 만족하는지 체크하면 됩니다. 이 접근법의 문제는 배열이 매우 클 때를 생각해봐야 한다는 것입니다. 각 인덱스에 대해서 모든 배열을 순회하며 체크하기 때문에 O(N)의 복잡도가 생기게 됩니다. 그렇기 때문에 총 복잡도는 O(N^2)이 됩니다. 이것보다 더욱 빠른 방법을 한번 생각해 봅시다.

Matching the Problem

이전 접근법에서는 데이터 구조를 활용하지 않았고 매우 느리게 동작했습니다. 왜 그럴까요? 이전 순회에서 방문했던 인덱스를 또 방문했기 때문에 필요없는 연산을 수행했기 때문입니다.

배열이 정렬되지 않았기 때문에 우리는 최소한 한번은 모든 배열의 인덱스를 방문해서 배열의 인덱스가 실제로 들고 있는 값을 조회 해야합니다. 그렇기 때문에 배열의 값을 나타내는 다른 데이터 구조를 활용해야합니다. 이상적으로는 빠르게 원소가 존재하는지 아닌지 구분하는 데이터 구조여야 할 것입니다. 배열에 특정 원소가 있는지 알아보려면 우리는 전체 배열을 순회해야 하고 이것이 각 순회를 느리게 만드는 것이죠. 알고리즘을 더욱 빠르게 하기위해 저는 해시테이블 쓰는 것을 생각해냈습니다.

해시테이블은 키-값 쌍의 데이터 구조입니다. 일반적으로 상수시간에 키가 있는지 알아낼 수 있습니다. 문제 정의에서 우리는 목표 숫자를 만들어 낼 수 있는지 알아내고 싶기 때문에 배열의 인덱스와 값을 매핑할 것입니다.

Planning the Solution

이번에는 우리의 알고리즘이 어떤 것을 하는지 글로 풀어서 써볼 것입니다. 여기에서는 우리가 영향을 주려는 헬퍼클래스도 포함되어야 하며 이런 모듈 접근법을 코딩에 활용해서 실무에서 시간을 절약할 수 있다는 것을 기억하세요.

처음으로 해야할 것은 배열의 값과 매핑된 키를 가지는 해시테이블을 만드는 것입니다. 해시테이블의 키의 값은 배열의 인덱스가 어떤 값을 가지고 있는지 나타냅니다.

그래서 위의 예제를 예로들자면 우리의 해시테이블은 다음과 같을 것입니다.

{
  '1': 1,
  '2': 0,
  '3': 3,
  '4': 2
}

이렇게 초기화를 하고 난 다음에는 뭘 해야 할까요? 실제로 배열을 한번더 지나가면서 우리의 해시테이블에 목표 숫자가 있는지 확인해야 합니다. 다른말로 하자면 target - arr[i]가 존재하는지 확인하는 것이죠. 만약 그렇다면 정답을 찾아낸 것이고 그렇지 않다면 계속해서 이것을 반복하는 것입니다.

UMPIRE 단계에서 가능한한 여러분은 접근에 포커스를 맞추고 나중에 코딩을 하실 때 참고 하기 쉽게 만드셔야 합니다. validValueExists()나 getIndex()메소드는 원치 않지만 가독성을 위해서 이 시점에 잠시 추가해 놨습니다. 제가 인터뷰를 볼 때 저는 가능한한 코드를 모듈화 하려고 했죠. 면접에서는 시간 제한이 있기 때문에 각 메소드가 무엇을 의미하는지 주석을 달아놔야 시간이 다되었을 때 면접관들이 의도를 알 수 있습니다.

그러면 한번 코드로 변환해 보겠습니다.

Implementing Your Solution

이전 단계들을 통해 우리가 무엇을 할지 이미 다 밑그림을 그려놨기 때문에 이 단계는 매우 쉬울 것입니다.

const twoSum = (arr, target) => {
  const hashTable = {};
  populateTable(hashTable, arr);

  for (let i = 0; i < arr.length; i++) {
    const desiredValue = target - arr[i];
    if ( validValueExists( desiredValue, hashTable, i)) {
      return [i, hashTable[desiredValue]]''
    }
  }

  return [-1, -1];
}

const validValueExists = (desiredValue, hashTable, currendIndex) => {
  return (
    hashTable.hasOwnProperty(desiredValue)
    && hashTable[desiredValue] !== currendIndex
  );
}

const populateTable = (hashTable, arr) => {
  for (let i = 0; i < arr.length; i++) {
    hashTable[arr[i]] = i;
  }
}

console.log(twoSum([2, 1, 4, 3], 6)); // [0, 2]
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

Reviewing Your Solution

인터뷰 관점에서 보자면 여기서는 여러분이 작성한 코드를 예제를 가지고 한줄 한줄 추적하는 것입니다. 면접관들은 여기서 여러분의 로직과 추적 능력을 확인하게 됩니다. 연습삼아 저는 여러분들이 이 문제의 답을 프로그램에 돌려보기 전에 어떻게 되는지 직접 추적해보길 추천드립니다. 구글이나 페이스북 같은 기업에서는 코드를 컴퓨터에서 돌리지 않기 때문에 100% 손으로 코딩하는 것이며 우버나 에어비엔비 같은 곳에서는 코드를 컴파일하고 테스트 케이스들에 대해 프로그램을 실행하게 됩니다.

Evaluating Your Solution

처음에 우리의 초기 알고리즘에 비효과적이라는 것을 알아챘기 때문에 그 다음 솔루션에서는 같은 곳을 재방문하면서 실행시간을 느리게 만들지 않고 최적의 답을 구해냈습니다. N이 배열의 길이라고 했을 때 우리 알고리즘의 공간 복잡도는 O(N)입니다. 그리고 배열을 한번씩만 볼 것이기 때문에 O(N)의 속도를 가집니다. 해시테이블에 대해서 한번씩만 비교를 하기 떄문에 O(1)의 복잡도를 가지며 실제 실행시간은 O(N+(N*1))이며 이것은 O(N)의 빠르기라고 할 수 있습니다.

Takeaways

문제에 접근하는 방법이 매우 매우 중요합니다. 절대로 절대로 절대로 처음에 생각난 대로 바로 코딩을 하지 마세요. 인터뷰 문제는 언뜻 보기엔 간단해 보이지만 우리가 접근하려는 데이터 구조에 대해 알 필요가 있고 해당 요소가 문제를 푸는데 어떤 영향을 미치는지 알아야 합니다. 예를들어 제가 해시테이블을 몰랐다면 우리가 찾아낼 수 있는 최적의 솔루션은 O(n^2)의 복잡도였을 것입니다.

Summary

• 알고리즘 문제를 풀 때는 UMPIRE 의 관점에서 차근차근 풀어보자
• 문제에 올바른 답을 찾는 것보다는 문제의 접근법, 주어진 테스트 케이스 외 예외 사항을 생각 하는 것, 복잡도를 생각하고 알고리즘을 개선하는 것이 중요하다.
• 코딩을 직접 하고 프로그램으로 돌리는 곳도 있지만 손코딩을 하고 로직을 따라가며 설명을 하는 것을 더욱 중요시 보는 곳도 있기 때문에 프로그램으로 정답을 확인 하기 전에 한번씩 코드를 머리속으로 돌려보자