Category: Javascript Coding Test

JavaScript Coding Test Course, Kevin Bacon’s Six Degrees of Separation

Hello! In this post, we will explore “The Six Degrees of Kevin Bacon,” one of the topics in the JavaScript coding test, and I will detail the process of solving the problem. In this lecture, we will learn how to design and implement algorithms, as well as how to efficiently use JavaScript syntax and functions.

1. What is the Six Degrees of Kevin Bacon?

The Six Degrees of Kevin Bacon is a theory that describes the relationships among movie actors. According to this theory, the relationship between two people can be achieved through a maximum of six connections. In other words, if actor A is connected to actor B, and B has another connection to C, it is believed that there is a relationship between A and C within six degrees.

2. Problem Description

This problem is based on graph theory. Given a list of actors and their relationships, the task is to find the links between a specific actor and another actor and calculate how many degrees of connection exist between them.

Problem Definition

    Represent the given list of actors and their relationships as a graph,
    and write a function that calculates and returns the number of steps 
    between the two given actors.
    
    Constraints:
    - Each actor is represented as a string, and two actors are directly connected
      if they appeared in the same movie together.
    - The edges of the graph are undirected, allowing us to use BFS 
      (Breadth-First Search) to find the shortest path.
    
    Example input:
    actors = [
        ['A', 'B'],
        ['B', 'C'],
        ['C', 'D'],
        ['D', 'E'],
        ['A', 'E']
    ]
    startActor = 'A'
    targetActor = 'D'
    
    Example output:
    3 (A -> B -> C -> D)

3. Solution Method

To solve this problem, we will proceed with the following steps.

3.1. Selecting Data Structure

First, we need a data structure to store the relationships among all actors. We will represent this relationship using a Map or Object as a graph. Each actor will be a key, and the corresponding value will be an array of actors they have appeared with.

3.2. Constructing the Graph

Using the given list of actors, we will add the relationships between actors to the selected data structure.

3.3. Finding the Shortest Path

We’ll use the BFS algorithm to find the shortest path between the starting actor and the target actor. BFS is a useful algorithm for solving shortest distance problems, as it explores nodes level by level and guarantees the shortest path.

4. JavaScript Implementation

Now, based on what has been described above, let’s implement it in JavaScript code.

    function findShortestPath(actors, startActor, targetActor) {
        // Create the graph
        const graph = {};
        
        for (const [actorA, actorB] of actors) {
            if (!graph[actorA]) graph[actorA] = [];
            if (!graph[actorB]) graph[actorB] = [];
            graph[actorA].push(actorB);
            graph[actorB].push(actorA);
        }
        
        // BFS algorithm
        const queue = [[startActor, 0]];
        const visited = new Set();
        visited.add(startActor);
        
        while (queue.length > 0) {
            const [currentActor, steps] = queue.shift();
            
            // If the target actor is reached
            if (currentActor === targetActor) {
                return steps;
            }
            
            for (const neighbor of graph[currentActor]) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push([neighbor, steps + 1]);
                }
            }
        }
        
        // No connection
        return -1;
    }
    
    // Example execution
    const actors = [['A', 'B'], ['B', 'C'], ['C', 'D'], ['D', 'E'], ['A', 'E']];
    const startActor = 'A';
    const targetActor = 'D';
    
    console.log(findShortestPath(actors, startActor, targetActor)); // Output: 3

5. Code Analysis

Through the above code, we have constructed a graph based on the relationships between the given actors and implemented a method to find the shortest path using BFS. Let’s analyze this part in more detail.

5.1. Graph Implementation

The graph is structured as an object, where the key is the actor’s name and the value is an array of connected actors. We update the bidirectional connections directly by adding the associated actors.

5.2. Functioning of BFS

BFS is implemented using a queue. We add the starting actor to the queue and include visited actors in a Set to avoid duplicate visits. We continuously explore until the queue is empty, returning the number of steps taken when the target actor is found.

5.3. Time Complexity

The time complexity of this algorithm is O(V + E), where V represents the number of actors and E represents the number of edges. This ensures efficient performance, allowing for quick results even with large data sets.

6. Conclusion

