Category: Javascript Coding Test

Problem Description

The Lowest Common Ancestor (LCA) is the problem of finding the most recent ancestor node of two nodes. This problem is very important in tree data structures and is a frequently asked topic in coding tests and interviews. In this course, we will cover how to find the LCA using JavaScript and examine the process of solving actual algorithm problems.

Problem Definition

Given a binary tree and two nodes A and B, write a function that finds and returns the lowest common ancestor of the two nodes.

Input Format

• The number of nodes is N, where 1 ≤ N ≤ 10^4.
• Each node has a unique integer ID.
• The IDs of the two nodes A and B are provided.

Output Format

• Returns the ID of the node representing the lowest common ancestor of the two nodes.

Examples

Example 1

        Input: 
        Tree Structure:
              1
            /   \
          2      3
         / \    / \
        4   5  6   7

        A = 4, B = 5
        Output: 2  // Lowest Common Ancestor: 2
    

Example 2

        Input: 
        Tree Structure:
              1
            /   \
          2      3
         / \    / \
        4   5  6   7

        A = 6, B = 7
        Output: 3  // Lowest Common Ancestor: 3
    

Problem Solving Process

1. Define Tree Node Structure

First, we need to define the node structure to represent a binary tree. Each node must have information about at least the parent and child nodes. In JavaScript, we can define the node structure as follows.

    class TreeNode {
        constructor(id) {
            this.id = id;  // Node's ID
            this.left = null;  // Left child node
            this.right = null;  // Right child node
        }
    }
    

2. Create the Tree

Let’s create the example tree from the problem. The code below shows how to construct the tree.

    const root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.right.left = new TreeNode(6);
    root.right.right = new TreeNode(7);
    

3. Find the Lowest Common Ancestor

Now we will implement a function to actually find the LCA. The common method for finding the lowest common ancestor in a binary tree is to traverse the tree recursively and return the node when both nodes A and B are found.

    function findLCA(root, A, B) {
        if (root === null) {
            return null;
        }

        // If the current node is A or B
        if (root.id === A || root.id === B) {
            return root;
        }

        const leftLCA = findLCA(root.left, A, B);
        const rightLCA = findLCA(root.right, A, B);

        // If LCA is found in both children, current node is LCA
        if (leftLCA && rightLCA) {
            return root;
        }
        
        return leftLCA !== null ? leftLCA : rightLCA;
    }
    

4. Test the Function

Now let’s test the LCA function we wrote. You can call the function with the following code to output the result.

    const A = 4;
    const B = 5;
    const lcaNode = findLCA(root, A, B);

    console.log(`Lowest Common Ancestor: ${lcaNode.id}`);  // Output: Lowest Common Ancestor: 2
    

Complexity Analysis

The time complexity of this algorithm is O(N), where N is the number of nodes. This is because we need to visit every node once. The space complexity is O(H), where H is the height of the tree. In the worst case, H can be close to N (when the tree is skewed).

Conclusion

In this course, we learned in detail about how to find the lowest common ancestor using JavaScript. This concept is a fundamental basis for solving various tree-related problems and will help in understanding tree traversal algorithms. Since it is frequently asked in coding tests and interviews, make sure to master it. In the next course, we will cover other tree-related problems, so stay tuned!

In this course, we will cover how to solve JavaScript coding test problems. The topic of the problem is to find the minimum value among prime and palindromic numbers. We will guide you through the problem-solving process step by step, along with the necessary algorithms.

Problem Definition

We have a given integer N. We need to find the minimum value among all numbers that are both prime and palindromic from 1 to N. If such a number does not exist, return -1.

Example Problems

• Input: N = 31
  Output: 3 (Among the primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, the palindromic number is 3)
• Input: N = 11
  Output: 11 (The prime number 11 is a palindromic number)
• Input: N = 1
  Output: -1 (1 is neither a prime nor a palindromic number)

Problem Solving Approach

To solve the problem, we will use the following methods.

1. Find prime numbers from 1 to N.
2. Filter the prime numbers to find those that are palindromic.
3. Find the minimum value among the palindromic numbers.

Step-by-Step Implementation

Step 1: Finding Prime Numbers

To find prime numbers, we can use a simple Sieve of Eratosthenes algorithm. This algorithm is an efficient way to find prime numbers with a time complexity of O(n log log n).

