Category: Javascript Coding Test

Problem Description

This problem involves finding the Lowest Common Ancestor (LCA) of two nodes.
Given a binary tree, the goal is to find the common ancestor of two specified nodes.

Input Format

• The root node of the binary tree is given.
• Two node values are provided.

Output Format

• The value of the Lowest Common Ancestor of the given two nodes, or -1 if it does not exist.

Example Problems

    Input:
        1
       / \
      2   3
     / \
    4   5

    The LCA of nodes 4 and 5 is 2.
  
    Input:
        1
       / \
      2   3
     / \
    4   5

    The LCA of nodes 4 and 3 is 1.

    Input:
        1
       / \
      2   3
     / \
    4   5

    The LCA of nodes 6 and 7 is -1.
    

Problem Solution

To solve this problem, we approach it with the following steps:

1. Define the binary tree structure:
   First, we define a node class to represent the structure of the tree. This class has a value for the node,
   and properties that reference left and right child nodes.
2. Recursive Approach:
   To find the lowest common ancestor, we recursively traverse the tree.
   If the current node corresponds to ${p} or ${q}, we return the current node.
3. Check Left and Right Subtrees:
   We find the LCA in both the left and right subtrees, and if both results exist,
   the current node is the LCA.
4. Return Result:
   If both nodes are found, return the current node; otherwise, return null.

JavaScript Code Implementation

// Define a binary tree node class
class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// Function to find the lowest common ancestor
function findLCA(root, p, q) {
    // Base case: when the current node is null
    if (root === null) {
        return null;
    }
    
    // If the current node is p or q, return the current node
    if (root.value === p || root.value === q) {
        return root;
    }
    
    // Find LCA in left and right subtrees
    const leftLCA = findLCA(root.left, p, q);
    const rightLCA = findLCA(root.right, p, q);
    
    // If results exist in both left and right, the current node is LCA
    if (leftLCA && rightLCA) {
        return root;
    }
    
    // Return the result found in one of the subtrees
    return leftLCA !== null ? leftLCA : rightLCA;
}

// Example usage
const 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);

const node1 = 4;
const node2 = 5;
const lca = findLCA(root, node1, node2);
console.log(lca ? lca.value : -1); // Output: 2
    

Conclusion

Finding the lowest common ancestor is an important search problem in binary trees.
It can be solved efficiently through a recursive approach for various tree structures and nodes.
This method is useful in many situations and will greatly aid in understanding recursive thinking and tree traversal.

Additional Tasks

Try to solve the following additional tasks!

• Add logic to handle the case where the given nodes do not exist.
• Research and implement an optimized method to find the LCA in a binary search tree.
• Also, implement a function to visualize various tree structures.

References

• Lowest Common Ancestor – Wikipedia
• LeetCode: Lowest Common Ancestor of a Binary Tree

Hello! In this article, we will take a detailed look at how to solve the “Maximum Square” problem using JavaScript. This problem can be efficiently solved using a Dynamic Programming approach. It is a type of problem frequently encountered in coding tests at actual companies, so by solving this problem, we will solidify our understanding of the concept of dynamic programming and explore its application in real-world scenarios.

Problem Description

Given a 2-dimensional array matrix, the problem is to find the length of the side of the largest square made up entirely of ‘1’s. For example, if the input matrix is as follows:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

In this matrix, the length of the side of the largest square is 2. In other words, the maximum size of ‘1’s is 2×2.

Approach to Solve the Problem

This problem can be approached in several ways, but using dynamic programming is the most efficient. By using dynamic programming, we can reuse previously calculated values to reduce unnecessary computations. Here is a step-by-step approach to solving this problem.

Step 1: Set Up the Dynamic Programming Table

First, create a 2-dimensional array dp with the same size as the original matrix. This array will store the maximum side length of the square made up of ‘1’s at each position.

Step 2: Handle Boundary Conditions

The first row and the first column of the matrix are set as boundary conditions. In this case, if the position is ‘1’, the maximum side length of the square is 1. If it is ‘0’, there can be no square, so it is set to 0.

Step 3: Fill the DP Array

Next, traverse the matrix and update the DP array based on the value at each position. If the current position matrix[i][j] is ‘1’, the length of the side of the square at that position is calculated as follows:

dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;

Here, the Math.min() function calculates the minimum value from above, left, and diagonal-left. This minimum value represents the minimal length needed to form a square.

Step 4: Process the Result

Finally, to find the side length of the square, look for the largest value in the DP array.

Algorithm Implementation

Now, let’s implement the actual algorithm using JavaScript based on the approach described above.

