Category: C# Coding Test Tutorials

Problem Description

The goal of this problem is to find the parent node of a specific node in a given binary tree.
A binary tree is a hierarchical data structure in which each node can have up to two children.
Our objective is to write a program that correctly finds the parent of the node based on the input node.

Problem Input

    The tree is given as an array, with each element representing a node of the tree. 
    The index of the array represents the position of the node, and index 0 is the root node. 
    For example, in the array [3, 5, 1, 6, 2, 0, 8],
    3 is the root node,
    5 is the left child of node 3,
    1 is the right child of node 3,
    6 is the left child of node 5, 
    2 is the right child of node 5,
    0 is the left child of node 1,
    8 is the right child of node 1.
    

Problem Output

    Outputs the value of the parent node for a specific node. 
    If there is no parent node, output -1.
    

Examples

Input

    Tree: [3, 5, 1, 6, 2, 0, 8]
    Node: 6
    

Output

    5
    

Input

    Tree: [3, 5, 1, 6, 2, 0, 8]
    Node: 3
    

Output

    -1
    

Solution Approach

To solve this problem, it is necessary to understand the structure of the tree and how to find the parent of each node.
In a binary tree, the parent node of each node can be found using the index of the child node and mathematical operations.

Finding the Parent Node

The index of the parent node for a given index can be calculated as follows:

• Parent node index: parentIndex = (childIndex - 1) / 2

– Here, childIndex is the index of the node you want to find.
– If childIndex is 0, this is the root node, so there is no parent node.

Implementation

Now, let’s write the C# code based on the above approach.

public class TreeNodeSearcher 
{
    public static int FindParent(int[] tree, int childIndex) 
    {
        // Check if the input childIndex is valid
        if (childIndex < 0 || childIndex >= tree.Length) 
        {
            throw new ArgumentOutOfRangeException("Child index is out of the range of the tree array.");
        }
        
        // No parent for the root node
        if (childIndex == 0) 
        {
            return -1; // No parent
        }

        // Calculate parent index
        int parentIndex = (childIndex - 1) / 2;
        return tree[parentIndex];
    }
}
    

Tests

To effectively test the above method, let’s create some cases.

public class Program 
{
    public static void Main() 
    {
        int[] tree = {3, 5, 1, 6, 2, 0, 8};

        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 3)); // Output: 5
        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 0)); // Output: -1
        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 5)); // Output: 1
        Console.WriteLine(TreeNodeSearcher.FindParent(tree, 1)); // Output: 3
    }
}
    

Conclusion

We have successfully implemented an algorithm to find the parent node of a specific node in a given binary tree.
This algorithm is very efficient with a time complexity of O(1).
Understanding and utilizing the structure of the tree is important, and these fundamental concepts can be applied usefully when dealing with more complex data structures.

Additional Learning

To deepen your understanding of trees, it is recommended to explore advanced topics such as binary search trees, AVL trees, and heaps.
These data structures will be very helpful in solving a variety of algorithm problems.

Problem Description

This is a problem to determine the direction of a line segment composed of two points A(x1, y1) and B(x2, y2). When the coordinates of points A and B are given, you need to write a function to determine whether the direction of the line segment is upwards, downwards, left, right, or diagonal.

The input consists of integer pairs representing the coordinates of A and B, and the output is one of “Up”, “Down”, “Left”, “Right”, “Diagonal”, or “Same”.

Input Example

(1, 1), (2, 2)

Output Example

Diagonal

Problem Analysis

To solve the problem, you need to calculate the difference in coordinates between the two points (A, B) to determine the direction of the line segment. The criteria for judgment are as follows.

• y2 > y1 means “Up”.
• y2 < y1 means “Down”.
• x2 > x1 means “Right”.
• x2 < x1 means “Left”.
• x2 == x1 && y2 == y1 means “Same”.
• In other cases: it is judged as “Diagonal”.

Algorithm Design

The flow of the algorithm is as follows.

1. Receive the coordinates of A and B as input.
2. Compare the x and y coordinate values of A and B.
3. Determine the direction based on the conditions.
4. Return the result.

C# Code Implementation

public class Program
{
    public static void Main(string[] args)
    {
        var result = GetLineDirection(1, 1, 2, 2);
        Console.WriteLine(result); // Diagonal
    }

