Category: C++ Coding Test Tutorials

In recent algorithm coding tests, the segment tree is one of the frequently appearing data structures. The segment tree is a data structure that helps to efficiently calculate the sum, minimum, maximum, etc., of specific intervals. In this article, we will examine algorithm problems using segment trees and provide the process of solving them along with actual implementation examples.

Problem Description

Write a program that can perform queries to compute the sum of the interval [l, r] from a given array. The input includes the size of the array n and the number of queries m, followed by n integers representing the array. Each query consists of two integers l and r.

Example Problem

Input:
5 3
1 2 3 4 5
1 3
2 4
1 5

Output:
6
9
15

Problem Approach

The above problem can be solved by simply traversing the array to calculate the sum, but this is inefficient when the number of queries is large and the size of the array is large. Therefore, using a segment tree allows for an efficient solution to the problem.

What is a Segment Tree?

A segment tree is a tree structure that divides the array into segments and stores information about each segment. This tree has the following characteristics:

• Each node represents an interval of the array.
• Each leaf node stores an element of the array.
• Each internal node stores the sum of its child nodes.

By utilizing a segment tree, the sum of an interval can be computed with O(log n) time complexity. This efficiency becomes more pronounced as the number of elements in the array increases.

Segment Tree Implementation

Now, let’s solve the problem using a segment tree. Below is the code to implement a segment tree in C++.

#include 
#include 
using namespace std;

class SegmentTree {
private:
    vector tree, arr;
    int n;

public:
    SegmentTree(const vector& input) {
        arr = input;
        n = arr.size();
        tree.resize(4 * n);
        build(0, 0, n - 1);
    }

