2020 카카오 블라인드 오프라인 코딩 테스트 후기

이번 주말에는 코테가 몰려있다. 오늘은 카카오 오프라인 코딩 테스트를 치렀고, 내일은 네이버 공채 온라인 테스트를 치게 된다. 내가 취준하는 시기에 맞춰서 IT회사들이 공채를 많이 뽑아서 감사하다.
목감기가 오고 전날 악몽을 꿔서 컨디션이 좋지 않은 상태로 시험을 치루러 판교로 이동했다. 오프라인 코딩 테스트에서는 총 300명 가량이 참석한 것 같았다.

작년 엘레베이터 문제

1차 코테를 치루고나서, 작년 오프라인 코딩테스트였던 엘레베이터 문제를 풀어보려다가, 1차보다 급격히 어려워진 난이도에 당황했었다. 서버와 통신하면서 문제를 푸는 방식이 낯설었다. 무엇보다 지금까지 알고리즘 문제들을 풀면서 보지 못했던, 중규모의 구현을 다루고 있었다.
가장 큰 차이점은, 백준이나 프로그래머스의 문제들을 특정 알고리즘들을 쓸 수 있느냐를 묻는 문제였다면, 엘레베이터 문제는 설계 능력을 묻고 있었다. 일반적으로 생각하는 큐, 스택, dp, 이진 탐색과 같은 알고리즘을 전혀 모르더라도 풀 수 있었다. 대신 문제를 푸는 과정에서 전체 프로세스를 설계하고 복잡한 의사 결정과정을 실제로 구현할 수 있는지를 묻고 있었다.

올해 : 팔로잉 추천 알고리즘

카카오가 새롭게 출시한 서비스에서는 팔로잉이 가능하다. 그리고 개발자는 유저에게 팔로잉할만한 사람들을 “잘” 추천해주어 빠르게 모든 유저들이 적어도 20명을 팔로잉 하도록 해야한다. 개발자는 유저가 추천해준 사람을 클릭할 확률을 미리 파악할 수 있는데

• 유저의 전화번호 북에 없는 사람들 : + 5%
• 유저의 전화번호 북에 있는 사람들 : + 30% 증가
• 유저의 전화번호 북에 있는 사람들이 팔로잉 하는 사람들 : 각 + 10%
• 유저가 팔로잉하는 사람들이 팔로잉 하는 사람 : 각 + 10%

위의 4가지 조건을 사용해 좋은 추천을 해주어야 한다.

• 하루 끝에 한 번만 추천을 해 줄 수 있다
• 각 유저에게 최대 10명까지 추천할 수 있다
• 모든 유저에 추천해주는 사람의 합은 현재 서비스에 가입한 사람 R명과 같아야 한다.
  • 예를 들어 현재 10명이 가입한 서비스에서는 10명의 유저에게 한 사람씩만 추천해주는 경우, 한 명의 유저만 열 사람을 추천해주는 경우도 가능하다.

이런 조건을 가지고 초기 가입자의 목록을 받을 수 있고, 하루가 지날 때마다 새로 가입한 유저를 받을 수 있다. 정보를 조합해 추천을 해주면 하루가 끝나고, 유저의 팔로잉 선택이 결정된다.

이 모든 과정이 로컬에서 작업한 후에 GET, POST, PUT 이라는 REST API Call을 통해 이루어진다.

문제를 처음 받고 저번 엘레베이터 문제보다 쉽다고 직감했다. 문제 복잡도가 높지 않을 것 같아서, 전체 알고리즘을 설계한 후에 처음부터 최적화한 버전으로 작성하기 시작하는 우를 범했다.
2시간쯤 남았을 때 코드를 돌려보면서, 내가 생각하지 못한 부분을 2가지쯤 발견했고, 최적화 부분에서 알 수 없는 동작을 1개 관찰했다. 결국 작은 단위로 코드를 테스트해보면서 1시간쯤을 썼고, 특정 유저에게 10명 이상을 추천해주고 있는 실수를 발견했다. 이 때까지만 해도 이런 조건이 있다는 사실조차 인지못하고 있었다. 결국 최적화 코드를 일부 포기하고 마지막 30분이 남았을 때 타임어택을 해서 두 문제를 풀었다. 실시간 점수가 나왔지만, 30분전에 리더보드를 얼려서, 그 전 리더보드 기준으로 판단하는 수 밖에 없었다. 그래도 나름 괜찮은 순위여서, 나처럼 30분 어택에 성공한 사람들이 있더라도 오프라인 코테까지는 무난히 통과할 거라고 생각했다.