Swift Coding Test Course, Calculating Average

In this course, we will solve an algorithm problem to calculate the average using the Swift programming language. This problem, frequently seen in coding tests for recruitment, is a good foundation for data processing. Additionally, it will be an opportunity to learn the basic syntax of Swift and how to manipulate arrays.

Problem Description

An array is given as follows. Write a function to calculate the average of all elements in this array. The elements of the array are integers.

Input

  • An integer array numbers is provided. (1 ≤ numbers.count ≤ 100, 0 ≤ numbers[i] ≤ 1000)

Output

  • Output the average value of the given array rounded to the nearest integer at the first decimal place.

Example

Input: [60, 82, 75, 90, 45]
Output: 70
Input: [100, 90, 80]
Output: 90

Solution Process

Step 1: Understanding the Problem

To understand the problem, one must acknowledge that to find the average, all elements of the given array should be summed and then divided by the number of elements. Additionally, it should be remembered that the average needs to be returned as an integer rounded to the nearest whole number.

Step 2: Input Handling

Swift provides various methods to handle arrays easily, so the input array can be used directly. For example, the reduce function can be used to calculate the sum of the array.

Step 3: Algorithm Implementation

Now, let’s implement the algorithm that we will actually use.

func average(numbers: [Int]) -> Int {
    // 1. Compute the total sum of the elements in the array.
    let total = numbers.reduce(0, +)
    
    // 2. Determine the number of elements in the array.
    let count = numbers.count
    
    // 3. Calculate the average and round it.
    let average = Double(total) / Double(count)
    return Int(round(average))
}

Step 4: Writing Test Cases

Based on the function we’ve written, let’s create a few test cases.

let test1 = average(numbers: [60, 82, 75, 90, 45]) // 70
let test2 = average(numbers: [100, 90, 80]) // 90
let test3 = average(numbers: [0, 0, 0, 0]) // 0
let test4 = average(numbers: [1, 2, 3, 4, 5, 6]) // 4
let test5 = average(numbers: [1, 2, 3]) // 2

Step 5: Checking Results and Output

Let’s output the results through testing. We will use the print function for this purpose.

print(test1) // 70
print(test2) // 90
print(test3) // 0
print(test4) // 4
print(test5) // 2

Complete Code

Now, let’s introduce the final code that integrates all the steps.

func average(numbers: [Int]) -> Int {
    let total = numbers.reduce(0, +)
    let count = numbers.count
    let average = Double(total) / Double(count)
    return Int(round(average))
}

// Test Cases
let test1 = average(numbers: [60, 82, 75, 90, 45]) // 70
let test2 = average(numbers: [100, 90, 80]) // 90
let test3 = average(numbers: [0, 0, 0, 0]) // 0
let test4 = average(numbers: [1, 2, 3, 4, 5, 6]) // 4
let test5 = average(numbers: [1, 2, 3]) // 2

print(test1)
print(test2)
print(test3)
print(test4)
print(test5)

Conclusion

Through this course, we learned how to solve the algorithm problem of calculating the average using Swift. The series of processes involved in summing array elements, calculating the average, and outputting the rounded result forms a foundation for data processing. The ability to solve such problems is very important for recruitment coding tests, so it is advisable to strengthen your skills through practice.

References

Swift Coding Test Course, Find Cities at a Specific Distance

Problem Description

There are N cities, and there are M one-way roads between them.
Each city is represented by an integer from 1 to N. If there is a road from city A to city B,
you can travel from A to B.
Write a program to find all cities that are exactly K distance away.
Ensure that the same city is not printed more than once.

Input Format

    N M K
    A1 B1
    A2 B2
    ...
    Am Bm
    
  • N: Number of cities (1 ≤ N ≤ 30000)
  • M: Number of roads (1 ≤ M ≤ 200000)
  • K: Distance to find (0 ≤ K ≤ 30000)
  • A1, B1: Road from city A to city B

