Category: Javascript Coding Test

Hello, everyone! Today, we will learn about one of the important algorithms in coding tests using JavaScript, the Extended Euclidean Algorithm. In this course, we will provide the concept of the Extended Euclidean Algorithm, the problem-solving process using it, and practical code examples.

1. Problem Description

We will define the problem as follows. Given two integers A and B, the task is to find integers X and Y that satisfy AX + BY = GCD(A, B). Here, GCD refers to the greatest common divisor.

Example

Input: A = 30, B = 21

Output: X = 1, Y = -1, GCD = 3

Solution: 30 * 1 + 21 * (-1) = 3

2. Concept Explanation

The Extended Euclidean Algorithm not only calculates the greatest common divisor (GCD) of two integers but also finds specific coefficients from it. This is primarily used in the following formula:

AX + BY = GCD(A, B)

Here, A and B are the given two integers, and X and Y are the integers we want to find. If the GCD is 1, A and B are coprime, and X and Y can also be used to find modular inverses.

3. Approach

We will implement the Extended Euclidean Algorithm based on the general Euclidean algorithm for finding GCD. The main idea of the algorithm is as follows:

1. Receive two integers A and B as input.
2. If B is 0, then the GCD is A, and X is 1, Y is 0.
3. Otherwise, recursively call with B and A % B using the Euclidean algorithm.
4. Use the results of the recursive call to calculate the values of X and Y.

4. Algorithm Implementation

Below is an example of implementing the Extended Euclidean Algorithm in JavaScript:

function extendedGCD(a, b) {
    if (b === 0) { // Base case
        return { gcd: a, x: 1, y: 0 };
    }
    // Recur with the new parameters b and a % b
    const { gcd, x: x1, y: y1 } = extendedGCD(b, a % b);
    const x = y1;
    const y = x1 - Math.floor(a / b) * y1;
    return { gcd, x, y };
}

// Test the function with example values
const a = 30;
const b = 21;
const { gcd, x, y } = extendedGCD(a, b);
console.log(`GCD: ${gcd}, X: ${x}, Y: ${y}`);

5. Code Explanation

In the above code, we are recursively calculating the GCD. In the base case, when B is 0, the GCD is A, and at that point, X is 1, Y is 0. After that, we calculate new values for X and Y using the returned X and Y values to ultimately get the result we desire.

6. Test Cases

Now let’s test the function with various test cases.

// Test cases
const testCases = [
    { a: 30, b: 21 },
    { a: 48, b: 18 },
    { a: 56, b: 15 },
    { a: 101, b: 10 },
];

testCases.forEach(({ a, b }) => {
    const { gcd, x, y } = extendedGCD(a, b);
    console.log(`A: ${a}, B: ${b} => GCD: ${gcd}, X: ${x}, Y: ${y}`);
});

7. Conclusion

Today, we learned about the Extended Euclidean Algorithm. This algorithm is very useful for finding the greatest common divisor of two integers and for finding specific coefficients related to it. It is especially used in modular arithmetic and complex algorithm problems, so it is important to understand and practice it thoroughly.

I hope the algorithm used in this article will help you in your coding exam preparations. If you have any additional questions, please leave them in the comments!

Problem Description

Solution Method

This problem requires efficiently calculating range sums and processing updates, so we can use a Segment Tree.
A Segment Tree is a binary tree-based data structure that stores the given array in intervals (for range sum queries).

Definition of Segment Tree

A Segment Tree has the following properties:

• Each node stores information about one array interval. This information can be set as the sum, minimum, maximum, etc. of the interval.
• The height of the tree is O(log n), meaning that both query and update operations take O(log n) time.

Steps to Implement a Segment Tree

To implement a Segment Tree, follow these steps:

1. Initialization: Initialize the Segment Tree based on the given array.
2. Range Sum Query: Recursively retrieve the nodes necessary to calculate the sum for a specific interval.
3. Update: Update the value at a specific index and refresh the relevant segment nodes.

JavaScript Code Implementation

class SegmentTree {
    constructor(arr) {
        this.n = arr.length;
        this.tree = new Array(this.n * 4);
        this.build(arr, 0, 0, this.n - 1);
    }

    build(arr, node, start, end) {
        if (start === end) {
            // Store integer value at leaf node
            this.tree[node] = arr[start];
        } else {
            const mid = Math.floor((start + end) / 2);
            // Define left child
            this.build(arr, node * 2 + 1, start, mid);
            // Define right child
            this.build(arr, node * 2 + 2, mid + 1, end);
            // Define parent node as the sum of both children
            this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
        }
    }

    rangeSum(left, right) {
        return this.sum(0, 0, this.n - 1, left, right);
    }

    sum(node, start, end, left, right) {
        if (right < start || end < left) {
            // Return 0 if requested range does not overlap
            return 0;
        }
        if (left <= start && end <= right) {
            // Return node if requested range is fully included
            return this.tree[node];
        }
        const mid = Math.floor((start + end) / 2);
        const leftSum = this.sum(node * 2 + 1, start, mid, left, right);
        const rightSum = this.sum(node * 2 + 2, mid + 1, end, left, right);
        return leftSum + rightSum;
    }

    update(index, value) {
        this.updateValue(0, 0, this.n - 1, index, value);
    }

    updateValue(node, start, end, index, value) {
        if (start === end) {
            // Update leaf node
            this.tree[node] = value;
        } else {
            const mid = Math.floor((start + end) / 2);
            if (index <= mid) {
                this.updateValue(node * 2 + 1, start, mid, index, value);
            } else {
                this.updateValue(node * 2 + 2, mid + 1, end, index, value);
            }
            // Update parent node
            this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
        }
    }
}

