Category: C++ Coding Test Tutorials

C++ Coding Test Course, Gift Delivery

Hello, everyone! In this post, we will discuss a C++ algorithm problem called “Gift Exchange.” This problem focuses particularly on testing sequential thinking and algorithm design skills.

Problem Description

The gift exchange problem models the process of passing gifts among a group of people. You need to solve the problem with the following conditions.

  • There are n people.
  • Each person has one gift.
  • Any two people can exchange gifts with each other.

Your goal is to find an optimal way to pass the gifts so that everyone receives at least one gift.

Input Format

The first line contains the number of people n, and the next n lines provide the information about the gifts each person has.

Output Format

Output the minimum gift exchange method such that everyone receives at least one gift.

Approach

To solve this problem, you need an understanding of the basics of graph theory and search algorithms like BFS or DFS. The strategy to solve the problem is as follows:

  1. Model the problem in the form of a graph.
  2. Use BFS or DFS to explore the gift exchange paths.
  3. Find the minimum path at each node (person) to exchange gifts.

C++ Code Implementation

Now, let’s solve the problem with C++ code. The code below is an example that implements gift exchange among people based on the given conditions.

            
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Person {
    int id;
    vector<int> gifts;
};

// Graph structure for gift exchange
void giftExchange(vector<Person> &people) {
    queue<int> q;
    vector<bool> received(people.size(), false);

    // Find people who have not received gifts and add them to the queue
    for (int i = 0; i < people.size(); ++i) {
        if (people[i].gifts.empty()) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        
        for (int giftRecipient : people[current].gifts) {
            if (!received[giftRecipient]) {
                cout << "Person " << current << " has delivered a gift to person " << giftRecipient << "!" << endl;
                received[giftRecipient] = true;
                // After delivering the gift, add the current person back to the queue
                q.push(giftRecipient);
            }
        }
    }
}

int main() {
    int n;
    cout << "Please enter the number of people: ";
    cin >> n;
    vector<Person> people(n);

    for (int i = 0; i < n; ++i) {
        people[i].id = i;
        int m;
        cout << "Please enter the number of gifts person " << i << " will give: ";
        cin >> m;

        for (int j = 0; j < m; ++j) {
            int giftRecipient;
            cout << "Please enter the ID of the person who will receive the gift from person " << i << ": ";
            cin >> giftRecipient;
            people[i].gifts.push_back(giftRecipient);
        }
    }

    giftExchange(people);
    return 0;
}

Code Explanation

The code above implements a C++ program to solve the gift exchange problem. Each person has a list of their gifts, and a queue is used to simulate the exchange process. Starting with those who have never received gifts, the simulation proceeds to properly exchange gifts for each person.

Code Analysis

Let’s analyze the code step by step:

  • Structure Definition: The struct Person stores the ID of a person and the information about the gifts they will give.
  • Queue Initialization: Finds those who have not received gifts and adds them to the queue.
  • Loop: Extracts each person from the queue one by one and processes the gift exchange.

Key Concept Explanation

This problem helps to understand the following algorithmic concepts:

  • BFS Search: Simulates the gift exchange process using the Breadth-First Search (BFS) algorithm.
  • Graph Modeling: Models the relationships between people and gift exchange in the form of a graph for efficient problem-solving.

Considerations After Solving the Problem

After solving the problem, consider asking yourself the following questions:

  • What is the time complexity of this algorithm?
  • Were there any alternative approaches?
  • What other problems could be modified or derived from this problem?

Conclusion

Preparing for coding tests is important as it helps you experience various problems and improve your algorithm design skills. I hope you could learn graph exploration using DFS and BFS through the “Gift Exchange” problem. Don’t neglect practicing writing efficient code by effectively utilizing the features of the C++ language!

Next time, I will bring another interesting problem. Thank you!

C++ Coding Test Course, Insertion Sort

Hello! In this post, I will discuss Insertion Sort, which is one of the algorithms frequently asked in coding tests using C++. Insertion Sort is a very intuitive sorting algorithm that works by inserting new data into a sorted array. So, shall we get started?

Problem Description

You have an array containing given integers. Output the result of sorting this array in ascending order using Insertion Sort.

Input Format

The first line contains the size of the array N. (1 ≤ N ≤ 1000)

The second line contains N integers separated by spaces. (Each integer is -1000 ≤ x ≤ 1000)

Output Format

Output the sorted array in one line. Each element is separated by a space.

Example

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

Algorithm Explanation

