Kakao Releases Solutions for 2021 Internship Coding Test (5 Problems)

Kakao has released official solutions for the 5 problems from the summer internship coding test held on May 8, 2021. This test consisted of 5 problems arranged by difficulty level, with some problems including efficiency test cases that required optimized algorithm implementations.

Core Solution Strategies by Problem

Problem 1 (Number String and English Words): A problem involving converting number words into integers, with approaches using character-by-character processing or the replace function suggested.

Problem 2 (Checking Distance): A problem requiring verification of whether candidates in a 5x5 waiting room are blocked by partitions when the Manhattan distance between them is 2 or less. Adjacency conditions are verified using DFS/BFS or simple loops.

Problem 3 (Table Editing): A table editing simulation allowing row deletion and restoration. Arrays are used for accuracy tests, while linked lists or segment trees/Fenwick trees are utilized to efficiently process commands in efficiency tests (n up to 1 million).

Problem 4 (Maze Escape): A problem finding the shortest path in a graph where edge directions reverse according to traps. Since the number of trap nodes is at most 10, graph states are represented using bitmasks and Dijkstra's algorithm is applied.

Problem 5 (Dividing Exam Rooms): A problem minimizing the maximum group size when dividing an exam room structured as a binary tree into k groups. Efficiency tests are solved by combining parametric search (binary search) and dynamic programming (DP).