JavaScript Coding Test Course, Understanding Friend Relationships

Coding tests often include problems related to data structures and algorithms. In particular, problems related to identifying friendships are related to graph theory, and many companies use these problems to evaluate candidates’ logical thinking and coding skills.

Problem Description

The algorithm problem for identifying friendships is as follows.
Problem: Friend Relationship Exploration
Given the number of people N and M pairs representing friend relationships, write a function to determine the number of people who are not friends with a specific individual.

Input Format

First line: Number of people N (1 ≤ N ≤ 100)
Second line: Number of friend relationships M (1 ≤ M ≤ 1000)
Third line: M pairs of friend relationships provided in the form (a b), meaning a and b are friends.
Fourth line: Specific individual X (1 ≤ X ≤ N) – the individual to check friendships for

Output Format

Output the number of people who are not friends with the input individual X.

Example Input

Example Output

Problem Solving Process

Step 1: Understanding and Analyzing the Problem

To understand the given problem, we need to be able to represent the provided friend relationships as a graph. To do this, we will use an adjacency list. This method allows us to connect each individual with their friends and easily understand the relationships.

Step 2: Designing Data Structures

Each individual can store friend relationships through array indices. For example, to save individuals who are friends with individual 1, we will add the relative individual’s number to the adjacency list. This structure allows us to easily find friends of a specific individual.

Step 3: Designing the Algorithm

To calculate the number of people who are not friends, we follow these procedures:

Check the friend relationships for all individuals (from 1 to N) to build a friend list.
Refer to the friend list of the specific individual X to calculate the number of people who are not friends.
Finally, declare a friendCount variable, and by subtracting the number of friends and X from the total number of individuals, we can obtain the number of people who are not friends.

Step 4: JavaScript Implementation


    function countNonFriends(N, M, relations, X) {
        // Create adjacency list
        const friends = Array.from({ length: N + 1 }, () => []);

        // Add relationships
        relations.forEach(([a, b]) => {
            friends[a].push(b);
            friends[b].push(a);
        });

        // Count the number of non-friends
        const friendSet = new Set(friends[X]);
        let count = 0;

        for (let i = 1; i <= N; i++) {
            if (i !== X && !friendSet.has(i)) {
                count++;
            }
        }

        return count;
    }
    
    const N = 5;
    const M = 4;
    const relations = [[1, 2], [1, 3], [2, 4], [4, 5]];
    const X = 1;
    console.log(countNonFriends(N, M, relations, X)); // 3

Step 5: Time Complexity Analysis

The time complexity of this algorithm is O(N + M) in the process of checking each friend relationship. This is efficient since each relationship is only explored once.

Conclusion

This problem provides an opportunity to learn the process of solving graph-related problems and understanding friend relationships. Additionally, it offers practice in managing data using arrays and objects in JavaScript, and in implementing algorithms. It is important to practice multiple problems of this type while preparing for coding tests.