Google Women Techmakers Interview Review

면접은

1. 코딩/알고리즘 문제풀이 면접 - 30분
2. 에세이 기반 인성 면접 - 15분 이렇게 약 한 시간 정도 진행되기로 계획 되어있었다.

Google에서 코딩 인터뷰는 모의 인터뷰를 포함해 이번에 4번째 였다.

1번째는 합격! : Google camp를 진행하게 되었다.

2번째는 구글 대학생 캠프에서 진행한 모의 인터뷰였다. “그 학년 (cs 2학년) 치고 잘한다. 앞으로 더 잘할 수 있을거다” 라는 평을 들었다. 이건 합격 선은 아니라는 것을 완곡히 돌려 말하신 것 같다고 생각한다. 인터뷰어의 맘에 들게 인터뷰를 봤던 게 아닌 걸로 결론.ㅠㅜ

3번째는 인턴 인터뷰 불합격… 이 때 현타가 정말 오지게 왔던 걸로 기억한다. 규리 넘나 슬펐따리ㅠㅜ 하지만 내가 생각해도 이 인터뷰 중 1차를 잘 보진 못했던 것 같다. 첫 번째는 분수를 소수로 바꾸는 거였는데, 구현에서 실수가 너무 많았다. 피융신 두 번째는 너무 쉬워서 금방 풀었고, 칭찬까지 받았다. 2차 인터뷰에서 문제를 너무 빨리 풀어서 문제를 2개 풀었던 기억이 난다. 결론은 구글 인턴을 하려면 1,2차 인터뷰 모두 문제를 다 잘 풀어야 한다는 것….

그리고 오늘! 구글 우먼 테크메이커스 인터뷰를 보았다. 코딩 인터뷰 30분 동안 문제를 총 3개를 주셨다. 30분 동안 이렇게 많은 문제를 풀긴 또 처음…

 

 

1번 문제

A = “Hello World”, S = {‘e’, ‘o’}

위와 같이 A라는 string과 S라는 set이 주어진다. 이 때 S안의 원소들이 A에 각각 몇번 쓰였는지를 출력하고, 이 것의 합을 출력하라는 문제였다.

지금 같은 경우엔 ‘e’는 1번, ‘o’는 2번 쓰였고 S안의 문자들이 총 3번 ,

1 2

3

과 같이 출력한다.

먼저 알파벳만 쓰이는 줄 알고, arr[30]과 같은 배열을 만들어서 ‘a’~’z’ 까지 각 인덱스를 0 ~ 25로 설정하고 개수를 세려고 했다. 그런데 알파벳 뿐만 아니라, 대소문자를 구분한 알파벳, 특수문자들이 모두 포함된다고 하셔서 조금 고민했다. 바로 답을 찾아냈긴 했지만 이건 좀 generous한 답변 같당..

반복문을 돌려서 set의 특성을 이용해 stl algorithm의 find함수를 써서 index를 반환하는 식으로 구상했다. arr[S.size] 배열을 놓고, 각 인덱스에는 S[idx]번째 문자가 몇개 쓰였는지를 저장하는 식으로 해결했다. 즉, A의 size를 N, S의 size를 M이라고 하면 결국 시간 복잡도는 O(N*M) 이다. ㅠㅜ 시간 복잡도가 너무 커…. 잘 해결했다고 생각했는데 지금 와 보니 N,M이 커지면 감당할 수가 없어질 것 같당. 다른 해결법이 있을까?

 

2번 문제

A = {4, 7, 1, 9, 10}, X = 5

입력이 이렇게 주어질 때, 합이 X가 되는 두 수가 있으면 true, 없으면 false를 반환하는 함수를 짜는 문제였다. 예를 들어 이 입력에선 4, 1을 더해 5가 되므로 true를 return. 이러한 쌍의 개수에 상관없이 유무의 여부만 반환해주면 된다.