Output Format

    Print the city numbers that are K distance away in ascending order.
    If there are no such cities, print -1.
    

Example

Input

    4 4 2
    1 2
    1 3
    2 4
    3 4
    

Output

    4
    

Approach to Solution

This problem can be solved using graph traversal (especially Breadth-First Search BFS).
The given cities can be modeled as nodes, and the roads as edges.
A BFS is performed to find the cities that reach a distance of K.

Overview of BFS Algorithm

BFS works by exploring all adjacent nodes from the starting node, and once
that is complete, it explores the next level of nodes. This method is
suitable for shortest path problems.

Implementation Details

Below is the code that finds cities at a specific distance using BFS in Swift.


    import Foundation

    struct City {
        var number: Int
        var distance: Int
    }

    func findCitiesAtDistanceN(n: Int, roads: [(Int, Int)], k: Int) -> [Int] {
        // Create adjacency list
        var graph = [[Int]](repeating: [Int](), count: n + 1)
        for road in roads {
            let a = road.0
            let b = road.1
            graph[a].append(b)
        }

        // Initialize BFS
        var queue = [City]()
        var distances = Array(repeating: -1, count: n + 1)
        distances[1] = 0 // Assume the starting city is 1
        queue.append(City(number: 1, distance: 0))

        while !queue.isEmpty {
            let current = queue.removeFirst()
            let currentDistance = current.distance
            for neighbor in graph[current.number] {
                if distances[neighbor] == -1 { // If not visited yet
                    distances[neighbor] = currentDistance + 1
                    queue.append(City(number: neighbor, distance: distances[neighbor]!))
                }
            }
        }

        // Find cities at distance K
        let result = distances.enumerated().compactMap { index, distance in
            distance == k ? index : nil
        }.sorted()

        return result.isEmpty ? [-1] : result
    }

    // Example input
    let roads = [(1, 2), (1, 3), (2, 4), (3, 4)]
    let result = findCitiesAtDistanceN(n: 4, roads: roads, k: 2)
    
    print(result) // Output: [4]
    

Code Explanation

In the above code, we first create an adjacency list.
Each city stores its connected neighboring cities as an array.
Then, we perform BFS to calculate the distances for each city.
Finally, we find and print the cities at distance K.

Complexity Analysis

Since we visit every node in the graph,
the time complexity is O(N + M).
The space complexity is also O(N + M).

Conclusion

In this lecture, we addressed the problem of finding cities at a specific distance.
It can be efficiently solved using BFS,
requiring careful implementation. By mastering this algorithm,
you can establish a solid foundation for solving complex graph
and road problems.

Swift Coding Test Course, Finding the Diameter of a Tree

Solving various algorithm problems for coding test preparation is very helpful in improving your programming skills. This time, we will take a deep dive into the ‘Finding the Diameter of a Tree’ problem. Understanding and knowing how to solve tree structures is very useful, as they frequently appear in many programming problems.

Problem Description

A tree is a non-linear data structure composed of nodes and edges. The diameter of a tree refers to the longest path between any two nodes in the tree. In other words, it is about finding the longest path between two nodes (the number of edges between the nodes). This problem can usually be solved using DFS (Depth-First Search) or BFS (Breadth-First Search).

Problem Definition

Given a tree, find the diameter of the tree.
Input: Number of nodes N in the tree (1 <= N <= 100,000)
      Edges in the form of N-1 pairs (u, v) representing each end node of the edge.
Output: Diameter of the tree
    

Problem Analysis

Due to the nature of trees, where all nodes are connected by exactly one path, the method for finding the longest distance between two nodes is to explore using either DFS or BFS. The general idea is as follows:

  1. Choose an arbitrary node A and find the node B that is farthest from A.
  2. Then, find the node C that is farthest from B. The distance at this point is the diameter of the tree.

Algorithm Implementation

Now let’s implement the above algorithm in Swift. We will use an adjacency list to represent the tree.

