Author: root

1. What is Sliding Window?

The Sliding Window technique is an algorithmic approach used to find a subarray or substring that meets specific conditions in a given array or list. It is primarily suitable for problems that require consecutive elements and can use either a fixed-size or variable-size window depending on the problem.

1.1 Advantages of Sliding Window

The biggest advantage of the sliding window is that it can significantly reduce time complexity compared to the brute force method. It is often possible to reduce from O(n^2) to O(n). The sliding window uses two pointers to traverse the array, enabling efficient access.

2. Example Algorithm Problem

Problem: Maximum Length of Repeating Character Replacement

Given a string, write a function that returns the length of the longest substring that can be created by changing at most ‘k’ characters.

    Example:
    Input: s = "AABABBA", k = 1
    Output: 4
    Explanation: The characters that can be changed are 'A' or 'B'. You can change two 'B's to 'A' to make 'AAAA'.
    

Approach to the Problem

You can use a sliding window to solve this problem. Here, we will count the number of characters present in the current window and check if we can replace ‘k’ characters.

2.1 Steps of the Algorithm

1. Initialize the left pointer and the right pointer.
2. Use a HashMap to count the characters in the substring.
3. Check the validity of the current window.
4. If invalid, move the left pointer.
5. Record the current window size and move the right pointer.
6. Repeat this process to find the maximum length.

3. Code Implementation