    void build(int node, int start, int end) {
        if (start == end) {
            // Leaf node
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            // Recursively build the segment tree
            build(2 * node + 1, start, mid);
            build(2 * node + 2, mid + 1, end);
            // Internal node will have the sum of the two children
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    int sum(int l, int r) {
        return sum(0, 0, n - 1, l, r);
    }

    int sum(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            // range represented by a node is completely outside the given range
            return 0;
        }
        if (l <= start && end <= r) {
            // range represented by a node is completely inside the given range
            return tree[node];
        }
        // range represented by a node is partially inside and partially outside the given range
        int mid = (start + end) / 2;
        int left_child = sum(2 * node + 1, start, mid, l, r);
        int right_child = sum(2 * node + 2, mid + 1, end, l, r);
        return left_child + right_child;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    SegmentTree segment_tree(arr);
    
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        // Adjusting for 0-based indexing
        cout << segment_tree.sum(l - 1, r - 1) << endl;
    }
    
    return 0;
}

Code Analysis

The above code implements the segment tree using the following procedures:

• Class Definition: Defines the SegmentTree class and declares necessary member variables, which include the tree vector to store the segment tree, the original array arr, and the size of the array n.
• Constructor: The constructor receives the input array, initializes the segment tree, and calls the build method to construct the tree.
• Tree Building: The build method recursively builds the tree. Leaf nodes store elements of the original array, while internal nodes store the sum of child nodes.
• Sum Calculation: The sum method calculates the sum of a given interval. This method checks whether a node falls within the given interval and returns an appropriate value or recursively calculates the sum.
• Main Function: Takes input from the user regarding the size of the array and the number of queries, inputs the array, creates a SegmentTree object, and outputs the results for each query.

Conclusion

Segment trees are a powerful tool for quickly calculating the sum of specific intervals. By implementing a segment tree in C++, we enhanced the efficiency needed for solving algorithm problems. This data structure can be utilized not only for simple sums but also for various queries, so it is important to master it through more practice.

Now you have the foundational knowledge to implement and use segment trees in C++. Explore the power of this data structure by solving various problems.

Problem Description

Write a function to sort a given integer array in ascending order. The sorting algorithm to be used is Selection Sort.

Input

• The first line contains an integer N. (1 ≤ N ≤ 1000)
• The second line contains N integers. (Integer A[i] is -10000 ≤ A[i] ≤ 10000)

Output

Output the sorted array in ascending order in a single line, separated by spaces.

Concept Review of Selection Sort

The selection sort is one of the simplest sorting algorithms. It works by finding the smallest value in the given list and swapping it with the value at the front. This process is repeated until the list is sorted.

Process of Selection Sort

1. Find the smallest value in the current list.
2. Swap that value with the value at the current position.
3. Repeat steps 1 and 2 to sort the list.

Problem-Solving Process

1. Understanding for Problem Solving

To solve the problem, we start by finding the smallest value in the array and placing it at the front, then we find the next smallest value and place it in the second position. This process is repeated for the length of the array, and we need to search the remainder of the array to find the smallest value at each step.

2. Implementation of Selection Sort Algorithm

Now let’s implement the selection sort algorithm in C++. First, we will take the input for the array, then apply the selection sort algorithm to sort it, and finally print the result.

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Set the current position as the index of the minimum value
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // If a minimum value is found
            }
        }
        // Swap the current position with the minimum value's position
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    selectionSort(arr, n);

    for(int i = 0; i < n; i++) {
        cout << arr[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;

    return 0;
}
    

3. Code Explanation

Let me explain each part of the code.

• void selectionSort(int arr[], int n): This function performs selection sort. It takes an array and its size as parameters.
• for (int i = 0; i < n - 1; i++): Iterates through the array to perform sorting.
• int minIndex = i;: Initializes the index of the minimum value at the current index.
• if (arr[j] < arr[minIndex]): Updates the new minimum value’s index if the current value is smaller than the minimum value.
• int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;: Swaps the value at the current index with the value at the minimum value’s index.

4. Example Execution

Below is an example execution of the selection sort algorithm. First, we input N and the array values.

Input:
5
64 25 12 22 11

Output:
11 12 22 25 64
    

Time Complexity

The time complexity of selection sort is O(N2). It requires two nested loops since we need to traverse all the elements to find the minimum value. Thus, performance can degrade with a large amount of data.

Conclusion

In this post, we implemented selection sort using C++ and learned the basic concepts of sorting algorithms. Although selection sort is simple, it is not very efficient, so we should consider other sorting algorithms for larger datasets.

Additional Resources

Many sorting algorithms exist beyond selection sort. It is recommended to learn the following algorithms:

• Bubble Sort
• Insertion Sort
• Merge Sort
• Quick Sort

If you want to learn more about algorithms and data structures, please refer to the following resources:

• Geeks for Geeks – Fundamentals of Algorithms
• Coursera – Algorithm Design and Analysis

Among modern programming languages, C++ is a very popular language due to its speed and efficiency. It is widely used in various fields and becomes a powerful tool, especially in solving algorithmic problems. In this article, we will look at the process of solving an algorithmic problem titled “Dividing Line Segments into Groups” step by step.

Problem Description

The given problem is to divide multiple line segments into groups such that they do not overlap. Two line segments overlap if the endpoint of one segment is before the starting point of another segment while still being after the endpoint of the other segment. Let’s explore the necessary steps and methods to solve this problem.

Example Problem

Let’s assume the following line segments are given:

    Line Segment 1: (1, 3)
    Line Segment 2: (2, 5)
    Line Segment 3: (6, 8)
    Line Segment 4: (7, 9)
    Line Segment 5: (10, 12)
    

Dividing the above line segments into groups could result in the following groups:

• Group 1: {(1, 3), (2, 5)}
• Group 2: {(6, 8), (7, 9)}
• Group 3: {(10, 12)}

Problem Solving Process

Step 1: Problem Analysis

To solve the problem, we must first clarify the input and output formats. The line segments are represented by two integers (start point, endpoint), and overlapping segments must be grouped together. Later, we need to output the number of groups.

Step 2: Approach

To determine whether the line segments overlap, we need to sort the segments by their starting points and then check each line segment in turn to see whether they overlap. A new group can be formed only if they do not overlap.

Step 3: Algorithm Design

The algorithm we will use is as follows:

• Sort all line segments based on the starting point.
• Iterate through the sorted segments, comparing the current group’s endpoint with the starting point of the next segment.
• If they overlap, update the current group’s endpoint; if they do not overlap, start a new group.

Step 4: Implementation

Below is the code implemented in C++:

#include 
#include 
#include 

using namespace std;

struct LineSegment {
    int start;
    int end;
};

bool compare(LineSegment a, LineSegment b) {
    return a.start < b.start;
}

int groupLineSegments(vector& segments) {
    if (segments.empty()) return 0;

    // Sort segments based on the starting point
    sort(segments.begin(), segments.end(), compare);
    
    int groupCount = 1;
    int currentEnd = segments[0].end;

    for (int i = 1; i < segments.size(); i++) {
        if (segments[i].start <= currentEnd) {
            // If they overlap, update currentEnd
            currentEnd = max(currentEnd, segments[i].end);
        } else {
            // If they don't overlap, start a new group
            groupCount++;
            currentEnd = segments[i].end;
        }
    }

    return groupCount;
}

int main() {
    vector segments = {{1, 3}, {2, 5}, {6, 8}, {7, 9}, {10, 12}};
    int result = groupLineSegments(segments);
    
    cout << "Number of groups: " << result << endl;
    return 0;
}

Step 5: Code Execution Result

When executing the above code, you can get the following result:

Number of groups: 3

Conclusion

In this tutorial, we solved the problem of 'Dividing Line Segments into Groups' using C++. Through this problem, we experienced the process of designing algorithms and learned the fundamental concepts of sorting and group classification. Such problems are frequently encountered in real coding tests, so it is essential to practice these kinds of problems repeatedly. I hope you continue to build your skills by practicing various algorithm problems in the future.

The coding test includes various problems to assess programming skills in the field. In this article, we will take a closer look at the process of solving the ‘Finding the Direction of a Line Segment’ problem using C++. This problem is geometric in nature and requires a basic understanding of points and vectors.

Problem Description

Given points A(x1, y1), B(x2, y2), and C(x3, y3), the task is to find the direction of the line segments AB and AC. The direction of the line segments can be classified as clockwise, counterclockwise, or collinear.

Input Format

3
0 0
1 1
2 2

The first line contains the number of points, followed by three lines, each containing the coordinates of a point.

Output Format

0

0 indicates collinear, 1 indicates counterclockwise, and -1 indicates clockwise.

Algorithm Approach

Given points A, B, and C, their directionality can be determined using the cross product of the vectors. The sign of the cross product of the vector from A to B and the vector from A to C can be used to ascertain the direction.

Calculating Cross Product

The result obtained from the cross product is defined as follows:

cross_product = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

Here:

• cross_product > 0 : Counterclockwise
• cross_product < 0 : Clockwise
• cross_product = 0 : Collinear

Code Implementation

Now, let’s write the code to solve the problem in C++.

#include <iostream>

using namespace std;

int main() {
    int x1, y1, x2, y2, x3, y3;
    
    // Input coordinates for points A, B, C
    cout << "Enter coordinates for point A (x1 y1): ";
    cin >> x1 >> y1;
    cout << "Enter coordinates for point B (x2 y2): ";
    cin >> x2 >> y2;
    cout << "Enter coordinates for point C (x3 y3): ";
    cin >> x3 >> y3;

    // Calculate cross product
    int cross_product = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    
    // Determine direction
    if (cross_product > 0) {
        cout << "Counterclockwise (1)" << endl;
    } else if (cross_product < 0) {
        cout << "Clockwise (-1)" << endl;
    } else {
        cout << "Collinear (0)" << endl;
    }

    return 0;
}

Code Explanation

The code includes the following steps:

1. It takes input for the coordinates of points A, B, and C from the user.
2. It calculates the cross product to obtain cross_product.
3. It determines and outputs the direction based on the result.

Additional Explanation for Deeper Understanding

This problem requires a geometric understanding. The cross product is generally used to distinguish the plane of two vectors in 3D space, but in 2D, it serves as a useful tool for determining direction. By understanding geometric concepts and vector mathematics, one can develop the ability to solve various problems.

Geometric Intuition

Geometrically, this problem also involves understanding the slope of a line. When moving from point A to B and from A to C, the relative slopes of the two vectors can be assessed to determine directionality. Depending on whether cross_product is positive or negative, one can ascertain if point C is to the left or right of line AB.

Conclusion

In this lecture, we covered a simple geometric problem that frequently appears in coding tests. The ‘Finding the Direction of a Line Segment’ problem requires a fundamental understanding of geometry and can be solved using the cross product of vectors. By practicing such problems, one can cultivate algorithmic thinking and improve basic C++ programming skills.