JavaScript Coding Test Course, Finding the Order of Building

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.