// Example usage
const arr = [1, 3, 5, 7, 9, 11];
const segmentTree = new SegmentTree(arr);
console.log(segmentTree.rangeSum(1, 3)); // 15
segmentTree.update(1, 10);
console.log(segmentTree.rangeSum(1, 3)); // 22

Conclusion

The Segment Tree is a powerful tool for efficiently handling the range sum of arrays.
This data structure allows for updates and range sum calculations with a time complexity of O(log n).
When faced with complex problems in practice, using a Segment Tree can provide many advantages.

Additional Practice Problems

Try practicing the following problems:

• Use a Segment Tree to find the minimum value in a given array
• Add a query to add a specific value over an interval
• Find the maximum value using a Segment Tree

Problem Introduction

You need to write a program that finds the fastest bus route from point A to point B. There are multiple bus routes, and each route passes through specified stops, with different travel times between stops. The ultimate goal is to find the fastest path from a specific point A to point B and return the travel time for that path.

Problem Description

The given routes are expressed as follows. Each route has travel times between stops, and the stops are represented in the following format:

        [
            {busRoute: "1", stops: [{stop: "A", time: 0}, {stop: "B", time: 5}, {stop: "C", time: 10}]},
            {busRoute: "2", stops: [{stop: "A", time: 0}, {stop: "D", time: 3}, {stop: "B", time: 8}]},
            {busRoute: "3", stops: [{stop: "B", time: 0}, {stop: "C", time: 4}, {stop: "E", time: 6}]},
            {busRoute: "4", stops: [{stop: "D", time: 0}, {stop: "E", time: 2}, {stop: "B", time: 7}]},
        ]
    

Input

The first parameter is an array of bus routes, and the second parameter is point A and point B.

Output

Print the travel time of the fastest route. If there is no route, print -1.

Example

        Input: 
        const routes = [
            {busRoute: "1", stops: [{stop: "A", time: 0}, {stop: "B", time: 5}, {stop: "C", time: 10}]},
            {busRoute: "2", stops: [{stop: "A", time: 0}, {stop: "D", time: 3}, {stop: "B", time: 8}]},
            {busRoute: "3", stops: [{stop: "B", time: 0}, {stop: "C", time: 4}, {stop: "E", time: 6}]},
            {busRoute: "4", stops: [{stop: "D", time: 0}, {stop: "E", time: 2}, {stop: "B", time: 7}]},
        ];
        const start = "A";
        const end = "B";

        Output: 
        5
    

Solution Method

To solve this problem, we can use a graph traversal algorithm. The stops represent nodes, and the travel times between stops represent the weights of the edges between those nodes. Suitable algorithms include BFS (Breadth-First Search) or Dijkstra’s algorithm. In this problem, Dijkstra’s algorithm is more effective because the weights of all edges may differ, necessitating an optimized method to find the shortest path.

Dijkstra’s Algorithm Overview

Dijkstra’s algorithm is used to find the shortest path in a weighted graph, continuously updating the cost of moving from the current node to adjacent nodes while exploring the path to the target node. For this, we use a priority queue to record each stop and its cost.

Code Implementation

        function getFastestBusRoute(routes, start, end) {
            // Priority queue for processing the stops
            const pq = new MinPriorityQueue();
            const distances = {};
            const parents = {};

            // Initialize distances and priority queue
            for (const route of routes) {
                for (const stop of route.stops) {
                    distances[stop.stop] = Infinity;
                    parents[stop.stop] = null;
                }
            }

            // Starting point
            distances[start] = 0;
            pq.enqueue(start, 0);

            while (!pq.isEmpty()) {
                const currentStop = pq.dequeue().element;

                // If we reach the target stop, return the distance
                if (currentStop === end) {
                    return distances[currentStop];
                }

                for (const route of routes) {
                    for (let i = 0; i < route.stops.length - 1; i++) {
                        const stop1 = route.stops[i].stop;
                        const stop2 = route.stops[i + 1].stop;
                        const time = route.stops[i + 1].time - route.stops[i].time;

                        if (stop1 === currentStop) {
                            const newTime = distances[stop1] + time;
                            if (newTime < distances[stop2]) {
                                distances[stop2] = newTime;
                                parents[stop2] = stop1;
                                pq.enqueue(stop2, newTime);
                            }
                        }
                    }
                }
            }
            return -1; // If there's no path to the end
        }

        // Example usage
        const routes = [
            {busRoute: "1", stops: [{stop: "A", time: 0}, {stop: "B", time: 5}, {stop: "C", time: 10}]},
            {busRoute: "2", stops: [{stop: "A", time: 0}, {stop: "D", time: 3}, {stop: "B", time: 8}]},
            {busRoute: "3", stops: [{stop: "B", time: 0}, {stop: "C", time: 4}, {stop: "E", time: 6}]},
            {busRoute: "4", stops: [{stop: "D", time: 0}, {stop: "E", time: 2}, {stop: "B", time: 7}]},
        ];
        const start = "A";
        const end = "B";
        console.log(getFastestBusRoute(routes, start, end)); // Output: 5
    

Conclusion

In this lecture, we learned how to solve the algorithm problem of finding the fastest path based on the given bus route information. Dijkstra's algorithm is a very useful method for finding the shortest path in weighted graphs. I hope you found it helpful to understand how to explore at each step and implement it in code.

Additional Practice Problems

If you've learned Dijkstra's algorithm through this problem, try tackling the following variations:

• A problem where you must find a route using only specific lines
• A problem that finds routes based on travel distance instead of travel time between stops
• A problem that finds the maximum path instead of the minimum path

References

• Dijkstra's Algorithm - Wikipedia
• JavaScript Guide - MDN Web Docs
• Dijkstra's Shortest Path Algorithm - GeeksforGeeks