Category: Java Coding Test

Hello! Today we will learn about Topological Sorting, which frequently appears in coding tests using Java. Topological sorting is an algorithm used in Directed Acyclic Graphs (DAGs) that is very useful for determining the order of tasks considering the precedence relations between them.

1. What is Topological Sorting?

Topological sorting refers to the arrangement of vertices in a directed graph such that every vertex appears after all its preceding vertices. Generally, topological sorting is used in the following cases:

• When determining the order of tasks in a project (e.g., Task B can only start after Task A is completed)
• When determining the order of classes in a learning process (e.g., a prerequisite course must be taken before enrolling in the next course)

2. Problem Description

Let’s solve the following problem:

3. Topological Sort Algorithm

There are two methods to perform topological sorting: one utilizing ‘in-degree’ and the other based on ‘DFS’. Here we will explain the in-degree based topological sorting method.

3.1. In-Degree Based Topological Sort

The in-degree based topological sorting consists of the following steps:

1. Calculate the in-degree of all vertices in the graph.
2. Add vertices with an in-degree of 0 to the queue.
3. Remove vertices one by one from the queue and decrease the in-degree of all vertices connected to it by 1.
4. Add vertices whose in-degree becomes 0 to the queue.
5. Repeat the above steps until the queue is empty.

4. Java Code Implementation

Let’s implement the topological sorting algorithm in Java. Below is the Java code to solve the problem.

import java.util.*;

public class TopologicalSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // Number of classes
        int M = scanner.nextInt(); // Number of relations

        List> graph = new ArrayList<>();
        int[] inDegree = new int[N + 1];
        
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        
        // Process graph input
        for (int i = 0; i < M; i++) {
            int A = scanner.nextInt();
            int B = scanner.nextInt();
            graph.get(A).add(B);
            inDegree[B]++;
        }
        
        // Add nodes with in-degree 0 to the queue
        Queue queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        List result = new ArrayList<>();
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);
            for (int next : graph.get(current)) {
                inDegree[next]--; // Decrease in-degree
                if (inDegree[next] == 0) {
                    queue.add(next);
                }
            }
        }
        
        // Check if the order is determined
        if (result.size() == N) {
            for (int i : result) {
                System.out.print(i + " ");
            }
        } else {
            System.out.println(0);
        }
        
        scanner.close();
    }
}
    

5. Code Explanation

The above Java code works as follows:

1. It uses a Scanner to read input and retrieves the number of classes N and the number of relations M.
2. It initializes an array to store the graph and in-degrees. The graph information for each class is stored as a list.
3. It receives M relations, adds the relations to the graph, and updates the in-degrees.
4. It starts by adding nodes with an in-degree of 0 to the queue.
5. It removes vertices from the queue, decreasing the in-degrees of all vertices connected to it by 1.
6. If any vertex’s in-degree becomes 0 during this process, it adds it to the queue.
7. It handles exceptional situations and ultimately prints the classes in the possible order.

6. Example Test

Let’s test with the following input:

5 4
1 2
1 3
2 4
3 4
    

This example includes 5 classes and 4 relations, so it can be executed appropriately. The correct output will be the possible order in which the classes can be taken.

7. Time Complexity

The time complexity of topological sorting is O(V + E), where V is the number of vertices (N) and E is the number of edges (M), so it operates efficiently even for large graphs.

8. Conclusion

Today we learned about the topological sorting algorithm with Java. This algorithm can be applied effectively in various fields and frequently appears in coding tests, so be sure to practice. Topological sorting will be a great help in solving complex problems!

In this article, we will explain the Union-Find data structure in detail through algorithm problems and implement it in Java. In particular, we will select problems that are frequently asked in coding tests and proceed with the process of writing actual code.

What is Union-Find?

Union-Find is a data structure used to manage ‘disjoint sets’, which is useful for finding connected components in graphs or determining whether two specific elements belong to the same set. The main operations of this data structure are twofold.

• Find: An operation that finds the set to which an element belongs.
• Union: An operation that merges two sets.

Problem Description

