소프트웨어 엔지니어 포지션에 지원중이고요.

인터뷰(알고리즘)을 볼 예정인데요.

면접에서 질문을 받았을 때!!

1. 좀 안좋은 방법이라도 빨리 생각이 드는 로직을 바로 답변하는게 좋을까요 (심하면 brute-force 스타일 방법)

2. 아니면 처음에 답변하는게 시간 좀 걸리더라도 좋은 로직으로 머리속에서 좀 정리해서 답변하는게 좋을까요?

어느쪽이 더 좋을까요?

일단 brute-force한 방법을 인터뷰어에게 먼저 이야기합니다. 이렇게 이렇게 하면 되는데 좀 brute-force한 방법이고, 아마 time-complexity는 이렇게 될 것 같다. 그리고 아마도 이러한 점을 찌르면 좀 더 좋은 알고리즘이 나올 것 같은데, 생각하는 시간이 좀 더 필요하다.

여기까지 하면 인터뷰어의 반응은 대략 두가지입니다.

1. 인터뷰이의 코딩 실력이 의심스러운 경우 or 옵티멀한 알고리즘이 코딩하기에 너무 복잡할 경우: 음..그래. 일단 코딩해봐라. 그리고 나서 어떻게 개선할지 디스커션해보자.

2. 인터뷰이의 생각을 더 듣고 싶은 경우 or brute-force 알고리즘이 너무 쉬워서 테스트해볼 가치가 없다고 생각할 경우: 그래 니 말이 맞다. 좀 더 개선된 알고리즘은 어떻게 될지 고민해봐라.

인터뷰어마다 성향이 다 다르긴하지만. 무엇보다 중요한건 인터뷰어에게 ‘멍때리고 있다’라는 인상을 안주는 것이라 생각합니다.

동양과 서양의 차이가 여기에 있다고 생각합니다. 서양식 사고방식을 가진 사람은 언어=사고라고 생각합니다. 동양인들은 퍼즐을 풀때 말을 안하고 풀지만 서양인들은 말로 표현하면서 풉니다. 말로 잘 표현할수록 똑똑해보이는거죠.

무조건 최선의 알고리즘부터 말하세요. 브룻포스 듣자고 절대 내는 문제들이 아닙니다 예를 들어 서치라면 빅오브로그엔 먼저 대답하고 옵티마이즈해보자할때 빅오브엔으로 가야됩니다.

윗분 교과서에 나오는 알고리즘을 그대로 묻는 인터뷰는 스크리닝 때나 하지 온사이트까지 온 캔디데잇에게 왜 할까요. 설령 교과서에 나오는 소팅을 그대로 활용하는 문제였다해도… 퀵, 인서션, 버켓소트 다 용도에 따른 쓰임새가 있고, 케바케로 문제에 따라서 용법이 다른데요.

그리고 만약 어려운 알고리즘 문제를 냈는데, 캔디데잇이 최적의 알고리즘을 턱~하고 내놓으면 인터뷰어가 제일 먼저 하는 생각은 “아. 이사람 이문제를 이미 알고 있었구나”라는거지요.

그리고 서치문제에게 O(logN)으로 답을 내고 다시 더 안좋은 O(N)으로 최적화한다는게 무슨 의미이신지?

우선 글쓴이님은 온사이트라고 한적 없습니다. 그리고 저는 제가 직접 구글, 퀄컴, 시게이트, 서너 등 내노라 하는 대기업에서 한 인터뷰를 경험으로 적었습니다. 물론 그대로 안 묻습니다. 그런데 전부 서칭 응용, 소팅 응용 문제입니다.