function findPrimes(n) {
        const isPrime = Array(n + 1).fill(true);
        isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime numbers.
        
        for (let i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (let j = i * i; j <= n; j += i) {
                    isPrime[j] = false; // Exclude multiples of i from primes
                }
            }
        }
        
        const primes = [];
        for (let i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.push(i);
            }
        }
        return primes;
    }

Step 2: Finding Palindromic Numbers

A palindromic number is an integer that reads the same forwards and backwards. For example, 121 and 1331 are palindromic numbers.

function isPalindrome(num) {
        const str = num.toString();
        return str === str.split('').reverse().join('');
    }

Step 3: Finding the Minimum Value

Now we gather the numbers that are both prime and palindromic and find the minimum value among them.

function findMinPalindromicPrime(n) {
        const primes = findPrimes(n);
        const palindromicPrimes = primes.filter(isPalindrome);
        
        return palindromicPrimes.length > 0 ? Math.min(...palindromicPrimes) : -1;
    }

Complete Code

Now let's look at the final code that combines all the steps.

function isPalindrome(num) {
        const str = num.toString();
        return str === str.split('').reverse().join('');
    }

    function findPrimes(n) {
        const isPrime = Array(n + 1).fill(true);
        isPrime[0] = isPrime[1] = false;

        for (let i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (let j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        const primes = [];
        for (let i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.push(i);
            }
        }
        return primes;
    }

    function findMinPalindromicPrime(n) {
        const primes = findPrimes(n);
        const palindromicPrimes = primes.filter(isPalindrome);
        
        return palindromicPrimes.length > 0 ? Math.min(...palindromicPrimes) : -1;
    }

    // Example usage
    console.log(findMinPalindromicPrime(31)); // Output: 3
    console.log(findMinPalindromicPrime(11)); // Output: 11
    console.log(findMinPalindromicPrime(1));  // Output: -1

Conclusion

In this course, we implemented an algorithm to solve the problem of finding the minimum value among prime and palindromic numbers. We explored the process of efficiently finding prime numbers using the Sieve of Eratosthenes, checking for palindromic numbers, and ultimately finding the minimum value that meets the criteria. To tackle such problems, both algorithmic thinking and programming skills are essential. I hope you continue to enhance your skills through various coding challenges.

1. Problem Definition

The Least Common Multiple (LCM) refers to the smallest common multiple among the multiples of two or more integers.
For example, the least common multiple of 4 and 5 is 20. This is because 20 is the smallest number shared among the multiples of 4 (4, 8, 12, 16, 20, …) and the multiples of 5 (5, 10, 15, 20, …). In this course, we will solve the problem of finding the least common multiple of two given numbers using JavaScript.

2. Problem Description

Write a function that takes two integers as input and returns their least common multiple.
Function Signature: function lcm(a: number, b: number): number

Input:

• Two integers a, b (1 ≤ a, b ≤ 10⁶)

Output:

• The least common multiple of a and b

Examples:

• Input: 4, 5 => Output: 20
• Input: 15, 20 => Output: 60
• Input: 7, 5 => Output: 35

3. Algorithm Approach

There are several ways to find the least common multiple. However, one of the most common methods is using the Greatest Common Divisor (GCD).
The least common multiple can be calculated using the following formula:

LCM(a, b) = (a * b) / GCD(a, b)

One efficient algorithm to find GCD is the Euclidean algorithm.
The Euclidean algorithm calculates the GCD of two integers as follows:

1. Let r be the remainder when a is divided by b; then, GCD(a, b) = GCD(b, r) holds true.
2. When r is 0, b is the GCD.

Now, let’s implement a function in JavaScript to find LCM based on this logic.

4. Code Implementation

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function lcm(a, b) {
    return (a * b) / gcd(a, b);
}

// Test cases
console.log(lcm(4, 5));  // 20
console.log(lcm(15, 20)); // 60
console.log(lcm(7, 5));   // 35
        

The above code is implemented to calculate GCD and use it to find LCM. The gcd function returns the GCD of a and b. The lcm function calculates and returns the LCM of the two numbers.

5. Code Explanation

gcd function:

• This function takes two integers as arguments and calculates the GCD.
• It uses a while loop to repeat until b is 0.
• In each iteration, it finds the remainder of a divided by b, assigns b to a, and the remainder to b.
• When b becomes 0, the value of a contains the GCD, which is returned.

lcm function:

• This function takes two integers as arguments and calculates the LCM.
• It calls GCD(a, b) to find the GCD and then calculates and returns LCM(a, b).

6. Optimization & Considerations

The above algorithm is efficient. GCD has a time complexity of O(log(min(a, b))), so the time needed for LCM calculation is also minimized.
However, the following considerations should also be taken into account:

• Handling negative numbers: While the problem restricts the range of integers to 1 and above, it may be beneficial to add exception handling to account for negatives in actual use.
• Handling maximum values: The product of a and b can become very large, potentially leading to overflow during calculation. In such cases, it is necessary to consider methods that can handle large numbers, like BigInt.

7. Conclusion

In this course, we studied the algorithm to find the least common multiple of two integers. We learned how to efficiently calculate GCD using the Euclidean algorithm and then use it to calculate LCM.
Such algorithms can be practically useful in various problems. In the next course, we will cover another algorithmic topic. Thank you.

Problem Description

A prime number is a natural number that has no divisors other than 1 and itself. For example, 2, 3, 5, 7, 11, and 13 are prime numbers. In this problem, you need to find curious primes. Curious primes refer to primes determined by certain criteria.

Problem Definition

For a given integer N, return an array containing all the curious primes that are smaller than N. Curious primes are defined by the following criteria:

1. A curious prime must be a natural number greater than or equal to 2.
2. If the sum of the digits of the prime exceeds 10, it is not a curious prime.
3. The number of odd digits must be greater than the number of even digits.
4. Each digit must be an integer and cannot include negative numbers.

Input and Output Format

Input: A positive integer N (2 ≤ N ≤ 10,000)
Output: An array of integers (curious primes)

Solution Process

Step 1: Implement Prime Checking Function

Implement a function that checks if a number is prime. This function should verify whether the input number is prime by checking for factors from 2 up to the square root of the number.

function isPrime(num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 === 0 || num % 3 === 0) return false;

        for (let i = 5; i * i <= num; i += 6) {
            if (num % i === 0 || num % (i + 2) === 0) return false;
        }
        return true;
    }

