Category: Javascript Coding Test

Hello, everyone! In this blog post, we will take an in-depth look at the coding test algorithm problem “Taking Out Pebbles” using JavaScript. This problem will greatly help in understanding data structures and algorithms. Now, let’s define the problem.

Problem Definition

There is a bag containing several pebbles. Each pebble is numbered, and you need to extract pebbles that satisfy specific conditions. The pebbles are represented by n numbers, each of which represents the unique ID of that pebble.

Your task is to return the number of pebbles that are smaller than the given integer k when provided with the pebble array rocks and the integer k. The length of the array is from 1 to 1000, and each pebble’s ID is between 1 and 10,000.

For example:

• Input: rocks = [5, 2, 8, 3, 6], k = 4
• Output: 2 (Pebble IDs: 2, 3)

Problem-Solving Strategy

To solve this problem, we will use a basic array search technique. We will follow these steps to arrive at a solution.

1. Array Search

We will traverse the given array rocks and check if each pebble’s ID is smaller than k. If this condition is met, we will increase the count.

2. Return Count

After reviewing all the pebbles, we will finally return the count.

JavaScript Code Implementation

Now, let’s write a JavaScript function based on the above plan:

function countRocks(rocks, k) {
    let count = 0;
    for (let i = 0; i < rocks.length; i++) {
        if (rocks[i] < k) {
            count++;
        }
    }
    return count;
}

// Example usage
const rocks = [5, 2, 8, 3, 6];
const k = 4;
console.log(countRocks(rocks, k)); // Output: 2

Code Analysis

In the above code, the countRocks function takes two parameters: the rocks array and the k value. We initialize the count with let count = 0; and traverse the array using a for loop. If each pebble’s ID is smaller than k, we increase the count. Finally, we return the count.

Time Complexity Analysis

The time complexity for this problem is O(n). Since we check each element in the array only once, it has a linear time complexity.

Conclusion

Through today’s problem, “Taking Out Pebbles,” we laid the foundation of array searching and learned how to design efficient algorithms. Such problems will frequently appear in coding tests, playing a crucial role in building your fundamentals. I hope you also gain experience by solving various problems!

Practice Problem

Now it’s your turn to test your skills. Try to solve the following modified problem.

• Modified Problem: Write a function to count the number of pebbles in the given rocks array that are greater than the value of k.

To solve this problem, you only need to change the condition. Think about what changes are needed in your code!

In this tutorial, we will take a detailed look at how to solve employment-related algorithm problems using JavaScript. This article will address the ‘Find Minimum 2’ problem, explaining the approach to problem-solving, step-by-step processes, and optimization methods.

Problem Description

The following problem involves finding the minimum value that satisfies specific conditions in an array. For the given array, the following conditions apply:

• An array consisting of positive integers is given.
• Only the elements at odd indices of the array should be considered to find the minimum value.
• If a minimum value cannot be found, it should return `null`.

Example of the Problem

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

            Input: [2, 9, 6, 7, 10]
            Output: 9

            Input: [4, 4, 4, 4]
            Output: null
        

Approach to Solve the Problem

To solve this problem, we follow these steps:

1. Extract only the elements at odd indices from the input array.
2. Find the minimum value among the extracted elements.
3. If a minimum value exists, return it; otherwise, return `null`.

Step 1: Extract Odd Index Elements

To extract elements at odd indices, we can use the `filter` method. This method returns an array of elements that satisfy a given condition.

Step 2: Find the Minimum Value

There are several ways to find the minimum value from the array extracted from odd indices. Using the `Math.min` function allows for straightforward minimum value retrieval.

Step 3: Return the Result

After finding the minimum value, we add logic to return it or `null` based on the condition.

Code Implementation for Problem Solving

Now, based on these processes, let’s write JavaScript code to solve the problem. Below is the code that implements the algorithm described above:

            function findMinOddIndex(arr) {
                // Extracting odd index elements
                const oddIndexedElements = arr.filter((_, index) => index % 2 === 1);

                // Return null if there are no odd index elements
                if (oddIndexedElements.length === 0) {
                    return null;
                }

                // Return the minimum value
                return Math.min(...oddIndexedElements);
            }

            // Example tests
            console.log(findMinOddIndex([5, 3, 4, 1, 2, 7, 6])); // 1
            console.log(findMinOddIndex([2, 9, 6, 7, 10])); // 9
            console.log(findMinOddIndex([4, 4, 4, 4])); // null
        

Code Explanation

The above code works as follows:

• The function `findMinOddIndex` takes the input array and filters out the elements corresponding to odd indices.
• If the filtered result is an empty array, meaning there are no elements at odd indices, it returns `null`.
• If not, it calculates and returns the minimum value using `Math.min`.

Testing and Verifying Results

Let’s run various test cases with the code we wrote. We will check the execution results to ensure the correct outcomes are returned.