Insertion Sort works by inserting new values into a sorted array. The algorithm proceeds in the following steps:

  1. The first element is considered to be sorted.
  2. Starting from the second element, find the position to insert it in the sorted array.
  3. Shift the elements of the array to the right one step to find the position for the new element.
  4. When the correct position is found, insert the new element.
  5. Repeat this process for all elements in the array.

C++ Code Implementation

Now let’s implement the above algorithm in C++. The code is as follows:

        
        #include <iostream>
        #include <vector>

        using namespace std;

        void insertionSort(vector<int>& arr) {
            int n = arr.size();
            for (int i = 1; i < n; i++) {
                int key = arr[i];
                int j = i - 1;

                // Move elements greater than key one position ahead
                while (j >= 0 && arr[j] > key) {
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = key; // Insert the key at the correct position
            }
        }

        int main() {
            int N;
            cin >> N;
            vector<int> arr(N);

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

            insertionSort(arr);

            for (int i = 0; i < N; i++) {
                cout << arr[i];
                if (i < N - 1) cout << " "; // To avoid adding a space after the last element
            }

            return 0;
        }

Code Explanation

The above code is an implementation of the Insertion Sort algorithm in C++. Let’s take a look at the main parts:

  • Including Header Files: Includes <iostream> and <vector> to handle input/output and to use dynamic arrays.
  • insertionSort Function: This function sorts the array. It sets the key for each element and finds its position to insert in the sorted array.
  • Main Function: Takes the size of the array as input, reads the array, calls the insertionSort function to sort it, and finally outputs the sorted result.

Time Complexity Analysis

The time complexity of Insertion Sort is as follows:

  • Worst Case: O(n^2) (when the array is in reverse order)
  • Average Case: O(n^2)
  • Best Case: O(n) (when the array is already sorted)

Due to this time complexity, Insertion Sort is efficient for small arrays but performs poorly on larger arrays.

Advantages and Disadvantages

Advantages

  • Easy to implement and understand
  • Very efficient for small data sets
  • It is a stable sort (the order of equal elements is preserved)

Disadvantages

  • Not efficient for large input sizes due to O(n^2) time complexity
  • Can be inefficient in terms of memory usage since it directly modifies the array

Additional Examples to Enhance Understanding

Let’s visualize the operation of Insertion Sort through additional examples. Below is an example demonstrating the process of Insertion Sort.

Example

        Input:
        6
        4 3 5 1 2 6
  
        Process:
        Initial array: 4 3 5 1 2 6
        Step 1: [4] [3] 5 1 2 6 → 3 4 5 1 2 6
        Step 2: 3 4 [5] [1] 2 6 → 3 4 5 1 2 6
        Step 3: 3 4 5 [1] [2] 6 → 1 3 4 5 2 6
        Step 4: 1 3 4 5 [2] 6 → 1 2 3 4 5 6
        Step 5: 1 2 3 4 5 [6] → 1 2 3 4 5 6

Conclusion

Today we learned about Insertion Sort using C++. Remember that Insertion Sort is a simple yet useful algorithm, effective for small data sets. In the next post, we will cover a more complex sorting algorithm called Quick Sort. If you have any questions or comments, please leave them below. Thank you!

References

C++ Coding Test Course, Dictionary

Hello! Today we will tackle an algorithm problem using C++. The topic is “Dictionary Lookup”. This problem deals with the process of finding a specific word in a given list of words. We will explore the related algorithm and learn how to efficiently solve the problem.

Problem Description

The problem is as follows.

    Problem: Finding a word in a dictionary
    - You are given a dictionary consisting of n words.
    - When a word to search is given as input, write a program to check if this word exists in the dictionary.
    
    Input:
    - The first line contains the number of words n (1 ≤ n ≤ 100,000).
    - In the next n lines, each line consists of a word made up of lowercase letters.
    - The last line contains the word to search.
    
    Output:
    - If the word exists in the dictionary, print 'YES', otherwise print 'NO'.

Analysis of the Problem

This problem is a simple string search problem that involves finding a word in a dictionary. Therefore, the main point to solve is an efficient search method. Since the number of words can be up to 100,000, inefficient methods can lead to timeouts.

The simplest method is to use a list to traverse all words and compare values, but this method has a time complexity of O(n), which is inefficient for lightweight search engines that demand optimal performance in the worst cases. Therefore, we need a method that utilizes a hashmap since it allows for average-case search time complexity of O(1).

Implementation Method

Now, let’s write the code in C++ to solve the problem. We will proceed with the following steps:

  1. Take the number of words as input.
  2. Create a hashmap using unordered_map to store the words.
  3. Add the words in the dictionary to the hashmap.
  4. Input the word to search and check for its existence in the hashmap.

Code Implementation

    
    #include 
    #include 
    #include 

    using namespace std;

    int main() {
        int n;
        cin >> n; // Input number of words
        unordered_map dictionary; // Initialize the hashmap

        // Input words
        for (int i = 0; i < n; i++) {
            string word;
            cin >> word;
            dictionary[word] = true; // Add word to hashmap
        }

        string searchWord;
        cin >> searchWord; // Input the word to search

        // Check the existence of the word
        if (dictionary.find(searchWord) != dictionary.end()) {
            cout << "YES" << endl; // If exists
        } else {
            cout << "NO" << endl; // If does not exist
        }

        return 0;
    }

Code Explanation

Let me briefly explain the code.

  • #include : Includes the library for input and output in C++.
  • #include : Library for using hashmaps, allowing for O(1) search time complexity.
  • #include : Library for handling strings.
  • unordered_map dictionary;: Declares a hashmap to store words.
  • cin >> n;: Takes the number of words as input.
  • dictionary[word] = true;: Adds the input word to the hashmap. The key of the hashmap is the word, and the value is set to true.
  • dictionary.find(searchWord): Searches for the query in the hashmap to check its existence.

Testing and Results

Now let's test this code in practice. For example, we will input the following:

    5
    apple
    banana
    cherry
    date
    elderberry
    banana

If we input as above, the output will be:

    YES

We can consider another example:

    5
    apple
    banana
    cherry
    date
    elderberry
    fig

In this case, the output will be:

    NO

Complexity Analysis

The time complexity of this algorithm is as follows:

  • Word Insertion: O(1) (on average, due to the nature of the hashmap)
  • Word Search: O(1) (also on average)

Thus, the overall time complexity is O(n). The space complexity depends on the number of words stored in the hashmap, which is O(n).

Conclusion

Today we learned how to solve the problem of finding a word in a dictionary using C++. We demonstrated how the approach using hashmaps can significantly improve time complexity. Algorithm problems can always be approached in various ways, so I encourage you to try out different methods!

C++ Coding Test Course, Finding Building Order

Problem Description

A city consists of several buildings, each with a unique number. There are directed roads between the buildings.
The problem is to determine the construction order of these buildings based on specific rules that must be followed.

The construction order of all buildings is determined by the given conditions. This problem can be represented
as a Topological Sort problem. The goal is to calculate and output the desired order of buildings based on the
given rules.

Input Format

The first line contains the number of buildings N and the number of roads M. (1 ≤ N ≤ 10^6, 0 ≤ M ≤ 10^6)
The next M lines contain the information about the roads, where two integers A and B indicate that building A
must be constructed before building B.

Output Format

Output the construction order of the buildings in a single line. If it is impossible to determine the construction order, output ‘0’.

Example

Input

    4 2
    1 2
    2 3

Output

    1 2 3 4

Approach

To solve this problem, we can consider two methods:
1. Using DFS (Depth-First Search)
2. Using Kahn’s algorithm

The topological sort problem involves finding a possible order of buildings in a directed graph without cycles.
If a cycle exists, the requirements of the problem cannot be satisfied, so a check for cycles is necessary.

1. Method Using DFS

We can perform topological sorting by exploring the graph with DFS, visiting each node. The key of this method
is to add a node to the stack when all of its child nodes have been visited.

2. Kahn’s Algorithm

Kahn’s algorithm uses the in-degree of each node to perform topological sorting. This algorithm includes the following steps:

  1. Calculate the in-degrees of the graph.
  2. Add nodes with an in-degree of 0 to the queue.
  3. Remove nodes from the queue one by one, outputting them, and decrease the in-degrees of all connected nodes.
    If a node’s in-degree becomes 0, add it to the queue.
  4. Repeat this process. If all nodes have been visited, we have successfully performed topological sorting
    without cycles.

Implementation

Now, let’s implement the code to solve the problem using the Kahn’s algorithm described above. 


#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void topologicalSort(int N, vector>& graph, vector& inDegree) {
    queue q;
    vector result;

    // Add nodes with in-degree 0 to the queue
    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        result.push_back(current);

        // Decrease the in-degree of all nodes connected to the current node
        for (int neighbor : graph[current]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // Output the result
    if (result.size() == N) {
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << " ";
        }
        cout << endl;
    } else {
        cout << "0" << endl; // If a cycle exists
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector> graph(N + 1);
    vector inDegree(N + 1, 0);

    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B; // A -> B
        graph[A].push_back(B);
        inDegree[B]++;
    }

    topologicalSort(N, graph, inDegree);

    return 0;
}

