Category: Swift Coding Test

The coding test is an important process for applicants to validate their programming skills. In this course, we will learn how to solve algorithm problems in Swift through the topic of Calculating the Amount of Water.

Problem Description

The problem is to calculate the amount of water that can be stored at each unit height when it rains, given an array of heights. For example, consider the following height array:

    heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    

Calculate the amount of water that can be stored in this height array when it rains. The amount of water stored at each position is determined by the higher boundaries on both sides.

Approach to the Problem

The basic approach to solve this problem is as follows:

1. Calculate the maximum heights on the left and right for each position.
2. Determine if water can be stored based on the smaller of the two maximum heights that are lower than the current height.
3. Accumulate the amount of water at each position to derive the result.

Algorithm Explanation

To implement the above algorithm, we use two arrays to store the maximum heights from the left and right at each position. We can then calculate the amount of water at each position.

Step 1: Analyzing the Height Array

This is the process of obtaining the maximum heights on both sides for each position in the given height array.

Creating the Left Maximum Height Array

First, we create an array to store the maximum height from the left. Each element of the array stores the maximum value of all building heights to the left of the current position.

    var leftMax = [Int](repeating: 0, count: heights.count)
    leftMax[0] = heights[0]
    for i in 1..
Creating the Right Maximum Height Array
Next, we create an array to store the maximum height from the right. This array is also created in the same manner.
    var rightMax = [Int](repeating: 0, count: heights.count)
    rightMax[heights.count - 1] = heights[heights.count - 1]
    for i in (0..<(heights.count - 1)).reversed() {
        rightMax[i] = max(rightMax[i + 1], heights[i])
    }
    
Step 2: Calculating the Amount of Water
Now, we calculate the amount of water that can be stored at each position. The amount of water stored can be calculated as the minimum of the left maximum height and the right maximum height minus the current height.
    var waterTrapped = 0
    for i in 0..
