Category: Javascript Coding Test

This article will cover one of the frequently asked algorithm problems in JavaScript coding tests, “Sum of Digits.” Through this problem, we will learn about basic algorithm construction abilities and how to handle data in JavaScript.

Problem Description

Given a string of numbers, write a function that calculates the sum of the digits included in the string.
For example, if the input string is “12345”, it should return 1 + 2 + 3 + 4 + 5 = 15.

Input

• A single string of digits with length n is provided (1 ≤ n ≤ 10⁶)

Output

• Returns the sum of all the digits in the string as an integer.

Problem Approach

To solve this problem, the following basic steps will be undertaken:

1. Traverse the string of digits and convert each character to a number.
2. Accumulate the converted numbers.
3. Return the final sum.

Code Implementation

The code implementation to solve this problem in JavaScript can be done as follows.

function sumOfDigits(numString) {
    // Initialize basic variable
    let total = 0;

    // Traverse characters
    for(let i = 0; i < numString.length; i++) {
        // Convert each character to number and accumulate
        total += parseInt(numString[i]);
    }

    // Return final sum
    return total;
}

// Function test
const inputString = "12345";
const result = sumOfDigits(inputString);
console.log("Input string:", inputString);
console.log("Sum of digits:", result); // Output: 15

Code Explanation

The above code defines a function called sumOfDigits. This function takes a string of numbers as input, traverses each character, converts it to an integer, and calculates the total sum.

• let total = 0;: Initializes a variable to store the sum from the string.
• for(let i = 0; i < numString.length; i++) { ... }: Uses a loop to iterate through each character of the input string based on its length.
• total += parseInt(numString[i]);: Uses parseInt to convert each character of the string to an integer and accumulates the sum.
• return total;: Returns the accumulated sum.

Time Complexity Analysis

The time complexity of this algorithm is O(n), where n refers to the length of the input string. Since we only traverse the string once, the time complexity is linear.

Space Complexity Analysis

The space complexity is O(1). This is because, apart from the input string, only one additional variable is used.

Variant Problem

If the above problem is the basic form, a variant might be "Calculate the sum of positive numbers in an array containing both negative and positive numbers."
Such problems may require adjusting the basic algorithm or considering additional conditions, thus necessitating slight modifications to the code.

Example Modified Code for Variant Problem

// Variant Problem: Calculate the sum of digits at even indices
function sumEvenIndexedDigits(numString) {
    let total = 0;

    // Sum only the digits at even indices
    for(let i = 0; i < numString.length; i += 2) {
        total += parseInt(numString[i]);
    }
    
    return total;
}

// Code test
const inputString = "123456"; // Example: sum 1, 3, and 5
console.log("Sum of even indices:", sumEvenIndexedDigits(inputString)); // Output: 12

Conclusion

The "Sum of Digits" problem is very useful for learning the basic syntax and algorithms of JavaScript.
Through this problem, one can learn foundational concepts like string handling, loops, and conditional statements.
Try exploring various variant problems to deepen your understanding of algorithms.

In the next session, we will tackle more complex problems. I hope this course helps you learn various techniques that you can use in JavaScript coding tests and aids you in effectively solving problems.

Hello! In this post, we will solve an algorithm problem based on the theme “Command of Jumong” for those preparing for coding tests with JavaScript. Throughout this process, we’ll thoroughly explain how to understand the problem, the approach, code implementation, and time complexity analysis.

Problem Description

Despite the winter, Jumong issued commands to his subordinates. His commands are given in the following format:

• A binary tree is given.
• Each node contains an integer from 0 to n.
• When a number x commanded by Jumong is provided, we need to count the occurrences of x in all paths of the binary tree.

In this problem, we must clearly understand what a path in the tree is and how to traverse it. A path refers to the set of all nodes moving from the root to a leaf node.

Input Format

{
    "root": {
        "value": 1,
        "left": {
            "value": 2,
            "left": null,
            "right": {
                "value": 3,
                "left": null,
                "right": null
            }
        },
        "right": {
            "value": 4,
            "left": null,
            "right": null
        }
    },
    "x": 1
}

Output Format

Return the sum of the occurrences of x in all paths containing the number x in the given binary tree.

{
    "result": 2
}

Approach to the Problem

To solve this problem, we will use the DFS (Depth-First Search) algorithm. It involves counting `x` while traversing the binary tree in a depth-first manner along the paths.

Step 1: Tree Traversal

First, we write a recursive function that can traverse the tree. This function takes the current node, the count of x included in the current path, and a variable to store the result as arguments.

Step 2: Save Path and Check Conditions