Swift Code Implementation


import Foundation

class Graph {
    var adjList: [[Int]]

    init(size: Int) {
        adjList = Array(repeating: [], count: size)
    }

    func addEdge(u: Int, v: Int) {
        adjList[u].append(v)
        adjList[v].append(u)
    }

    func bfs(start: Int) -> (Int, Int) {
        var dist = Array(repeating: -1, count: adjList.count)
        var queue: [Int] = []
        
        dist[start] = 0
        queue.append(start)

        var farthestNode = start
        var maxDistance = 0

        while !queue.isEmpty {
            let node = queue.removeFirst()
            for neighbor in adjList[node] {
                if dist[neighbor] == -1 { // If not visited
                    dist[neighbor] = dist[node] + 1
                    queue.append(neighbor)
                    if dist[neighbor] > maxDistance {
                        maxDistance = dist[neighbor]
                        farthestNode = neighbor
                    }
                }
            }
        }
        return (farthestNode, maxDistance)
    }
}

func findTreeDiameter(edges: [(Int, Int)], n: Int) -> Int {
    let graph = Graph(size: n)
    for edge in edges {
        graph.addEdge(u: edge.0 - 1, v: edge.1 - 1) // 0-indexed
    }

    let (farthestNode, _) = graph.bfs(start: 0)
    let (_, diameter) = graph.bfs(start: farthestNode)
    return diameter
}

// Example Input
let n = 5
let edges: [(Int, Int)] = [(1, 2), (1, 3), (2, 4), (2, 5)]
let diameter = findTreeDiameter(edges: edges, n: n)
print("Diameter of the tree: \(diameter)")
    

Code Explanation

This code calculates the diameter of the tree in the following way:

  1. First, we define a Graph class to store the edge list.
  2. We add edge information using the addEdge method.
  3. The bfs function performs BFS starting from a given node and returns the farthest node and its distance.
  4. The findTreeDiameter function creates a graph using the given edges and finds the diameter of the tree through two BFS calls.

Execution Result

When the code is executed, it produces the following output:

Diameter of the tree: 3

This indicates the longest path between node 4 and node 5.

Conclusion

In this lesson, we dealt with the problem of finding the diameter of a tree. This problem can be solved using DFS or BFS and helps enhance understanding of tree structures. It is a question that often appears in actual coding tests, so be sure to practice enough to become familiar with algorithm implementation. It is also beneficial to experiment with various tree cases for a deeper understanding.

In the next lesson, we will cover more algorithm problems, so please stay tuned!

Swift Coding Test Course, Finding the Parent of a Tree

In computer science, a tree is a type of hierarchical data structure and a kind of graph made up of nodes. In this course, we will solve an algorithm problem to find the parent node of a given node using Swift.

Problem Description

Write a function to find the parent node of a specific node in a given binary tree. The tree is represented as follows.


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

You will be given a structure like the one above. Implement the `findParent` function to find the parent node of a specific node in the binary tree that uses this structure.

Function Signature


func findParent(root: TreeNode?, target: Int) -> Int?

Input

  • root: The root node of the binary tree (TreeNode? type)
  • target: The value of the node whose parent you want to find (Int type)

Output

The value of the parent node of the given node. If the given node does not exist or if the root node is the target, return nil.

Example

Assume there is a binary tree as follows:

            1
          /   \
         2     3
        / \   / \
       4   5 6   7

    findParent(root: rootNode, target: 5) ➔ 2
    findParent(root: rootNode, target: 1) ➔ nil
    findParent(root: rootNode, target: 8) ➔ nil
    

Algorithm Design

To find the parent node, we need to traverse the binary tree. We can use common traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS). Here, we will adopt a method using DFS to recursively explore the tree.

DFS Traversal Method

  • If the current node is nil, end the search
  • Check if the value of the current node matches target
  • If matched, return the value of the current node’s parent
  • If not matched, recursively call on the left and right child nodes