function maximalSquare(matrix) {
    if (matrix.length === 0) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    const dp = Array.from({ length: rows }, () => Array(cols).fill(0));
    let maxSide = 0;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (matrix[i][j] === '1') {
                if (i === 0 || j === 0) {
                    dp[i][j] = 1; // For the first column or row, it is 1
                } else {
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                }
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide; // Return the area of the square
}

Performance and Complexity Analysis

The time complexity of this algorithm is O(m*n), and the space complexity is O(m*n). Here, m is the number of rows in the matrix, and n is the number of columns. Since a DP array is used, additional space is needed, but this can be optimized to O(n).

Optimization: Reducing Space Complexity

In some cases, the space complexity of the DP array can be reduced to O(n). Two arrays can be used to save the previous DP array, and only the previous state is needed when updating the current state.

function maximalSquare(matrix) {
    if (matrix.length === 0) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    let dp = Array(cols).fill(0);
    let maxSide = 0, prev = 0;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            let temp = dp[j]; // Store the previous value
            if (matrix[i][j] === '1') {
                if (i === 0 || j === 0) {
                    dp[j] = 1;
                } else {
                    dp[j] = Math.min(dp[j], dp[j-1], prev) + 1;
                }
                maxSide = Math.max(maxSide, dp[j]);
            } else {
                dp[j] = 0; // Set to 0 for '0'
            }
            prev = temp; // Update the previous value
        }
    }

    return maxSide * maxSide; // Return the area of the square
}

Conclusion

Today, we learned how to solve the “Maximum Square” problem, which frequently appears in JavaScript coding tests, using dynamic programming. This problem helps to understand the basic concepts of dynamic programming and will greatly enhance your coding skills in real-world scenarios. Don’t forget to improve your understanding of algorithms and data structures by solving various problems!

We will cover more algorithmic problems in the future, so please stay tuned. Thank you!

Hello! In this blog post, we will discuss an algorithm problem to prepare for the JavaScript coding test. The topic is ‘Creating Blu-rays’. The problem is to find the minimum number of Blu-rays needed to create the given movies. To solve this, we will need to utilize binary search and the greedy algorithm.

Problem Description

You want to create multiple movies on Blu-ray. The running time of each movie is given, and a Blu-ray can hold up to K amount of time. Your goal is to minimize the number of Blu-rays to store all the movies. However, each Blu-ray must contain movies such that their total running time does not exceed K.

Input

• The first line contains N and K. (1 ≤ N ≤ 1000, 1 ≤ K ≤ 10^6)
• The second line contains N natural numbers separated by spaces, representing the running times of each movie. (1 ≤ movie running time ≤ 10^6)

Output

Print the minimum number of Blu-rays.

Example

Input:
4 5
2 3 1 4

Output:
2

Problem Solving Process

To approach this problem, we can proceed in the following steps.

Step 1: Understand the Problem

Consider how to allocate the given movies into Blu-rays with a maximum running time of K. Since the running times of each movie are provided, we need to consider how to combine them without exceeding K.

Step 2: Derive Ideas

Since we cannot simply fit all movies into one Blu-ray, we will iteratively explore the movie list to check if they can fit into each Blu-ray. To do this, we will use binary search to find the minimum number of Blu-rays needed.

Step 3: Exception Handling

If the time to fit a movie exceeds K, we must place that movie on a new Blu-ray. It is important to be mindful of this condition to fit as many movies as possible into Blu-rays.

Step 4: Algorithm Implementation

Now, we will implement a JavaScript function based on the above ideas.

function minBluRays(N, K, movies) {
    let bluRays = 0;
    let currentTime = 0;

    for (let i = 0; i < N; i++) {
        if (currentTime + movies[i] > K) {
            bluRays++;
            currentTime = movies[i];
        } else {
            currentTime += movies[i];
        }
    }

    if (currentTime > 0) {
        bluRays++;
    }

    return bluRays;
}

// Example execution
const N = 4;
const K = 5;
const movies = [2, 3, 1, 4];
console.log(minBluRays(N, K, movies)); // Output: 2

Conclusion

In this article, we demonstrated the process of solving a commonly encountered algorithm problem in JavaScript coding tests through the ‘Creating Blu-rays’ problem. Understanding the essence of the problem and finding the necessary algorithms is very important. It is advisable to utilize the given time well to write efficient code.

I hope this problem helps you develop a basic understanding of JavaScript and an algorithmic mindset. Thank you!

Problem: Maze Exploration

This is a problem to determine whether there is a path from the starting point to the destination in the given 2D array. The values of the array are given as 0 (passable) and 1 (impassable). The starting point is (0, 0) and the destination is (N-1, M-1). Movement is allowed only up, down, left, and right, and if a path exists, it should return true; if not, it should return false.

Example Problem

Input

    [
        [0, 0, 1, 0],
        [1, 0, 1, 0],
        [0, 0, 0, 0],
        [0, 1, 1, 0]
    ]
    

Output

true

Explanation

In the above example, starting from the starting point (0, 0), the path goes through (1, 1), (2, 1), (2, 2), (2, 3), (3, 3) to reach the destination (3, 3).

Problem Solving Process

1. Overview of the Algorithm

This problem can be solved using the Depth First Search (DFS) algorithm. DFS is a method that goes as deep as possible into the nodes before backtracking to explore other paths. We will implement this using recursion. DFS is applied to explore the maze and check whether it is possible to reach the destination from the starting point.

