Category: Javascript Coding Test

Graphs are powerful data structures for solving various problems. In this post, we will explore how to represent graphs and explain the problem-solving process in detail.

Definition of Graph

A graph is a data structure composed of vertices and edges, where vertices represent objects or nodes, and edges represent relationships between vertices. Graphs can be divided into directed graphs (Directed Graph) and undirected graphs (Undirected Graph).

Additionally, graphs can be weighted (Weighted Graph) or unweighted (Unweighted Graph). In weighted graphs, costs or distances are assigned to edges.

Ways to Represent Graphs

There are two main ways to represent graphs:

• Adjacency Matrix: Represent the relationships between vertices using a two-dimensional array. The size of the array is determined by the number of vertices, and the values in the matrix indicate the presence of an edge between two vertices or include weights.
• Adjacency List: Represent a list of adjacent vertices for each vertex. This method is memory efficient and advantageous for sparse graphs.

Problem: Finding Paths in a Graph

Let’s solve the following problem.

Problem Description: Given a graph with two vertices A and B, write a function to find and print all paths from A to B.

The graph is given as an adjacency list.

Example Problem

Input:
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': ['E'],
    'E': []
}
start = 'A'
end = 'E'

Output:
['A', 'B', 'D', 'E']
['A', 'C', 'D', 'E']
            

Problem-Solving Process

To solve this problem, we will use the Depth-First Search (DFS) algorithm. DFS is an algorithm that explores the depth of the graph to find all possible paths.

Step 1: Define the DFS Function

First, we define a DFS function that explores all paths starting from the current vertex. This function maintains the current path as a list and stores the path when it reaches the target vertex.

function findPaths(graph, start, end, path = [], paths = []) {
    path.push(start); // Add the current vertex to the path

    // Save the path if the target vertex is reached
    if (start === end) {
        paths.push([...path]);
    } else {
        // Call DFS for adjacent vertices
        for (const neighbor of graph[start] || []) {
            findPaths(graph, neighbor, end, path, paths);
        }
    }

    path.pop(); // Remove the current vertex from the path (backtracking)
    return paths; // Return all paths
}
            

Step 2: Define the Graph and Input Values

Now, we define the graph along with the starting and ending vertices.

const graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': ['E'],
    'E': []
};

const start = 'A';
const end = 'E';
            

Step 3: Execute the Function

We will execute the function to find all paths and print the results.

const allPaths = findPaths(graph, start, end);
console.log(allPaths);
            

Final Code

function findPaths(graph, start, end, path = [], paths = []) {
    path.push(start); // Add the current vertex to the path
    if (start === end) {
        paths.push([...path]); // Add the path when it is complete
    } else {
        for (const neighbor of graph[start] || []) {
            findPaths(graph, neighbor, end, path, paths); // Call DFS
        }
    }
    path.pop(); // Backtracking
    return paths; // Return all paths
}

const graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': ['E'],
    'E': []
};

const start = 'A';
const end = 'E';
const allPaths = findPaths(graph, start, end);
console.log(allPaths);
            

Conclusion

In this post, we explained how to represent graphs using JavaScript and how to solve the path-finding problem using DFS. Understanding the essence and applications of graphs is very important as they are useful for solving various real-life problems. I hope you will develop your problem-solving skills by tackling more algorithmic problems in the future.

Hello! Today we will learn about one of the important topics in JavaScript coding tests, ‘Finding the Next Greater Element’. This problem involves finding the next greater number for each element in an array, requiring efficient algorithm design. In this article, we will cover the problem description, approach, and algorithm implementation in detail.

Problem Description

The problem is to find the first number that appears to the right of each element in the given array that is larger than that element. If there is no such number, return -1.

Examples

• Input: [2, 3, 3, 5, 4, 9, 6]
  
  Output: [3, 5, 5, 9, 9, -1, -1]
• Input: [1, 2, 3, 4]
  
  Output: [2, 3, 4, -1]
• Input: [5, 4, 3, 2, 1]
  
  Output: [-1, -1, -1, -1, -1]

Approach to the Problem

There are two approaches to solving this problem. The first is using a simple nested loop, and the second is using a stack. The second method is more efficient in terms of time complexity.

1. Nested Loop Approach

This method involves checking all elements to the right of each element to find the next greater element. Although this method is easy to implement, it has a time complexity of O(N^2), making it inefficient.

function findNextGreaterElements(arr) {
    const result = [];
    const n = arr.length;
    
    for (let i = 0; i < n; i++) {
        let found = false;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] > arr[i]) {
                result[i] = arr[j];
                found = true;
                break;
            }
        }
        if (!found) {
            result[i] = -1;
        }
    }
    return result;
}