    public static string GetLineDirection(int x1, int y1, int x2, int y2)
    {
        if (x1 == x2 && y1 == y2)
        {
            return "Same";
        }
        else if (y2 > y1 && x2 > x1)
        {
            return "Diagonal";
        }
        else if (y2 > y1)
        {
            return "Up";
        }
        else if (y2 < y1)
        {
            return "Down";
        }
        else if (x2 > x1)
        {
            return "Right";
        }
        else if (x2 < x1)
        {
            return "Left";
        }
        else
        {
            return "Diagonal";
        }
    }
}

Code Explanation

The code above contains the GetLineDirection function, which takes the coordinates of two points A(x1, y1) and B(x2, y2) as input to determine the direction of the line segment.
In the Main method, the function is called based on sample coordinates, and the result is printed. Each conditional statement determines the direction of the line segment and returns the corresponding string.

Time Complexity Analysis

This algorithm performs simple comparison operations for the inputted two points, so the time complexity is O(1). In other words, it takes a constant amount of time regardless of the size of the input data.

Test Cases

Various test cases are used to verify the accuracy of the algorithm.

    // Test cases
    Console.WriteLine(GetLineDirection(1, 1, 1, 1)); // Same
    Console.WriteLine(GetLineDirection(1, 1, 2, 2)); // Diagonal
    Console.WriteLine(GetLineDirection(1, 1, 1, 2)); // Up
    Console.WriteLine(GetLineDirection(1, 2, 1, 1)); // Down
    Console.WriteLine(GetLineDirection(1, 1, 2, 1)); // Right
    Console.WriteLine(GetLineDirection(2, 1, 1, 1)); // Left

Conclusion

Through this problem, we learned a simple but useful algorithm to determine the direction of a line segment based on the coordinates of two points.
We were able to learn how to solve the problem using simple mathematical operations by utilizing the features of C#.
It is important to approach the problem from various angles and verify the accuracy of the algorithm through multiple test cases.

You too can develop your ability to solve your own problems based on this algorithm!

Introduction

Hello. In this lecture, we will take a deep dive into one of the useful sorting algorithms for preparing coding tests, called ‘Insertion Sort’. Sorting algorithms are an important topic that forms the foundation for data structures and algorithm problem-solving. In particular, we aim to help readers understand by presenting theoretical background, code implementation, and specific examples of problem-solving.

What is Insertion Sort?

Insertion Sort is a sorting algorithm that works by inserting new data into an already sorted state. It selects one element at a time from the given data and inserts it into the appropriate position by comparing it with the already sorted portion. This algorithm is very intuitive and easy to implement.

How Insertion Sort Works

Insertion Sort works in the following way:

1. Select the first element from the unsorted list. This element is considered to be already sorted.
2. Select the next element and compare it with the sorted elements.
3. If the currently selected element is smaller than the sorted element, insert it into the appropriate position in the sorted list.
4. Repeat this process until the end of the list.

Time Complexity of Insertion Sort

The time complexity of Insertion Sort is O(n²) in the worst case. However, if the data is nearly sorted, it shows an average performance of O(n). This can be an advantage of Insertion Sort compared to other algorithms. In special cases, it operates in O(n), making it frequently used in real problems.

C# Implementation of Insertion Sort

Now, let’s implement the Insertion Sort algorithm using C#:

using System;

