개요
카카오톡 블라인드 채용 과정 중 진행한 온라인 코딩 테스트 문제를 스칼라를 이용해서 풀어봄.
실제 코딩 테스트는 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을 만족한다.
출력 형식
원래의 비밀지도를 해독하여 “#”, 공백으로 구성된 문자열 배열로 출력하라.
코딩
//val n = 5
//val arr1: Array[Int] = Array(9, 20, 28, 18, 11)
//val arr2: Array[Int] = Array(30, 1, 21, 17, 28)
val n = 6
val arr1: Array[Int] = Array(46, 33, 33 ,22, 31, 50)
val arr2: Array[Int] = Array(27 ,56, 19, 14, 14, 10)
val convertArr1 = arr1 map { i =>
val s = i.toBinaryString
if (s.length != n) "0" * (n - s.length) + s
else s
}
val convertArr2 = arr2 map { i =>
val s = i.toBinaryString
if (s.length != n) ("0" * (n - s.length)) + s
else s
}
def compare(a: Char, b: Char): Char = (a, b) match {
case ('0', '0') => ' '
case _ => '#'
}
val r = for {
(a1, a2) <- (convertArr1 zip convertArr2)
} yield {
(for ((a1Char, a2Char) <- (a1 zip a2)) yield compare(a1Char, a2Char)) mkString
}
r mkString ("[\"", "\", \"", "\"]") 2번 다트 게임
카카오톡 공지 난이도: 하
체감 난이도: 하
입력 형식
점수|보너스|[옵션]으로 이루어진 문자열 3세트. 예) 1S2D*3T점수는 0에서 10 사이의 정수이다.
보너스는 S, D, T 중 하나이다.
옵선은 *이나 # 중 하나이며, 없을 수도 있다.
출력 형식
3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다. 예) 37
코딩
옵션이 *이나 # 둘 다 되는 경우가 존재한다고 오해하고 처음에 잘못 접근하였음.
val allScoreString = "1D2S3T*"
val pattern = "([0-9]+)(S|D|T)(\\*|#)?([0-9]+)(S|D|T)(\\*|#)?([0-9]+)(S|D|T)(\\*|#)?".r
val pattern(score1, area1, opt1, score2, area2, opt2, score3, area3, opt3) = allScoreString
def squareN(n:Int)(i: Int): Int = math.pow(i, n).toInt
val square2 = squareN(2) _
val square3 = squareN(3) _
def decisionRoundScore(
score: Int,
area: String,
opt: String,
previousScores: Seq[Int] = Seq.empty // default case 1st round
): Seq[Int] = {
val scoreWithArea: Int = area match {
case "S" => score
case "D" => square2(score)
case "T" => square3(score)
}
opt match {
case s: String if s == "*" =>
val converted =
if(previousScores.isEmpty) previousScores
else previousScores.patch(previousScores.length-1, Seq(previousScores.last * 2), 1)
converted :+ (scoreWithArea * 2)
case s: String if s == "#" => previousScores :+ (-1 * scoreWithArea)
case _ => previousScores :+ scoreWithArea
}
}
val first = decisionRoundScore(score1.toInt, area1, opt1)
val second = decisionRoundScore(score2.toInt, area2, opt2, first)
val third = decisionRoundScore(score3.toInt, area3, opt3, second)
third.sum 3번 캐시
카카오톡 공지 난이도: 하
체감 난이도: 하
입력 형식
캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
출력 형식
입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.
조건
캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
cache hit일 경우 실행시간은 1이다.
cache miss일 경우 실행시간은 5이다.
코딩
type ExecutionTime = Int
def cacheHitOrMiss(
cachedCities: Array[String],
city: String
): ExecutionTime = {
if(cachedCities.map(_.toLowerCase).contains(city.toLowerCase)) 1
else 5
}
def caching(
cachedCities: Array[String],
city: String,
cacheSize: Int
): Array[String] = {
require(cacheSize >=0 && cacheSize <= 30)
// Apply LRU(Least Recently Used)
cachedCities.length match {
case i if i == cacheSize && cachedCities.contains(city) =>
cachedCities.patch(cachedCities.indexOf(city), Array.empty[String], 1) :+ city
case i if i == cacheSize =>
cachedCities.drop(1) :+ city
case _ => cachedCities :+ city
}
}
def start(inputCities: Array[String], size: Int): ExecutionTime = {
def loop(
index: Int,
cached: Array[String],
sum: ExecutionTime
): ExecutionTime = {
index match {
case i: Int if i < inputCities.length =>
val next = i + 1
val targetCity = inputCities(i)
loop(
next,
caching(cached, targetCity, size),
sum + cacheHitOrMiss(cached, targetCity)
)
case _ => sum
}
}
loop(0, Array.empty[String], 0)
}
// Array item(City name) condition:
// - 공백, 숫자, 특수문자 등이 없는 영문자로 구성
// - 대소문자 구분하지 않음
// - 최대 20자
val Size: Int = 3
val Cities: Array[String] = Array("Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA")
require(Cities.length <= 100000)
start(Cities, Size)
val Size2: Int = 3
val Cities2: Array[String] = Array("Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul")
require(Cities2.length <= 100000)
start(Cities2, Size2)
val Size3: Int = 2
val Cities3: Array[String] = Array("Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome")
require(Cities3.length <= 100000)
start(Cities3, Size3)
val Size4: Int = 5
val Cities4: Array[String] = Array("Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome")
require(Cities4.length <= 100000)
start(Cities4, Size4)
val Size5: Int = 2
val Cities5: Array[String] = Array("Jeju", "Pangyo", "NewYork", "newyork")
require(Cities5.length <= 100000)
start(Cities5, Size5)
val Size6: Int = 0
val Cities6: Array[String] = Array("Jeju", "Pangyo", "Seoul", "NewYork", "LA")
require(Cities6.length <= 100000)
start(Cities6, Size6)
Updated at 2017.10.14
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 사이의 값이 될 수 있다.
코딩
// 정렬되지 않은 time table sorting
def sort(timeTable: Array[String]): Array[String] = {
timeTable.sortBy{ time =>
val Array(h, m) = time.split(":").map(_.toInt)
(h, m)
}
}
def nextArrivalTime(previousArrivalTime: String, interval: Int): String = {
require(interval > 0 && interval <= 60)
require(previousArrivalTime.contains(":") && previousArrivalTime.size == 5)
val Array(h, m) = previousArrivalTime.split(":").map(_.toInt)
val mPlusInterval = m + interval
val (nextH, nextM) =
if(mPlusInterval >= 60) (h + 1, mPlusInterval - 60)
else (h, mPlusInterval)
val nextHString = if(nextH < 10) s"0$nextH" else nextH.toString
val nextMString = if(nextM < 10) s"0$nextM" else nextM.toString
s"$nextHString:$nextMString"
}
def remainCrews(
crews: Array[String],
currentShuttleTime: String,
max: Int
): Array[String] = {
val Array(currentShuttleH, currentShuttleM) = currentShuttleTime.split(":").map(_.toInt)
def loop(remain: List[String], capacity: Int): List[String] = remain match {
case head :: tail if capacity < max =>
val Array(h, m) = head.split(":").map(_.toInt)
if(h < currentShuttleH || (h == currentShuttleH && m <= currentShuttleM)) {
loop(tail, capacity + 1)
}
else remain
case _ => {
remain
}
}
loop(crews.toList, 0).toArray
}
val timeTable =
Array("23:59")
// Array("00:01", "00:01", "00:01", "00:01", "00:01")
// Array("09:00", "09:00", "09:00", "09:00")
// Array("09:10", "09:09", "08:00")
// Array("08:00", "08:01", "08:02", "08:03")
// Array("23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59")
val initArrivalTime = "09:00"
val n = 1
val t = 1
val m = 1
val shuttleTimeTable: List[String] = {
def loop(current: String, i: Int): List[String] = {
if(i <= n) current +: loop(nextArrivalTime(current, t), i + 1)
else List.empty[String]
}
loop(initArrivalTime, 1)
}
def loop(shuttle: List[String], crews: Array[String]): String = {
shuttle match {
// shuttle 시간이 더 있을 경우
case head :: tail if tail.nonEmpty =>
val nextCrews = remainCrews(crews, head, m)
loop(tail, nextCrews)
// shuttle 시간이 더 이상 없을 경우
// 남은 crew 더 없을 경우
case head :: tail if tail.isEmpty && crews.isEmpty =>
head
// 남은 crew 존재할 경우
case head :: tail if tail.isEmpty && crews.nonEmpty =>
val nextCrews = remainCrews(crews, head, m)
// 남은 crew가 마지막 shuttle에 다 탈 수 있을 경우,
// 남은 crew들이 마지막 shuttle 시간보다 늦어서 다 못 타는 경우,
// 마지막 shuttle 시간에 맞춰서 도착
if((nextCrews.isEmpty && crews.length < m) || (nextCrews.nonEmpty && nextCrews.length == crews.length)) headd
// 인원 초과로 인해 못탈 경우, 탈 수 있는 마지막 crew 보다 1분 먼저 도착
else {
val Array(currentShuttleH, currentShuttleM) = head.split(":").map(_.toInt)
val Array(lastCrewH, lastCrewM) = crews(m-1).split(":").map(_.toInt)
if(lastCrewH < currentShuttleH || (lastCrewH == currentShuttleH && lastCrewM <= currentShuttleM)) {
val (mMinusOneH, mMinusOneM) = if(lastCrewM == 0) (lastCrewH-1, 59) else (lastCrewH, lastCrewM-1)
val nextHString = if(mMinusOneH < 10) s"0$mMinusOneH" else mMinusOneH.toString
val nextMString = if(mMinusOneM < 10) s"0$mMinusOneM" else mMinusOneM.toString
s"$nextHString:$nextMString"
} else head
}
}
}
loop(shuttleTimeTable, sort(timeTable)) 5번 뉴스 클러스터링
카카오톡 공지 난이도: 중
체감 난이도: 중하
입력 형식
입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 “ab+”가 입력으로 들어오면, “ab”만 다중집합의 원소로 삼고, “b+”는 버린다.
다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. “AB”와 “Ab”, “ab”는 같은 원소로 취급한다.
출력 형식
입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
코딩
// Test1 => 16384
val str1 = "FRANCE"
val str2 = "french"
// Test2 => 65536
//val str1 = "handshake"
//val str2 = "shake hands"
// Test3 => 43690
//val str1 = "aa1+aa2"
//val str2 = "AAAA12"
// Test4 => 1
//val str1 = "E=M*C^2"
//val str2 = "e=m*c^2"
def makeSet(str: String) =
for(i<- 0 until str.length-1 if str.substring(i, i+2).matches("[A-Za-z]+"))
yield str.substring(i,i+2).toUpperCase
val str1Set = makeSet(str1).toVector
val str2Set = makeSet(str2).toVector
def jaccardSimilarity(vec1: Vector[String], vec2: Vector[String]): Int =
if(vec1.isEmpty && vec2.isEmpty) 1
else {
type Union = Vector[String]
type Intersection = Vector[String]
def loop(
v1: Vector[String], v2: Vector[String],
union: Vector[String], intersection: Vector[String]
):(Union, Intersection) = v1 match {
case head +: nextV1 if nextV1.nonEmpty || v2.nonEmpty =>
val findIndexV2 = v2.indexOf(head)
// vector2에 v1의 item중 공통되는게 존재하면
val (nextV2, nextIntersection) =
if(findIndexV2 != -1) (v2.patch(findIndexV2, Nil, 1), head +: intersection)
else (v2, intersection)
val nextUnion = head +: union
loop(nextV1, nextV2, nextUnion, nextIntersection)
case _ => (union ++ v1 ++ v2, intersection)
// 두 vector 중 하나가 empty면 비교 끝내고 다 합집합으로 넣는다.
}
val (union, intersection) = loop(vec1, vec2, Vector.empty[String], Vector.empty[String])
((intersection.length.toDouble / union.length.toDouble) * 65536).toInt
}
jaccardSimilarity(str1Set, str2Set) 6번 프렌즈4블록
카카오톡 공지 난이도: 상
체감 난이도: 중상
입력 형식
입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
2 <= n, m <= 30
board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
출력 형식
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
코딩
type Row = Int
type Col = Int
def getRemovedCoordinates(m: Int, n: Int, board: Array[String]): IndexedSeq[(Row, Col)] =
(for {
row <- 0 until m-1
col <- 0 until n-1
} yield {
val baseChar = board(row).charAt(col)
lazy val baseCharRight = board(row).charAt(col+1)
lazy val baseCharDown = board(row+1).charAt(col)
lazy val baseCharRightDown = board(row+1).charAt(col+1)
if(baseChar != ' ' && baseChar == baseCharRight && baseChar == baseCharDown && baseChar == baseCharRightDown)
IndexedSeq((row, col), (row, col+1),(row+1, col), (row+1, col+1))
else IndexedSeq.empty[(Row, Col)]
}).flatten.distinct.sortBy(s => (s._1, s._2))
def getNextBoard(board: Array[String], removed: IndexedSeq[(Row, Col)]) = {
def loop(state: Array[String], index: Int): Array[String] = index match {
case index if index < removed.length =>
val (r,c) = removed(index)
def movingUpper(upperRow: Int, b: Array[String]): Array[String] =
upperRow match {
case i if i < 0 || b(i).charAt(c) == ' ' => b
case _ =>
val originRow = upperRow + 1
val nextUpperRow = upperRow - 1
val replacedChar = b(upperRow).charAt(c)
val replacedUpperRow = b(upperRow).patch(c, " ", 1)
val replacedOriginRow = b(originRow).patch(c, replacedChar.toString, 1)
val next = b.patch(upperRow, Array(replacedUpperRow, replacedOriginRow),2)
movingUpper(nextUpperRow, next)
}
val removedCoordState = state.patch(r, Array(state(r).patch(c, " ", 1)), 1)
val movingCoordState =
if(r == 0) removedCoordState
else {
movingUpper(r-1, removedCoordState)
}
loop(movingCoordState, index+1)
case _ => state
}
loop(board, 0)
}
def getResult(b: Array[String], m: Int, n: Int): Int = getRemovedCoordinates(m, n, b) match {
case removedCoordinates if removedCoordinates.nonEmpty =>
getResult(getNextBoard(b, removedCoordinates), m, n)
case _ =>
b.flatten.count(s => s == ' ')
}
/*
* Test 1 => 14
* */
//val m = 4
//val n = 5
//val board = Array("CCBDE", "AAADE", "AAABF", "CCBBF")
/*
* Test 2 => 15
* */
val m = 6
val n = 6
val board = Array("TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ")
getResult(board, m, n)
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번보다는 체감상 쉬웠던 것 같음.
import java.time.LocalTime
import java.time.format.DateTimeFormatter
import java.time.temporal.ChronoUnit
case class LogString(s: String) {
private val splitedByEmpty = s.split(" ")
private val formatter = DateTimeFormatter.ofPattern("HH:mm:ss.SSS")
val end: LocalTime = LocalTime.parse(splitedByEmpty(1), formatter)
val processing: Float = {
val processingString = splitedByEmpty.last
processingString.substring(0, processingString.length-1).toFloat
}
require(0.001 <= processing && processing <= 3.000)
val start: LocalTime = {
val processingToMillis = (processing * 1000).toInt
end.minus(processingToMillis, ChronoUnit.MILLIS).plus(1, ChronoUnit.MILLIS)
}
private def isBetween(target: LocalTime, from: LocalTime, to: LocalTime) = {
if(from.isAfter(to)) from.isAfter(target) && to.isBefore(target)
else from.isBefore(target) && to.isAfter(target)
}
private def overlaps(end: LocalTime)(other: LogString): Boolean = {
isBetween(other.start, this.start, end) ||
isBetween(other.end, this.start, end) ||
isBetween(this.start, other.start, other.end) ||
isBetween(end, other.start, other.end)
}
def overlapsStartBeforeOneSec(other: LogString): Boolean = {
val startBeforeOneSec = start.minusSeconds(1)
overlaps(startBeforeOneSec)(other)
}
def overlapsnStartAfterOneSec(other: LogString): Boolean = {
val startAfterOneSec = start.plusSeconds(1)
overlaps(startAfterOneSec)(other)
}
def overlapsEndBeforeOneSec(other: LogString): Boolean = {
val endBeforeOneSec = end.minusSeconds(1)
overlaps(endBeforeOneSec)(other)
}
def overlapsnEndAfterOneSec(other: LogString): Boolean = {
val endAfterOneSec = end.plusSeconds(1)
overlaps(endAfterOneSec)(other)
}
}
def loop(logLines: List[LogString], max: Int): Int = logLines match {
case head :: tail if tail.nonEmpty =>
val (l1, l2, l34) = (for {
other <- tail
} yield (
head.overlapsStartBeforeOneSec(other), head.overlapsnStartAfterOneSec(other),
(head.overlapsEndBeforeOneSec(other), head.overlapsnEndAfterOneSec(other))
)).unzip3
val (l3, l4) = l34.unzip
val s = Seq(l1.count(b=>b), l2.count(b=>b), l3.count(b=>b), l4.count(b=>b))
println(s)
val r = s.max + 1
val nextMax = if(max > r) max else r
loop(tail, nextMax)
case _ => max
}
//val lines = List("2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s")
//val lines = List("2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s")
val lines = List("2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-15 21:00:00.748 2.31s", "2016-09-15 21:00:00.966 0.381s", "2016-09-15 21:00:02.066 2.62s")
loop(lines.map(s=>LogString(s)), 1)
Comments