Category: Javascript Coding Test

Problem Description

This problem involves taking an array of given natural numbers and using a stack to create a sequence sorted in ascending order.
The array of natural numbers consists of integers between 1 and 1000, and each natural number is unique.
Additionally, the sequence must be constructed using only a stack while satisfying the following conditions:

• Each natural number can be used only once.
• The given natural numbers must be pushed onto the stack, and the numbers must be sorted in ascending order by popping from the stack.
• During the sequence creation, the state of the stack must be output at intermediate steps.

Input Example

5
    3
    2
    4
    1

Output Example

1
    2
    3
    4
    5

Solution Process

To solve this problem, we need to utilize the LIFO (Last-In-First-Out) characteristic of the stack.
By using the fundamental operations of the stack, push and pop, we should be able to create a sequence sorted in ascending order from the given numbers.

Step 1: Problem Analysis

To solve the problem, we must first push the given natural numbers onto the stack and appropriately pop them to output the required sequence.
Specifically, we need to consider how to manipulate the stack to sequentially output the smallest number first.
In other words, while pushing numbers onto the stack, we should compare the top number of the stack with the number we need to output later and pop appropriately.

Step 2: Algorithm Design

The following algorithm describes the step-by-step process to output the given sequence in ascending order using a stack.

1. Read the natural numbers sequentially.
2. Add the read number to the stack.
3. Check the current minimum value, and if the top number of the stack equals this minimum value, perform a pop operation and output it.
4. Repeat the above process until all input numbers are processed.

Step 3: JavaScript Code Implementation

function createSortedSequence(arr) {
        // Initialize Stack
        const stack = [];
        const result = [];
        
        // Initialize the next number to be output
        let next = 1;
        
        // Iterate through the given array
        for (let i = 0; i < arr.length; i++) {
            // Push the current number onto the stack
            stack.push(arr[i]);

            // If the top number of the stack equals next, pop it
            while (stack.length > 0 && stack[stack.length - 1] === next) {
                result.push(stack.pop());
                next++;
            }
        }
        
        // Return the result
        return result;
    }
    
    const inputArray = [3, 2, 4, 1, 5];
    console.log(createSortedSequence(inputArray));

Step 4: Code Explanation

In the above code, the createSortedSequence function takes an array containing natural numbers as input.
It initializes a stack and uses a next variable to determine which number should be output.
Then, it pushes the given array of numbers onto the stack and compares the top number of the stack with next.
If they match, it pops the number and adds it to the result array. This process continues to obtain an array sorted in ascending order.

Step 5: Test Results

When the code is executed, the following result is produced.

    [1, 2, 3, 4, 5]
    

Step 6: Conclusion

Through this problem, we gained a basic understanding of how to use stacks and learned how to utilize the properties of stacks to sort the given numbers.
Moreover, we were able to systematically carry out the entire process from problem interpretation to algorithm design, code implementation, and testing.
Solving such problems is not only useful for preparing for algorithm interviews but also in real applications.

Additional Learning Resources

To gain a deeper understanding of stack structures, we recommend referring to the following materials:

• JavaScript Array – MDN Documentation
• Stack (Abstract Data Type) – Wikipedia

Frequently Asked Questions

Q: Is it possible to solve this problem without using a stack?
A: Since the problem requires the use of the properties of stacks, it cannot be solved without using a stack.

Q: Could there be performance issues if the input is a very large array?
A: This algorithm operates with O(n) time complexity, so it works efficiently. However, memory usage may increase depending on the size of the array.

Problem Description

There is a given undirected graph. The graph consists of nodes and edges,
and each edge has a weight. Let’s solve the problem of finding the shortest path from the starting node
to all other nodes. This algorithm can be solved using Dijkstra’s algorithm.

Problem Definition

Let’s assume the graph below. The number of nodes is n, and the number of edges is e.

    Input
    n = 6
    e = 9
    edges = [
        [1, 2, 1],
        [1, 3, 4],
        [2, 3, 2],
        [2, 4, 5],
        [3, 4, 1],
        [4, 5, 3],
        [3, 5, 6],
        [5, 6, 2],
        [4, 6, 1]
    ]
    start = 1
    

Write a function that finds the shortest path from the start node (node 1) to other nodes in the given graph.
The function should return an array of the minimum distances to each node.