// Example usage
console.log(findNextGreaterElements([2, 3, 3, 5, 4, 9, 6]));
// Output: [3, 5, 5, 9, 9, -1, -1]
    

2. Stack Approach

This method uses a stack to solve the problem. Since this method processes each element using a stack, it has a time complexity of O(N) and a space complexity of O(N).

The algorithm is as follows:

1. Initialize the stack.
2. Iterate over each element.
3. If the top element of the stack is smaller than the current element, pop it from the stack and set its next greater element to the current element.
4. Push the index of the current element onto the stack.
5. At the end of the iteration, set remaining elements in the stack to -1.

function findNextGreaterElements(arr) {
    const result = new Array(arr.length).fill(-1);
    const stack = [];
    
    for (let i = 0; i < arr.length; i++) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
            const index = stack.pop();
            result[index] = arr[i];
        }
        stack.push(i);
    }
    
    return result;
}

// Example usage
console.log(findNextGreaterElements([2, 3, 3, 5, 4, 9, 6]));
// Output: [3, 5, 5, 9, 9, -1, -1]
    

Conclusion

The problem of finding the next greater element is a great way to develop algorithmic problem-solving skills by identifying larger numbers that appear later based on the elements of an array. It is important to understand and apply both the simple approach using loops and the efficient approach using stacks. I hope you continue to study more algorithms and data structures through such problems!

References

• Data structures and algorithms: lectures and books
• Online coding test platforms (e.g., LeetCode, HackerRank)
• Official JavaScript documentation

Binary Search is an efficient algorithm for finding a specific value in a sorted array. The basic idea of binary search is to repeatedly narrow down the portion of the array that contains the desired value by splitting the array in half. In this article, we will provide a detailed explanation of the binary search algorithm and solve a problem using it.

Problem Description

The following is a problem that can be solved using binary search:

Problem: Find a specific value in an array using binary search

Given a sorted array nums and an integer target, return the index of target. If target does not exist in the array, return -1. The function assumes that nums is sorted in ascending order.

Examples

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

Principle of the Binary Search Algorithm

The binary search algorithm proceeds with the following steps:

1. Calculate the middle index of the array.
2. Compare the middle value with the desired value (target):
• If the middle value is equal to the target, return the middle index.
• If the middle value is less than the target, search the right half. (from middle index + 1 to the end)
• If the middle value is greater than the target, search the left half. (from the start to middle index – 1)
3. Repeat this process until the exact value is found.

The time complexity of binary search is O(log n), which allows for quick searches in large datasets.

Problem-Solving Process

Now, let’s write the code to solve the above problem. First, we define a function that accepts the array and target.

function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2); // calculate the middle index
        
        if (nums[mid] === target) {
            return mid; // return middle index if found
        } else if (nums[mid] < target) {
            left = mid + 1; // move to the right half
        } else {
            right = mid - 1; // move to the left half
        }
    }

    return -1; // return -1 if the value does not exist
}

Code Explanation

In the above code, the binarySearch function performs binary search on the nums array using the target value as an argument.

1. Sets the search range using the left and right variables. The initial values are the start and end indices of the array, respectively.
2. Uses a while loop to repeat while left is less than or equal to right.
3. Calculates the middle index each iteration and compares the middle value with the target.
4. Adjusts the search range based on conditions and ultimately returns -1 if the value is not found.

Example Execution

Below is an example execution of the binary search function:

const nums = [-1,0,3,5,9,12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Result Analysis

Through the above examples, we can see that the function outputs the correct index. binarySearch(nums, 9) returns 4, and binarySearch(nums, 2) returns -1.

Conclusion

Binary search is a very efficient search algorithm that allows for a quick search of desired values in sorted data. I hope this lecture has helped you understand the principles and implementation methods of binary search. Since it is also a common algorithm that appears in coding tests, it is essential to familiarize yourself with it and practice.

Welcome to the blog! Today, we will learn both the theory and practical implementation by solving problems using DFS (Depth-First Search) and BFS (Breadth-First Search) algorithms.

Problem Description

We will tackle the problem of finding the shortest path to a specific node in a given undirected graph. The graph is provided in the form of an adjacency list, and the shortest path can be found using BFS. DFS can be used to verify the existence of a path rather than finding the shortest path.

Problem

Input:
- n: number of vertices (1 ≤ n ≤ 10^4)
- edges: list of edges (undirected)
- start: starting vertex
- end: ending vertex

Output:
- List of edges that form the shortest path from start to end
            

Example

Input: n = 5, edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]], start = 1, end = 5

Output: [1, 2, 4, 5] or [1, 3, 4, 5]

Theory

DFS (Depth-First Search)

DFS is a method that starts from a node in the graph and explores as far as possible along each branch before backtracking. This algorithm can be implemented recursively or using a stack. The advantage of DFS is its low memory usage, making it useful when deep node exploration is needed.