We check if the node is a leaf node, and when we reach a leaf node, we add the count of x included in the path to the result variable. If the current node is not a leaf, we recursively traverse the left and right child nodes.

Step 3: Time Complexity Analysis

The time complexity of this algorithm is O(n) since we visit each node in the tree once.

Code Implementation

function countXPaths(root, x) {
    let totalPathsCount = 0;

    function dfs(node, currentCount) {
        if (node === null) {
            return;
        }

        // Check the value of the current node
        let newCount = currentCount + (node.value === x ? 1 : 0);

        // Check if it's a leaf node
        if (node.left === null && node.right === null) {
            totalPathsCount += newCount;
            return;
        }

        // Traverse the left and right child nodes
        dfs(node.left, newCount);
        dfs(node.right, newCount);
    }

    dfs(root, 0);
    return { result: totalPathsCount };
}

Test Cases

Now, let’s create various test cases to ensure that the code we wrote works as expected.

// Test Case 1
const testCase1 = {
    root: {
        value: 1,
        left: {
            value: 2,
            left: null,
            right: {
                value: 1,
                left: null,
                right: null
            }
        },
        right: {
            value: 4,
            left: null,
            right: null
        }
    },
    x: 1
};
console.log(countXPaths(testCase1.root, testCase1.x)); // Output: { result: 2 }

// Test Case 2
const testCase2 = {
    root: {
        value: 2,
        left: {
            value: 1,
            left: null,
            right: null
        },
        right: {
            value: 1,
            left: {
                value: 3,
                left: null,
                right: null
            },
            right: null
        }
    },
    x: 1
};
console.log(countXPaths(testCase2.root, testCase2.x)); // Output: { result: 3 }

// Test Case 3
const testCase3 = {
    root: {
        value: 5,
        left: {
            value: 1,
            left: {
                value: 1,
                left: null,
                right: null
            },
            right: {
                value: 2,
                left: null,
                right: null
            }
        },
        right: {
            value: 7,
            left: null,
            right: null
        }
    },
    x: 1
};
console.log(countXPaths(testCase3.root, testCase3.x)); // Output: { result: 2 }

Conclusion

In this post, we understood and implemented the concepts of depth-first search and recursive functions through the algorithm problem called “Command of Jumong.” By creating various test cases, we increased the reliability of the code and systematically organized how to solve the problem step by step.

The mindset for approaching problems and implementation skills are very important in the process of preparing for coding tests. Continuously practicing will help you become familiar with solving such problems.

Hello! In this tutorial, we will cover one of the frequently asked problems in coding tests, the Traveling Salesman Problem (TSP). This problem helps to understand important concepts in graphs and dynamic programming.

1. Problem Description

The Traveling Salesman Problem is the problem of finding the minimum cost path that visits all given cities once and returns to the starting city. This problem is typically represented by a distance matrix that provides the cost of moving between cities, and the salesman must visit all cities exactly once.

2. Mathematical Representation of the Problem

Let the number of cities be represented as N. The distance matrix between cities is defined in the form of cost[i][j]. Here, cost[i][j] represents the cost of moving from city i to city j. The path that the salesman must take can be expressed as follows:

min(cost[0][1] + cost[1][2] + ... + cost[N-1][0])

3. Approach to Solve the Problem

Since the Traveling Salesman Problem is NP-hard, the time complexity is very high for solving it using brute force. Therefore, we can solve the problem more efficiently using dynamic programming.

To solve this problem using a dynamic programming approach, we will use bit masking. Bit masking helps to easily check the visiting status by representing each city as a bit. Let’s approach the problem using the following algorithmic steps.

3.1 State Representation through Bit Masking

We represent the state of visited cities as a bitmask. For example, if there are 4 cities:

• 0000: No city visited
• 0001: City 0 visited
• 0010: City 1 visited
• 0011: Cities 0 and 1 visited
• …All combinations can be expressed in this way.

3.2 Definition of the Dynamic Programming Table

The DP table dp[mask][i] stores the minimum cost of visiting the cities corresponding to mask and starting from city i. In the initial state, mask is set to 1, and all other states are initialized to infinity (INFINITY).

4. Algorithm Implementation

Now, let’s implement the algorithm we wrote in JavaScript.

function tsp(cost) {
    const N = cost.length;
    const INF = Number.MAX_SAFE_INTEGER;
    const dp = new Array(1 << N).fill(null).map(() => new Array(N).fill(INF));
    
    // Starting point
    dp[1][0] = 0;

    for (let mask = 0; mask < (1 << N); mask++) {
        for (let u = 0; u < N; u++) {
            if (dp[mask][u] === INF) continue; // Skip if u is not visited

            // Visit all other cities not in the current mask
            for (let v = 0; v < N; v++) {
                if (mask & (1 << v)) continue; // Skip if v is already visited

                const nextMask = mask | (1 << v);
                dp[nextMask][v] = Math.min(dp[nextMask][v], dp[mask][u] + cost[u][v]);
            }
        }
    }

    let ans = INF;
    for (let i = 1; i < N; i++) {
        ans = Math.min(ans, dp[(1 << N) - 1][i] + cost[i][0]);
    }

    return ans;
}