Algorithm Overview

Dijkstra’s algorithm is used to find the shortest path from a given node to all other nodes in graph theory.
This algorithm efficiently finds the shortest path using a priority queue. The following steps are followed
in the actual implementation.

1. Initialize the shortest distance array for each node. Set the initial value to infinity, but set the distance of the starting node to 0.
2. Add the starting node to the priority queue (min-heap).
3. Repeat while the queue is not empty.
4. Extract the node with the shortest distance from the queue and update the distances for its adjacent nodes. If the new distance is smaller than the existing distance, add it to the priority queue.
5. Return the array after calculating the shortest distances for all nodes.

JavaScript Implementation

Now, let’s implement a JavaScript function that solves the above problem based on the algorithm.

    function dijkstra(n, edges, start) {
        // 1. Construct the graph
        const graph = Array.from({ length: n + 1 }, () => []);
        for (const [u, v, weight] of edges) {
            graph[u].push({ node: v, weight });
            graph[v].push({ node: u, weight }); // undirected
        }

        // 2. Initialize shortest distance
        const distance = Array(n + 1).fill(Infinity);
        distance[start] = 0;

        // 3. Initialize the priority queue
        const pq = new MinHeap();
        pq.insert({ node: start, weight: 0 });

        while (!pq.isEmpty()) {
            const { node: currentNode, weight: currentWeight } = pq.extractMin();

            if (currentWeight > distance[currentNode]) continue;

            // 4. Process adjacent nodes
            for (const { node: neighbor, weight } of graph[currentNode]) {
                const newDistance = currentWeight + weight;
                if (newDistance < distance[neighbor]) {
                    distance[neighbor] = newDistance;
                    pq.insert({ node: neighbor, weight: newDistance });
                }
            }
        }

        return distance.slice(1); // Return distance array excluding the start node
    }

    // Min-heap class (priority queue implementation)
    class MinHeap {
        constructor() {
            this.heap = [];
        }

        insert({ node, weight }) {
            this.heap.push({ node, weight });
            this.bubbleUp();
        }

        bubbleUp() {
            let index = this.heap.length - 1;
            while (index > 0) {
                let parentIndex = Math.floor((index - 1) / 2);
                if (this.heap[index].weight >= this.heap[parentIndex].weight) break;
                [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
                index = parentIndex;
            }
        }

        extractMin() {
            if (this.heap.length === 1) return this.heap.pop();
            const min = this.heap[0];
            this.heap[0] = this.heap.pop();
            this.bubbleDown();
            return min;
        }

        bubbleDown() {
            let index = 0;
            const length = this.heap.length;
            const element = this.heap[0];

            while (true) {
                let leftChildIndex = 2 * index + 1;
                let rightChildIndex = 2 * index + 2;
                let leftChild, rightChild;
                let swap = null;

                if (leftChildIndex < length) {
                    leftChild = this.heap[leftChildIndex];
                    if (leftChild.weight < element.weight) {
                        swap = leftChildIndex;
                    }
                }

                if (rightChildIndex < length) {
                    rightChild = this.heap[rightChildIndex];
                    if (
                        (swap === null && rightChild.weight < element.weight) ||
                        (swap !== null && rightChild.weight < leftChild.weight)
                    ) {
                        swap = rightChildIndex;
                    }
                }

                if (swap === null) break;
                this.heap[index] = this.heap[swap];
                index = swap;
            }

            this.heap[index] = element;
        }

        isEmpty() {
            return this.heap.length === 0;
        }
    }
    

Test

To test the above code, you can call the function as follows to check the result.

    const n = 6;
    const edges = [
        [1, 2, 1],
        [1, 3, 4],
        [2, 3, 2],
        [2, 4, 5],
        [3, 4, 1],
        [4, 5, 3],
        [3, 5, 6],
        [5, 6, 2],
        [4, 6, 1]
    ];
    const start = 1;
    const distances = dijkstra(n, edges, start);
    console.log(distances); // [0, 1, 3, 4, 6, 7]
    

Conclusion

Dijkstra's algorithm is a very useful algorithm for finding the shortest path. Through the problems and code discussed in this tutorial,
I hope you gained an understanding of the basic concepts of Dijkstra's algorithm and its implementation in JavaScript. A deeper understanding of algorithms will help enhance your coding test skills and problem-solving abilities.

Continue to study and practice various algorithms!

Problem Description

Write a program that sorts a given integer array in ascending order. The elements of the array may include positive integers, negative integers, and zero. You must implement this using the basic sorting algorithm known as bubble sort.

Explanation of Bubble Sort Algorithm

Bubble sort is one of the simplest sorting algorithms, which sorts by comparing adjacent elements. This algorithm repeatedly traverses the array and compares two adjacent elements, swapping them if necessary. After traversing the array n times, the sorting is complete. In each iteration, the largest element bubbles up to the end of the array, hence the name ‘bubble sort.’

Working Process of Bubble Sort

1. Let the length of the array be n, and perform n-1 iterations.
2. In each iteration, traverse and compare the index i from 0 to n-1.
3. Compare two adjacent elements, and if the left element is greater than the right element, swap them.
4. This process consistently moves the maximum value to the end of the array.
5. Repeat this process until sorting is complete.

Problem Solving Process

Step 1: Declare the Array

First, declare the array to be sorted. For example, we will use an array like the following.

let arr = [64, 34, 25, 12, 22, 11, 90];

Step 2: Write the Bubble Sort Function

Write a function named bubbleSort that implements bubble sort. This function takes an array as a parameter and returns the sorted array.

function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}
    