class Program
{
    static void InsertionSort(int[] arr)
    {
        for (int i = 1; i < arr.Length; i++)
        {
            int key = arr[i];
            int j = i - 1;

            // Move elements that are greater than the current key one position back
            while (j >= 0 && arr[j] > key)
            {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key; // Insert the key in the appropriate position
        }
    }

    static void Main()
    {
        int[] array = { 12, 11, 13, 5, 6 };
        InsertionSort(array);

        Console.WriteLine("Sorted array: ");
        foreach (int num in array)
        {
            Console.Write(num + " ");
        }
    }
}

Problem Solving: Sorting Given Array

Here is an example of a problem that may be given in a coding test:

Problem: Given an integer array, use insertion sort to sort the array in ascending order.

Input Example: [64, 34, 25, 12, 22, 11, 90]

Output Example: [11, 12, 22, 25, 34, 64, 90]

To solve the above problem, we can implement the Insertion Sort algorithm as previously described. Let’s sort the given array using insertion sort.

using System;

class InsertionSortExample
{
    static void InsertSort(int[] array)
    {
        for (int i = 1; i < array.Length; i++)
        {
            int key = array[i];
            int j = i - 1;

            while (j >= 0 && array[j] > key)
            {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }

    static void Main()
    {
        int[] nums = { 64, 34, 25, 12, 22, 11, 90 };
        InsertSort(nums);

        Console.WriteLine("Sorted array: ");
        foreach (var num in nums)
        {
            Console.Write(num + " ");
        }
    }
}

Conclusion

In this lecture, we have deeply understood the Insertion Sort algorithm, how to implement it in C#, and the process of solving actual problems. Due to its relatively easy understanding and implementation, Insertion Sort is often used as the basis for many coding test problems. Now that you have mastered Insertion Sort, try solving various problems to further improve your skills!

Hello, everyone! Today, we will take a deep dive into one of the important algorithms dealt with in coding tests using C#, which is Breadth-First Search (BFS). BFS is an algorithm for exploring graph or tree data structures, and it is useful for solving shortest path problems or finding specific nodes.

1. What is Breadth-First Search (BFS)?

BFS is a search algorithm implemented using the Queue data structure. This algorithm starts from a given node, explores all the adjacent nodes to that node, and then continues to explore the adjacent nodes of the nodes it has just explored. This approach gradually explores wider areas, hence the name ‘Breadth-First’.

2. Characteristics of BFS

• Shortest path exploration: BFS is suitable for finding the shortest path when all edge weights are the same.
• Sunlight exploration: BFS visits closer nodes first, exploring in a way that can be likened to sunlight shining.
• Uses a queue: It uses a queue to store the order of exploration, managing the nodes to be visited in a FIFO (First In First Out) manner.

3. How BFS Works

The basic operation of BFS is as follows:

1. Add the starting node to the queue and mark it as visited.
2. Remove a node from the queue and check all its adjacent nodes.
3. If an adjacent node has not been visited yet, add it to the queue and mark it as visited.
4. Repeat steps 2 and 3 until the queue is empty.

4. Problem Solving

Now, let’s understand BFS through a problem that is likely to come up in a real coding test.

Problem: ‘Labeling Complexes’

We have an array of size n × n consisting of 0s and 1s. Here, 1 indicates where a house exists, and 0 indicates where there are no houses. We consider connected houses as a single complex, and we will use BFS to label the complexes. The problem is to count the number of houses belonging to the same complex and output the size of each complex.

Input

5
01101
11011
11100
00011
00000

Output

3
2
1

5. C# Code Implementation

Below is the C# code written to solve this problem using BFS.

using System;
using System.Collections.Generic;

class Program
{
    static int n;
    static int[,] map;
    static bool[,] visited;
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };

    static void Main()
    {
        n = int.Parse(Console.ReadLine());
        map = new int[n, n];
        visited = new bool[n, n];

        for (int i = 0; i < n; i++)
        {
            string line = Console.ReadLine();
            for (int j = 0; j < n; j++)
            {
                map[i, j] = line[j] - '0';
            }
        }

        List results = new List();

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (map[i, j] == 1 && !visited[i, j])
                {
                    results.Add(BFS(i, j));
                }
            }
        }

        results.Sort();
        Console.WriteLine(results.Count);
        foreach (int count in results)
        {
            Console.WriteLine(count);
        }
    }

    static int BFS(int startX, int startY)
    {
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((startX, startY));
        visited[startX, startY] = true;

        int count = 0;

        while (queue.Count > 0)
        {
            var (x, y) = queue.Dequeue();
            count++;

            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < n && ny < n && map[nx, ny] == 1 && !visited[nx, ny])
                {
                    queue.Enqueue((nx, ny));
                    visited[nx, ny] = true;
                }
            }
        }

        return count;
    }
}

6. Code Explanation

The C# code above works as follows:

1. It receives n as input and stores the house placement information in a 2D array of size n × n.
2. The visited array records whether each house has been visited.
3. Nesting for loops are used to explore all houses, executing BFS only for unvisited houses.
4. The BFS method uses a queue to explore connected houses from the starting point and counts the number of connected houses.
5. It stores the sizes of all complexes in a list, sorts them, and then outputs them.

7. Conclusion

In this lecture, we explored how to solve problems in coding tests using Breadth-First Search (BFS). BFS is a powerful tool applicable to various problems. Understanding BFS is crucial in situations like exploring graphs or finding the shortest path.

