Category: Java Coding Test

Hello! In this tutorial, we will address an algorithm problem to calculate the average using Java. Calculating an average is one of the basic operations regardless of the programming language and is often a topic in coding tests. The complexity of the average calculation problem can vary depending on how input values are processed. Therefore, we will start learning step by step from the basics.

Problem Solving Process

To solve the problem, we will proceed with the following steps:

1. Receive the input and create the array.
2. Add all the elements of the array.
3. Calculate the average by dividing the total by the number of elements in the array.
4. Print the average rounded to two decimal places.

Step 1: Receiving Input

The first step to solving the problem is to receive input from the user. In Java, we can use the Scanner class to receive input. We need to read the length of the array and its elements in order.

import java.util.Scanner;

public class AverageCalculator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the length of the array: ");
        int N = scanner.nextInt();
        int[] A = new int[N];
        
        System.out.println("Enter the elements of the array:");
        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }
        
        // Proceed to the next step.
    }
}

Step 2: Add All Elements of the Array

In the second step, we sum all the elements of the array. To do this, declare a variable to store the total sum and initialize it to 0, then add each element one by one using a loop.

        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += A[i];
        }
        
        // Proceed to the next step.

Step 3: Calculate Average

Now that we have the total sum, it's time to calculate the average. The average can be calculated by dividing the total by the length of the array. Please declare a variable to store the average value.

        double average = (double) sum / N;  // Cast is needed due to integer division

Step 4: Print Average Rounded

In the final step, we need to print the average rounded to two decimal places. In Java, we can use the Math.round method for rounding. After rounding, we can print it in a suitable format.

        average = Math.round(average * 100.0) / 100.0; // Round to two decimal places
        System.out.printf("Average: %.2f\n", average);  // Print to two decimal places
    }
}

Complete Code

When we combine all the steps above, the final program looks like this:

import java.util.Scanner;

public class AverageCalculator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Step 1: Receive Input
        System.out.print("Enter the length of the array: ");
        int N = scanner.nextInt();
        int[] A = new int[N];

        System.out.println("Enter the elements of the array:");
        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }
        
        // Step 2: Add All Elements of the Array
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += A[i];
        }

        // Step 3: Calculate Average
        double average = (double) sum / N;  // Cast is needed due to integer division

        // Step 4: Print Average Rounded
        average = Math.round(average * 100.0) / 100.0; // Round to two decimal places
        System.out.printf("Average: %.2f\n", average);  // Print to two decimal places
    }
}

Conclusion

In this tutorial, we solved a simple algorithm problem to calculate the average using Java. Although calculating an average is a basic concept, it requires a deeper understanding through various variations of the problem. There are often cases where the range of input data or exception handling must be considered. In the future, we will also cover these additional elements.

To strengthen your basics for coding tests, I recommend practicing by solving various problems through repetition. Thank you!

Hello, everyone! Today, we will be tackling algorithm problems for job preparation using Java. The topic this time is “Finding Cities at a Specific Distance,” utilizing graph theory and the BFS (Breadth-First Search) algorithm. We will delve deep into the fundamental concepts of algorithms and how to effectively use Java’s useful data structures while solving this problem.

Problem Description

The given cities are interconnected by roads, and each city is marked with a number. The task is to find and return all cities that can be reached by traveling a specific distance K starting from city number 1. Thus, the input consists of the number of cities N, the number of roads M, the starting city X, and the target distance K, and the output should be the city numbers sorted in ascending order.

Input

• First line: Number of cities N (1 ≤ N ≤ 30000), number of roads M (1 ≤ M ≤ 200000)
• Second line: Starting city number X (1 ≤ X ≤ N) and target distance K (0 ≤ K ≤ 30000)
• Next M lines: Two connected cities A, B (1 ≤ A, B ≤ N, A ≠ B)

Output

Print the numbers of the cities that can be reached at the target distance K in ascending order. If there are no reachable cities, print -1.

Solution Approach

To solve this problem, we need to construct a graph and use the BFS algorithm to find the cities reachable by the given distance K. BFS is suitable for this as it visits all vertices of the graph in level order, which helps in reaching cities at a specific distance.

Step 1: Graph Representation

