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.’<\/p>\n
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.<\/p>\n
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.<\/p>\n
\n const statements = [\n [0, 1], \/\/ Friend 0 claims friend 1\n [1, 2], \/\/ Friend 1 claims friend 2\n [2, 0], \/\/ Friend 2 claims friend 0\n [3, 2], \/\/ Friend 3 claims friend 2 (here, friend 3 is a liar)\n ];\n <\/pre>\nExample Output<\/h3>\n
Number of lying friends: 1<\/p>\n
Problem Solving Process<\/h2>\n
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.<\/p>\n
1. Data Structure Design<\/h3>\n
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.<\/p>\n
\n const graph = {};\n statements.forEach(([speaker, listener]) => {\n if (!graph[speaker]) {\n graph[speaker] = [];\n }\n graph[speaker].push(listener);\n });\n <\/pre>\n2. Exploration through DFS\/BFS<\/h3>\n
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.<\/p>\n
\n function hasContradictions(speaker) {\n const visited = new Set();\n const stack = [speaker];\n\n while (stack.length) {\n const curr = stack.pop();\n if (visited.has(curr)) {\n return true; \/\/ A contradiction occurs when visiting a node that has already been visited\n }\n visited.add(curr);\n\n if (graph[curr]) {\n graph[curr].forEach(listener => {\n stack.push(listener);\n });\n }\n }\n return false;\n }\n <\/pre>\n3. Check all friends<\/h3>\n
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.<\/p>\n
\n let liarsCount = 0;\n for (let i = 0; i < statements.length; i++) {\n if (hasContradictions(i)) {\n liarsCount++;\n }\n }\n return liarsCount;\n <\/pre>\nFinal Code<\/h2>\n
\n function findLiars(statements) {\n const graph = {};\n statements.forEach(([speaker, listener]) => {\n if (!graph[speaker]) {\n graph[speaker] = [];\n }\n graph[speaker].push(listener);\n });\n\n function hasContradictions(speaker) {\n const visited = new Set();\n const stack = [speaker];\n\n while (stack.length) {\n const curr = stack.pop();\n if (visited.has(curr)) {\n return true; \n }\n visited.add(curr);\n\n if (graph[curr]) {\n graph[curr].forEach(listener => {\n stack.push(listener);\n });\n }\n }\n return false;\n }\n\n let liarsCount = 0;\n for (let i = 0; i < statements.length; i++) {\n if (hasContradictions(i)) {\n liarsCount++;\n }\n }\n return liarsCount;\n }\n\n console.log(findLiars(statements)); \/\/ Output: 1\n <\/pre>\nConclusion<\/h2>\n
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.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"