Continue to build your skills by practicing BFS with examples and tackling more complex problems. If you have any questions or comments, feel free to leave them in the comments. In the next session, we will cover another algorithm!

Hello, blog readers! Today, as part of the C# coding test course, we will address the line-up problem. This problem may seem simple, but without the right algorithm, it can become quite complex. Additionally, it is one of the types of problems frequently encountered in actual job coding tests.

Problem Description

This problem involves lining up students based on their height information. Students should be sorted in ascending order by height, and those with the same height must maintain their original order. In other words, stability must be maintained during sorting.

Problem Definition

    Given an array of students' heights, the task is to sort the array in ascending order.

    Input
    - Integer N: The number of students (1 ≤ N ≤ 100,000)
    - Integer array heights: Heights of the students (1 ≤ heights[i] ≤ 200 cm)

    Output
    - The sorted heights of the students should be returned.
    

Sample Input and Output

    Input: [160, 155, 170, 160, 175]
    Output: [155, 160, 160, 170, 175]
    

Problem-Solving Strategy

It’s important to devise a strategy for solving the problem. Since we need to sort the students’ heights, we should apply an efficient sorting algorithm. Among various sorting algorithms, we can use Merge Sort or Quick Sort, which both have a time complexity of O(N log N).

1. Merge Sort Explanation

Merge sort is a divide-and-conquer algorithm that splits an array into two sub-arrays, sorts each, and then merges the sorted sub-arrays to produce a final sorted array. This method is stable and useful when a sorted array is required.

2. Quick Sort Explanation

Quick sort is also a divide-and-conquer algorithm. It splits the array into two parts based on a pivot and sorts them recursively. The average time complexity is O(N log N), but in the worst case, it can be O(N^2). However, performance can be improved with an appropriate pivot selection.

C# Code Implementation

In this section, we will write code to solve the problem using the C# language. Below is the code that sorts students’ heights using merge sort.

using System;

class Sort
{
    public static void MergeSort(int[] heights, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;
            MergeSort(heights, left, mid);
            MergeSort(heights, mid + 1, right);
            Merge(heights, left, mid, right);
        }
    }

    public static void Merge(int[] heights, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; i++)
            leftArray[i] = heights[left + i];
        for (int j = 0; j < n2; j++)
            rightArray[j] = heights[mid + 1 + j];

        int k = left;
        int iIndex = 0, jIndex = 0;

        while (iIndex < n1 && jIndex < n2)
        {
            if (leftArray[iIndex] <= rightArray[jIndex])
            {
                heights[k] = leftArray[iIndex];
                iIndex++;
            }
            else
            {
                heights[k] = rightArray[jIndex];
                jIndex++;
            }
            k++;
        }

        while (iIndex < n1)
        {
            heights[k] = leftArray[iIndex];
            iIndex++;
            k++;
        }

        while (jIndex < n2)
        {
            heights[k] = rightArray[jIndex];
            jIndex++;
            k++;
        }
    }

    static void Main(string[] args)
    {
        int[] heights = { 160, 155, 170, 160, 175 };
        MergeSort(heights, 0, heights.Length - 1);

        Console.WriteLine("Sorted heights: " + string.Join(", ", heights));
    }
}
    

Code Explanation

The code above is an example of sorting a given array using the merge sort algorithm. The MergeSort method recursively divides the array, and the Merge method merges the two sub-arrays to achieve sorted order.

Code Flow

• MergeSort Method: Recursively divides the array into halves to sort it.
• Merge Method: Merges two sorted sub-arrays into one sorted array.
• Main Method: The starting point of the program, defining a sample array, sorting it, and outputting the result.

Performance Analysis

The time complexity of merge sort is O(N log N) and remains the same in the worst case. The space complexity is O(N). This is advantageous when processing large datasets. Because sorting is stable, for example, in cases where heights are the same, the original order can be guaranteed.

Applications of This Problem

The line-up problem can be applied in many fields. For example, it can be useful in queue management, student performance analysis, and various other scenarios. While solving this problem, it's good to consider the potential for expanding to other data sorting problems.

Conclusion

In this post, we explored how to solve the line-up problem using C#. Through defining the problem and implementing algorithms and code to solve it, we can develop algorithmic thinking. It is important to enhance algorithmic thinking through various problems.

Next time, we will address another type of algorithm problem. Please leave any questions or feedback in the comments. Thank you!