Implementation

Now, let’s implement the findParent function based on the above algorithm.


func findParent(root: TreeNode?, target: Int) -> Int? {
    return findParentHelper(root, target: target, parent: nil)
}

private func findParentHelper(_ node: TreeNode?, target: Int, parent: TreeNode?) -> Int? {
    guard let node = node else { return nil } // If the current node is nil

    if node.value == target {
        return parent?.value // Return the parent node
    }

    // Search left child
    let leftResult = findParentHelper(node.left, target: target, parent: node)
    if leftResult != nil {
        return leftResult // Return if found parent in the left
    }

    // Search right child
    return findParentHelper(node.right, target: target, parent: node)
}

Test

Now, let’s test the implemented function to check if it works correctly.


let rootNode = TreeNode(value: 1)
rootNode.left = TreeNode(value: 2)
rootNode.right = TreeNode(value: 3)
rootNode.left?.left = TreeNode(value: 4)
rootNode.left?.right = TreeNode(value: 5)
rootNode.right?.left = TreeNode(value: 6)
rootNode.right?.right = TreeNode(value: 7)

print(findParent(root: rootNode, target: 5) ?? "nil") // 2
print(findParent(root: rootNode, target: 1) ?? "nil") // nil
print(findParent(root: rootNode, target: 8) ?? "nil") // nil

Conclusion

In this course, we implemented an algorithm to find the parent of a specific node in a binary tree using Swift. We applied the basic concept of DFS in the traversal problem of tree structures and learned how to write code.
Through these problems, you can enhance your understanding of trees and recursive thinking.

Additionally, I hope you build your skills by solving problems related to other properties of trees.

Swift Coding Test Course, Understanding Trees

1. Problem Description

In this course, we will enhance our understanding of tree structures using Swift and solve algorithmic problems based on it.
Specifically, we will address the following problem:

Problem: Calculate the Height of a Binary Tree

Write a function to calculate the height of a given binary tree. The height of a binary tree is defined as the length of the longest path from the root node to a leaf node.
The height of a node starts at 0, with leaf nodes having a height of 0.

2. Example

When given the following binary tree,

        1
       / \
      2   3
     / \
    4   5
    

The height of this tree is 2, as the leaf nodes 4 and 5 are two steps away from the root node 1.

3. Approach

This problem can be solved recursively, and the main ideas are as follows:

  1. Define a recursive function to calculate the height of the current node’s left and right child nodes.
  2. Compare the heights of each child node to find the maximum.
  3. The height of the root node is 1 plus the maximum of the left and right child heights.

4. Implementation

Below is the function for calculating the height of a binary tree implemented in Swift:

struct TreeNode {
    var value: Int
    var left: TreeNode?
    var right: TreeNode?
}

func height(of node: TreeNode?) -> Int {
    guard let node = node else {
        return -1 // A null node has a height of -1.
    }
    let leftHeight = height(of: node.left)
    let rightHeight = height(of: node.right)
    return max(leftHeight, rightHeight) + 1
}
    

5. Code Explanation

The function height(of node: TreeNode?) is called recursively.
First, it returns -1 if the node is nil (null), indicating that there is no height for the path including leaf nodes.
After calculating the heights of the left and right children, it selects the larger of the two values and adds 1 to return the height of the current node.

6. Time Complexity

The time complexity of this algorithm is O(N), where N is the number of nodes in the tree.
It takes this time because we have to visit every node once.

7. Additional Tasks

Users can practice more through the following additional tasks:

  • Write a function to check if a specific value exists in the given tree.
  • Write a function to return all the leaf nodes of the binary tree.
  • Implement level order tree traversal to visit all nodes in level order.

8. Conclusion

In this course, we have learned about the concept of binary trees and the basic height calculation algorithm.
Trees play a very important role in data structures, and understanding them is essential for solving algorithmic problems.
Tree-related problems are frequently encountered in coding tests, so practice enough to improve your skills.