Category: Swift Coding Test

Hello! Today, we will solve a coding test problem related to binary trees. Binary trees are a data structure that appears frequently in many problems. A binary tree is a tree structure where each node can have a maximum of two children, allowing for various traversal methods. Our goal is to understand binary trees and utilize them to solve specific problems.

Problem Description

Given the following binary tree, write a function that traverses all nodes using DFS (Depth-First Search) and returns the values of the nodes as a list.

Problem Definition

func depthFirstTraversal(root: TreeNode?) -> [Int] {}

Input: The root node of the binary tree, root

Output: An integer array containing the values of the nodes from the DFS traversal

Example

Input:

        1
       / \
      2   3
     / \
    4   5
    

Output:

[1, 2, 4, 5, 3]

Definition of Binary Tree

A binary tree is a tree structure that can have two child nodes. Each node has a value, and binary trees are usually defined recursively. Since a node may be empty, the root node should be handled as nil.

Problem Solving Process

To solve this problem, we will explore the tree using the DFS method. DFS means Depth-First Search, which involves completely traversing one branch before moving on to the next. Below, we explain the process of tree traversal using DFS.

Step 1: Define Tree Node

First, we need to define a tree node. We will implement the TreeNode class to define a tree node.

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

Step 2: Implement DFS Function

Now we will implement a function to traverse the binary tree using the DFS method. The priority is current node -> left child -> right child. We will perform this recursively.

    func depthFirstTraversal(root: TreeNode?) -> [Int] {
        guard let node = root else { return [] }
        
        // Add the current node's value to the array
        var result = [node.value]
        
        // Explore the left subtree
        result += depthFirstTraversal(root: node.left)
        
        // Explore the right subtree
        result += depthFirstTraversal(root: node.right)
        
        return result
    }
    

Step 3: Test and Validate

Now, we will create a binary tree to test the function we have implemented. We will use the example above to create the tree.

    let root = TreeNode(value: 1)
    let leftChild = TreeNode(value: 2)
    let rightChild = TreeNode(value: 3)
    let leftLeftChild = TreeNode(value: 4)
    let leftRightChild = TreeNode(value: 5)
    
    root.left = leftChild
    root.right = rightChild
    leftChild.left = leftLeftChild
    leftChild.right = leftRightChild
    
    let result = depthFirstTraversal(root: root)
    print(result)  // [1, 2, 4, 5, 3]
    

Conclusion

We have implemented a DFS algorithm to traverse binary trees. Through this problem, we were able to understand the structure of binary trees and the concept of DFS traversal. In Swift, trees can be easily traversed using recursion, and problems like this are common in coding tests, making it important to practice. In the next session, we will explore another algorithmic problem. Thank you!

1. Overview of Binary Search

Binary Search is an algorithm used to find the position of a specific value in a sorted array.
It is very efficient as it divides the array in half to find the desired value,
having a time complexity of O(log n) in both average and worst cases.
This is significantly better than the O(n) of linear search.

1.1 Principle of Binary Search

Binary Search proceeds with the following steps:

1. Check if the array to be searched is sorted.
2. Set the start index and end index.
3. Calculate the middle index.
4. Compare the middle value to the value you want to find.
5. If the value to be found is less than the middle value, set the end index to middle index – 1,
   and if it’s greater, set the start index to middle index + 1.
6. Repeat until the value is found or the start index is greater than the end index.

2. Algorithm Problems

Now, let’s look at a problem that utilizes binary search.

Problem: Finding the Index of a Specific Number in an Array

Given an integer array nums and an integer target, 
write a function that returns the index of target if it exists in the array nums, 
or -1 if it does not exist.

Example:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

3. Problem Solving Process

To solve the problem, we will use the binary search algorithm to find the target value in the array.
I will explain step by step.

3.1 Function Definition

First, we define the binarySearch function that will perform the binary search.
This function takes the array nums and the target value as arguments.