#include <algorithm>
using namespace std;
bool sol( A, X){
    
    sort(A, A+(sizeof(A)/sizeof(int)));
    int st = 0, en = lower_bound(A, A+(sizeof(A)/sizeof(int)),X)-A;
    en--;
    while(st<en){
        if(A[st]+A[en]==X) return true;
        else if(A[st]+A[en]>X) en--;
        else if(A[st]+A[en]<X) st++;
    }
    return false;
}

정확히 이렇게 짠 것 같다. 근데 while문 안에 배열 이름을 A로 했는지 arr로 했는지 기억이 안난다. 진짜 븅신인가…… ㅠㅜㅜㅜㅜ 왜 지 맘대로 배열 이름 쓰고 제대로 썼는지 기억도 못하나ㅠㅜ 이거 진짜 잘 풀었다고 생각했는데 이것 때문에 마음에 걸린다 엉엉ㅇ엉 븅신새끼

시간복잡도는 sort+최악의 경우 N번 탐색하므로 O(lgN + N)

 

 

3번 문제

특이한 문제라고 하면서 문제를 내셨다. 마을에서 이장을 뽑는데 이장의 조건은 다음과 같다.

1. 이장을 제외한 모든 사람이 이장을 알아야 한다.
2. 형평성을 위해서 이장은 자신을 제외한 마을의 사람들을 아무도 몰라야 한다.
3. 사람들의 인덱스는 0~N-1과 같다.

그리고 다음과 같은 함수가 주어졌다.

bool know ( i, j)

이 함수는 i가 j를 알면 true, 모르면 false가 주어진다.

몇 번의 질문을 통해 더 얻은 추가 정보는 이 함수에선 i가 j를 아는지만 알려준다. J가 i를 아는지 알아보려면 know(j, i)를 호출해야 한다. 또한, i가 k를 알고, k가 j를 안다고 해서 i가 j를 아는 것은 아니다. 그 때 당시엔 아무리 생각해도 O(n^2) 해법밖에 생각이 안났다…

인터뷰 시간이 몇분 남지 않아 대충 해결방식만 생각해보라고 하셔서 당장 생각나는 rough한 풀이만 말씀드렸다.

반복문을 통해 모든 (i,j)쌍에 대해 know함수를 호출하고, col[N], row[N]을 선언한다.

col[k] : k를 아는 사람들의 수

row[k] : k가 아는 사람들의 수

if(know(i,j)) col[j]++; row[i]++;

따라서 if(col[k]==N-1 && row[k] ==0)이라면 k번 사람은 이장이 될 수 있는 것이다!

근데 아직도 이거말고 시간복잡도를 줄일 수 있는 풀이가 생각나지 않는다… -> 숭고한 가서 갓갓고인물들한테 물어봤다 무조건 O(n^2) 밖에 정해가 없다고 했다 아싸 다행

이 문제 정해는 O(n)

retreat가서 언니들이랑 얘기 나누다가 정해가 n이라는 소리를 듣고 엄청 놀랫다;; 잘생각해보니 O(n)은 아니고 Ω(n)정도 되는듯 know(i, j)를 호출해서 true가 반환되는 순간 j는 절대 이장이 될 수 없다. 이렇게 계속 호출하다보면 상수 * n번 동안 후보를 많이 제거할 수 있다.

쨌든 이번 인터뷰는 딱 끝나고 나와서는! 오! 좀 잘한듯?! 했던 인터뷰였다. 또 다시 돌아보니 그것도 잘 모르겠지만...ㅋㅋㅋㅋㅋㅋㅋㅋ 인턴 인터뷰 때는 아 존나 망했구나 하는 게 느껴졌었고…

결과는 9월 12일! 수요일! 에 나온다고 말씀해주셨다. 아마 매번 그렇듯이 이번에도 오후 5,6시 쯤 메일이 올 것 같다. 업무시간 끝나갈 때 쯤 한번에 몰아서 보내시는 것 같다링

일주일 동안 좀 게으르긴 했지만 코딩인터뷰 책도 틈틈히 보고,,, 교통사고 회복한 뒤 코딩도 초큼 했다.

인턴이나 진짜 Googler가 되기 위핸 코딩인터뷰는 좀 더 공부를 해야겠지???

합격! update at Sep 12, 2018