Category: Javascript Coding Test

Problem Definition

The problem is to calculate the amount of water that can be collected when it rains, given an array of heights of bars. The heights of the bars are provided as each element of the array.

For example, if the array is [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the amount of water that can be collected is 6. Visually representing how water is stored between each bar in this example is as follows:

Approaches to Solve the Problem

There are various methods that can be used to solve this problem. The two most commonly used approaches are as follows.

1. Two Pointers Method

   This method progresses by moving two pointers inwards from both ends. Each pointer tracks the height from the left and right, allowing calculation of positions where water can accumulate.

2. Dynamic Programming

   This method involves finding the tallest bar from both left and right at each position, using the shorter of the two to calculate the amount of water. However, this method has the drawback of using a lot of additional memory.

Solving the Problem with JavaScript

First, let’s implement the code using the two pointers method. We will create an algorithm that starts from both ends of the array and moves towards the center to calculate the amount of water.

Code Example

function trap(height) {
    if (height.length === 0) return 0;

    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let waterTrapped = 0;

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

    return waterTrapped;
}

            

The above function takes the height array as input and calculates the amount of water that can be collected after it rains.

Code Explanation

Let’s take a step-by-step look at the above code:

1. Initialization: left is initialized to 0, and right is initialized to the last index of the array (length – 1). leftMax and rightMax store the maximum heights from their respective directions. waterTrapped indicates the final amount of water collected.
2. Loop Execution: The loop runs until left is less than right. In each iteration, the heights from the left and right are compared to calculate the amount of water from the lower side.
3. Water Calculation: If the height from the left is lower, it compares the maximum height on the left with the current height to calculate the amount of water that can be stored. Similarly, the same operation is performed on the right side.
4. Return Result: After all loops are completed, it returns the waterTrapped variable to output the final result.

Code Testing

Now, let’s test the algorithm we’ve written. We can verify the performance of the function through several examples like the following:

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trap([4, 2, 0, 3, 2, 5])); // 9
console.log(trap([])); // 0
console.log(trap([1, 0, 1])); // 1

            

Each output should match the predicted amount of water. The following results will be displayed:

• trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) – 6
• trap([4, 2, 0, 3, 2, 5]) – 9
• trap([]) – 0
• trap([1, 0, 1]) – 1

Performance Analysis

The algorithm above has a time complexity of O(n) and a space complexity of O(1). This means that the execution time and space required are proportional to the size of the input array. Therefore, it works efficiently even with large amounts of data.

If dynamic programming is used, it requires an additional array to store heights, resulting in a space complexity of O(n). However, the time complexity remains O(n) as well.

Conclusion

In this lecture, we discussed the ‘Calculating the Amount of Water’ problem and introduced how to solve it using JavaScript. By using the two pointers algorithm, we effectively tackled the problem and also conducted code implementation and performance analysis.

This problem includes important concepts that can be applied to other algorithm problems, so practicing other similar problems can further enhance your algorithm skills.

This concludes the JavaScript coding test lecture. I hope it helps you improve your coding skills!

Problem Description

Here is a simple version of the DDR game. The game proceeds in the following format.

The user must press the corresponding keys based on the four arrows shown below:

• ↑ (Up)
• ↓ (Down)
• ← (Left)
• → (Right)

The goal of the game is to score points by accurately pressing the keys in the order of the given arrow inputs. If a wrong arrow is pressed, the user loses points.

You need to write a function that receives user input and calculates the score when given n arrows. This function adds 1 point for each correct input matching the answer sequence and subtracts 1 point for each incorrect input.

Input Format

        - Arrow array: ["↑", "↓", "←", "→"]
        - User input array: ["↑", "↑", "←", "→", "↓"]
        

Output Format

Returns the user’s final score.

Problem Solving Process

To solve this problem, let’s first design the algorithm. The steps to solve the problem are as follows.

1. Declare the arrow array and user input array.
2. Initialize a variable to maintain the score.
3. Iterate over user inputs and compare each input with the correct answers.
4. If the input is correct, increase the score by 1; if incorrect, decrease it by 1.
5. After checking all inputs, return the final score.

Now that the algorithm is clear, let’s write the code.

Code Implementation

function calculateScore(correctArrows, userArrows) {
    let score = 0;

    for (let i = 0; i < userArrows.length; i++) {
        if (userArrows[i] === correctArrows[i]) {
            score += 1; // Correct
        } else {
            score -= 1; // Incorrect
        }
    }

    return score; // Return final score
}

// Example usage
const correctArrows = ["↑", "↓", "←", "→"];
const userArrows = ["↑", "↑", "←", "→", "↓"];

const finalScore = calculateScore(correctArrows, userArrows);
console.log("Final score is:", finalScore);
        

Code Explanation

Let’s explain the code step by step.

1. Function Definition

The function calculateScore takes the arrow array and user input array as parameters. It initializes the score variable to 0 for score calculation.

2. Checking with Loop

Using a for loop, we iterate through the user input array. We check if each user’s input matches the correct arrows.

If they match, we add 1 point; if they do not match, we subtract 1 point.

3. Return Final Score

After checking all user inputs, we return the score value. This value is the final score.

Code Testing

To verify that the code works correctly, let’s create some test cases.

Test Case 1

const correct1 = ["↑", "↓", "←", "→"];
const user1 = ["↑", "↓", "←", "→"];

console.log("Test Case 1 - Score:", calculateScore(correct1, user1)); // 4
        

Test Case 2

const correct2 = ["↑", "↓", "←", "→"];
const user2 = ["↑", "↑", "←", "→", "↓"];

console.log("Test Case 2 - Score:", calculateScore(correct2, user2)); // 2
        

Test Case 3

const correct3 = ["↑", "↓", "←", "→"];
const user3 = ["→", "→", "→", "→"];

console.log("Test Case 3 - Score:", calculateScore(correct3, user3)); // -4
        

Conclusion

In this article, we solved a basic algorithm problem of the DDR game using JavaScript. We were able to solidify the basics of JavaScript through basic problem-solving methods and code writing.

This simple algorithm problem is one of the common types of problems that appear in interviews. Therefore, it’s beneficial to solve many similar problems and develop your own coding style. Thank you!