Below is the JavaScript code based on the algorithm described above.

    function characterReplacement(s, k) {
        const countMap = {};
        let left = 0;
        let maxLength = 0;
        let maxCount = 0;

        for (let right = 0; right < s.length; right++) {
            countMap[s[right]] = (countMap[s[right]] || 0) + 1;
            maxCount = Math.max(maxCount, countMap[s[right]]);

            while (right - left + 1 - maxCount > k) {
                countMap[s[left]]--;
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    // Example usage
    console.log(characterReplacement("AABABBA", 1)); // 4
    

4. Code Explanation

In the above code, we are processing the string ‘s’ in relation to the given ‘k’ repeatedly. We use countMap to count the frequency of each character, and we track the number of the most frequent character in the current window.

4.1 Explanation of Key Variables

• countMap: An object that counts the occurrences of each character
• left: The left boundary of the window
• maxLength: Stores the maximum length
• maxCount: The number of the most frequent character in the current window

4.2 Movement of the Sliding Window

The right pointer increases and moves to the end of the string while the left pointer only moves when the current window is invalid. The valid condition is that the number of most frequent characters subtracted from the current window size must be less than or equal to ‘k’. This checks whether specific characters can be replaced.

5. Time Complexity and Space Complexity

The time complexity of this algorithm is O(n). It traverses each character of the string only once, and the space complexity is O(1) because it only needs to store 26 letters due to considering only uppercase alphabet letters.

6. Various Problem-Solving Methods

The sliding window technique can be applied in many diverse ways. Thus, mastering this concept will help in solving many other algorithm problems. For example:

• Maximum number of consecutive 1’s problem
• Minimum-length subarray sum problem
• Finding all anagrams problem

6.1 Additional Example Problem

The following problem can also be efficiently solved using the sliding window:

    Problem: Shortest subarray sum case
    Find the minimum length of the subarray that sums up to a specific number in the given array.
    

7. Conclusion

In this lecture, we covered the basic concept of the sliding window technique and solved an algorithm problem using it. This technique is particularly useful for string processing and subarray-related problems, so practice and familiarize yourself to tackle various variations of problems effectively.

Mastering the sliding window pattern can significantly reduce the difficulty of algorithm problems, and it often appears in coding tests in companies. I hope you acquire this technique perfectly through ample practice in the future.

8. Additional Resources

If you want to solve more sliding window problems, you can find numerous problems on online platforms such as LeetCode and HackerRank.

These days, many companies are evaluating applicants’ algorithm and problem-solving skills through coding tests. This time, we will take a look at the process of solving a problem with the topic of sorting cards. Sorting cards is one of the very simple yet frequently asked questions, requiring a fundamental understanding of algorithms and data structures.

Problem Description

We are trying to sort cards that have numbers written on them for a card game. The number of cards is N, and each card has an integer number from 1 to N. After sorting the given card array in ascending order, we need to print the final state of the card array.

Input Format

The first line contains the number of cards N (1 ≤ N ≤ 1000), and the second line contains the card numbers separated by spaces.

Output Format

Print the sorted card numbers separated by spaces.

Example Input

5
3 2 1 4 5

Example Output

1 2 3 4 5

Approach to the Problem

We can use the following approach to solve the problem.

1. Data Collection: Collect the number of cards and the card numbers.
2. Select a Sorting Algorithm: Use JavaScript’s built-in methods to sort the array.
3. Output Data in the Required Format: Output the sorted array.

Code Writing

Now let’s write the code. Below is the JavaScript code to solve the card sorting problem.

function sortCards(cards) {
    return cards.sort((a, b) => a - b);
}

function main() {
    const n = parseInt(prompt("Enter the number of cards:")); // Prompt to enter the number of cards
    const cardsInput = prompt("Enter the card numbers (separated by spaces):"); // Enter card numbers
    const cards = cardsInput.split(" ").map(Number); // Convert the space-separated string to an integer array

    const sortedCards = sortCards(cards); // Call the sorting method
    console.log(sortedCards.join(" ")); // Output the sorted cards
}

main();

Code Explanation

Let’s explain each part of the code we wrote.

sortCards Function

The sortCards function takes an array of card numbers and returns it sorted in ascending order. It uses JavaScript’s built-in sort method, along with an arrow function to compare the sizes of the numbers.

Main Function

The main function performs the following tasks:

• Uses prompt to input the number of cards.
• Uses prompt again to input the card numbers and passes them as a string.
• Uses the split method to convert the space-separated string into an array, and uses the map method to convert each element into a number.
• Calls the sortCards function to get the sorted array.
• Converts the result to a string using the join method and outputs it to the console.

Testing and Validation

We will test the code we wrote to verify that it works correctly with various inputs.

Test Case 1

Input:
5
3 2 1 4 5

Output:
1 2 3 4 5

Test Case 2

Input:
4
8 3 5 2

Output:
2 3 5 8

Conclusion

In this tutorial, we explored how to solve the card sorting problem using JavaScript’s array methods. Additionally, we had a chance to understand the approach and the role of each function through code writing. Problems like this are frequently asked in algorithm tests, so it is important to improve problem-solving skills through practice.

Additional Resources

For those who want to practice more advanced algorithm problems, please refer to the links below:

• LeetCode – Provides various algorithm problems.
• HackerRank – Provides algorithm and data structure problems.
• Codewars – Offers problems of various difficulties and allows interaction with the community.

With that, we will conclude the JavaScript coding test course. Always strive to prepare for successful coding tests!

One of the frequently encountered problems in coding tests is array sorting. In this tutorial, we will learn about the Quick Sort algorithm and explain in detail how to implement it in JavaScript. Quick sort is an efficient sorting algorithm that uses the divide and conquer technique.

Problem Description

Sort the given array in ascending order using the quick sort algorithm.

Example Input: [34, 7, 23, 32, 5, 62]
Example Output: [5, 7, 23, 32, 34, 62]

Overview of Quick Sort Algorithm

Quick sort proceeds through the following steps.

1. Select one element from the array as the pivot.
2. Divide the array into two subarrays based on the pivot. One consists of elements smaller than the pivot, while the other consists of elements larger than the pivot.
3. Apply the same method recursively to each subarray.
4. Repeat until the subarrays have a size of 0 or 1.

Example Explanation

If the input array is [34, 7, 23, 32, 5, 62], it undergoes the following process.

1. Selecting Pivot: Choose 62, the last element of the array, as the pivot.
2. Partitioning: Divide the array into elements smaller than pivot 62 ([34, 7, 23, 32, 5]) and larger elements ([]) based on the pivot.
3. Recursive Call: Repeat the same process for the subarray [34, 7, 23, 32, 5], which is smaller than the pivot.
4. By repeating this process, the array will ultimately be sorted.

JavaScript Implementation

Now, let’s implement the quick sort algorithm in JavaScript.

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr; // Return as is if the size is 0 or 1
    }
    
    const pivot = arr[arr.length - 1]; // Choose the last element as pivot
    const left = []; // Array to store elements less than the pivot
    const right = []; // Array to store elements greater than the pivot

    // Iterate through the array and compare with the pivot
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    // Recursive calls and return the result array
    return [...quickSort(left), pivot, ...quickSort(right)];
}

// Example array
const array = [34, 7, 23, 32, 5, 62];
const sortedArray = quickSort(array);
console.log(sortedArray); // [5, 7, 23, 32, 34, 62]

Time Complexity of the Algorithm

The average time complexity of the quick sort algorithm is O(n log n). However, in the worst case, it can have a time complexity of O(n²). This can occur when the pivot selection is imbalanced. For this reason, quick sort can be optimized through techniques such as randomly selecting the pivot to enhance performance.

Advantages and Disadvantages of Quick Sort

Advantages

• An efficient sorting algorithm suitable for sorting large datasets.
• It uses less memory, allowing for in-place sorting.

Disadvantages

• In the worst case, the time complexity of O(n²) is inefficient.
• It uses stack memory due to recursive calls.

Conclusion

In this tutorial, we learned about the quick sort algorithm and how to implement it in JavaScript. Quick sort is a simple and efficient sorting algorithm frequently used in coding tests and algorithm problem solving. Based on what you have learned, try solving various array sorting problems.

In the next tutorial, we will cover another sorting algorithm, Merge Sort. Please stay tuned!

In this course, we will learn how to implement an Absolute Value Heap in JavaScript. An Absolute Value Heap is a heap structure sorted by two criteria, primarily arranging the data based on absolute values. For instance, if the absolute values are the same, the actual values are sorted accordingly.

Problem Description

We will solve an algorithm problem by constructing an Absolute Value Heap and performing the given tasks. The problem is as follows.

Given an array of integers, perform the operation of deleting and returning the number with the smallest absolute value using the Absolute Value Heap. In cases where the absolute values are the same, the smaller actual value is deleted first.

Input Format

["I 5", "I -5", "I 3", "I -2", "I 0", "I 4", "D 1", "D 1"]
    

Output Format

[0, -2, 3, 4]
    

Problem Solving Process

To implement an Absolute Value Heap, we can use JavaScript arrays. We declare an array and implement methods for insertion and deletion based on this array.

Step 1: Define the Heap Class

First, we will design the basic structure of the heap. The heap must always maintain a specific relationship between parent nodes and child nodes according to certain rules. It is sorted in order of increasing absolute value, and in cases of equal absolute values, it is sorted in order of the original values.

class AbsoluteValueHeap {
    constructor() {
        this.heap = [];
    }

    insert(value) {
        this.heap.push(value);
        this.bubbleUp(this.heap.length - 1);
    }

    bubbleUp(index) {
        const element = this.heap[index];
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];
            if (this.isCorrectOrder(element, parent)) break;
            this.heap[index] = parent;
            index = parentIndex;
        }
        this.heap[index] = element;
    }

    isCorrectOrder(child, parent) {
        if (Math.abs(child) < Math.abs(parent)) return true;
        if (Math.abs(child) > Math.abs(parent)) return false;
        return child < parent;
    }

    delete() {
        if (this.heap.length === 0) return null;
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.bubbleDown(0);
        }
        return min;
    }

    bubbleDown(index) {
        const element = this.heap[index];
        const length = this.heap.length;
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (!this.isCorrectOrder(element, leftChild)) {
                    swap = leftChildIndex;
                }
            }

            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if (
                    (swap === null && !this.isCorrectOrder(element, rightChild)) ||
                    (swap !== null && !this.isCorrectOrder(leftChild, rightChild))
                ) {
                    swap = rightChildIndex;
                }
            }

            if (swap === null) break;
            this.heap[index] = this.heap[swap];
            index = swap;
        }
        this.heap[index] = element;
    }

    peek() {
        return this.heap[0] || null;
    }
}
    