The problem we will solve now is Counting Connected Components. Given n vertices and m edges, the task is to count the number of connected components. A connected component is a set of vertices that are connected in the graph.

For example, consider the graph below. If there are 5 vertices and the edges are as follows,

            1 - 2
            |   |
            3 - 4
            5
        

the connected components are {1, 2, 3, 4} and {5}, totaling two components.

Problem Definition

        Given the number of vertices n and a list of edges, output the number of connected components.

        Input: 
        n = 5
        edges = [[1, 2], [1, 3], [2, 4]]

        Output: 2
    

Approach to Solve the Problem

This problem can be solved using Union-Find. As we visit each node, we check which set the node belongs to, and when a new connection is discovered, we unify the sets through the union operation. Finally, we can count the number of distinct sets to determine the number of connected components.

Implementing Union-Find

To implement Union-Find, we will define two functions. One is the find function, which finds the parent of a specific element, and the other is the union function, which connects two elements.

Java Code Implementation

        public class UnionFind {
            private int[] parent;
            private int[] rank;

            public UnionFind(int n) {
                parent = new int[n + 1];
                rank = new int[n + 1];
                for (int i = 1; i <= n; i++) {
                    parent[i] = i;  // Initialize each node's parent to itself
                    rank[i] = 0;    // Initial rank is 0
                }
            }

            public int find(int x) {
                if (parent[x] != x) {
                    parent[x] = find(parent[x]);  // Path compression
                }
                return parent[x];
            }

            public void union(int x, int y) {
                int rootX = find(x);
                int rootY = find(y);
                if (rootX != rootY) {
                    if (rank[rootX] > rank[rootY]) {
                        parent[rootY] = rootX;
                    } else if (rank[rootX] < rank[rootY]) {
                        parent[rootX] = rootY;
                    } else {
                        parent[rootY] = rootX;
                        rank[rootX]++;
                    }
                }
            }

            public int countComponents(int n, int[][] edges) {
                // Perform union operation using edges
                for (int[] edge : edges) {
                    union(edge[0], edge[1]);
                }
                // Count the number of connected components
                HashSet componentRoots = new HashSet<>();
                for (int i = 1; i <= n; i++) {
                    componentRoots.add(find(i));
                }
                return componentRoots.size();
            }
        }
    

Main Function

        public class Main {
            public static void main(String[] args) {
                UnionFind uf = new UnionFind(5);
                int[][] edges = {{1, 2}, {1, 3}, {2, 4}};
                int result = uf.countComponents(5, edges);
                System.out.println("Number of connected components: " + result);  // Output: 2
            }
        }
    

Code Analysis

The above code creates a UnionFind class and implements the union-find algorithm. The constructor initializes the values and ranks of each node, and implements the find and union functions. The find function uses path compression to reduce time complexity, while the union function uses rank to maintain balance.

Conclusion

Union-Find is a very useful data structure for graph problems. Through the problem of counting connected components presented earlier, I hope you have laid a foundation for understanding Union-Find. Since this data structure can be asked in various forms in actual coding tests, understanding it is essential. I hope you continue to solve various problems using Union-Find to deepen your understanding and improve your skills.

Hello! Today we will discuss one of the Java algorithm problems called “Finding the Desired Integer.” This problem will help you understand basic search algorithms that can be applied in various situations. I hope this article can contribute to enhancing your coding skills.

Problem Description

Given an integer array nums and a target integer target, the problem is to check if target exists in the array and return the index of that number if it exists. If it does not exist, it should return -1.

Input

• nums: integer array (e.g., [2, 7, 11, 15])
• target: the integer to be found (e.g., 9)

Output

• The index of target in the integer array, or -1 if it does not exist

Examples

Problem Solving Approach

There are several approaches to solving this problem, but the most basic method is to iterate through the array to find the target element. However, this method has a time complexity of O(n) and cannot use Binary Search if the elements are not sorted. So, what if the array is sorted? In that case, we can utilize binary search.

Binary Search Concept

Binary search is an efficient algorithm for finding the desired value in a sorted array. Here are the basic steps of binary search:

1. Calculate the middle index of the array.
2. If the middle value equals target, return that index.
3. If target is smaller than the middle value, search the left half of the array; if larger, search the right half.
4. Repeat this process.

Java Implementation

Now, let’s implement binary search in Java. Below is the code representation of the algorithm.

public class Solution {
        public int search(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;

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

                if (nums[mid] == target) {
                    return mid; // found the target
                } else if (nums[mid] < target) {
                    left = mid + 1; // search in the right half
                } else {
                    right = mid - 1; // search in the left half
                }
            }
            return -1; // not found
        }
    }
    

Code Explanation

In the code above, the search method takes two arguments: the nums array and target. The method performs the following steps:

• Uses left and right variables to manage the range of search.
• The main loop continues searching as long as left is less than or equal to right.
• Calculates the middle index mid and returns that index if the middle value equals target.
• If the middle value is less than target, adjusts the left range; if more, adjusts the right range.
• If the search ends and target is not found, returns -1.

Complexity Analysis

The time complexity of the binary search algorithm is O(log n). This is because the range to search is halved each time the size of the array doubles. This algorithm is very fast and its efficiency stands out, especially in large arrays. The space complexity is O(1) as no additional space is needed.

Conclusion

In this article, we covered the Java algorithm problem of finding a desired integer. Through this problem, you could understand and implement binary search, which is fundamental to array searching. Since binary search is frequently featured in coding tests, I recommend practicing enough on this topic. Why not write your own code for various cases?

Finally, don’t forget to keep solving problems to improve your coding abilities! If you have any questions, feel free to ask in the comments. Thank you!

Hello, in this blog post, we will delve deeply into one of the frequently encountered problems in Java coding tests: the “Traveling Salesman Problem.” This problem is very useful for laying the foundations of graph theory and combinatorics, and it serves as a good example to apply various algorithmic techniques.

Problem Description

The Traveling Salesman Problem can be described as follows. The salesman is tasked with finding the shortest path that visits all the given cities and returns to the starting city. All cities are connected, and the distance between any two cities is provided. The goal is to complete the tour of the visited cities with the minimum cost.

Input

• Number of cities N (2 ≤ N ≤ 10)
• A cost matrix C of size N x N is provided. C[i][j] represents the cost of traveling from city i to city j. If it is not possible to travel from city i to j, C[i][j] is infinite.

Output

Output the minimum cost to visit all cities once and return to the starting city.

Problem Analysis

This problem is classified as an NP-hard problem, generally solvable with a complete search method. However, since N is limited to a maximum of 10, it can be solved efficiently using a bitmask technique with dynamic programming (DP). By using a bitmask, we can represent the visit status of each city as bits, allowing us to calculate the minimum cost for all possible paths.

Algorithm Design

The basic idea for solving the problem is as follows:

1. Use a bitmask to indicate the visit state of each city.
2. Recursively explore all possible paths while calculating the minimum path.
3. Use memoization to store already calculated minimum costs to avoid redundant calculations.

Key Variables

• N: Number of cities
• C[][]: Cost matrix
• cache: Array for memoization
• allVisited: Bitmask to check if all cities have been visited
• start: Starting city

Java Code Implementation

The code below implements the Traveling Salesman Problem according to the given algorithm. Check how each step progresses through the code.

import java.util.Arrays;

public class TravelingSalesman {
    
    static int N; // Number of cities
    static int[][] C; // Cost matrix
    static int[][] cache; // Array for memoization
    static final int INF = Integer.MAX_VALUE; // Infinite value

    public static void main(String[] args) {
        // Example: Number of cities N = 4
        N = 4; 
        C = new int[][]{
            {0, 10, 15, 20},
            {5, 0, 9, 10},
            {6, 13, 0, 12},
            {8, 8, 9, 0}
        };

        // Initialize the memoization array
        cache = new int[1 << N][N];
        for (int i = 0; i < (1 << N); i++) {
            Arrays.fill(cache[i], -1);
        }

        int result = tsp(1, 0); // Start from the initial city 0 having visited all cities
        System.out.println("Minimum cost: " + result);
    }