Step 3: Call the Function and Output the Result

Call the function you wrote to check the result. The function can be called as follows, and the result is printed out.

let sortedArr = bubbleSort(arr);
console.log("Sorted Array:", sortedArr);
    

Complete Code Combination

The final code, combining all the processes, is as follows.

function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

let arr = [64, 34, 25, 12, 22, 11, 90];
let sortedArr = bubbleSort(arr);
console.log("Sorted Array:", sortedArr);
    

Performance Analysis

The time complexity of bubble sort in the worst case is O(n²). This occurs because every element must be compared at least once. The average case also remains O(n²), and the best case (already sorted array) is O(n). Therefore, bubble sort can be efficient for small datasets, but it is not suitable for large data sets.

Conclusion

In this lesson, we learned how to sort an array using bubble sort. Although it’s a simple algorithm, one must be aware that repeatedly performing the same task can lead to performance degradation. Understanding such basic algorithms will serve as an important foundation when encountering more complex algorithms. In the next lesson, we will cover a more efficient sorting algorithm known as Quick Sort.

Problem Description

The bridge building problem is as follows. The given citizens want to build a bridge from ‘A’ to ‘B’.
This bridge will serve as a road connecting the two points ‘A’ and ‘B’ directly. Each citizen can choose several points to build the bridge,
and the distance between each point is predetermined. The problem is to find the length of the shortest bridge connecting the two points in the city.

Problem Input

– The first line contains the number of points n (1 ≤ n ≤ 1000).
– The second line contains an integer array positions representing the location of each point.

Problem Output

Output the minimum length required to build the bridge.

Example Input

    5
    1 2 4 5 10
    

Example Output

    9
    

Solution Process

The first step to solving this problem is to sort the positions of the given points.
The first point in the sorted list represents the location of ‘A’, and the last point represents the location of ‘B’.
This way, it will be easy to calculate the total distance that needs to be traveled to build the bridge.

Step 1: Input and Sorting

function buildBridge(positions) {
    // Sort the positions
    positions.sort((a, b) => a - b);
    return positions;
}
    

Step 2: Distance Calculation

The next step is to calculate the distance between the first and the last point.
This is the most important factor in determining the length of the bridge.

function calculateBridgeLength(positions) {
    const firstPoint = positions[0];
    const lastPoint = positions[positions.length - 1];
    return lastPoint - firstPoint;
}
    

Step 3: Complete Function Implementation

Now, finally, we will integrate the two implemented steps to complete the function that calculates the total length needed to build the bridge.

function buildBridge(positions) {
    // Sort the positions
    positions.sort((a, b) => a - b);
    
    // First and last points
    const firstPoint = positions[0];
    const lastPoint = positions[positions.length - 1];
    
    // Calculate bridge length
    return lastPoint - firstPoint;
}

