Category: Javascript Coding Test

One of the problems often presented in coding interviews is the problem of finding the product of a specific range (subarray) of an array. In this course, we will define this as the Range Product Problem and explain how to solve it in detail.

Problem Definition

Given an array A and a list of queries, each query includes a range [L, R], and we need to calculate the product from A[L] to A[R]. Let’s assume the given array A and queries are as follows:

A = [2, 3, 4, 5, 6]
Queries = [(1, 3), (0, 2), (2, 4)] // Indices start from 0

We need to output the result of each query. For example, for the query (1, 3), A[1] * A[2] * A[3] = 3 * 4 * 5 = 60.

Understanding the Problem

To solve this problem, we need to understand a few conditions of the problem:

• Validation of the size of array A and the range (L, R) of each query
• How to quickly calculate the product of the range
• How to address the inefficiency issue of calculating multiple products when each element of the array is given

Solution Strategy

To efficiently calculate the range product, we can utilize the prefix product. This method generates a new array P(A) from the original array A, storing the product from index 0 to index i for each index i. Then the product for a query (L, R) can be calculated as follows.

Range Product Q(L, R) = P(R) / P(L - 1)

Here, P(i) represents the product up to index i, and P(0) is A[0].

Implementation

Now, let’s implement the above strategy in JavaScript:

function productRange(arr, queries) {
    // Array size
    const n = arr.length;

    // Initialize the prefix product array
    const prefixProduct = new Array(n);
    prefixProduct[0] = arr[0];

    // Calculate the prefix product
    for (let i = 1; i < n; i++) {
        prefixProduct[i] = prefixProduct[i - 1] * arr[i];
    }

    // Initialize the result array
    const result = [];

    // Process the queries
    queries.forEach(([L, R]) => {
        if (L === 0) {
            result.push(prefixProduct[R]);
        } else {
            result.push(prefixProduct[R] / prefixProduct[L - 1]);
        }
    });

    return result;
}

// Test
const A = [2, 3, 4, 5, 6];
const queries = [[1, 3], [0, 2], [2, 4]];
console.log(productRange(A, queries)); // Expected result: [60, 24, 120]

Analysis

The time complexity of the above code is O(N + Q), where N is the size of the array and Q is the number of queries. This is because calculating the prefix product takes O(N) time, and processing each query takes O(1) time.

This approach allows us to efficiently solve the range product problem, making it useful for query processing under various conditions.

Alternative Method

If there are changes made to the array, an efficient data structure may be needed for updates or dynamically increasing queries. In this case, a data structure such as a segment tree can be utilized. This allows both updates and query processing to be done in O(log N) time.

Conclusion

In this course, we discussed the problem of calculating range products in JavaScript. We demonstrated how to efficiently solve the problem using the prefix product and mentioned that it can be extended into more complex structures if necessary.

Try using these techniques to solve your own coding problems!

Problem Description

There is a given string text and a string pattern that needs to be found.
Write a function that returns the position where pattern first appears in text.
If the pattern does not exist in text, return -1.

Input Example

• text: “hello world”
• pattern: “world”

Output Example

• Result: 6 (the string “world” starts at index 6)

Problem Solving Strategy

To solve this problem, we need to check if a specific pattern exists within the string and,
if it does, find its starting index. There are various algorithms for string searching, but
in this tutorial, we will use the most basic and intuitive method called ‘Brute Force’ and
a more efficient algorithm called ‘KMP (Knuth-Morris-Pratt)’.
Let’s first take a look at the Brute Force method.

Brute Force Approach

The Brute Force method compares all combinations of the given string and the pattern to be found.
This method is simple and easy to understand, but in the worst case, its time complexity is O(n*m),
where n is the length of the text and m is the length of the pattern.

Algorithm Steps

1. Set the variable for the length of the text (n) and the length of the pattern (m).
2. Increase the starting position of the text one by one and compare with the pattern from the current position.
3. If all character comparisons match, return the current starting index.
4. If all characters are compared and the pattern is not found, return -1.

