Category: Java Coding Test

In modern software development, algorithms and data structures play a very important role. In particular, one of the problem types that frequently appears in coding tests is tree-related problems. In this article, we will address the problem of counting the number of leaf nodes.

Problem Definition

This is a problem to count the number of leaf nodes in a given binary tree. A leaf node refers to a node that has no children, and considering the properties of a binary tree, a leaf node can have a maximum of two children. This problem will help you practice recursive thinking and tree traversal algorithms.

Problem Description

        // Definition of a binary tree node
        class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }
        
        // Method to count the number of leaf nodes
        int countLeafNodes(TreeNode root);
    

Input: The root node of the binary tree (root).
Output: The number of leaf nodes.

Algorithm Approach

The most common way to find leaf nodes is to traverse the tree and count the nodes that have no children. This problem can be easily solved using a recursive approach.

Recursive Approach

While traversing the tree recursively, perform the following for each node:

1. If the current node is null, return 0.
2. Check if the current node is a leaf node. (If both left and right children are null)
3. If it is a leaf node, return 1; otherwise, respectively count the number of leaf nodes in the left and right subtrees and combine the results.

Implementation

        public class Main {
            public static void main(String[] args) {
                TreeNode root = new TreeNode(1);
                root.left = new TreeNode(2);
                root.right = new TreeNode(3);
                root.left.left = new TreeNode(4);
                root.left.right = new TreeNode(5);
                root.right.right = new TreeNode(6);

                System.out.println("Number of leaf nodes: " + countLeafNodes(root));
            }

            public static int countLeafNodes(TreeNode root) {
                if (root == null) {
                    return 0;
                }
                if (root.left == null && root.right == null) {
                    return 1;
                }
                return countLeafNodes(root.left) + countLeafNodes(root.right);
            }
        }
    

Example

Let’s assume the binary tree is structured as follows:

                1
              /   \
             2     3
            / \     \
           4   5     6
    

In the above tree, the leaf nodes are 4, 5, and 6, and therefore the number of leaf nodes is 3.

Testing and Validation

To test the implemented method, create several different binary trees and validate the number of leaf nodes. For example, create tests for a tree with 1 node, left/right-skewed trees, and an empty tree.

Test Cases

        // Single node tree
        TreeNode singleNode = new TreeNode(1);
        assert countLeafNodes(singleNode) == 1;

        // Empty tree
        assert countLeafNodes(null) == 0;

        // Left skewed tree
        TreeNode leftSkewedTree = new TreeNode(1);
        leftSkewedTree.left = new TreeNode(2);
        leftSkewedTree.left.left = new TreeNode(3);
        assert countLeafNodes(leftSkewedTree) == 1;

        // Right skewed tree
        TreeNode rightSkewedTree = new TreeNode(1);
        rightSkewedTree.right = new TreeNode(2);
        rightSkewedTree.right.right = new TreeNode(3);
        assert countLeafNodes(rightSkewedTree) == 1;
    

Complexity Analysis

The time complexity is O(N). We must visit each node once, so N is the number of nodes. The space complexity is O(h), where h is the height of the tree. In the worst case (skewed tree), h can be equal to N.

Conclusion

In this article, we tackled the algorithm problem of counting the number of leaf nodes. I hope this helped you understand recursive thinking and basic binary tree concepts while traversing the tree. While solving algorithm problems, it is essential to always consider how to break down and solve the problem. Practicing with various tree structures is also vital.

Java Coding Test Course: Exploring Debugging Use Cases

Coding tests have become an essential process in many IT industries today. Every year, countless developers prepare for coding tests and try various methods to enhance their algorithm problem-solving abilities. In this course, we will focus on solving algorithm problems using Java and the application of debugging techniques.

Problem: Finding Two Sum in an Array

The following problem is to find the indices of two numbers in a given array such that their sum equals a specific target value.

Problem Description:
Given an integer array nums and an integer target target, write a function that returns the indices of the two numbers that add up to the target. Each input has exactly one solution, and you may not use the same element twice.

Function Signature: 
public int[] twoSum(int[] nums, int target)

Example

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: Since nums[0] + nums[1] = 2 + 7 = 9, the output is [0, 1].

Problem Solving Process

This problem is about finding two numbers in an array that sum to the given target value. We can consider several approaches to solve this.

1. Brute Force Method