func binarySearch(nums: [Int], target: Int) -> Int {
    var left = 0
    var right = nums.count - 1

    while left <= right {
        let mid = left + (right - left) / 2

        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

3.2 Variable Initialization

Initialize the variables left and right to 0 and the length of the array - 1, respectively.
left represents the starting index of the search range, and right represents the ending index.

3.3 Calculating the Middle Value

Use the while loop to repeat until left is less than or equal to right.
In each iteration, calculate the middle index mid.
When calculating the middle value, use left + (right - left) / 2 to prevent overflow.

3.4 Comparing the Target

If the middle value nums[mid] equals target, return that index mid.
If nums[mid] is less than target,
set left to mid + 1 to search the right half.
Conversely, if nums[mid] is greater than target,
set right to mid - 1 to search the left half.

3.5 Returning the Result

When the loop ends, it means target does not exist in the array, so return -1.

4. Full Code

func binarySearch(nums: [Int], target: Int) -> Int {
    var left = 0
    var right = nums.count - 1

    while left <= right {
        let mid = left + (right - left) / 2

        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

// Example usage
let nums = [-1, 0, 3, 5, 9, 12]
let target = 9
let result = binarySearch(nums: nums, target: target)
print(result) // 4

5. Advantages and Disadvantages of Binary Search

5.1 Advantages

The main advantage of binary search is its fast search speed.
It shows significantly higher performance compared to linear search when dealing with very large datasets.

5.2 Disadvantages

However, a disadvantage of using binary search is that the data must be sorted.
Frequent insertion and deletion of data may require separate sorting operations.

6. Conclusion

Binary search is an efficient searching method and is one of the topics frequently asked in coding tests.
Through the above problem, I hope you have understood the principles and implementation methods of binary search,
and gained useful experience in writing code in Swift.

7. Additional Practice Problems

To deepen your understanding of binary search, try solving the additional problems below.

• Write a function that finds and returns all indices of a specific number in a given integer array.
• Implement a function that finds the first and last positions in a sorted array.
• Write a function that determines whether there is a combination of two numbers in an integer array that adds up to a specific number.

What is a bipartite graph?
A bipartite graph is a graph whose vertex set can be divided into two mutually exclusive subsets. In other words, it is a division such that all edges of the graph only exist between vertices of the two different sets.
The most common example of a bipartite graph is the “matching” problem. For instance, when matching students to classes, students and classes can be entered as each of the respective sets.
Bipartite graphs have the property that they can always be colored with two colors.

Problem Description

Write a function to determine if the given undirected graph is bipartite.
The given graph is presented in the form of an adjacency list, and the vertices are connected from 0 to n-1.
The function should return true if the graph is bipartite, and false otherwise.

Input Example

    n = 4
    edges = [[0, 1], [0, 3], [1, 2], [2, 3]]
    

Output Example

    false
    

Problem Solving Process

1. Understanding the Structure of the Graph

   The given graph consists of nodes and edges, with each node connected to other nodes.
   We will represent the graph in an undirected linked list format.
   Many programming languages, including Java and Swift, can implement this structure using arrays or hashmaps.

2. Properties of Bipartite Graphs and Search Methods

   A bipartite graph can be divided into two sets of vertices,
   where all adjacent vertices must belong to different sets. Utilizing this property, we can employ depth-first search (DFS) or breadth-first search (BFS)
   as an approach to color the graph.

3. Exploring the Graph Using DFS or BFS

   We start exploring the graph by coloring each vertex.
   Two colors are used (e.g., 1 and -1), and if we revisit a node that is already colored,
   we can determine that it is not a bipartite graph if the colors match.

Code Implementation

We will now implement an algorithm to determine bipartiteness in Swift.

    class Solution {
        func isBipartite(_ graph: [[Int]]) -> Bool {
            let n = graph.count
            var color = Array(repeating: -1, count: n) // -1 means uncolored
            
            for i in 0..

    0 -- 1
    |    |
    3 -- 2