Step 2: Implement Curious Prime Checking Function

Implement a function to check for curious primes. This function should include functionalities to calculate the sum of the digits and count the digits.

function isCuriousPrime(num) {
        if (!isPrime(num)) return false;

        const digits = num.toString().split('').map(Number);
        const sumOfDigits = digits.reduce((acc, digit) => acc + digit, 0);
        const oddCount = digits.filter(digit => digit % 2 !== 0).length;
        const evenCount = digits.filter(digit => digit % 2 === 0).length;

        return sumOfDigits <= 10 && oddCount > evenCount;
    }

Step 3: Implement Result Generation Function

Now, create the main function findCuriousPrimes that will find all curious primes smaller than the given N.

function findCuriousPrimes(N) {
        const curiousPrimes = [];
        for (let i = 2; i < N; i++) {
            if (isCuriousPrime(i)) {
                curiousPrimes.push(i);
            }
        }
        return curiousPrimes;
    }

Step 4: Complete Code and Example Execution

Combine the functions created above to complete the full code. Below is the final code example.

function isPrime(num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 === 0 || num % 3 === 0) return false;

        for (let i = 5; i * i <= num; i += 6) {
            if (num % i === 0 || num % (i + 2) === 0) return false;
        }
        return true;
    }

    function isCuriousPrime(num) {
        if (!isPrime(num)) return false;

        const digits = num.toString().split('').map(Number);
        const sumOfDigits = digits.reduce((acc, digit) => acc + digit, 0);
        const oddCount = digits.filter(digit => digit % 2 !== 0).length;
        const evenCount = digits.filter(digit => digit % 2 === 0).length;

        return sumOfDigits <= 10 && oddCount > evenCount;
    }

    function findCuriousPrimes(N) {
        const curiousPrimes = [];
        for (let i = 2; i < N; i++) {
            if (isCuriousPrime(i)) {
                curiousPrimes.push(i);
            }
        }
        return curiousPrimes;
    }

    console.log(findCuriousPrimes(50));  // Example Output: [3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47]
    

Optimization Plan

The current algorithm has a time complexity proportional to N, and there is room for improvement. You can optimize by calculating primes in advance and storing them in an array, then using this array to find curious primes.

Conclusion

This article discussed methods for finding curious primes in JavaScript. The algorithm was explained step by step, and the final code was included. By solving this problem, one can deepen their understanding of conditional statements, loops, and array manipulation in JavaScript.

References and Links

• Prime Numbers – Wikipedia
• JavaScript Guide – MDN