We use an adjacency list to represent the road relationships between cities. In Java, we can utilize ArrayList to store adjacent cities for each city. This minimizes memory use and makes it easy to manage the relationships between cities.

Step 2: Implementing BFS

To implement BFS, we use a queue to store the current city and the current distance, continuing the search until this distance reaches K. Care should be taken not to revisit cities that have already been visited during the search process. Additionally, we must compare the current distance accurately with K.

Step 3: Output the Results

After collecting the cities that reached the target distance K, we sort them in ascending order and print them. If no city was reachable, we print -1.

Java Code Example

import java.util.*;

public class SpecificDistanceCity {
    static ArrayList[] graph;
    static boolean[] visited;
    static int[] distance;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // Number of cities
        int M = sc.nextInt(); // Number of roads
        int X = sc.nextInt(); // Starting city
        int K = sc.nextInt(); // Target distance

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

        // Input road information
        for (int i = 0; i < M; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            graph[A].add(B);
        }

        // Output the results
        List result = bfs(X, K);
        if (result.isEmpty()) {
            System.out.println(-1);
        } else {
            Collections.sort(result);
            for (int city : result) {
                System.out.println(city);
            }
        }

        sc.close();
    }

    private static List bfs(int start, int targetDistance) {
        List reachableCities = new ArrayList<>();
        Queue queue = new LinkedList<>(); // City and current distance
        visited = new boolean[graph.length];
        distance = new int[graph.length];

        queue.offer(new int[]{start, 0}); // (city, distance)
        visited[start] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int currentCity = current[0];
            int currentDistance = current[1];

            // Add city when reaching target distance
            if (currentDistance == targetDistance) {
                reachableCities.add(currentCity);
            }

            // Move to the next distance
            for (int neighbor : graph[currentCity]) {
                if (!visited[neighbor] && currentDistance + 1 <= targetDistance) {
                    visited[neighbor] = true;
                    queue.offer(new int[]{neighbor, currentDistance + 1});
                }
            }
        }

        return reachableCities;
    }
}

Code Explanation

The code above can be divided into three main parts. The main function initializes the graph and inputs the road information, then explores reachable cities using BFS. The BFS function uses a queue to manage the current city and distance and adds the city to the result list when it reaches the target. After all BFS explorations are completed, it sorts and outputs the reachable cities.

Try It Yourself

Now it’s your turn to run the code. Test with various input data to verify if the desired output is achieved. Additionally, try adding comments or modifying conditions in different parts of the code to experiment with its functionality. This will deepen your understanding of the algorithm.

Conclusion

Through this lecture, we learned the basic BFS algorithm and how to implement graphs to solve the problem of finding cities at a specific distance. As employment is the goal, I hope you solve many of these problems and build your skills. In the next lecture, we will tackle a more challenging topic. Thank you!

Coding tests are a mandatory requirement for many companies, and understanding data structures and algorithms has become a core competency. In this article, we will address the tree structure and the problem of finding its parent node. We will detail the importance of this problem, the methods to solve it, and the process of solving it in Java.

Problem Description

A tree structure is a data structure that represents the hierarchical relationship between nodes. Each node can have child nodes, and within this simple structure, various problems can arise. The problem at hand is to find the parent node of a given node.

Problem Definition

Write a program that takes the given tree and the value of a specific node as input and returns the corresponding parent node. If the input node is the root node or does not exist, it should return -1.

Input Format

First line: number of nodes  (1 ≤ N ≤ 100,000)
Second line: parent node information of each node (represented as space-separated integers)
Third line: the node to be found 

Output Format

Value of the parent node or -1

Approach to Problem Solving

We can use several methods to quickly find the parent node of the given tree. The most commonly used method is through array access. By storing the parent node information in an array, we can find the parent of a specific node in constant time. The process is as follows:

1. Choosing a Data Structure

To effectively store the parent information of nodes, we will use an array. The index of the array corresponds to the value of the node, and the value stored at each index is the value of the parent node. For example, if the parent information of the nodes is as follows:

[-1, 0, 0, 1, 1, 2]

In the above array:

• Parent of node 0: -1 (root node)
• Parent of node 1: 0
• Parent of node 2: 0
• Parent of node 3: 1
• Parent of node 4: 1
• Parent of node 5: 2

