Category: Java Coding Test

1. Introduction

For programming beginners and aspiring developers, arrays and lists are fundamental data structures. Understanding these two data structures is crucial for achieving excellent performance in various coding test problems. In this article, we will solve an algorithm problem using arrays and lists in Java.

2. Problem Description

Problem: Write a method that removes duplicate elements from a given integer array and returns the remaining elements sorted. The result array should be sorted in ascending order, and duplicate values should be removed.

Problem Summary

• Input: Integer array
• Output: Array sorted in ascending order after removing duplicates

3. Example

Input: [3, 1, 2, 3, 4, 2, 1]
Output: [1, 2, 3, 4]

4. Approach

To solve this problem, we will follow these steps:

• Step 1: Remove duplicate elements from the input array.
• Step 2: Sort the remaining elements.
• Step 3: Return the final result.

5. Code Implementation

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

        
import java.util.Arrays;
import java.util.HashSet;

public class RemoveDuplicatesAndSort {

    public static int[] removeDuplicatesAndSort(int[] arr) {
        // Use HashSet to remove duplicates
        HashSet set = new HashSet<>();
        for (int num : arr) {
            set.add(num);
        }

        // Convert unique elements to an array
        int[] uniqueArray = new int[set.size()];
        int index = 0;
        for (int num : set) {
            uniqueArray[index++] = num;
        }

        // Sort the array
        Arrays.sort(uniqueArray);
        return uniqueArray;
    }

    public static void main(String[] args) {
        int[] input = {3, 1, 2, 3, 4, 2, 1};
        int[] result = removeDuplicatesAndSort(input);
        System.out.println(Arrays.toString(result)); // [1, 2, 3, 4]
    }
}
        
    

Code Explanation

The above code defines a method called removeDuplicatesAndSort. This method removes duplicate elements from the input array and returns a sorted array.

• First, we use a HashSet to easily remove duplicate integers.
• Then we copy the contents of the HashSet into a new array.
• Finally, we use Arrays.sort to sort the array.

6. Complexity Analysis

The time complexity of this algorithm is as follows:

• Removing duplicates: O(n), where n is the size of the input array.
• Sorting: O(m log m), where m is the size of the array after duplicates have been removed.

Therefore, the overall time complexity is O(n + m log m).

7. Conclusion

In this tutorial, we implemented a duplicate removal and sorting algorithm using arrays and lists in Java. Through each step, we understood how basic data structures work and learned how to improve our skills. I hope you gain more experience by solving various algorithm problems in the future.

References

• Books on data structures and algorithms
• Java official documentation

8. Additional Practice Problems

Try the following problem as an additional exercise.

• Implement a method that removes duplicate values and returns a new array when given a sorted array.

Enhance your understanding of algorithms and improve your skills through coding practice!

Coding interviews and algorithm tests are common challenges for many candidates. One such problem, Maze Exploration, is a very popular algorithm problem that is suitable for learning search algorithms like BFS (Breadth-First Search) and DFS (Depth-First Search). In this article, we will examine the problem of exploring a maze using Java and explain a step-by-step approach to solve it.

Problem Description

In a given 2D array, 0 represents a space that can be traversed, and 1 represents a wall. The task is to find a path from the starting point to the destination point. If a path exists, print that path; if not, print “There is no path.”

Example Problem

    Input:
    [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0]
    ]
    Starting point (0, 0)
    Destination point (4, 4)

    Output:
    (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (3, 2) -> (4, 2) -> (4, 3) -> (4, 4)
    

Solution Process

1. Understand the Problem

First and foremost, it is essential to understand the problem accurately. In the 2D array representing the maze, you need to find a path from the starting point to the destination point without crossing any walls (1). In the example above, you should determine which path can lead from the starting point to the destination point.

2. Choose a Search Algorithm

Maze exploration can be solved using BFS or DFS. BFS is advantageous for finding the shortest path, while DFS is better suited for exploring paths deeply. Here, we will choose the BFS solution method.

3. Design the Algorithm

We will explore the path using the BFS algorithm in the following steps:

1. Add neighboring points to the queue from the starting point.
2. Remove points one by one from the queue and check if the point is the destination point.
3. If it is not the destination point, add its neighboring points to the queue.
4. If all paths have been explored and the destination point has not been reached, print “There is no path.”

4. Implement the Java Code

    import java.util.LinkedList;
import java.util.Queue;

public class MazeSolver {
    static class Point {
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        int[][] maze = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0}
        };
        
        findPath(maze, new Point(0, 0), new Point(4, 4));
    }

    static void findPath(int[][] maze, Point start, Point end) {
        int n = maze.length;
        int m = maze[0].length;
        boolean[][] visited = new boolean[n][m];
        Point[][] previous = new Point[n][m];

        Queue queue = new LinkedList<>();
        queue.offer(start);
        visited[start.x][start.y] = true;

        while (!queue.isEmpty()) {
            Point current = queue.poll();
        
            if (current.x == end.x && current.y == end.y) {
                printPath(previous, start, end);
                return;
            }

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

                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && maze[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    previous[nx][ny] = current;
                    queue.offer(new Point(nx, ny));
                }
            }
        }

        System.out.println("There is no path.");
    }

    static void printPath(Point[][] previous, Point start, Point end) {
        StringBuilder path = new StringBuilder();
        for (Point at = end; at != null; at = previous[at.x][at.y]) {
            path.insert(0, String.format("-> (%d, %d) ", at.x, at.y));
        }
        System.out.println(path.substring(4)); // Remove the initial "-> "
    }
}

    