JavaScript Code Implementation

function findFirstOccurrence(text, pattern) {
    const n = text.length;
    const m = pattern.length;

    for (let i = 0; i <= n - m; i++) {
        let j;
        for (j = 0; j < m; j++) {
            if (text[i + j] !== pattern[j]) {
                break;
            }
        }
        if (j === m) {
            return i; // Pattern found
        }
    }
    return -1; // Pattern not found
}

// Test examples
console.log(findFirstOccurrence("hello world", "world")); // 6
console.log(findFirstOccurrence("hello world", "abc")); // -1
    

KMP Algorithm

While the Brute Force method is simple, it can be inefficient. The KMP algorithm improves performance by
preventing unnecessary re-inspections during the search. The basic concept of the KMP algorithm is
‘when part of the pattern matches, reuse the remainder’.

Principle of the KMP Algorithm

The KMP algorithm optimizes string searching using a ‘partial match table (or failure function)’.
This table provides information that can be cached during the search.
The time complexity of the KMP algorithm is O(n + m), making it effective for large datasets.

Algorithm Steps

1. Create a partial match table for the pattern.
2. While comparing text and pattern, if there is a mismatch, refer to the table to specify the pattern’s position.
3. Repeat until a match is found, and ultimately return the index.

Creating the Partial Match Table

The algorithm for creating the partial match table is as follows. This table is used to adjust
the index for the next comparison based on the same prefixes and suffixes from the previously examined string.

