Category: Javascript Coding Test

Problem Definition

Write a function that meets the following conditions:

Given an integer array, write a function that returns the indices of the two numbers that add up to a specific target value. Assume that there is always a solution, and you may not use the same element twice.

function twoSum(nums, target) {
    // Write your code here.
}

Input Example

Input:

twoSum([2, 7, 11, 15], 9)

Output Example

Output:

0, 1

Solution Process

To solve this problem, we can use two approaches. The first is to use a double loop, and the second is to use a hash map. Considering efficiency, we will choose to use a hash map.

1. Problem Analysis

What we need to do is look at each element of the array and find the value that, when subtracted from the target, gives us that element. When we find this value, we can return the index of that element.

2. Using Hash Map

As a first step, we create an empty hash map (object). We traverse the array, adding each element to the hash map and also storing its index. Then, with each iteration, we check if the value that equals the target minus the current element exists in the hash map. If it does, we return that index.

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
}

3. Debugging Cases

After writing the code, it is important to check for parts that may cause errors. Through debugging, you can verify whether the logic for ‘finding the value equal to the target minus the current element’ works as intended. You can also use console logs to check the status of variables at each step.

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        console.log(`Current Number: ${nums[i]}, Complement: ${complement}`);
        if (map.has(complement)) {
            console.log(`Found complement: ${complement} at index ${map.get(complement)}`);
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
}

Conclusion

By solving the problem in the above manner, you can utilize the characteristics of JavaScript and conduct debugging more easily. After writing the code, it is always a good idea to use debugging tools (such as the developer tools in the browser) to test various cases and check the status of each variable, focusing on a deeper understanding of the problem.

In this lecture, we learned about algorithm problem-solving in JavaScript and the importance of debugging. We hope that this approach will help you in your coding test preparations.

Problem Description

This is an algorithm problem that tracks the movement path of game characters.

Problem: Given a game map, the character starts at (0, 0) and moves to position (n, m). The character can move one step at a time in the upward, downward, left, or right directions, and obstacles are set as impassable tiles. When a map including obstacles is given, find the number of all possible paths for the character to reach the target location.

Input:

• First line: integers n, m (1 ≤ n, m ≤ 10)
• Next n lines: m integers (0 is an empty space, 1 is an obstacle)

Output: The number of paths to the target location

Problem-Solving Approach

To solve the problem, we will use the Depth First Search (DFS) method. DFS is effective in exploring all possible paths and counting the number of valid paths. We will proceed with the following steps:

1. Initialize the map as a 2D array.
2. Implement a recursive function to explore the path from (0, 0) to (n, m).
3. Stop the exploration when encountering obstacles or boundaries, and count the paths.
4. After exploring all paths, return the number of paths.

Code Implementation

Now, based on the above approach, we will proceed with the code implementation using JavaScript.

function countPaths(map, x, y, n, m) {
    // If the goal position is reached
    if (x === n - 1 && y === m - 1) {
        return 1;
    }
    
    // If encountering boundaries or obstacles
    if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] === 1) {
        return 0;
    }
    
    // Mark the current position as visited
    const temp = map[x][y];
    map[x][y] = 1; // Mark as obstacle to indicate visit
    
    // Move up, down, left, and right
    const paths = countPaths(map, x + 1, y, n, m) +
                  countPaths(map, x - 1, y, n, m) +
                  countPaths(map, x, y + 1, n, m) +
                  countPaths(map, x, y - 1, n, m);
    
    // Restore the visited position
    map[x][y] = temp;
    
    return paths;
}

function findAllPaths(map) {
    const n = map.length;
    const m = map[0].length;
    return countPaths(map, 0, 0, n, m);
}

// Test case
const gameMap = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];

console.log(findAllPaths(gameMap)); // Output the number of paths

The above code calculates the number of paths that can be traversed from (0, 0) to (n-1, m-1) on the game map. It demonstrates well how to handle obstacles and boundaries.

Optimization

The implementation above is simple and easy to understand. However, this method may be inefficient due to duplicate explorations. To solve this, we can use memoization techniques. By using memoization, we can save the number of paths that have already been calculated and reuse the stored results when calculating at the same position, improving performance.

const memo = {};

function countPathsOptimized(map, x, y, n, m) {
    const key = x + ',' + y;
    // Check memoization
    if (key in memo) {
        return memo[key];
    }
    
    // If the goal position is reached
    if (x === n - 1 && y === m - 1) {
        return 1;
    }
    
    // If encountering boundaries or obstacles
    if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] === 1) {
        return 0;
    }
    
    // Mark the current position as visited
    const temp = map[x][y];
    map[x][y] = 1;
    
    // Calculate paths
    const paths = countPathsOptimized(map, x + 1, y, n, m) +
                  countPathsOptimized(map, x - 1, y, n, m) +
                  countPathsOptimized(map, x, y + 1, n, m) +
                  countPathsOptimized(map, x, y - 1, n, m);
    
    // Restore the visited position
    map[x][y] = temp;
    
    // Store in memoization
    memo[key] = paths;
    
    return paths;
}

function findAllPathsOptimized(map) {
    memo = {};
    const n = map.length;
    const m = map[0].length;
    return countPathsOptimized(map, 0, 0, n, m);
}

The optimized code above is almost similar to the previous code, but this time it prevents redundant calculations through memoization. This greatly enhances performance.

Conclusion

Through this course, we learned how to solve problems related to game development using JavaScript. We learned the basic approach needed to solve problems using DFS and memoization techniques. Practice solving algorithm problems to encounter and tackle more challenges.

Game development requires creative and logical thinking. By solving various algorithm problems, enhance your coding abilities and apply them to real projects. We will prepare more lectures related to algorithms and game development in the future. Thank you!