Complete Swift Code
    func trap(_ heights: [Int]) -> Int {
        guard heights.count > 2 else { return 0 }

        var leftMax = [Int](repeating: 0, count: heights.count)
        var rightMax = [Int](repeating: 0, count: heights.count)

        leftMax[0] = heights[0]
        for i in 1..
Result Analysis
When the above code is executed, the amount of water stored in the given height array is output as 6. This can be visualized as follows:

Index 2 can store 1 unit of water.
Index 4 can store 1 unit of water.
Index 5 can store 3 units of water.
Index 6 can store 1 unit of water.
Index 8 can store 1 unit of water.

Conclusion
In this course, we covered an algorithm problem of calculating the amount of water using Swift. This problem can be solved using arrays, loops, and conditional statements, and requires comparing the maximum heights at each position. It is important to understand the structure of the problem well and organize the approach systematically when solving algorithm problems.
If you want to learn more algorithm problems and solutions, I recommend referring to various related materials for practice.

	

The programming language Swift is widely used in the Apple ecosystem and is often utilized for iOS and macOS application development.
It is important for developers to have problem-solving skills for algorithms. Especially for employment, it is necessary to demonstrate
the ability to solve various problems. Today, we will look into the maze exploration problem. To solve this problem, we will compare
the Depth-First Search (DFS) algorithm and the Breadth-First Search (BFS) algorithm.

Problem Definition

The problem is to find the shortest path from the starting point to the destination in a maze represented by a given 2D array.
The maze consists of 0s and 1s, where 0 represents a traversable space and 1 represents a wall.
The starting point is (0, 0) and the destination is (n-1, m-1).
Here is an example maze:

            0 0 1 0 0
            1 0 1 0 1
            0 0 0 0 1
            0 1 1 0 0
            0 0 0 0 0
        

Input Format

A 2D array of size n x m is inputted. The array consists of 0s and 1s.

Output Format

The length of the shortest path from the starting point to the destination is outputted. If it is not reachable, -1 is outputted.

Approach to Solve the Problem

Various search algorithms can be used to solve this problem. Among them,
Depth-First Search (DFS) and Breadth-First Search (BFS) are the most commonly used.
BFS is suitable for shortest path problems. I will provide a brief explanation of each algorithm.

BFS (Breadth-First Search)

BFS visits all vertices of a graph level by level. It visits all adjacent vertices from the starting vertex,
then explores adjacent vertices in the next step to explore all paths. BFS is implemented using a queue,
and it can find the shortest path by recording the depth of the path each time a vertex is visited. The time complexity of BFS is O(V + E).

DFS (Depth-First Search)

DFS starts at one vertex of the graph and explores as deeply as possible before backtracking to explore alternative paths.
DFS is implemented using a stack, and the order of visiting depends on the depth. Since DFS explores all paths, it does not guarantee
the shortest path. Therefore, BFS is more suitable for maze exploration problems. The time complexity of DFS is O(V + E),
and its space complexity is O(V).

Algorithm Design

Now, let’s design an algorithm to solve the maze exploration problem using BFS.
We need to define and initialize the necessary variables to proceed to the next steps.

            // maze size n, m
            let n = maze.count
            let m = maze[0].count
            // direction array (up, down, left, right)
            let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
            var queue: [(Int, Int)] = []
            // add starting point (0, 0) to queue
            queue.append((0, 0))
            // visited array
            var visited = Array(repeating: Array(repeating: false, count: m), count: n)
            visited[0][0] = true
            // distance array
            var distance = Array(repeating: Array(repeating: -1, count: m), count: n)
            distance[0][0] = 0
        

Code Implementation

Let’s solve the problem with code. Below is the BFS algorithm implemented in Swift.

            func bfs(maze: [[Int]]) -> Int {
                let n = maze.count
                let m = maze[0].count
                let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
                var queue: [(Int, Int)] = []
                var visited = Array(repeating: Array(repeating: false, count: m), count: n)
                var distance = Array(repeating: Array(repeating: -1, count: m), count: n)
                
                queue.append((0, 0))
                visited[0][0] = true
                distance[0][0] = 0
                
                while !queue.isEmpty {
                    let (x, y) = queue.removeFirst()
                    
                    for direction in directions {
                        let newX = x + direction.0
                        let newY = y + direction.1
                        
                        if newX >= 0 && newY >= 0 && newX < n && newY < m &&
                           maze[newX][newY] == 0 && !visited[newX][newY] {
                            visited[newX][newY] = true
                            distance[newX][newY] = distance[x][y] + 1
                            queue.append((newX, newY))
                        }
                    }
                }
                
                return distance[n-1][m-1] != -1 ? distance[n-1][m-1] : -1
            }

            let maze = [
                [0, 0, 1, 0, 0],
                [1, 0, 1, 0, 1],
                [0, 0, 0, 0, 1],
                [0, 1, 1, 0, 0],
                [0, 0, 0, 0, 0]
            ]

            let result = bfs(maze: maze)
            print(result) // Result: 8
        

Code Explanation

In the above code, we used the BFS algorithm to explore the maze and find the shortest path.
Initially, we start at the coordinate (0, 0), and set up the queue, visited array, and distance array.
When we dequeue one coordinate from the queue, we check all adjacent coordinates. If it is a traversable coordinate, we add it to the queue and update the
visited array and distance array. Finally, we return the distance value of the destination point.
If it is unreachable, we return -1.

Conclusion

In this tutorial, we learned how to solve the maze exploration problem with Swift.
Through the BFS algorithm, we effectively utilized the queue and dimensional arrays to find the shortest path.
Such search algorithms are often encountered in job interviews, so we need to practice sufficiently to solve a variety of problems.
These fundamental concepts are very useful when solving algorithm problems in Swift.

Hello! In this post, we will solve a problem of finding a string using Swift. String problems are common in coding tests, and they greatly help in understanding efficient search algorithms and string processing methods. Through this course, we will solidify our foundation in string processing.

Problem Description

Here is a string search problem:

Given a string haystack and needle, write a function to find the index of the first occurrence of needle in haystack. If needle does not exist, it should return -1.

Examples:

• haystack = "hello", needle = "ll" => Output: 2
• haystack = "aaaaa", needle = "bba" => Output: -1
• haystack = "", needle = " => Output: 0

Problem Approach

To solve this problem, we need to compare the strings sequentially to check where needle appears in haystack. We can follow these steps:

1. First, check the length of needle and compare it with the length of haystack to determine if needle can exist in haystack.
2. Then, extract substrings of the length of needle from each index of haystack and compare them.
3. If the comparison matches, return the index; otherwise, return -1.

Swift Code Implementation

Now, let’s implement the above logic in Swift:

func strStr(_ haystack: String, _ needle: String) -> Int {
        let haystackCount = haystack.count
        let needleCount = needle.count

        // Return 0 when needle is empty
        if needleCount == 0 {
            return 0
        }

        // Return -1 if the length of haystack is shorter than needle
        if haystackCount < needleCount {
            return -1
        }

        // Convert haystack to an array
        let haystackArray = Array(haystack)

        // Compare substring with needle at each index
        for i in 0...(haystackCount - needleCount) {
            var j = 0

            while j < needleCount && haystackArray[i + j] == needle[needle.index(needle.startIndex, offsetBy: j)] {
                j += 1
            }

            // If needle is found
            if j == needleCount {
                return i
            }
        }

        // If needle is not found
        return -1
    }

Code Explanation

Now let’s explain the code in detail:

• func strStr: A function that takes two strings haystack and needle as arguments and performs the string search.
• let haystackCount = haystack.count: Stores the length of haystack.
• let needleCount = needle.count: Stores the length of needle.
• if needleCount == 0: If needle is empty, return 0.
• if haystackCount < needleCount: If the length of haystack is shorter than needle, return -1 as it cannot be found.
• let haystackArray = Array(haystack): Converts the string into an array to allow access to each character.
• for i in 0...(haystackCount - needleCount): Iterates through all indices of haystack. The loop should consider the length of needle for the search range.
• The inner while loop compares the substring from needle with haystack at each index.
• If all comparisons match, it returns index i.
• Finally, it returns -1 if needle is not found.

Test Cases

Let’s write some test cases to validate this code:

print(strStr("hello", "ll"))   // Output: 2
print(strStr("aaaaa", "bba"))     // Output: -1
print(strStr("", ""))              // Output: 0
print(strStr("abcde", "abc"))      // Output: 0
print(strStr("abcde", "xyz"))      // Output: -1

Conclusion

In this lesson, we learned how to solve a string finding problem using Swift. It’s important to carefully check the length of the strings, compare substrings, and define the search range to solve the given problem. String-related problems have various variations, so ensure to practice to handle more diverse cases.

In the next lesson, we will cover another type of string problem. Thank you!

Problem Description

Problem Analysis

This problem involves implementing an algorithm that can count the number of nodes with no child nodes (i.e., leaf nodes) in the given binary tree. You can traverse the binary tree using either a recursive or iterative approach to find the leaf nodes.

Algorithm Design

To find the leaf nodes, the following steps are followed:

1. Define a function to traverse the binary tree.
2. If the current node is not NULL:
• Recursively call the left child node.
• Recursively call the right child node.
• Check if the current node is a leaf node; if it is, increment the count.
3. If it is NULL, the function terminates.

Swift Implementation

Now, let’s implement the above algorithm in Swift. Below is the code for the function that counts the number of leaf nodes:

    class TreeNode {
        var value: Int
        var left: TreeNode?
        var right: TreeNode?
        
        init(value: Int) {
            self.value = value
            self.left = nil
            self.right = nil
        }
    }

    func countLeafNodes(root: TreeNode?) -> Int {
        guard let node = root else {
            return 0
        }
        
        // Check if it is a leaf node
        if node.left == nil && node.right == nil {
            return 1
        }
        
        // Recursively count the number of leaf nodes in the left and right child nodes
        return countLeafNodes(root: node.left) + countLeafNodes(root: node.right)
    }
    

Code Explanation

The above code implements the countLeafNodes function to count the number of leaf nodes in a binary tree. I will describe each part:

• TreeNode class: Defines each node in the binary tree. Each node has a value and left and right children.
• countLeafNodes function: Takes a given node as an argument and returns the number of leaf nodes.
• guard let: Checks if the current node is NULL, and if it is, returns 0 to terminate the search.
• Leaf node check: Returns 1 if the current node has no left and right child nodes.
• Recursive calls: Recursively calls the left and right child nodes and adds up the number of leaf nodes.

Test Cases

Let’s create some test cases to verify that the function works correctly.

    // Create tree
    let root = TreeNode(value: 1)
    let node2 = TreeNode(value: 2)
    let node3 = TreeNode(value: 3)
    let node4 = TreeNode(value: 4)
    let node5 = TreeNode(value: 5)

    // Connect tree structure
    root.left = node2
    root.right = node3
    node2.left = node4
    node2.right = node5

    // Output the number of leaf nodes
    let leafCount = countLeafNodes(root: root)
    print("Number of leaf nodes: \(leafCount)")  // Number of leaf nodes: 3
    

Conclusion

In this article, we explored how to count the number of leaf nodes in a binary tree using Swift. In the process of designing the algorithm and implementing it, we understood the principles of recursive calls and practiced writing actual code. Such problems are frequently encountered in coding tests, so it’s important to practice repeatedly to enhance your proficiency.

Additional Learning Resources

If you want to find more resources related to the problem of counting leaf nodes, consider the following materials:

• GeeksforGeeks: Count Leaf Nodes in Binary Tree
• LeetCode: Number of Leaf Nodes in Binary Tree
• HackerRank: Tree Level Order Traversal

In modern software development, debugging is an essential process. Especially in algorithm tests for employment, it is important not only to solve problems but also to verify the accuracy and efficiency of the code. In this article, we will take a closer look at how to solve algorithm problems using the Swift language and the importance of debugging.

Problem Definition

Problem-Solving Process

Step 1: Understand the Problem

To understand the problem, it is essential to clarify the requirements first. Here, we need to take two integers as input and return their sum. This is a very simple operation, but in coding tests, there may be situations that are not as straightforward as they seem.

Step 2: Design the Algorithm

To solve the problem, we can approach it with a simple set of steps. We will take two integers as input, add them together, and output the result. To do this, we will design the following algorithm:

1. Take the two integers A and B as input.
2. Store the sum of A and B in a variable sum.
3. Return sum.

Step 3: Implement the Code

Let’s implement the above algorithm using Swift.

func addNumbers(A: Int, B: Int) -> Int {
    let sum = A + B
    return sum
}

// Function Test
print(addNumbers(A: 5, B: 10))  // Output: 15

Step 4: Fix Errors Through Debugging

Debugging is the process of verifying that the code we wrote functions as intended. If the function behaves unexpectedly, we need to identify the cause and fix it.

Debugging Techniques

• Using Print Statements: Output the values of variables to verify intermediate processes.
• Condition Checks and Error Verification: Perform additional checks when using boundary conditions or abnormal values.
• Adding Test Cases: Create and run test cases with various input values.

For example, let’s consider the case where A or B might be negative. We can modify the function as follows:

func addNumbers(A: Int, B: Int) -> Int {
    guard A >= 0 && B >= 0 else {
        print("Error: Negative numbers are not allowed.")
        return -1
    }
    let sum = A + B
    return sum
}

// Test - Normal Operation
print(addNumbers(A: 5, B: 10))  // Output: 15

// Test - Abnormal Operation
print(addNumbers(A: -5, B: 10))  // Output: Error: Negative numbers are not allowed.

Step 5: Final Review and Submission

Finally, review the code created and add comments if necessary to enhance readability. In coding tests, it is crucial to ensure that other developers can easily understand my code, considering collaboration.

The Importance of Debugging

Debugging goes beyond merely fixing errors; it provides opportunities to ensure code quality and improve performance through optimization. The problems presented in coding tests are often similar to situations that can arise in real work, so it is important to develop the ability to solve such problems.

Conclusion

We have explored the process of solving algorithm problems using Swift and the importance of debugging. Debugging is a skill essential for successful developers, playing a significant role in enhancing code quality in algorithm tests for employment or actual projects. Furthermore, the experience gained through debugging will greatly assist in solving similar problems in the future.