(집합 A – 집합 를 구하라. 실제로 제가 받은 문제입니다. 가장 쉽고 단번에 생각나는 것이 집합 B에서 집합 A의 모든 요소를 검색해보는 거겠죠. 집합 B에 없는 것들만 답. O(N^2) 이 되겠죠. 말그대로 브룻포스 입니다. 저는 이거 스킵하고 처음에 머지소팅을 응용해서 말했습니다. O(NlogN) 이 되겠죠. 상대방이 유딛 프리리 굿 벗 모스트 캔디데이츠 앤서드 잇이라고 하더군요. 그러면서 컴플렉시티를 더 줄여보라고 하더군요. 몇초간 생각하다보니 번뜩이던게 해싱이었습니다. 집합 B를 해싱테이블로 만든후 집합 A를 인서트 하면서 컨플릭트 나지 않는다면 그것들이 답. B를 해싱테이블로 만드는데 O(N), A인서트 하는데 O(N) 결국 O(N). 그쪽에서 베리 웰이라고 했습니다. 그리고는 하지만 이것은 데이터가 작을때 좋고 만약 데이터가 테라 바이츠라면 어떻게 하겠냐고 나왔습니다 .그래도 해싱을 하겠냐… 여기서 막혓죠. 이것을 수초만에 하는 알고리즘이 있느냐..당시에는 예상치 못해서 ㅈㅈ. (구사 인터뷰임). 하지만 이 인터뷰는 통과했고 담 인터뷰때 떨어졌습니다. ㅠㅠ 하필 구글 인터뷰가 첫인터뷰;; 미리 공부도 못해서 ㅈㅈ 쳤습니다. 그 뒤로 다른 회사들은 전부 파이널 인터뷰까지 초청받았는데..암튼, 이런식으로 흘러가고 퀄컴은 카테고리 몇개 주고 자신있는거 골라라고 합니다. 퍼포먼스나 랭귀지 택하면 위의 문제랑 비슷한 유형들 냅니다. “지나가다”님의 질문에 답변이 됐는지 모르겠습니다. 어느 정도 수준의 회사에 지원하시는지 모르지만 브룻포스부터 대답하시면 “모스트 캔디데이츠” 수준에도 못끼는 겁니다.

두 방법 다 괜찮고 다만 표현하기 나름이라고 생각하는데요. 먼저 간단한 방법을 얘기하면서 이보다 더 좋은 방법이 있을 것 같으니 생각해 보겠다 라면서 시간을 벌고 생각을 정리해서 더 나은 방법을 제시하면 됩니다. 이때 최적의 알고리즘이 나올 수도 있지만 그렇지 않더라도 대개 인터뷰어가 더 나은 방법은 없겠냐고 물어보면서 힌트를 줍니다. 그러면 그에 따라 더 나은 방법을 제시하면 되겠죠.

이 방법의 장점은 1) 그 문제를 외워서 푸는게 아니다라는 걸 보여주고, 2) 생각을 얼마나 논리 정연하게 표현하는지를 보여줍니다. 간단한 작업을 빠른 시간 안에 해야 하는 프로젝트를 하는 곳에서는 이런 점이 별로 중요하지 않을 수 있지만, 어려운 문제들에 계속 부닥친다거나 그 솔루션을 장기적으로 적용할 수 있는 방법이 중요해서 그 방법에 대해 대화가 자주 필요할 때 등에 커뮤니케이션 스킬은 굉장히 중요하죠. 어떻게 보면 어차피 코딩 자체는 일단 어느 정도 수준이 되면 인터뷰 문제로 가늠할 길이 없으니, 어느 수준 정도만 보여주면 그 다음부터는 본인이 얼마나 어울리기 좋고 일하기 좋은 팀원이고, 본인의 생각을 얼마나 잘 표현하고 또한 남의 생각을 얼마나 잘 이해하나가 인터뷰에서 보여주기에 코딩보다도 중요한게 아닐까 싶습니다.

그리고 여기서 하나 더 생각해야 할 점은, 공통으로 통용되는 정답은 없고, 회사마다 팀마다 혹은 개인마다 생각이 다 다르다는 겁니다. 따라서 인터뷰에서 떨어지더라도 반드시 그 인터뷰어에 맞게 하는 것이 다른 회사에도 통하리란 건 없습니다. 상식적으로 잘 판단해 보아서 보안할 점은 보안하고 본인이 잘했다고 생각하는 부분은 계속 미록 나가는 것도 좋다고 생각합니다. 사람은 누구나 다르고 다른 이가 했다면 단점일 것이 본인이 하면 장점인 부분도 있으니까요.

다만 일반적으로 생각되는 나쁜 점들이 있는데, 이런 점들을 어느정도 고쳐서 간다면 좋을 듯 합니다. 가령 너무 자신감이 없어 보이는 표정과 말투라던지, 유별나게 긴장한 표정, 웃지 않는 인상등은 마이너스가 될 수 있을 듯 합니다. 또한 거부감을 일으킨다거나 스마트해보이지 않을 수 있는 자잘한 말투의 실수들도 비디오로 본인을 녹화한 다음 검토해서 없앤다면 좋을 듯 합니다. 제 경우 so… 나 uh… 를 많이 말하게 되는데 제가 듣기에도 거슬려서 없애려고 노력하니 많이 좋아졌습니다. 한국인들이 유난히 so… 를 남발한다고 하더군요. 발음도 sou 로 해야 하는데 soh 처럼 하는 사람도 많다고 하고요.

인터뷰 터프하기로 유명한 회사 중 하나를 다니고 있습니다. 인터뷰어로도 자주 참여하구요. 위 cccsss님의 조언에 전반적으로 동의합니다.

동료들끼리 얘기해보면 가장 안전한 방법은 역시 brute force 한 방법으로 최대한 빨리 구현하고 차츰 개선시켜나가는 겁니다. 이 때 시간이 오래 걸리면 안 됩니다. brute force solution 조차 버벅댄다거나 시간을 너무 많이 뺏겨서 본게임 시간이 부족하면 거의 탈락입니다. 따라서 슈도 코드로 아주 간단히만 적고 넘어가거나 ‘이러 저러하게 푸는 게 일단 가장 간단해 보이는데, 더 좋은 방법이 있을 것 같으니 더 생각을 해보겠다’라고 언급만 하는 전략도 괜찮습니다.

막바로 최적의 솔루션을 위해 고민하는 건 그닥 추천하지 않습니다. 인터뷰어와 계속 얘기하면서 고민하는 게 아니라면 고민하는 동안의 정적 자체가 부정적인 인상을 남기기 쉽습니다. 그리고 brute force로 풀어놓고 점진적으로 개선하다가 막히면 중간 점수라도 받는데 최적 솔루션으로 가다가 막히면 그 마저도 못 받는 경우가 허다합니다.

게다가 최적의 솔루션이 짧은 시간 내에 바로 나오면 대부분의 인터뷰어는 ‘아는 문제였나?’라고 의심합니다. 물론 많은 문제에 대해서 최적의 솔루션을 바로 바로 다 내주면 대박이죠. 거의 hire됩니다. 근데 한두 문제만 그렇게 풀고, 다른 문제는 고민하다가 답도 못 내면 잘 푼 것도 무시되고 정직하지 못 하다는 오해까지 받습니다.