• Input: [5, 3, 4, 1, 2, 7, 6] → Output: 1
• Input: [2, 9, 6, 7, 10] → Output: 9
• Input: [4, 4, 4, 4] → Output: null
• Input: [] → Output: null
• Input: [0, -1, 3, -5, 4] → Output: -5 (the minimum value among -1 and -5 at odd indices)

Performance Optimization

The performance of the currently implemented code is good, with an average time complexity of O(n). However, if the array size is very large, we can further optimize performance. For example, we can use a single iteration to find the minimum value at odd indices. Below is an example of this implementation:

            function findMinOddIndexOptimized(arr) {
                let min = Infinity;

                for (let i = 1; i < arr.length; i += 2) {
                    if (arr[i] < min) {
                        min = arr[i];
                    }
                }

                return min === Infinity ? null : min;
            }

            // Example tests
            console.log(findMinOddIndexOptimized([5, 3, 4, 1, 2, 7, 6])); // 1
            console.log(findMinOddIndexOptimized([2, 9, 6, 7, 10])); // 9
            console.log(findMinOddIndexOptimized([4, 4, 4, 4])); // null
        

Conclusion

In this tutorial, we learned how to find the minimum value at odd indices in a given array using JavaScript. Clearly understanding the requirements of the problem, and deriving the optimal solution through an efficient algorithm is a crucial skill in coding tests. While filtering and mapping arrays can easily solve problems, optimization with performance in mind is also necessary.

In your practice for upcoming coding tests, I hope you get familiar with solving similar pattern problems repeatedly. Additionally, attempting various variations of problems can help enhance your problem-solving abilities.

In this course, we will take a detailed look at solving algorithm problems using JavaScript and the usage of the Trie data structure. The Trie is a very useful data structure to improve the efficiency of string processing. In this course, we will explain the process of solving specific problems using the Trie.

What is a Trie?

A Trie is a tree-like data structure used to store a large number of strings. Common applications include auto-completion, word search, and prefix search. Each node in the Trie corresponds to a character in the string, allowing for efficient word composition through paths.

Problem: Word Search

Below is a problem utilizing the Trie data structure.

When given a list of words and a search term, find all the words in the list that exist, and return all words that contain the search term.

Problem-Solving Strategy

1. First, implement the Trie structure.
2. Insert the given list of words into the Trie.
3. Use the search term to explore all possible words in the Trie.

Trie Implementation

To implement a Trie, the following basic structure is needed:

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    search(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) return [];
            node = node.children[char];
        }
        return this._findAllWords(node, prefix);
    }

    _findAllWords(node, prefix) {
        const results = [];
        if (node.isEndOfWord) {
            results.push(prefix);
        }
        for (let char in node.children) {
            results.push(...this._findAllWords(node.children[char], prefix + char));
        }
        return results;
    }
}

Inserting and Searching Words

Now, I will explain how to insert words into the Trie and find all possible words for a specific search term. The process will be illustrated through the example below:

const getWords = (words, searchWord) => {
    const trie = new Trie();
    for (let word of words) {
        trie.insert(word);
    }
    return trie.search(searchWord);
};

const wordsList = ["apple", "app", "apricot", "banana", "bat", "ball"];
const searchTerm = "ap";
const foundWords = getWords(wordsList, searchTerm);
console.log(foundWords); // ["apple", "app", "apricot"]

Code Explanation

In the above code, the getWords function first inserts the provided list of words into the Trie, then searches the Trie with the given search term. The insert method takes a word and connects each character as a node, while the search method finds and returns all words corresponding to the given prefix.

Complexity Analysis

The performance of insertion and search in the Trie varies depending on the length of the string and the depth of the tree:

• Insertion: O(L), where L is the length of the word.
• Search: O(P + W), where P is the length of the prefix, and W is the number of words returned as a result.

Conclusion

In this course, we learned how to solve string search problems using the Trie data structure in JavaScript. Tries have the capability to efficiently handle large numbers of words, making them particularly useful for implementing features like auto-completion or word search.

Explore more examples and problems regarding the Trie algorithm to enhance your understanding. Stay tuned for more algorithms and data structures in the next course!

Problem Description

The problem of finding the Longest Increasing Subsequence (LIS) involves finding the longest subsequence within a given sequence while maintaining the order of increasing values. A subsequence does not need to be contiguous, but the chosen numbers must follow an increasing order.

Input Format

• The first line contains an integer N (1 ≤ N ≤ 1,000), which represents the length of the sequence.
• The second line contains N integers A1, A2, …, AN (1 ≤ Ai ≤ 1,000,000).

Output Format

Output the length of the longest increasing subsequence.

Example

Input Example

6
10 20 10 30 20 50

Output Example

4

Problem Solving Process