    static int tsp(int visited, int pos) {
        // Base case: when all cities have been visited
        if (visited == (1 << N) - 1) {
            return C[pos][0] == 0 ? INF : C[pos][0]; // Cost to return to the starting city
        }

        // If already computed
        if (cache[visited][pos] != -1) {
            return cache[visited][pos];
        }

        int answer = INF;

        // Check all cities
        for (int city = 0; city < N; city++) {
            // If the city hasn't been visited yet
            if ((visited & (1 << city)) == 0 && C[pos][city] != 0) {
                int newVisited = visited | (1 << city);
                int newCost = C[pos][city] + tsp(newVisited, city);
                answer = Math.min(answer, newCost);
            }
        }

        return cache[visited][pos] = answer; // Store the minimum cost
    }
}

Code Explanation

1. Main Method: Initializes the number of cities and the cost matrix with the example, calls the TSP function, and outputs the result.
2. tsp Method: Recursively calculates the minimum cost based on the bitmask and current city information.
3. Base Case: When all cities have been visited, returns the cost to return to the starting city.
4. Memoization: Already computed states are stored in the cache array and reused as needed to enhance efficiency.

Results

The above code calculates the minimum cost for the provided cities and cost matrix. The output is the minimum cost to visit all cities and return to the starting city. You can input your own cost matrix using this code and check the results, which will help you understand the flow of the algorithm.

Conclusion

Through this tutorial, we learned how to solve the Traveling Salesman Problem using dynamic programming and bitmasks. This problem frequently appears in coding tests and will significantly aid in learning fundamental algorithmic techniques to tackle such challenges. Like other algorithm problems, there are multiple ways to approach the problem. Try various solutions to enhance your algorithm skills.

Stay tuned for our next post, where we will cover another problem. If you have any questions or comments, please leave them below. Thank you!

The problem of finding the next greater number (Next Greater Element) for a given array is one of the frequently asked algorithm problems in coding tests. In this article, we will define the next greater element problem, explain various approaches to solve it, and describe efficient algorithms. Additionally, we will provide a step-by-step explanation of how to implement it in Java, and we will discuss the time complexity and space complexity after the implementation.

Problem Definition

In a given integer array, the next greater element is defined as the first number that appears after an element that is greater than that element. If a next greater element does not exist, -1 should be placed for that element.

Problem Example

Input: [2, 1, 3, 2, 5]
Output: [3, 3, 5, 5, -1]

Problem Analysis

The traditional method to solve this problem is to use a nested loop. However, this method is inefficient with a time complexity of O(N^2). Therefore, a more efficient method needs to be found.

Efficient Approach: O(N) Solution Using Stack

To solve this problem, we can use the stack data structure. Below is the main idea of the algorithm for finding the next greater element using a stack:

Algorithm Explanation

1. Initialize the result array with the length of the given array.
2. Initialize the stack. The stack will store the indices of the array.
3. Traverse the array from left to right.
4. Check the value (index) at the top of the stack. If the current element is greater than the element at that index:
• The next greater element is the current element.
• Store that value in the result array.
• Pop that index from the stack.
5. Push the current index onto the stack.
6. Once all elements have been processed, the remaining indices in the stack do not have a next greater element, so set those to -1 in the result array.

Java Implementation

Now let’s implement the above algorithm in Java.

import java.util.Stack;

public class NextGreaterElement {
    public static int[] findNextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Stack stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }

        // Set -1 for the indices remaining in the stack, which do not have a next greater element
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 3, 2, 5};
        int[] result = findNextGreaterElements(nums);
        
        System.out.print("Result: [");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}

Time Complexity and Space Complexity

The algorithm implemented above has a time complexity of O(N). Each element is pushed and popped from the stack at most once. The space complexity is O(N) because the stack can be used up to N.

Conclusion

The problem of finding the next greater element can be efficiently solved using an algorithm that utilizes a stack. Since this problem is frequently included in coding tests, it is important to familiarize yourself with how to use stacks and solve these types of problems. Practice with various examples to enhance your problem-solving abilities.