// Example usage
const inputPositions = [1, 2, 4, 5, 10];
const bridgeLength = buildBridge(inputPositions);
console.log(bridgeLength);  // 9
    

Conclusion

Through this lecture, we practiced how to approach the given problem.
By organizing basic arrays and calculating lengths, we were able to obtain the desired output from the provided input.
This methodology is very useful for solving other algorithmic problems.
Try out more challenging problems in the future!

Future Learning References

• Basic Data Structures and Algorithms: here
• Solve Algorithm Problems Using JavaScript: here
• Coding Test Preparation: here

Hello, everyone! Today, we will solve one of the coding test problems using JavaScript, which is the “Finding Non-Perfect Squares” problem. This problem is commonly encountered in developer interviews and requires an understanding of basic algorithmic thinking and the fundamental syntax of JavaScript.

Problem Description

Write a function that filters out and returns only the non-perfect square numbers from a given array of numbers.

A perfect square refers to a number that can be expressed as n*n for some integer n. For example, 1, 4, 9, 16, and 25 are, respectively, the squares of 1, 2, 3, 4, and 5.

Input and Output

• Input: An array of integers (e.g., [1, 2, 3, 4, 5, 6])
• Output: An array composed of non-perfect square numbers (e.g., [2, 3, 5, 6])

Examples

Input: [1, 2, 3, 4, 5, 6]
Output: [2, 3, 5, 6]

Input: [9, 10, 11, 12, 13, 14]
Output: [10, 11, 12, 13, 14]

Problem Solving Process

Step 1: Understand the Problem

First, let’s clarify the requirements to understand the problem. We will receive an array of integers and need to find the numbers that are not perfect squares from this array. To determine if a number is a perfect square, we can calculate the square root of each number and check whether it is an integer.

Step 2: Analyze the Examples

Let’s check which numbers are perfect squares using the given examples. For instance, in the array [1, 2, 3, 4, 5, 6], the perfect squares are 1 and 4. The remaining numbers 2, 3, 5, 6 are not perfect squares and should be included in the result array.

Step 3: Think of a Solution

We can use the following method to solve the problem:

1. Iterate through each number and check if it is a perfect square.
2. If a number exists such that n*n equals the integer n, then that number is a perfect square.
3. Add the non-perfect square numbers to a new array.
4. Finally, return the new array.

Step 4: Implement the Code

Based on the methods discussed above, let’s write the JavaScript code.

function isPerfectSquare(num) {
    const sqrt = Math.sqrt(num);
    return sqrt === Math.floor(sqrt);
}

function findNonPerfectSquares(arr) {
    return arr.filter(num => !isPerfectSquare(num));
}

// Example tests
console.log(findNonPerfectSquares([1, 2, 3, 4, 5, 6])); // [2, 3, 5, 6]
console.log(findNonPerfectSquares([9, 10, 11, 12, 13, 14])); // [10, 11, 12, 13, 14]

Step 5: Explain the Code

In the code above, we defined two functions:

• isPerfectSquare(num): This function checks whether the given number is a perfect square. It computes the square root and compares it with the original number after removing the decimal part.
• findNonPerfectSquares(arr): This function filters out the non-perfect square numbers from the given array and returns them as a new array. It uses the Array.filter() method to find the non-perfect squares.

Step 6: Consider Performance

The time complexity of this code is O(n). Since we check each element of the array once, the performance depends linearly on the length of the array in the worst case. This algorithm is efficient enough and should perform well in real-world problems.

Step 7: Handle Various Test Cases

Finally, let’s utilize additional test cases to solve this problem:

• Edge case: What should be the output for an empty array []? – It should return an empty array [].
• Including negative numbers: For [-1, -4, 3, 8], the non-perfect squares are -1, 3, 8.
• Changing array: For [0, 1, 2, 3, 16, 25], the non-perfect squares are [2, 3].

Conclusion

Today, we solved the “Finding Non-Perfect Squares” problem. Through this problem, we gained an understanding of basic array processing and the mathematical concept of perfect squares. We learned how to solve problems using the fundamental syntax of JavaScript and array methods.

While preparing for coding tests, it is essential to practice various types of problems. By solving multiple problems, you can establish a fundamental understanding of algorithms and improve your problem-solving skills. In the next lesson, we will tackle even more interesting problems!

Thank you!