5. Code Explanation

The above code implements the BFS algorithm. It uses an inner class named Point to define (x, y) coordinates for queue and path tracking. Neighboring coordinates of the current position are added to the queue, and visited points are checked in the visited array to prevent duplicate searches. When the destination point is reached, the printPath method is called to print the path.

6. Code Execution Result

    (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (3, 2) -> (4, 2) -> (4, 3) -> (4, 4)
    

Conclusion

You have now learned how to solve the maze exploration problem. This algorithm is a useful technique that can be applied to various problems. Understanding the basics of search algorithms and implementing them in Java is a very rewarding experience. I hope this helps you in your coding test preparation!

Algorithm problems are very important in coding tests. In particular, the ability to solve problems using Java is one of the skills that many companies require. In this article, I will explain in detail the topic of “Calculating the Amount of Water.” Through this problem, we will explore the process of finding an algorithmic solution and implementing it in Java step by step.

Problem Description

You have an array of given heights. Each index represents a block, and the value at each index represents the height of the block. You need to write a program to calculate the amount of water that can be stored due to the given rain in this array.

For example, if the given array is [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], you need to find the amount of water stored in the array.

Approach to Solving the Problem

There are several approaches to solving this problem, but the most intuitive way is to use the two-pointer approach. By using two pointers that move from both ends of the array toward the center, we can calculate the amount of water that can be stored at each index.

Step 1: Understanding the Problem

The amount of water stored at each index is determined by the height of the tallest block to the left and right of that index. Therefore, the amount of water stored is
min(left max height, right max height) - current block height. If this value is negative, it means no water is stored, so it can be set to 0.

Step 2: Designing the Algorithm

To design the algorithm, we will set up the following steps:

1. Calculate the length of the array and handle exceptions for the user.
2. Start from both ends and set up two pointers.
3. Track the maximum height at each pointer.
4. Repeat until the two pointers meet.
5. Calculate the amount of water stored at each step.

Step 3: Implementing the Code

Now, based on the above design, let’s implement the Java code.

public class WaterTrapping {
    public static int calculateWater(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int totalWater = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    totalWater += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    totalWater += rightMax - height[right];
                }
                right--;
            }
        }

        return totalWater;
    }

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("Amount of water stored: " + calculateWater(height) + " units");
    }
}
        

Step 4: Explaining the Code

The key part of the code is the while (left < right) loop. This loop continues until the two pointers cross each other.

• If the left pointer is less than the right pointer: Update the maximum height on the left or, if the current value is lower, calculate the amount of water that can be stored.
• If the right pointer is less than the left pointer: Update the maximum height on the right or calculate the amount of water that can be stored.

In this way, the loop continues until the two pointers meet, summing up the total amount of water stored.

Conclusion

Today, we learned about the algorithm frequently presented in coding tests through the problem of "Calculating the Amount of Water." The algorithm using two pointers provides efficient space utilization and time complexity, so it is commonly used in actual coding tests, and it is important to practice it thoroughly.

I hope you continue with deeper learning through various additional examples and complex test cases. May this problem enhance your algorithmic thinking.

Problem Description

This is a problem to find how many times a specific pattern appears in a given string.
For example, determining how many times the pattern "ana" appears in the string "banana".

Input

• String text: The entire string to search (1 ≤ |text| ≤ 100,000)
• String pattern: The string to find (1 ≤ |pattern| ≤ 50)

