Problem # Given a network represented as a graph with n nodes labeled from 0 to n-1 and an array connections where connections[i] = [a, b] indicates that there is a bidirectional road between nodes a and b, your task is to find the node that, if removed, would minimize the connectivity of the network. The connectivity of a network is defined as the number of nodes that are reachable from any node. ...
Problem # You are given a 2D grid map of '1's (land) and '0's (water). An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water. Write an algorithm to find the perimeter of the island in the grid. If there are multiple islands, calculate the perimeter of the largest one. ...
Problem # Given a binary tree where each node can either be 0 or 1, each root-to-leaf path represents a binary number. A leaf is a node with no children. The root is the top node of the tree. Calculate the sum of these numbers. Example: # Input: 1 / \ 0 1 / \ / \ 0 1 0 1 Output: 22 Explanation: The binary numbers are 100, 101, 110, and 111, which sum to 22. ...
Problem # Given an m x n matrix, return all elements of the matrix in spiral order. Example: # Input: [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] Output: [1, 2, 3, 6, 9, 8, 7, 4, 5] Input: [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ] Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] ...
Problem # Given a directed graph, write a function to detect whether the graph contains a cycle. Example: Input: Graph with edges [[0, 1], [1, 2], [2, 0]] Output: True (There is a cycle 0 -> 1 -> 2 -> 0) Solution # Algorithm: Depth-First Search (DFS) Use DFS to detect the presence of a cycle in the graph. The idea is to traverse the graph along a particular path and if during the traversal we revisit a node, then there is a cycle in the graph. ...
Problem # Given a 2D board of letters and a target word, find all occurrences of the word in the board. Solution # Below is the complete Python code for the function find_word_occurrences, which finds all occurrences of a given word in a 2D board of letters. You can use this code in your Python environment: def find_word_occurrences(board, word): if not board or not word: return [] def dfs(board, word, index, x, y): if index == len(word): return True if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or board[x][y] ! ...
Problem # Given the root to a binary search tree, find the second largest node in the tree. Solution # class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value self.left = left self.right = right def find_second_largest(root): """ Function to find the second largest element in a binary search tree. :param root: Root node of the binary search tree :return: Value of the second largest node """ # Helper function to find the rightmost and the parent of rightmost nodes def find_rightmost_and_parent(node): parent = None while node. ...
Problem # Scenario: You are a treasure hunter exploring a maze filled with rooms and tunnels. The maze is represented as a graph, where nodes are rooms and edges are tunnels connecting them. Some rooms contain treasure chests, and some may have locked doors requiring specific keys. You can only move through unlocked doors and have a limited carrying capacity for keys. Your Task: Design an algorithm to find the shortest path from the entrance to the room containing the main treasure, collecting all necessary keys along the way. ...
Problem # The horizontal distance of a binary tree node describes how far left or right the node will be when the tree is printed out. More rigorously, we can define it as follows: The horizontal distance of the root is 0. The horizontal distance of a left child is hd(parent) - 1. The horizontal distance of a right child is hd(parent) + 1. For example, for the following tree, hd(1) = -2, and hd(6) = 0. ...