The simplest method is to use a double loop to consider all combinations. In the worst case, this checks all elements of the array with a time complexity of O(n²) to find the two numbers that make the target.

Java Code:
public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

2. Using HashMap

Instead of using a double loop, we can use a HashMap to store values and indices, checking if the required value exists in the HashMap. This can reduce the time complexity to O(n).

Java Code:
import java.util.HashMap;

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");
}

Debugging Process

Now let’s learn how to use debugging techniques in the above code. Debugging plays a crucial role in understanding the code’s operation and solving problems. The most commonly used debugging methods in Java are as follows.

• Print Statements (System.out.println): A way to understand the state of variables by printing them at specific points in the code.

    System.out.println("Current index: " + i);
    System.out.println("Current number: " + nums[i]);
    System.out.println("Complement: " + complement);
    

• Using the IDE Debugger: Tools in IDEs like Eclipse or IntelliJ to trace code execution line by line.
• Unit Tests: Writing test cases that check inputs and expected outputs to verify the correctness of the code.

Test Cases

Here are various test cases for the function we wrote. These tests help ensure that the code works as expected.

public void testTwoSum() {
    assertArrayEquals(new int[] {0, 1}, twoSum(new int[]{2, 7, 11, 15}, 9));
    assertArrayEquals(new int[] {1, 2}, twoSum(new int[]{3, 2, 4}, 6));
    assertArrayEquals(new int[] {0, 1}, twoSum(new int[]{3, 3}, 6));
}

Conclusion

In this article, we discussed the problem of finding the sum of two numbers in an array, and explained various approaches and debugging techniques. To solve algorithm problems, it is important not only to understand the problem but also to use different algorithms and apply debugging skills in the process. I hope that by solving these problems using Java, you can further enhance your programming abilities.

If you found this course useful, I encourage you to continue studying other algorithm problems and debugging techniques. The stronger your foundation, the easier it will be to solve more complex problems.

1. What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic technique that involves breaking a problem down into smaller subproblems and solving them. It typically uses a recursive approach but is characterized by storing the results of subproblems to reduce redundant calculations.

DP is mainly effective for optimization problems and is divided into two main concepts: ‘memoization’ and ‘tabulation’.

2. Problem Description

2.1 Problem: Longest Common Subsequence (LCS)

Given two strings A and B, the problem is to find the length of the longest common subsequence between A and B. A subsequence is a set of characters that can be selected from A and B while maintaining their order but possibly leaving out some characters.

2.2 Example Input

        A: "ABCBDAB"
        B: "BDCAB"
    

2.3 Example Output

        "The length of the LCS is 4." // "BCAB" or "BDAB"
    

3. Problem Solving Process

3.1 Problem Analysis

To solve the problem, we use the following approach:

• Define the lengths of strings A and B as n and m, respectively.
• Create a 2D array dp to store the lengths of LCS up to the i-th character of A and the j-th character of B such that dp[i][j] holds this value.
• If the characters match, set dp[i][j] = dp[i-1][j-1] + 1; otherwise, set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

3.2 State Transition Relation

The state transition in dynamic programming can be defined as follows:

        dp[i][j] = 
            { 
                dp[i-1][j-1] + 1, if A[i-1] == B[j-1]
                max(dp[i-1][j], dp[i][j-1]), if A[i-1] != B[j-1]
            }
    

3.3 Java Implementation Code

Now, let’s implement LCS in Java.

        
        public class LCS {

            public static int longestCommonSubsequence(String A, String B) {
                int n = A.length();
                int m = B.length();
                int[][] dp = new int[n + 1][m + 1];

                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= m; j++) {
                        if (A.charAt(i - 1) == B.charAt(j - 1)) {
                            dp[i][j] = dp[i - 1][j - 1] + 1;
                        } else {
                            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                        }
                    }
                }
                return dp[n][m];
            }

            public static void main(String[] args) {
                String A = "ABCBDAB";
                String B = "BDCAB";
                int length = longestCommonSubsequence(A, B);
                System.out.println("The length of the LCS is " + length + ".");
            }
        }
        
    

4. Overall Time Complexity and Space Complexity

The time complexity of this algorithm is O(n * m), and the space complexity is O(n * m). However, it can be reduced to O(min(n, m)) through space optimization.

5. Additional Solutions and Examples