Output

Returns the total count of how many times pattern appears in the string text.

Example

Input

text = "banana"
pattern = "ana"

Output

2

Solution Process

To solve this problem, a string search algorithm must be used.
The simplest way is to traverse the string one character at a time and compare the pattern, but this is inefficient and has a time complexity of O(n*m) for large data.

Efficient Solution: KMP Algorithm

One of the ways to efficiently solve the string search problem is by using the KMP (Knuth-Morris-Pratt) algorithm.
This algorithm consists of the following two parts:

1. Create an ‘LPS (Longest Prefix which is also Suffix)’ array based on the pattern.
2. Traverse the text, comparing the pattern while utilizing the LPS array.

Generating the LPS Array

The LPS array indicates how much the prefix and suffix match within the pattern. This allows for the pattern to be reused during the search.
For example, if the pattern is "ABAB", the LPS array will be [0, 0, 1, 2].

Algorithm Implementation

Now, based on the above process, we will implement the string search algorithm in Java.

public class KMP {
    public static int[] computeLPS(String pattern) {
        int[] lps = new int[pattern.length()];
        int length = 0; 
        int i = 1;
        
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static int KMPsearch(String text, String pattern) {
        int[] lps = computeLPS(pattern);
        int i = 0; 
        int j = 0; 
        int count = 0;

        while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;

                if (j == pattern.length()) {
                    count++;
                    j = lps[j - 1];
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String text = "banana";
        String pattern = "ana";
        int result = KMPsearch(text, pattern);
        System.out.println("Substring Count: " + result);
    }
}

Code Explanation

The code above implements the KMP algorithm, which consists of two main functions.
The computeLPS function generates the LPS array for the pattern, and the KMPsearch function searches for the pattern in the text and counts the matches.

Complexity Analysis

The time complexity of the KMP algorithm is O(n + m). Here, n is the length of the text and m is the length of the pattern.
This is an efficient method because the pattern moves and is reused within the text.

Conclusion

Today, we explored the KMP algorithm to solve the string search problem.
By using this algorithm, we can efficiently tackle various string search problems.
As you encounter problems, try experimenting with different algorithms to build your skills!

1. Introduction

Coding tests are currently an important part of the hiring process for many companies.
However, countless technical questions and algorithm problems are tormenting the applicants.
In this article, we will present algorithm problems that will help prepare for coding tests using Java,
and emphasize the importance of debugging during the problem-solving process.

2. Algorithm Problem

Problem Description

Write a function that returns the indices of two numbers from a given integer array
such that their sum equals a specific value.
Each element in the array is unique, and the returned indices start from 0.

Input

• The first line contains an integer array nums.
• The second line contains an integer target.

Output

You should return an array containing the indices of the two numbers that sum to the target.

Example

Input: nums = [2, 7, 11, 15], target = 9

Output: [0, 1]
(2 + 7 = 9)

3. Problem Solving Process

3.1 Algorithm Design

To solve this problem, we need to search each element while checking if the complement exists in the array.
We can use a hashmap to achieve this,
allowing us to solve the problem with a time complexity of O(n).
Understanding hashmaps is the first step to solving this problem.

3.2 Java Code Implementation

            
                import java.util.HashMap;

                public class Solution {
                    public int[] twoSum(int[] nums, int target) {
                        HashMap map = new HashMap<>();
                        for (int i = 0; i < nums.length; i++) {
                            int complement = target - nums[i];
                            if (map.containsKey(complement)) {
                                return new int[] { map.get(complement), i };
                            }
                            map.put(nums[i], i);
                        }
                        throw new IllegalArgumentException("No two sum solution");
                    }
                }
            
        

4. Importance of Debugging

While preparing for coding tests,
debugging is as important as implementing the algorithm logic.
First, we need to verify that the written code functions as intended.
The ability to quickly identify and fix bugs or errors is essential for a developer.

Nonetheless, things may not go smoothly at first,
so you can try the following debugging techniques.

• Check for syntax and logical errors line by line: It is useful to analyze code line by line
  or print each variable.
• Write unit tests: Create tests to validate whether a specific function works correctly,
  helping to discover errors.
• Utilize debugging tools in the IDE: Use the debugger feature provided by the IDE
  to execute the code step by step.

5. Conclusion

The process of solving algorithm problems is more than just finding the answers.
Problem-solving skills, code implementation skills, and debugging skills should develop together.
We hope you prepare better for coding tests through programming languages like Java,
while also strengthening your debugging skills.