In this post, we examined the process of solving an algorithm problem using “The Six Degrees of Kevin Bacon.” We covered the entire process from algorithm design to data structure selection, implementation, and analysis. Such problems are frequently featured in actual coding tests, so it is important to practice and master them.

In the future, I will continue to post about various algorithms and problem-solving methods. Always remember to practice coding, and feel free to leave any questions in the comments!

7. Additional Reference Materials

JavaScript Coding Test Course, Pathfinding

Coding tests are taken by many developers, and they are assessed through various algorithm problems. In this article, we will take a closer look at the algorithm problem-solving process through the ‘pathfinding’ problem. This problem is suitable for using graph traversal techniques such as DFS (Depth-First Search) or BFS (Breadth-First Search).

Problem Description

You need to find a path from the starting point to the destination point in a given 2D grid. Each cell of the grid indicates whether it can be moved to or not, and the following are the problem conditions:

  • The grid has dimensions N x M.
  • Each cell is marked with 0 or 1, where 0 indicates a traversable path and 1 indicates a blocked path.
  • The starting point is at (0, 0) and the destination point is at (N-1, M-1).
  • You can move up, down, left, or right.

Example Input

    4 4
    0 0 1 0
    0 1 0 0
    0 1 1 0
    0 0 0 0

Example Output

    Yes

Problem Solving Process

The algorithm we will use to solve this problem is BFS. BFS is advantageous for finding the shortest path as it explores each node in order. We will solve the problem through the following steps:

1. Create the grid space

Convert the received grid information into an array. This will facilitate access to and movement through each cell.

2. Initialize BFS

Add the starting point (0, 0) to the queue. Additionally, we use an extra array to track visited nodes.

3. Perform BFS search

Repeat the following while the queue is not empty:

  • Dequeue a node to check the current position.
  • Check if the current position is the destination point (N-1, M-1). If so, output ‘Yes’ and terminate the search.
  • For all cells that can be moved to up, down, left, or right, do the following:
    • Check the boundary conditions and whether it has been visited.
    • If the cell’s value is 0 and it has not been visited, add it to the queue and mark it as visited.

If the search completes and the destination point has not been reached, output ‘No’.

4. Code Implementation

    function canReachDestination(grid) {
        const N = grid.length;
        const M = grid[0].length;
        const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        const queue = [[0, 0]];
        const visited = Array.from({length: N}, () => Array(M).fill(false));

        visited[0][0] = true;

        while (queue.length > 0) {
            const [x, y] = queue.shift();

            // Check the destination point
            if (x === N - 1 && y === M - 1) {
                return "Yes";
            }

            for (const [dx, dy] of directions) {
                const nx = x + dx;
                const ny = y + dy;

                // Check boundary conditions and whether visited
                if (nx >= 0 && ny >= 0 && nx < N && ny < M && 
                    !visited[nx][ny] && grid[nx][ny] === 0) {
                    visited[nx][ny] = true;
                    queue.push([nx, ny]);
                }
            }
        }
        return "No";
    }

    const grid = [
        [0, 0, 1, 0],
        [0, 1, 0, 0],
        [0, 1, 1, 0],
        [0, 0, 0, 0]
    ];
    console.log(canReachDestination(grid)); // Result: "Yes"

Conclusion

Through this problem, we have solved a pathfinding problem using the BFS algorithm. In actual coding tests, you will often encounter such problems, so it is important to practice various algorithms to develop problem-solving skills for diverse challenges. In the next lesson, we will address different types of algorithm problems. Thank you!

Javascript Coding Test Course, Combine Numbers to Maximize Value

Hello! In this blog post, we will discuss the Making Maximum Value by Pairing Numbers problem that can be presented in coding tests with JavaScript. This problem requires various algorithmic thinking and provides an opportunity to deepen understanding of optimization problems. The goal is to combine the given numbers to create the largest possible number.

Problem Definition

You need to repeatedly combine two given numbers and multiply them to create the maximum value. The detailed problem definition is as follows:

Problem: Given an array of N natural numbers, write a program that pairs all the numbers two by two to maximize the sum of their products.

Input:
- The first line contains a natural number N (1 ≤ N ≤ 1000).
- The second line contains N natural numbers a1, a2, ..., aN (1 ≤ ai ≤ 1000).