2. Implementing the DFS Algorithm

To implement DFS, the following steps are necessary:

1. Check if the current position is within bounds.
2. Check if the current position is an impassable point.
3. Check if the current position is the destination.
4. Mark the current position as visited.
5. Recursively call DFS in all four directions (up, down, left, right).
6. After exploring all paths, unmark the visited position.

3. Code Implementation

The following code implements the DFS algorithm using JavaScript:

function isPathExists(maze) {
    const rows = maze.length;
    const cols = maze[0].length;

    function dfs(x, y) {
        // Boundary conditions
        if (x < 0 || y < 0 || x >= rows || y >= cols) return false;
        // Impassable point
        if (maze[x][y] === 1) return false;
        // Destination
        if (x === rows - 1 && y === cols - 1) return true;

        // Mark current position as visited
        maze[x][y] = 1;

        // Explore DFS in four directions
        const found = dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1);

        // Unmark visited position
        maze[x][y] = 0;

        return found;
    }

    return dfs(0, 0);
}

// Example Test
const maze = [
    [0, 0, 1, 0],
    [1, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 1, 0]
];

console.log(isPathExists(maze)); // Output: true

4. Code Explanation

Let me explain the key parts of the code:

• Boundary condition check: Ensures the current position does not exceed the array boundaries.
• Impassable point check: Verifies if the value at the current position is 1 to determine if it is passable.
• Destination reached: Returns true if the current position is the destination (N-1, M-1).
• Mark as visited: Marks the current position to prevent duplicate exploration.
• Recursive call: Calls DFS recursively in the four directions to explore the path.
• Unmarking: Unmarks the visited position after the exploration is complete.

5. Time Complexity Analysis

The time complexity of this algorithm is O(N * M), where N is the number of rows and M is the number of columns. This is because each cell can be visited once. However, there may be additional memory required in the worst-case scenario due to stack space overhead from recursion.

Conclusion

In this tutorial, we learned how to solve the maze exploration problem using Depth First Search (DFS). DFS can be effectively used even in complex graph structures, and it can be applied to various problems. Once you understand the characteristics and workings of DFS, it is advisable to apply it to different problems. In the next tutorial, we will explore the Breadth First Search (BFS) algorithm. I hope you found this tutorial helpful.

Problem Description

This problem is about finding the number closest to a given num value in the provided array arr. If there are multiple closest numbers, the one closer to num with a lower value takes precedence.

Input

• An integer array arr (-10⁶ ≤ arr[i] ≤ 10⁶, 1 ≤ arr.length ≤ 10⁵)
• An integer num (-10⁶ ≤ num ≤ 10⁶)

Output

Return the closest number.

Examples

Example 1:
Input: arr = [1, 2, 3, 4, 5], num = 3
Output: 3

Example 2:
Input: arr = [1, 2, 4, 5], num = 3
Output: 2

Example 3:
Input: arr = [5, 10, 15], num = 12
Output: 10

Solution Process

To solve this problem, we follow these steps.

Step 1: Understand the Problem

First, since the task is to find the number closest to num, the key is to calculate the absolute differences between each element and num and find the smallest value. If there are multiple numbers with the same difference, the smaller value should be returned.

Step 2: Choose an Approach

The simplest method is to iterate through the array and calculate the absolute differences for each element. However, this has a time complexity of O(n), so we need to consider a faster algorithm.

Step 3: Utilize Binary Search through Sorting

By sorting the input array, we can efficiently find the number closest to num using binary search. To find the index of a specific value num in the sorted array, we will use Array.prototype.sort() and then implement a binarySearch() function.

Step 4: Implement the Code

Below is the JavaScript code based on the above explanation.

function findClosest(arr, num) {
    // Sort the array
    arr.sort((a, b) => a - b);
    
    let left = 0;
    let right = arr.length - 1;
    let closest = arr[0];

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        // Compare absolute differences
        if (Math.abs(arr[mid] - num) < Math.abs(closest - num) ||
            (Math.abs(arr[mid] - num) === Math.abs(closest - num) && arr[mid] < closest)) {
            closest = arr[mid];
        }
        
        // Determine the direction of binary search
        if (arr[mid] < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return closest;
}

// Example Tests
console.log(findClosest([1, 2, 3, 4, 5], 3)); // 3
console.log(findClosest([1, 2, 4, 5], 3));    // 2
console.log(findClosest([5, 10, 15], 12));      // 10

Step 5: Analyze Time Complexity

The above code first sorts the array, which has a time complexity of O(n log n), and then the searching process using binary search requires O(log n) time. Therefore, the overall time complexity can be evaluated as O(n log n).

Conclusion

This problem has taught us the importance of choosing an efficient algorithm considering time complexity. It is necessary to try various approaches for the given problem and select the appropriate algorithm based on the results. I hope you apply these principles well in future coding tests!