Step 2: Create a Function to Handle Commands

Now, we will create a function to process various commands based on the Absolute Value Heap. The command 'I' represents insertion, while 'D' represents deletion.

function processCommands(commands) {
    const heap = new AbsoluteValueHeap();
    const results = [];

    for (const command of commands) {
        const [action, value] = command.split(' ');
        const num = parseInt(value);

        if (action === 'I') {
            heap.insert(num);
        } else if (action === 'D' && num === 1) {
            const deleted = heap.delete();
            results.push(deleted !== null ? deleted : 0);
        } else if (action === 'D' && num === -1) {
            // No need to delete since it's implemented as a min heap
            const deleted = heap.delete();
            results.push(deleted !== null ? deleted : 0);
        }
    }
    return results;
}
    

Step 3: Summary of the Complete Code

Now we will combine all the previously created code into a complete summary.

class AbsoluteValueHeap {
    // Utilize the previously defined code.
}

function processCommands(commands) {
    // Utilize the previously defined code.
}

// Execute the test example
const commands = ["I 5", "I -5", "I 3", "I -2", "I 0", "I 4", "D 1", "D 1"];
console.log(processCommands(commands)); // [0, -2, 3, 4]
    

Conclusion

In this course, we explored the process of implementing an Absolute Value Heap in JavaScript to solve the given problem. To aid understanding of the algorithm, we explained the basic concepts of heap sorting and the operational principles of a heap based on absolute values. We hope that this course will help you develop your skills in more advanced data structures and algorithm problem-solving.

