JavaScript Coding Test Course, I Don't Want to Be a Liar

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.

JavaScript Coding Test Course, I Don’t Want to Be a Liar