Kakao blind recruitment comments


Categories: Programming Scala
Tags: #Scala #스칼라 #Programming #kakao

개요

카카오톡 블라인드 채용 과정 중 진행한 온라인 코딩 테스트 문제를 스칼라를 이용해서 풀어봄. 실제 코딩 테스트는 9월 16일(토) 오후 2시 ~ 7시 5시간 동안 진행되었으며, 자바, C++, 파이썬, 자바스크립트, 스위프트의 언어를 선택할 수 있었음(통계 및 문제 해설 관련 링크). 1, 2, 3번 문제 풅 때까지는 그래도 이정도면 쉽다고 생각하면서 풀었는데, 4번 문제에서 가장 오래 걸렸고, 5, 6, 7은 4번보다는 그나마 재미있게 풀었음. 시간을 재고 풀지도 않았고, 7문제를 이어서 푼게 아니지만 5시간 동안 7문제 전부 풀지는 못할 것 같았음. 4번 문제 보고 어려움을 간파하고 바로 넘어가면 (과연 그럴 수 있을지는 잘 모르겠지만) 4~5개의 문제를 시간 내에 풀 수 있을 것 같음.

문제

1번 비밀 지도

  • 카카오톡 공지 난이도: 하
  • 체감 난이도: 하
  • 입력 형식
    • 입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.
    • 1 ≦ n ≦ 16
    • arr1, arr2는 길이 n인 정수 배열로 주어진다.
    • 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2^n - 1을 만족한다.
  • 출력 형식
    • 원래의 비밀지도를 해독하여 “#”, 공백으로 구성된 문자열 배열로 출력하라.
  • 코딩

2번 다트 게임

  • 카카오톡 공지 난이도: 하
  • 체감 난이도: 하
  • 입력 형식
    • 점수|보너스|[옵션]으로 이루어진 문자열 3세트. 예) 1S2D*3T
    • 점수는 0에서 10 사이의 정수이다.
    • 보너스는 S, D, T 중 하나이다.
    • 옵선은 *이나 # 중 하나이며, 없을 수도 있다.
  • 출력 형식
    • 3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다. 예) 37
  • 코딩
    • 옵션이 *이나 # 둘 다 되는 경우가 존재한다고 오해하고 처음에 잘못 접근하였음.

3번 캐시

  • 카카오톡 공지 난이도: 하
  • 체감 난이도: 하
  • 입력 형식
    • 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
    • cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
    • cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
    • 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
  • 출력 형식
    • 입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.
  • 조건
    • 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
    • cache hit일 경우 실행시간은 1이다.
    • cache miss일 경우 실행시간은 5이다.
  • 코딩
  • Updated at 2017.10.14
    LRU 알고리즘을 고려하지 않은 것을 지적받아서 수정하였음. city를 caching 할 때, cache array에 이미 그 city가 존재하면 그 city를 pop 하고 맨 나중으로 push.

4번 셔틀버스

  • 카카오톡 공지 난이도: 중
  • 체감 난이도: 상
  • 입력 형식
    • 셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.
    • 0 < n ≦ 10
    • 0 < t ≦ 60
    • 0 < m ≦ 45
    • timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
    • 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.
  • 출력 형식
    • 콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.
  • 코딩

5번 뉴스 클러스터링

  • 카카오톡 공지 난이도: 중
  • 체감 난이도: 중하
  • 입력 형식
    • 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
    • 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 “ab+”가 입력으로 들어오면, “ab”만 다중집합의 원소로 삼고, “b+”는 버린다.
    • 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. “AB”와 “Ab”, “ab”는 같은 원소로 취급한다.
  • 출력 형식
    • 입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
  • 코딩

6번 프렌즈4블록

  • 카카오톡 공지 난이도: 상
  • 체감 난이도: 중상
  • 입력 형식
    • 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
    • 2 <= n, m <= 30
    • board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
  • 출력 형식
    • 입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
  • 코딩

7번 추석 트래픽

  • 카카오톡 공지 난이도: 상
  • 체감 난이도: 상
  • 입력 형식
    • solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
    • 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
    • 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
    • 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 “2016년 9월 15일 오전 3시 10분 33.010초”부터 “2016년 9월 15일 오전 3시 10분 33.020초”까지 “0.011초” 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
    • 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
    • lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.
  • 출력 형식
    • solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.
  • 코딩
    • 자바8의 java.time.LocalTime을 사용하여 String 시간 값을 파싱하여 시간에 대한 계산을 하여서 그런지 4번보다는 체감상 쉬웠던 것 같음.

Comments