Problem Description

You are managing a project management system where various tasks are interconnected. Each task must be performed for a specific duration, and certain tasks can only start after others have been completed. Implement an algorithm to determine the minimum time required for the project to be completed based on these relationships.

The project consists of the following information:

• n : number of tasks
• dependencies : an array representing the dependency relationships between each task
• times : an array of the time required to perform each task

The function format is as follows:

function criticalPath(n, dependencies, times) {
    // Write your code here.
}
    

Example Input

n = 5
dependencies = [[1, 0], [2, 1], [3, 1], [3, 2], [4, 3]]
times = [3, 2, 5, 1, 2]
Input: criticalPath(n, dependencies, times)
    

Example Output

Output: 11
    

Problem Solving Approach

To solve this problem, the following steps should be taken:

1. Graph Modeling

Represent the tasks and their dependency relationships as a graph. Each task can be represented as a vertex, and the dependencies as edges.

2. Topological Sort

Determine the order of task execution through topological sorting of the given graph. Topological sorting is the process of finding a linear arrangement of all vertices in a directed graph.

3. Calculate the Longest Path

Use the topological sort to calculate the start time of each task and ultimately find the minimum time required for all tasks to be completed.

Implementation Code

Below is the JavaScript code that implements the above approach:

function criticalPath(n, dependencies, times) {
    const adjList = Array.from({length: n}, () => []);
    const inDegree = Array(n).fill(0);
    
    // 1. Build the graph and calculate in-degrees
    for (const [next, prev] of dependencies) {
        adjList[prev].push(next);
        inDegree[next]++;
    }
    
    // 2. Create a queue for topological sorting
    const queue = [];
    const timeToComplete = Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        timeToComplete[i] = times[i];
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }
    
    // 3. Calculate the longest path
    let maxTime = 0;

    while (queue.length) {
        const current = queue.shift();
        maxTime = Math.max(maxTime, timeToComplete[current]);

        for (const neighbor of adjList[current]) {
            timeToComplete[neighbor] = Math.max(timeToComplete[neighbor], timeToComplete[current] + times[neighbor]);
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }
    
    return maxTime;
}
    

Code Explanation

Now, let’s look at each part of the code:

1. Build the graph and calculate in-degrees

First, based on the dependency relationships given in the input, an adjacency list is created, and the in-degrees of each vertex are calculated. Tasks with an in-degree of 0 can start immediately, so they are added to the queue.

2. Topological sorting and longest path calculation

Tasks are removed one by one from the queue, updating the longest completion times for their subsequent tasks. If the in-degree of a subsequent task becomes 0, it is added back to the queue. After processing all tasks, the longest recorded time is the critical path.

Time Complexity Analysis

This algorithm explores each vertex and edge of the graph once, so its time complexity is O(V + E), where V is the number of tasks and E is the number of dependency relationships between tasks.

Final Thoughts

Finding the critical path is an important element in project management and scheduling, and it is widely used in industry. This problem allows you to understand the concepts of graphs and topological sorting, while also developing your ability to solve complex problems in JavaScript.

Additional Practice Problems

Now, to test your skills, try solving the following problems:

1. Implement an algorithm to track changes in the critical path when the dependency relationships between tasks change.
2. Consider not only the time required for tasks but also their costs. What would be your approach to finding the optimal path in this case?
3. How can you apply topological sorting when the graph has a different structure (e.g., directed acyclic graph)?

References

If you want to know more about the critical path problem, check the links below:

• Critical Path Method - Wikipedia
• Graph Theory - Carnegie Mellon University