February 10, 2024
Problem Statement # You are given a 2D integer grid terrain representing the elevation of a landscape. Imagine that rain falls uniformly across the area and is trapped depending on the terrain’s shape. Calculate the total volume of water that would be trapped.
Example:
Input: terrain = [ [2, 3, 5, 1], [6, 5, 3, 4], [3, 1, 2, 5] ] Output: 7 Solution Approach # This problem can be effectively solved using a combination of Breadth-First Search (BFS) and a priority queue (Min-Heap).
...
January 14, 2024
Problem # Given a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).
Example:
Input: 3 / \ 9 20 / \ 15 7 Output: [[3], [20, 9], [15, 7]] Solution Approach # The solution uses a breadth-first search (BFS) approach with a queue, alternating the direction of traversal with each level of the tree.
...
December 27, 2023
Problem # Given a 2D grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Solution 1 # Here’s the Python code to count the number of islands in a 2D grid map, where ‘1’s represent land and ‘0’s represent water:
def numIslands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) visited = set() islands = 0 def dfs(r, c): # If the current cell is out of bounds, water, or already visited, return if (r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0' or (r, c) in visited): return # Mark the cell as visited visited.
...
December 26, 2023
Problem # In a given grid, each cell can have one of three values: 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any fresh orange that is adjacent to a rotten orange becomes rotten. Find the minimum number of minutes that must elapse until no cell has a fresh orange.
Solution # To solve this problem, we can use the Breadth-First Search (BFS) algorithm. The idea is to iteratively spread the rot from the rotten oranges to the adjacent fresh oranges and track the time taken for all fresh oranges to become rotten.
...
December 24, 2023
Problem # Print the nodes in a binary tree level-wise. For example, the following should print 1, 2, 3, 4, 5.
1 / \ 2 3 / \ 4 5 Solution # Here is the Python code to print the nodes of a binary tree level-wise:
class Node: def __init__(self, key): self.left = None self.right = None self.val = key def printLevelOrder(root): if not root: return queue = [] queue.
...
December 24, 2023
Problem # Given two words, find the shortest chain of words you can create by changing only one letter at a time, such that each word in the chain is a valid English word. You can use a dictionary or online database to check word validity.
Solution # Solving the “Word Ladder” problem in Python typically involves using a breadth-first search (BFS) algorithm to traverse through word transformations.
Here’s the general idea of the solution:
...
December 14, 2023
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.
...
December 14, 2023
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.
...