5. Time Complexity

The time complexity of this algorithm is O(N^2 * 2^N). Since the method of representing states through bit masking and the process of updating the DP table are combined, significant computation time is required as the number of cities increases. Therefore, this algorithm is only practical when N is less than or equal to 20.

6. Testing and Examples

Now, let's provide some examples to test the algorithm. Below is the cost matrix between cities:

const costMatrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
];
console.log(tsp(costMatrix)); // Expected output: 80

7. Conclusion

By dealing with the Traveling Salesman Problem, we gained an understanding of the pathfinding techniques using dynamic programming and bit masking. This problem may seem like a simple route-finding problem, but it is an important algorithmic problem that can be applied in various fields, such as route optimization for internet companies.

I hope this tutorial has been helpful in solving algorithmic problems using JavaScript, and I encourage you to solve more problems through additional practice. Thank you!

1. Problem Description

The diameter of a tree refers to the length of the longest path in the tree. A single tree is a connected set of nodes, with each node branching out from a root node.
The problem of finding the diameter of a tree frequently appears in graph theory and is primarily solved using Depth First Search (DFS) or Breadth First Search (BFS).
In this course, we will explore how to find the diameter of a tree and how to implement it using JavaScript.

2. Example Input and Output

        7
        1 2 3
        1 3 4
        2 4 3
        2 5 2
        3 6 1
        3 7 3
        

7

3. Problem Approach

One way to find the diameter of a tree is to use two rounds of DFS or BFS as follows:

1. Start from a random node and find the most distant node. We will call this node a temporary node.
2. Starting from the temporary node, perform DFS or BFS again to find the distance to the furthest node. This distance is the diameter of the tree.

4. JavaScript Implementation

Now, let’s write the code to find the diameter of the tree in JavaScript using the above method. Before we begin, we need to define a simple data structure.

    class TreeNode {
        constructor(value) {
            this.value = value;
            this.children = [];
        }
    }

    class Tree {
        constructor() {
            this.root = null;
        }

        addEdge(parentValue, childValue) {
            const parentNode = this.findNode(this.root, parentValue);
            const childNode = new TreeNode(childValue);
            if (parentNode) {
                parentNode.children.push(childNode);
            } else {
                this.root = parentNode; // If root is null, set it as the first node
            }
        }

        findNode(node, value) {
            if (!node) return null;
            if (node.value === value) return node;
            for (const child of node.children) {
                const result = this.findNode(child, value);
                if (result) return result;
            }
            return null;
        }

        diameter() {
            return this.diameterHelper(this.root).diameter;
        }

        diameterHelper(node) {
            if (!node) return { height: 0, diameter: 0 };

            let maxHeight1 = 0, maxHeight2 = 0, diameter = 0;

            for (const child of node.children) {
                const { height, diameter: childDiameter } = this.diameterHelper(child);
                diameter = Math.max(diameter, childDiameter);
                if (height > maxHeight1) {
                    maxHeight2 = maxHeight1;
                    maxHeight1 = height;
                } else if (height > maxHeight2) {
                    maxHeight2 = height;
                }
            }

            diameter = Math.max(diameter, maxHeight1 + maxHeight2);
            return { height: maxHeight1 + 1, diameter };
        }
    }
    

5. Code Explanation

The code above includes the functionality to find the diameter of a tree. Let’s explain the main parts.

• TreeNode Class: Represents each node of the tree. It includes the node value and a list of the node’s children.
• Tree Class: This class manages the tree. It includes the addEdge method to add child nodes and the findNode method to find a node with a given value.
• diameter Method: Calls the diameterHelper function to calculate the tree’s diameter.
• diameterHelper Function: Recursively computes the maximum height at each node and updates the diameter at the current node.

6. Performance Analysis

The time complexity of this algorithm is O(n) as it visits every node in the tree once.
The space complexity is O(h) in the worst case because stack frames are used up to the maximum height of the tree, where h signifies the height of the tree.

7. Conclusion

We have explored how to find the diameter of a tree using JavaScript. Problems of this type frequently appear in coding tests, so
it is beneficial to practice many example problems to become familiar with them.
Understanding and utilizing tree structures and DFS/BFS search methods is important, and these fundamental concepts can be applied in various contexts.