Category: Javascript Coding Test

This article will discuss the ‘Building Order Problem’ among JavaScript coding test questions. This problem is an interesting one that can be solved using concepts from graph theory and topological sorting. Before we begin, let’s review the problem’s definition and requirements.

Problem Definition

The problem is to determine the order in which all buildings must be constructed based on the given N buildings and their dependencies. If building A must be constructed before building B, then there is a dependency relationship between these two buildings.

Input

Input is in the following format:
- First line: N (number of buildings), M (number of dependencies)
- Next M lines: A B (indicates that building A must be constructed before building B)
    

Output

Print a possible construction order of buildings, separated by spaces in one line. If the order is not possible, print "Impossible".
    

Examples

Example 1

Input:
4 2
1 2
2 3

Output:
1 2 3 4
    

Example 2

Input:
3 3
1 2
2 3
3 1

Output:
Impossible
    

Problem Solving Process

Topological Sorting

The most important concept for solving this problem is topological sorting. Topological sorting is a method of ordering the vertices of a directed graph considering their precedence relationships. For a topological sorting result to exist, the graph must not contain cycles. In other words, all dependencies must be clear to determine the order.

Problem Solving Algorithm

The algorithm to solve the problem can be structured as follows.

1. Read the number of vertices (N) and the number of edges (M) in the graph.
2. Create an adjacency list for the graph while counting the number of buildings required to be constructed for each building (in-degree).
3. Add buildings with an in-degree of 0 to the queue.
4. Remove one building at a time from the queue, add it to the result list, and decrease the in-degree of the buildings that depend on it.
5. Add buildings whose in-degree becomes 0 to the queue.
6. After processing all buildings, if the length of the result list equals N, print the possible construction order; otherwise, print “Impossible”.

JavaScript Code Implementation

function getConstructionOrder(N, M, dependencies) {
    const graph = Array.from({ length: N + 1 }, () => []);
    const indegree = Array.from({ length: N + 1 }, () => 0);
    
    // Add dependencies to the graph
    for (const [a, b] of dependencies) {
        graph[a].push(b);
        indegree[b]++;
    }
    
    const queue = [];
    
    // Add nodes with in-degree of 0
    for (let i = 1; i <= N; i++) {
        if (indegree[i] === 0) {
            queue.push(i);
        }
    }
    
    const order = [];
    
    while (queue.length > 0) {
        const current = queue.shift();
        order.push(current);
        
        for (const neighbor of graph[current]) {
            indegree[neighbor]--;
            if (indegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }

    return order.length === N ? order : "Impossible";
}

// Test example
const N = 4;
const M = 2;
const dependencies = [[1, 2], [2, 3]];
const result = getConstructionOrder(N, M, dependencies);
console.log(result.join(' ')); // Output: 1 2 3 4
    

Conclusion

In this tutorial, we learned the concept of topological sorting and how to solve the ‘Building Order Problem’ in JavaScript. Through the process of constructing a graph based on arbitrary input and deriving the possible construction order from it, we hope to enhance your algorithm problem-solving skills. Similar problems may appear in various technical interviews, so continuous practice and understanding are necessary. Thank you!

References

If you wish to deepen your understanding of related materials and algorithms, please refer to the resources below.

• Wikipedia: Topological Sorting
• MDN Web Docs: JavaScript
• Codewars: Algorithm Practice

JavaScript is one of the most commonly used languages in web development and often appears in coding tests. In this article, we will cover algorithm problems that can be solved with JavaScript and learn more about time complexity notation. Through the process of solving algorithm problems, let’s understand the importance of time complexity and build a foundation for writing efficient code.

function twoSum(nums, target) {
    const map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
}
        

Understanding Time Complexity Notation

Time complexity is an important concept used to evaluate the performance of algorithms. The execution time of an algorithm varies depending on the input size, and time complexity is the numerical expression of this.

Types of Time Complexity

• O(1): Takes a constant amount of time regardless of input size.
• O(log n): The growth rate is slow as the input size increases. The binary search algorithm falls under this category.
• O(n): Occurs when traversing an array or list once.
• O(n log n): Advanced sorting algorithms such as merge sort and quicksort belong to this category.
• O(n^2): Occurs in cases with nested loops. A typical bubble sort is an example of this.
• O(2^n): Refers to recursive problems such as calculating the Fibonacci sequence.

The Importance of Time Complexity Analysis

Choosing efficient algorithms is crucial in software development. Understanding and optimizing time complexity is essential for improving program performance and providing a better experience for users.

Final Thoughts

In this article, we explored methods for solving algorithm problems using JavaScript and time complexity notation. In future coding tests, you will be able to solve more problems based on these algorithms and time complexities.

Problem Definition

This is a problem of calculating the number of ways to fill a 2*N rectangle with tiles of size 1*2 or 2*1. In other words, for a given length N, we aim to find the number of ways to completely fill the rectangle using the tiles. This problem can be solved using the Dynamic Programming technique.

Problem Description

For example, when N=3, the 2*3 rectangle can be filled in the following ways:

• 1->1->1
• 1->2
• 2->1
• 2->2
• 2->1->1

Various cases are generated depending on how the tiles are arranged. Therefore, it is possible to recursively explore all combinations by finding appropriate rules.

Problem Approach

1. Recursive Approach

The most basic method is to use recursion to explore all possible cases. However, this is inefficient and has a high time complexity, making it impractical.

2. Dynamic Programming

Using Dynamic Programming allows us to store previous computed results and utilize them to avoid redundant calculations. This approach reduces the time complexity to O(N).

Dynamic Programming Implementation

Recurrence Relation

The following recurrence relation can be established:

dp[n] = dp[n-1] + dp[n-2]

When filling the last column with a 1×2 tile, we consider the case of dp[n-1], and when filling with a 2×1 tile, we consider the case of dp[n-2]. The base conditions are as follows:

• dp[1] = 1 (Filling with a 1*2 tile)
• dp[2] = 2 (Filling with a 2*1 or 1*2 tile)

JavaScript Example Code

function tileWays(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;

    let dp = new Array(n + 1);
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

console.log(tileWays(3)); // Output: 3
    

Conclusion

The 2*N tile filling problem is a fundamental dynamic programming problem that is frequently featured in coding tests. Through this problem, we learn the importance of choosing efficient approaches when solving algorithmic problems.
It is essential to understand the basics of Dynamic Programming well and to develop the ability to solve complex problems step by step using it. I hope to become a better developer through practice on various problems.