Output:
- Print the maximum value.

Example of the Problem

Input:
5
1 2 3 4 5

Output:
43

Approach to the Problem

To solve this problem, several key steps are needed.

  • Sorting: Sort the given numbers in descending order. This is a preparatory step to keep the largest number and create a large multiplication result.
  • Pairing: Pair and multiply the numbers two by two from the array, and accumulate all the results. When pairing, pair the two largest numbers first and then proceed with the next two largest numbers.
  • Exception Handling: If an odd number of numbers are inputted, the remaining last number must be handled separately and included in the result.

Implementation

Let’s write the code to solve this problem with JavaScript. Below is the implemented code.


function maxSumFromPairs(numbers) {
    // Sort the array in descending order
    numbers.sort((a, b) => b - a);
    
    let maxSum = 0;

    // Pair two and multiply, then sum
    for (let i = 0; i < numbers.length; i += 2) {
        // If the last element is odd, add the remaining element alone
        if (i === numbers.length - 1) {
            maxSum += numbers[i];
        } else {
            maxSum += numbers[i] * numbers[i + 1];
        }
    }
    return maxSum;
}

// Example usage
const numbers = [1, 2, 3, 4, 5];
console.log(maxSumFromPairs(numbers)); // 43

Code Analysis

Let’s analyze each part of the code.

1. Sorting

First, we sort the array in descending order. This allows larger numbers to come first, and we calculate the product based on this. Sorting the array in JavaScript can be easily accomplished using the sort method.

2. Pairing and Summing

Through a loop, we read the elements of the array two by two and accumulate their product in maxSum. If the length of the array is odd, the last remaining element is simply added as it is.

3. Returning the Result

Finally, we return maxSum. The code is simple, but it allows us to efficiently obtain the maximum value.

Complexity Analysis

The time complexity of this algorithm is O(N log N). This is due to the time required to sort the array. The subsequent loop operates at O(N), making the overall operations linear, excluding sorting. The space complexity is O(1), as no additional space is used, making it memory efficient.

Test Cases

Let’s add a few test cases to verify the accuracy of the code.


console.log(maxSumFromPairs([3, 5, 1, 2, 4])); // 47
console.log(maxSumFromPairs([1])); // 1
console.log(maxSumFromPairs([9, 7, 5, 3])); // 64
console.log(maxSumFromPairs([1, 1, 1, 1, 1])); // 5

Conclusion

In this article, we discussed the problem of making maximum value by pairing numbers. We implemented the algorithm by sorting the array and calculating the maximum value. I hope this has been a valuable experience in considering how to efficiently handle immediate processing of arrays.

In coding tests using JavaScript, such optimization problems are often presented, so consistent practice is required. Additionally, I encourage you to challenge yourself with various problems to develop your algorithmic thinking!

JavaScript Coding Test Course, Sorting Numbers 1

Problem Description

Write a program to sort N given numbers in non-decreasing order. Non-decreasing order means that in the sorted sequence, a number can be equal to or greater than the preceding number.

Input

The first line contains the number of integers N (1 ≤ N ≤ 1,000,000). From the second line, N lines follow, each containing one integer. Each integer is a whole number and its absolute value does not exceed 1,000,000.

Output

Print the sorted numbers in ascending order, one per line, starting from the first line.

Input Example:
5
5
2
3
1
4

Output Example:
1
2
3
4
5

Problem Solving Process

Step 1: Problem Analysis

To understand the given problem, we need to clarify the structure of the input data and the required output.
– Input: Number N and the next N integers
– Output: The N integers sorted in non-decreasing order

The key to the problem is using an efficient sorting algorithm.
Since the size of the array can be up to 1,000,000, we cannot use common O(N^2) algorithms (like bubble sort, selection sort, etc.).
Therefore, we need to use sorting algorithms with a complexity of O(N log N), such as quicksort or mergesort.

Step 2: Algorithm Selection

We can use the built-in method of JavaScript Array.prototype.sort(), but since we need to guarantee the stability of the sort, we will implement quicksort or mergesort.

Step 3: Implementation

I will solve the problem using the Merge Sort algorithm.
Merge Sort works by dividing the list in half, recursively sorting each part, and then merging the two sorted parts.