BFS (Breadth-First Search)

BFS explores all neighboring nodes at the present depth prior to moving on to nodes at the next depth level. It is implemented using a queue and is particularly suitable for finding the shortest path. BFS is very useful in finding the shortest path, ensuring that it exists if a shortest path is available.

Solution

Step 1: Build the Graph

First, let’s build the graph using an adjacency list.

function buildGraph(n, edges) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u); // Since it's an undirected graph, add both ways
    }
    return graph;
}

const n = 5;
const edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]];
const graph = buildGraph(n, edges);
console.log(graph);
            

Step 2: Implement BFS

Now, let’s find the shortest path from the starting vertex to the ending vertex using BFS.

function bfs(graph, start, end) {
    const queue = [[start]];
    const visited = new Set([start]);

    while (queue.length > 0) {
        const path = queue.shift();
        const node = path[path.length - 1];

        if (node === end) {
            return path; // Return the shortest path found
        }

        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([...path, neighbor]); // Add neighboring node to current path
            }
        }
    }
    return []; // Return empty array if no path found
}

const start = 1,
      end = 5;

const result = bfs(graph, start, end);
console.log(result);
            

Step 3: Implement DFS

Now, let’s use DFS to check the existence of a path and how to find that path.

function dfs(graph, start, end, visited = new Set(), path = []) {
    visited.add(start);
    path.push(start);
    
    if (start === end) {
        return path; // Return when the path is found
    }

    for (const neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            const resultPath = dfs(graph, neighbor, end, visited, [...path]);
            if (resultPath.length > 0) {
                return resultPath; // Return when a path is discovered
            }
        }
    }
    return []; // Return empty array if no path found
}

const dfsResult = dfs(graph, start, end);
console.log(dfsResult);
            

Hello, everyone! In this post, we will explore the ‘Least Common Ancestor (LCA)’ problem, which frequently appears in JavaScript coding tests. This problem is a very important concept when dealing with tree structures. We will implement an algorithm to find the least common ancestor and take a detailed look at the process.

Problem Description

This is the problem of finding the least common ancestor of two nodes in a given binary tree. The tree follows these rules:

• Each node can have at most two children.
• The given two nodes always exist in the tree.

Input

• Address of the root node of the tree (root)
• Address of the first node (node1)
• Address of the second node (node2)

Output

Print the node value of the least common ancestor of the two nodes.

Example

Input:
          3
         / \
        5   1
       / \ / \
      6  2 0  8
        / \
       7   4
       
       node1 = 5, node2 = 1
       
Output:
3

Solution

There can be several approaches to solve this problem. However, the most common approach is to use DFS (Depth First Search). This method allows us to find the least common ancestor by visiting each node. Let’s examine this process step by step.

Step 1: Define the Tree Structure

First, we need to create a class defining the tree. In JavaScript, a tree node can generally be defined as follows:

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null; // left child
        this.right = null; // right child
    }
}

Step 2: Create the Tree

Let’s write sample code to create the tree. The following code creates a tree like the one in the example above:

const root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(2);
root.right.left = new TreeNode(0);
root.right.right = new TreeNode(8);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);

Step 3: Implement the DFS Algorithm

Now it’s time to implement the DFS algorithm. The process for finding the least common ancestor follows these steps:

1. If the current node is null, return null.
2. If the current node is equal to node1 or node2, return the current node.
3. Recursively call the left and right children to obtain the results.
4. If both left and right child node results are not null, the current node is the least common ancestor.
5. If only one of the left or right children is not null, return the non-null child.

function lowestCommonAncestor(root, node1, node2) {
    if (root === null) return null;
    if (root.value === node1.value || root.value === node2.value) return root;

    const left = lowestCommonAncestor(root.left, node1, node2);
    const right = lowestCommonAncestor(root.right, node1, node2);

    if (left && right) return root;
    return left ? left : right;
}

Step 4: Output the Result

Now that the least common ancestor algorithm is complete, let’s test it:

const lca = lowestCommonAncestor(root, root.left, root.right); // node1: 5, node2: 1
console.log(lca.value); // 3

Summary and Conclusion

In this post, we covered the Least Common Ancestor (LCA) problem. We defined the tree structure, implemented an algorithm using DFS, and verified the results through examples. The key point is that this algorithm visits each node through recursive calls, structurally setting conditions to find the least common ancestor.

Such problems have various forms, so it is important to practice solving different types of problems. We will continue to introduce various algorithms that will help you prepare for JavaScript coding tests, so please stay tuned!

References

• GeeksforGeeks – Lowest Common Ancestor in a Binary Tree
• ProgramCreek – LeetCode: Lowest Common Ancestor of a Binary Tree

I hope this helps you prepare for your coding tests. Thank you!