Step 1: Understand the Problem

To understand the problem, let’s examine the sequence. For the given sequence [10, 20, 10, 30, 20, 50], there are several possible increasing subsequences. Among them, the longest increasing subsequence is [10, 20, 30, 50], which has a length of 4. Therefore, the answer is 4.

Step 2: Choose an Algorithm

There are various algorithms for finding the longest increasing subsequence, but the most efficient method is to use dynamic programming. This method has a time complexity of O(N^2). I will use this method to solve the problem.

Step 3: Dynamic Programming Solution

function LIS(array) {
        const N = array.length;
        const dp = new Array(N).fill(1); // Initialize subsequence lengths to 1

        for (let i = 1; i < N; i++) {
            for (let j = 0; j < i; j++) {
                if (array[i] > array[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        return Math.max(...dp);
    }

    const sequence = [10, 20, 10, 30, 20, 50];
    console.log(LIS(sequence)); // Output: 4
    

Explanation

1. Declare the dp array to store the length of the longest increasing subsequence for each index. The initial value is set to 1 since each element can form a subsequence by itself.

2. Use two loops to compare indices i and j. If array[i] is greater than array[j], the value of dp[i] is updated to the maximum of dp[j] + 1 and the current value of dp[i]. This considers the subsequence that includes array[j] as well as array[i].

3. After all iterations, the largest value in the dp array will be the length of the longest increasing subsequence.

Result

Executing the above code will successfully determine the length of the longest increasing subsequence in the given sequence.

Conclusion

The Longest Increasing Subsequence (LIS) problem is one of the frequently asked algorithm problems. Through this problem, one can learn the basics of dynamic programming and enhance problem-solving skills in real coding tests. It is important to gain experience by solving various problems.

Let’s learn about the essential algorithm for coding tests, Bubble Sort.

1. Problem Definition

Implement the Bubble Sort algorithm that takes an array as input and sorts it in ascending order.
Bubble Sort operates by comparing two adjacent elements and repeatedly moving the largest element to the end of the array.

Input Format

The input is an integer array with a length between 1 and 1000. Each element can have a value between -10,000 and 10,000.

Output Format

Return the array sorted in ascending order.

2. Problem Approach

Bubble Sort is a very intuitive sorting algorithm. The basic approach is to compare two adjacent elements,
and if they are not in order, swap them repeatedly until the entire array is sorted. This process is repeated for the size of the array,
and continues until no more swaps occur. This way, the largest value moves to the end of the array in each step.

2.1. Algorithm Steps

1. Obtain the length of the array.
2. Use two indices to compare the elements of the array.
3. If adjacent elements are not sorted, swap them.
4. Consider the sorting complete if no swaps occur during a full pass.
5. Repeat the above process and ultimately return the array sorted in ascending order.

3. Bubble Sort Code Implementation

Now let’s implement the above algorithm in JavaScript. The basic Bubble Sort function is as follows.

// Bubble Sort function implementation
function bubbleSort(arr) {
    let n = arr.length;  // Store the length of the array

    // Repeat to sort the array
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;  // Variable to check if a swap has occurred

        // Compare and swap adjacent elements
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;  // Record that a swap has occurred
            }
        }

        // Exit if no swaps have occurred
        if (!swapped) break;
    }

    return arr;  // Return the sorted array
}

// Test
let testArray = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(testArray));  // [11, 12, 22, 25, 34, 64, 90]

        

4. Time Complexity Analysis

The time complexity of the Bubble Sort algorithm is O(n²) in the worst case. This is due to the presence of two nested loops, each proportional to the length of the array.
The best case (when the array is already sorted) is O(n). In this case, no swaps occur, and the process terminates after the first step.
Bubble Sort is generally inefficient, and it is advisable to use other algorithms (e.g., Quick Sort, Merge Sort) when sorting large datasets in practice.

4.1. Space Complexity

The space complexity of Bubble Sort is O(1). It does not use any unnecessary additional memory,
as sorting is performed within the given array.

5. Advantages and Disadvantages of Bubble Sort

Advantages

• The algorithm is simple and easy to understand.
• It does not have any specific requirements, so no additional memory management is necessary.
• It works effectively with small datasets.

Disadvantages

• The time complexity is inefficient (O(n²)).
• Even when the array is well sorted, it must perform a complete pass, reducing efficiency.
• It is inefficient for sorting large datasets.

6. Conclusion

In this lecture, we implemented the Bubble Sort algorithm using JavaScript.
Due to its structural simplicity, Bubble Sort is useful for educational purposes, but in real production environments, it is advisable to use more efficient algorithms.
I hope you can further develop your coding skills as you explore more complex algorithms and data structures in the future.

7. References

• Bubble Sort – Wikipedia
• JavaScript Guide – MDN Web Docs
• Bubble Sort – GeeksforGeeks