Execution Process of Merge Sort

  • Divide the array into two subarrays by splitting it in half.
  • Recursively sort each subarray.
  • Combine the two sorted subarrays to create one sorted array.

Implementation of Merge Sort


function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0; 
    let j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

Step 4: Input and Output Processing

Now, I will write a function that takes input, sorts it using merge sort, and then outputs the results.
I will read the nodes, convert them to an array, and then call the merge sort function. 


const fs = require('fs');

// Read input from the file.
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);
const n = input.shift(); // Remove the first line which indicates the number of integers.

const sortedArray = mergeSort(input);

console.log(sortedArray.join('\\n')); // Print the sorted result with line breaks.

Step 5: Testing and Result Verification

I have tested the implemented code using the sample input.
Using the following input: 


5
5
2
3
1
4

The expected output is as follows. 


1
2
3
4
5

Conclusion

Through this problem, I learned about the importance of sorting algorithms in JavaScript and how to implement Merge Sort.
Since this is a common topic in practical interviews and coding tests, it is important to practice and implement various cases.
Understanding the theory of algorithms, along with writing code to get hands-on experience, is a crucial method for improving skills.

Reference Material: Try solving problems on various platforms for algorithm problem-solving (e.g., Baekjoon, Codeforces, etc.).

JavaScript Coding Test Course, Calculating Interval Sum 1

Hello! Today we will tackle the problem of calculating the range sum using JavaScript. The range sum problem is very helpful in learning how to efficiently process data and manipulate arrays. This topic frequently appears in coding tests and algorithm problem-solving, so I encourage you to thoroughly understand it through this opportunity.

Problem Description

Implement a function rangeSum(array, start, end) that efficiently calculates the sum of a specific range in the given array. Here, array is an array of integers, and start and end represent the indices of the array. The sum of the range is defined as array[start] + array[start + 1] + ... + array[end].

Input

  • 1 ≤ array.length ≤ 105
  • -109 ≤ array[i] ≤ 109
  • 0 ≤ start ≤ end < array.length

Output

Returns an integer that represents the sum of the range.

Example

Input: rangeSum([1, 2, 3, 4, 5], 1, 3)
Output: 9 // 2 + 3 + 4 = 9

Solution

To compute the range sum, it is essential to understand the array and the starting and ending indices of the range. The problem we need to solve is to sum all the numbers within a specified index range in the given array. However, as the size of the array may increase, it is important to use an efficient method.

Simple Loop Approach

The simplest and most intuitive way is to calculate the sum of the range directly using a loop within the given index range. The time complexity of this method is O(n).

function rangeSum(array, start, end) {
        let sum = 0;
        for (let i = start; i <= end; i++) {
            sum += array[i];
        }
        return sum;
    }

The above code sums all the values in the range using the given array and start and end indices. However, this method is inefficient because it requires recalculating from the beginning every time the range changes.

More Efficient Method: Prefix Sum Array

One approach is to scan the array once and store the cumulative sum. This method consists of the following steps:

  1. Create a prefix sum array.
  2. Calculate the cumulative sum based on the original array.
  3. To find the range sum, simply calculate sum[end] - sum[start - 1].

The implementation code is as follows:

function rangeSum(array, start, end) {
        const prefixSum = new Array(array.length).fill(0);
        prefixSum[0] = array[0];
        for (let i = 1; i < array.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + array[i];
        }
        return start > 0 ? prefixSum[end] - prefixSum[start - 1] : prefixSum[end];
    }

This method goes through an initialization process with a time complexity of O(n), after which the range sum can be calculated in O(1). By scanning the array once to obtain the prefix sum, it operates very efficiently based on the number of ranges that need to be calculated afterwards.

Time Complexity

The time complexity for the simple loop approach, which is the first method, remains O(n) regardless of the size of the range. However, using the prefix sum method allows each range sum to be calculated in O(1) after the initial O(n) time complexity, thus becoming advantageous as the number of queries increases.

Conclusion

Today, we learned how to calculate the range sum using JavaScript. By learning to solve problems efficiently, you will develop the ability to overcome frequently encountered challenges in coding tests. Now, practice with different arrays and test them yourself!

References