Category: Javascript Coding Test

Coding tests are a very important element in modern software development. Companies issue various algorithm problems to evaluate developers’ problem-solving abilities. Today, we will address the problem of finding the Kth smallest number in an array. This problem is a good example to build basic algorithm skills in handling arrays.

Problem Description

Given an array arr and an integer k, find and return the Kth smallest number in arr. The array index starts from 0.

Input

• Integer array arr, length between 1 and 100,000.
• Integer k, between 1 and the length of the array.

Output

Return the Kth smallest number from arr.

Example

Solution Process

This problem can be easily solved by sorting the array first and then finding the Kth element, but the time complexity may vary depending on the sorting method. Here, we will explore two approaches.

Method 1: Sorting the array and finding the Kth number

1. Sort the array in ascending order.
2. Return the value at index k - 1 to find the Kth number.

JavaScript Code Example

function findKthNumber(arr, k) {
    arr.sort((a, b) => a - b); // Sort the array in ascending order
    return arr[k - 1]; // Return Kth number
}

// Example execution
console.log(findKthNumber([3, 1, 2, 4, 5], 2)); // 2
console.log(findKthNumber([7, 10, 4, 3, 20, 15], 3)); // 7

In the code above, we simply sorted the array and found the Kth element. The time complexity of this method is O(n log n). However, there is a way to find the Kth smallest number without necessarily sorting.

Method 2: Quickselect Algorithm

The Quickselect algorithm is a method to find the Kth smallest number in a way similar to Quicksort. This method has an average time complexity of O(n). This algorithm is performed by setting up a subarray and choosing a pivot.

1. Select a pivot element from the array.
2. Place values smaller than the pivot on the left and larger values on the right.
3. If the pivot’s position is the same as the position of the Kth number, return the pivot.
4. If not, perform Quickselect recursively in the appropriate subarray based on whether the Kth number is in the left or right subarray.

JavaScript Code Example

function quickSelect(arr, left, right, k) {
    if (left === right) {
        return arr[left]; // If there is only one element in the array
    }
    const pivotIndex = partition(arr, left, right);
    if (k === pivotIndex) {
        return arr[k]; // Kth number found
    } else if (k < pivotIndex) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k);
    }
}

function partition(arr, left, right) {
    const pivot = arr[right]; // Select the last element as the pivot
    let i = left; 
    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap
            i++;
        }
    }
    [arr[i], arr[right]] = [arr[right], arr[i]]; // Final position of the pivot
    return i; // Return the index of the pivot
}

function findKthNumber(arr, k) {
    return quickSelect(arr, 0, arr.length - 1, k - 1); // Pass K-1 as the argument
}

// Example execution
console.log(findKthNumber([3, 1, 2, 4, 5], 2)); // 2
console.log(findKthNumber([7, 10, 4, 3, 20, 15], 3)); // 7

With the above code, we can efficiently find the Kth number using the Quickselect algorithm. This method is particularly useful for large datasets due to its average time complexity of O(n).

Conclusion

In this lecture, we explored the problem of finding the Kth number in an array, which is frequently covered in JavaScript coding tests. Although the problem can be solved simply with sorting, we can maximize performance by using efficient methods like Quickselect. Such knowledge can be very useful in actual coding tests, so I highly recommend practicing it.

All algorithms require a basic understanding followed by developing applicability through various problems. In the next lecture, we will cover more diverse array problems and advanced algorithms. Thank you!

In this article, we will address the algorithm problem of finding the Catalan numbers using JavaScript. Catalan numbers are related to mathematical concepts such as structural concepts like nested parentheses, and this problem often appears in programming interviews. Therefore, we will explore a way to thoroughly understand and solve this problem.

What are Catalan numbers?

Catalan numbers are strings of length N composed of 0s and 1s that follow the following rules:

• The first and last characters of the string must be 0.
• The number of 1s in the string must always be at least 1, there cannot be consecutive 1s, and each 1 must be surrounded by 0s.

For example, the Catalan numbers of length 5 include 00000, 01000, 00100, 00010, 00001,
01010, 01100, 10000, etc. Catalan numbers are similar to the Fibonacci sequence, and
they can take different counts depending on the length N.

Problem Description

Given a natural number N, the problem is to output the count of Catalan numbers of length N.
For example, when N = 5, we need to find the number of Catalan numbers,
and the result should be 8.

Solution

To find the Catalan numbers, we can use recursive calls or dynamic programming (DP) methods.
Below is the formula for computing the Catalan numbers.

• p(n) = p(n-1) + p(n-2) (n ≥ 2, p(0) = 1, p(1) = 1)

This formula recursively computes the Catalan numbers.
It is important to note that it should return 1 when n is 0.
Moreover, the relationship between p(n-1) and p(n-2) refers to the counts of previous Catalan numbers.

Algorithm Implementation

        
            // Function to calculate Catalan numbers in JavaScript.
            function countCatalanNumbers(n) {
                // Array to store Catalan numbers
                const dp = new Array(n + 1).fill(0);
                dp[0] = 1; // Case for length 0
                dp[1] = 1; // Case for length 1

                // Using dynamic programming to calculate the Catalan numbers.
                for (let i = 2; i <= n; i++) {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }

                return dp[n]; // Return the count of Catalan numbers of length n.
            }

            // Example of function call
            const n = 5; // Value of N
            console.log(`The number of Catalan numbers of length ${n} is: ${countCatalanNumbers(n)}`);
        
        

Process Explanation

1. Understanding the Problem: This is a problem to find the Catalan numbers for a natural number N.
2. Dynamic Programming Approach: We define the Catalan numbers structurally.
3. Array Initialization: Create the dp array and set the base values.
4. Executing the Loop: Calculate and store the count of Catalan numbers in the array.
5. Verifying the Result: Validate that the output of the function is correct.

Execution Result

        
            // Input: N = 5
            // Output: The number of Catalan numbers of length 5 is: 8
        
    

Conclusion

We have learned how to find the Catalan numbers and have been able to efficiently solve the problem through dynamic programming.
This problem frequently appears in programming interviews, so it is important to develop the ability to understand and implement the principles of the algorithm.