function buildKMPTable(pattern) {
    const m = pattern.length;
    const lps = new Array(m).fill(0);
    let len = 0; 
    let i = 1;

    while (i < m) {
        if (pattern[i] === pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len !== 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}
    

KMP Algorithm Code Implementation

function KMPSearch(text, pattern) {
    const n = text.length;
    const m = pattern.length;
    const lps = buildKMPTable(pattern);
    let i = 0; // Text index
    let j = 0; // Pattern index

    while (i < n) {
        if (pattern[j] === text[i]) {
            i++;
            j++;
        }
        if (j === m) {
            return i - j; // Pattern found
        } else if (i < n && pattern[j] !== text[i]) {
            if (j !== 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1; // Pattern not found
}

// Test examples
console.log(KMPSearch("hello world", "world")); // 6
console.log(KMPSearch("hello world", "abc")); // -1
    

Conclusion

In this tutorial, we explored two algorithms for solving the string search problem,
the Brute Force method, and the KMP algorithm.
The Brute Force method is intuitive and straightforward but can be inefficient when searching large strings.
In contrast, the KMP algorithm provides a more efficient way to search for patterns.
Understanding and appropriately utilizing these diverse algorithms is important in real coding tests.

Problems related to string searching are frequently featured in coding tests, so
it’s necessary to gain experience by solving various examples.
Keep learning different algorithm problems to further enhance your skills.

Problem Description

There is a problem of finding the index of a specific permutation among the permutations that can be made from the given numbers.

For example, when the numbers 1, 2, and 3 are given, all the possible permutations are as follows:

• 123
• 132
• 213
• 231
• 312
• 321

The question is to find out the index of a specific number’s permutation. In the above example, 231 corresponds to the 4th position.

Input Format

The first line contains the number of digits n (1 ≤ n ≤ 10).

The second line contains n natural numbers. (Each number is a different natural number from 1 to n.)

The third line contains the desired permutation index k (1 ≤ k ≤ n!).

Output Format

Print the desired permutation.

Problem Solving

Approach

To solve this problem, we define the following steps:

1. Generate all combinations of the numbers to create a list of permutations.
2. Find the desired permutation in the list of permutations.

Permutation Generation Algorithm

Here, we will describe the process of generating permutations and finding a specific order using JavaScript. We will use the DFS (Depth-First Search) method to generate permutations.

JavaScript Code

        
function getPermutations(arr) {
    const result = [];
    
    const backtrack = (current, remaining) => {
        if (remaining.length === 0) {
            result.push(current);
            return;
        }
        
        for (let i = 0; i < remaining.length; i++) {
            const newCurrent = [...current, remaining[i]];
            const newRemaining = [...remaining.slice(0, i), ...remaining.slice(i + 1)];
            backtrack(newCurrent, newRemaining);
        }
    };
    
    backtrack([], arr);
    return result;
}

function findPermutation(n, nums, k) {
    const permutations = getPermutations(nums);
    return permutations[k - 1].join('');
}

// Example input
const n = 3;
const nums = [1, 2, 3];
const k = 4;

// Output
console.log(findPermutation(n, nums, k)); // 231
        
    

Code Explanation

The above code consists of two functions:

• getPermutations: Generates all permutations of the given array.
• findPermutation: Returns the permutation corresponding to the desired index.

Detailed Explanation of getPermutations Function

This function generates permutations recursively:

• Select one of the elements from the current array and add it to the current combination.
• Create a new array with the remaining elements, excluding the selected element, and proceed with the recursive call.
• Repeat this process until all elements are selected, and add the completed permutation to the result.

Detailed Explanation of findPermutation Function

This function goes through the following steps:

1. Generates all permutations for the given number array.
2. Finds the permutation corresponding to the k-1 index in the generated permutation array and returns it as a string.

Time Complexity

The time complexity of this algorithm is O(n!). Since it generates all permutations, the calculation time can become very long as the number of digits increases. However, since the value of n is limited to 10 or less, the problem can be solved at a practical level.

Conclusion

Now you have learned how to create permutations and find a specific ordered permutation. This is one of the types of problems that frequently appear in coding tests, so practice until you are fully proficient.

In the next session, I will return with another algorithm problem. Thank you!

Coding tests are a challenging process that many developers face. Especially when solving problems in JavaScript, one must have a good understanding of the language’s characteristics. In this course, we will explore the characteristics of JavaScript and algorithmic approaches through a problem titled ‘I Don’t Want to be a Liar.’

Problem Description

Imagine the following situation. You are going camping with several friends. Some of your friends are quirky and have decided to lie about a certain incident. Here is what each friend has claimed.

The given input is represented as an array, where each array value is the number of friends that a friend claims. Your goal is to determine that if the number of friends stated in the claims is a majority, then those friends are considered to be lying.

Example Input

    const statements = [
        [0, 1], // Friend 0 claims friend 1
        [1, 2], // Friend 1 claims friend 2
        [2, 0], // Friend 2 claims friend 0
        [3, 2], // Friend 3 claims friend 2 (here, friend 3 is a liar)
    ];
    

Example Output

Number of lying friends: 1

Problem Solving Process

The first step in approaching this problem is to understand the relationships in which each friend claims someone. We can use a directed graph to represent each friend as a node and the claiming relationship as edges.

1. Data Structure Design

First, we need to define a data structure that can store the claims made by each friend. To do this, we can use an object to map each friend’s ID to a list of IDs of the friends they claim.

    const graph = {};
    statements.forEach(([speaker, listener]) => {
        if (!graph[speaker]) {
            graph[speaker] = [];
        }
        graph[speaker].push(listener);
    });
    

2. Exploration through DFS/BFS

To explore the relationships between claims, we can use either DFS (Depth-First Search) or BFS (Breadth-First Search). This will allow us to verify the validity of each friend’s claims.

    function hasContradictions(speaker) {
        const visited = new Set();
        const stack = [speaker];

        while (stack.length) {
            const curr = stack.pop();
            if (visited.has(curr)) {
                return true; // A contradiction occurs when visiting a node that has already been visited
            }
            visited.add(curr);

            if (graph[curr]) {
                graph[curr].forEach(listener => {
                    stack.push(listener);
                });
            }
        }
        return false;
    }
    

3. Check all friends

We count the number of friends who have invalid claims by checking all friends. This is the process of identifying how many among the total friends are creating contradictions.

    let liarsCount = 0;
    for (let i = 0; i < statements.length; i++) {
        if (hasContradictions(i)) {
            liarsCount++;
        }
    }
    return liarsCount;
    

Final Code

    function findLiars(statements) {
        const graph = {};
        statements.forEach(([speaker, listener]) => {
            if (!graph[speaker]) {
                graph[speaker] = [];
            }
            graph[speaker].push(listener);
        });

        function hasContradictions(speaker) {
            const visited = new Set();
            const stack = [speaker];

            while (stack.length) {
                const curr = stack.pop();
                if (visited.has(curr)) {
                    return true; 
                }
                visited.add(curr);

                if (graph[curr]) {
                    graph[curr].forEach(listener => {
                        stack.push(listener);
                    });
                }
            }
            return false;
        }

        let liarsCount = 0;
        for (let i = 0; i < statements.length; i++) {
            if (hasContradictions(i)) {
                liarsCount++;
            }
        }
        return liarsCount;
    }

    console.log(findLiars(statements)); // Output: 1
    

Conclusion

Through problems like the one described above, we learned how to apply basic syntax in JavaScript, utilize data structures, and implement DFS/BFS algorithms. It is important to practice such problems while preparing for coding tests to enhance algorithmic thinking.

Problem Description

Write a function that calculates the average of an array of given numbers.
The average is the sum of all numbers divided by the count of numbers.
If the array is empty, appropriate exception handling should return a suitable message.

Problem Example

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

        Input: []
        Output: "The array is empty."
    

Algorithm Approach

To solve this problem, we follow these steps:

1. Check if the input array is empty.
2. Iterate through each element of the array and calculate the sum.
3. Determine the length of the array to calculate the average.
4. Return the final calculated average value.

JavaScript Code Implementation

Now let’s implement each step in JavaScript.

function calculateAverage(numbers) {
    // Check if the input array is empty
    if (numbers.length === 0) {
        return "The array is empty.";
    }
    
    // Variable to store the sum
    let sum = 0;
    
    // Iterate through each element of the array and calculate the sum
    for (let i = 0; i < numbers.length; i++) {
        sum += numbers[i];
    }
    
    // Calculate the average
    const average = sum / numbers.length;
    
    // Return the average
    return average;
}

// Example test
console.log(calculateAverage([1, 2, 3, 4, 5])); // Output: 3
console.log(calculateAverage([])); // Output: "The array is empty."
    

Detailed Explanation of the Problem Solving Process

Step 1: Check the Input Array

In the first step, we check if the given array is empty.
If the length of the array is 0, the function immediately returns the string "The array is empty."
This is exception handling for cases where the user has incorrectly specified the input array.

Step 2: Calculate the Sum

If the array is not empty, we proceed to the next step to calculate the sum.
Here, we initialize a variable called sum to 0 and then iterate through each element of the array,
adding its value to the sum. The length of the array can be checked with numbers.length.

Step 3: Calculate the Average

Once the summation is complete, we divide the sum by the length of the array to calculate the average value.
In this process, we can write the calculation like const average = sum / numbers.length;.
Since the average may include decimal parts, there is no need to separately adjust the number of decimal places if not required.

Step 4: Return the Result

In the final step, we return the calculated average value.
This value can be utilized by the caller to print it out using console.log or other methods.

Results and Review

Thus, the algorithm for calculating the average is implemented through exception handling that checks if the array length is 0
and a simple method of summation through iteration.

To review, the process of calculating the average involves summing all the numbers in parentheses and dividing that value
by the count of numbers.
Handling exception situations in this process is crucial in actual coding tests, so it is always important to remain vigilant.

Overcoming Challenges

Here are some points to consider while solving this problem.

• Need to check if the input array always contains numbers
• Define the messages or values to be returned consistently when handling exceptions
• Consider the method of handling if non-number elements are included

When conducting coding tests, always keep the above exception situations in mind
to reduce the likelihood of problems arising.

Conclusion

The problem of finding the average is simple, but requires careful consideration of various exception situations and conditions.
With practice, you will be able to implement algorithms more effectively.

If you have any more questions or concerns, please leave a comment!
Next time, we'll return with another algorithm problem.