Conclusion

The topological sorting problem is one of the types of algorithm problems that can commonly be encountered,
especially when determining the work order of a project. In this tutorial, we solved the problem of finding the
building order using Kahn’s algorithm. There are various variations of this problem, so to build your skills in
actual coding tests, it is recommended to solve a variety of problems.

Great job! I hope this has been helpful in your preparation for coding tests.

C++ Coding Test Course, Creating Blu-ray

Hello! In this post, we will deeply explore the topic of ‘Creating Blu-ray’ by solving algorithm problems in preparation for C++ coding tests. This problem can primarily be approached using dynamic programming and binary search. Let’s write some code together and follow the step-by-step process of solving the problem.

Problem Description

A Blu-ray is a disc that stores and plays media content such as movies. A user is given a specific list of movies, and we aim to store these movies on Blu-ray as efficiently as possible. The user can set a maximum time for each Blu-ray, and we will minimize the number of Blu-rays needed using this constraint.

Problem Definition

    The list of movies consists of N movies, with the length of each movie given as A[i]. Now, we want to store all the movies using Blu-ray limited by duration T with the minimum number of Blu-rays.
    Let's solve the problem of calculating the number of Blu-rays using the given constraints algorithmically.

Input

  • The first line contains the number of movies N (1 ≤ N ≤ 1000) and the maximum time T (1 ≤ T ≤ 10000) that can be stored on a Blu-ray.
  • The second line provides N integers representing the length of each movie. The length of each movie is between 1 and T.