2. Designing the Algorithm

Now, we will design the algorithm. The overall process is as follows:

1. Initialize an array to store the parent information.
2. Receive the parent information array as input.
3. Receive the node to be found as input.
4. Check if the input node is within the range of the array.
5. Find and return the parent node.
6. If the parent node is the root node, return -1.

Java Code Implementation

Now, let’s implement the algorithm described above in Java. First, we will define the necessary classes and write the main method:

import java.util.Scanner;

public class FindParentNode {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // Input the number of nodes
        int n = sc.nextInt();
        int[] parents = new int[n];
        
        // Input parent information
        for (int i = 0; i < n; i++) {
            parents[i] = sc.nextInt();
        }
        
        // Input the target node
        int target = sc.nextInt();
        
        // Find the parent node
        int result = findParent(parents, target);
        System.out.println(result);
        
        sc.close();
    }
    
    // Method to find the parent node
    public static int findParent(int[] parents, int node) {
        if (node < 0 || node >= parents.length) {
            return -1; // Node does not exist
        }
        // Return the parent node
        return parents[node];
    }
}

Explanation

In the above code, we use the Scanner class to read inputs and store the parent information in the parents array. We then input the target node and call the findParent method to find the parent node. This method checks if the input node is valid, then returns the parent of the specified node.

Test Cases

Now, let’s create some test cases to ensure that the implemented code works correctly.

Test Case 1

Input:

6
-1 0 0 1 1 2
3

Output:

1

Test Case 2

Input:

6
-1 0 0 1 1 2
0

Output:

-1

Test Case 3

Input:

6
-1 0 0 1 1 2
6

Output:

-1

Conclusion

Through this posting, we explored the process of solving the problem of finding the parent node of a tree using Java. The tree structure is one of the fundamental concepts in data structures, and understanding the basic parent-child relationships will also be useful for solving other complex tree problems. I hope you will practice various problems and create your own solutions in preparation for coding tests.

The tree is a data structure frequently used in programming, consisting of nodes and edges in a connected structure. Each node contains data and connection information and has one root node connected to child nodes. In this article, we will learn about the basic concepts of trees and how to solve problems related to trees.

Basic Concepts of Trees

A tree consists of the following terms:

• Node: A structure that contains data and the information connecting that data.
• Root Node: The topmost node of the tree.
• Parent Node: A node that has child nodes.
• Child Node: A node connected to a parent node.
• Leaf Node: A node that has no child nodes.
• Depth: The length of the path from the root node to a specific node.
• Height: The length of the path from a specific node to the deepest leaf node.

Problem Definition

Let’s solve a tree-related problem using Java. The problem is to find the depth of a given binary tree.

Problem: Finding the Depth of a Binary Tree

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }
}

Problem Solving Process

1. Understanding the Problem

The goal of this problem is to traverse the given binary tree and calculate the depth of each node. The depth is defined as the number of edges from the root node to a specific node.

2. Choosing a Solution Method

We will use a recursive approach to explore the tree to solve this problem. When the current node is null, it indicates a depth of 0. Otherwise, we will recursively find the depth of the left and right subtrees, choose the larger value, and add 1.

3. Writing the Code

We will write the code based on the above approach.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public int maxDepth(TreeNode root) {
        // Base case: when the node is empty
        if (root == null) {
            return 0;
        }

        // Recursively find the depth of the left and right subtrees
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        // Return the greater value plus 1
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

4. Time Complexity Analysis

The time complexity of this algorithm is O(n), where n is the number of nodes in the tree. This is because we need to visit all the nodes once.

5. Final Code and Testing

Now let’s test the completed code to see if it works correctly.

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

        Solution solution = new Solution();
        System.out.println("The depth of the tree is: " + solution.maxDepth(root)); // Output: 3
    }
}

6. Conclusion

In this lecture, we covered the basic concepts of trees and the algorithmic problem of finding the depth of a binary tree. We found that the recursive approach can effectively solve this problem. Understanding these foundational concepts is very important for solving various tree problems and will be helpful for tackling more complex problems.

Additional Resources

• LeetCode Problem List
• GeeksforGeeks – Tree Data Structures
• Educative – Data Structures in Java