We will look at several other problems or variations that can be solved by extending this problem. For example, after finding the longest common subsequence of the given strings, we can also add a function to print that subsequence.

6. Final Summary

Dynamic programming is a very useful technique for breaking down complex problems into subproblems. If you have understood the basic concept of DP through the LCS problem, it is recommended to practice by solving your own problems.

7. Next Course Announcement

In the next course, we will cover other examples of dynamic programming and learn about various optimization techniques. If you are interested, we encourage your participation!

In this post, we will learn about Dijkstra’s algorithm and solve a problem using it. Dijkstra’s algorithm is an algorithm used to find the shortest path between each vertex in a graph and is mainly used in various pathfinding problems.

1. Understanding the Algorithm

Dijkstra’s algorithm is an efficient method for finding the shortest path from a starting vertex to all other vertices in a weighted graph. This algorithm works by calculating the path length to reach specific vertices and continuously updating the shortest path.

1.1. Basic Concepts

• Weighted Graph: A graph where each edge has a cost or weight assigned to it.
• Priority Queue: Used to manage the current shortest paths.
• Greedy Approach: A method of finding shorter paths based on the currently discovered shortest path.

2. Problem Statement

Problem Description

This problem involves finding the shortest path between the starting vertex and the destination vertex in a given weighted graph. The graph is provided with a number of vertices and edges, and the weights of each edge are also given.

Input

• First line: Number of vertices N (1 ≤ N ≤ 1000)
• Second line: Number of edges M (1 ≤ M ≤ 10000)
• Third line: Starting vertex S, destination vertex E
• The next M lines: Starting vertex A, ending vertex B, weight W of each edge (1 ≤ A, B ≤ N, 1 ≤ W ≤ 10000)

Output

Print the length of the shortest path from the starting vertex S to the destination vertex E. If it cannot be reached, print -1.

3. Writing the Code

3.1. Java Code

import java.util.*;

public class Dijkstra {
    static class Edge {
        int to;
        int weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Graph construction
        int N = scanner.nextInt(); // Number of vertices
        int M = scanner.nextInt(); // Number of edges
        int S = scanner.nextInt(); // Starting vertex
        int E = scanner.nextInt(); // Destination vertex

        List[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // Receive edge input
        for (int i = 0; i < M; i++) {
            int A = scanner.nextInt();
            int B = scanner.nextInt();
            int W = scanner.nextInt();
            graph[A].add(new Edge(B, W));
            graph[B].add(new Edge(A, W)); // Undirected graph
        }

        // Execute Dijkstra's algorithm
        int result = dijkstra(graph, N, S, E);
        System.out.println(result);
    }

    public static int dijkstra(List[] graph, int N, int start, int end) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.offer(new Edge(start, 0));

        boolean[] visited = new boolean[N + 1];

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int currentNode = current.to;

            if (visited[currentNode]) continue;
            visited[currentNode] = true;

            for (Edge edge : graph[currentNode]) {
                if (visited[edge.to]) continue;

                if (dist[currentNode] + edge.weight < dist[edge.to]) {
                    dist[edge.to] = dist[currentNode] + edge.weight;
                    pq.offer(new Edge(edge.to, dist[edge.to]));
                }
            }
        }

        return dist[end] == Integer.MAX_VALUE ? -1 : dist[end];
    }
}

3.2. Code Explanation

The above code is an implementation of Dijkstra's algorithm written in Java. Here is an explanation of the main parts:

• Edge Class: A class that defines the edges of the graph. Each edge has a destination node and a weight.
• Graph Initialization: Initializes the graph using an adjacency list approach.
• Priority Queue: Used to explore the current shortest paths, prioritizing nodes with shorter distances.
• Dijkstra's Algorithm: In each iteration, it selects the node with the smallest distance and updates the distances of the connected nodes.

4. Time Complexity

The time complexity of Dijkstra's algorithm varies depending on the use of the priority queue. When using an array as a priority queue, it is O((N + M) log N). Here, N is the number of vertices and M is the number of edges. This algorithm performs well in graphs with many vertices compared to the number of edges.

5. Conclusion

In this post, we explored how to solve the shortest path problem using Dijkstra's algorithm. This algorithm can be applied in various fields, particularly in networks, mapping services, and optimization problems. Understanding and problem-solving abilities related to such algorithms are crucial in coding tests, so it is recommended to practice consistently.