Kakao Releases Solutions for 5 Problems from 2024 Winter Internship Coding Test

Kakao has released detailed solutions for the 5 problems in its 2024 employment-linked winter internship coding test. This test was designed to evaluate various algorithmic competencies, ranging from data structure utilization to dynamic programming, and includes optimal solutions and time complexity analyses for each problem.

Key Solution Strategies by Problem

• Most Received Gifts: A data structure problem that uses a 2D array to count gift exchange relationships and rank participants based on these counts.
• Donut and Stick Graphs: Analyzes the number of vertices and edges, as well as in-degrees and out-degrees, to distinguish between generated vertices and graph shapes (donut, stick, figure-8). This method can be solved with O(V+E) time complexity.
• Choosing Dice: Performs exhaustive search on dice combinations, but optimizes time complexity to the O(m log m) level by separating the results for A and B, simulating them, and then applying sorting and the two-pointer technique.
• Card Game: Applies a greedy algorithm to minimize coin consumption by distinguishing between cards in hand (a) and drawn cards (b), prioritizing cases with 0 coins (both cards are a), 1 coin (one of each), and 2 coins (both cards are b).
• Mountain Tiling: Classifies the covering cases of rhombus tiles in an equilateral triangle grid into 4 types and establishes a dynamic programming (DP) recurrence relation considering conditions where the number of cases depends on the previous state. The overall time complexity is O(n).