Output

Print the minimum number of Blu-rays required.

Problem Approach

To solve the problem, we follow these steps:

  1. Utilize binary search to set the range of possible maximum storage time for the Blu-ray.
  2. Count the number of Blu-rays needed to store the movies on each Blu-ray.
  3. If the time exceeds T, increase the number of Blu-rays; if it is within T, adjust the maximum Blu-ray storage time.
  4. Finally, print the required number of Blu-rays.

Code Implementation

    
    #include <iostream>
    #include <vector>
    #include <algorithm>

    using namespace std;

    int countBluRays(const vector<int>& movies, int maxTime) {
        int count = 1; // At least 1 Blu-ray is needed
        int currentTime = 0;

        for (int movie : movies) {
            if (currentTime + movie > maxTime) {
                count++; // A new Blu-ray is needed
                currentTime = movie; // Assign current movie
            } else {
                currentTime += movie; // Add movie to the current Blu-ray
            }
        }
        return count;
    }

    int main() {
        int N, T;
        cin >> N >> T;

        vector<int> movies(N);
        for (int i = 0; i < N; i++) {
            cin >> movies[i];
        }

        // Determine the maximum time for Blu-ray using binary search
        int low = *max_element(movies.begin(), movies.end());
        int high = accumulate(movies.begin(), movies.end(), 0);
        int result = high;

        while (low <= high) {
            int mid = (low + high) / 2;
            int requiredBluRays = countBluRays(movies, mid);

            if (requiredBluRays <= T) {
                result = mid; // We can reduce the maximum time for Blu-ray
                high = mid - 1;
            } else {
                low = mid + 1; // Increase the maximum time for Blu-ray
            }
        }

        cout << result << endl;
        return 0;
    }

Code Explanation

The code above consists of the following main parts:

  1. countBluRays function: Calculates the number of Blu-rays needed to store the movies based on the given maximum Blu-ray time (maxTime). It iterates through each movie to check if it can be added to the current Blu-ray and adds a Blu-ray if needed.
  2. main function: Receives the number of movies N and the maximum time T for the Blu-ray, then stores the lengths of the movies. It then finds the minimum Blu-ray time needed to store all movies using binary search.

Algorithm Complexity

The time complexity of the algorithm is O(N log S). Here, N is the number of movies, and S is the sum of movie lengths. The binary search process requires iterating through all movies each time, making it efficient.

Conclusion

In this post, we easily understood the basics of binary search and dynamic programming through the coding problem ‘Creating Blu-ray’. It is essential to grasp the essence of the problem and find an appropriate approach when solving algorithmic problems. As experience builds through practice, solving more complex problems will become easier. In the next post, we will explore more diverse problems!

© 2023 C++ Coding Test Course