Problem In a directed graph, each node is assigned an uppercase letter. We define a path’s value as the number of most frequently-occurring letter along that path. For example, if a path in the graph goes through “ABACA”, the value of the path is 3, since there are 3 occurrences of ‘A’ on the path. Given a graph with n nodes and m directed edges, return the largest value path of the graph. If the largest value is infinite, then return null. ...
Problem Using a function rand7() that returns an integer from 1 to 7 (inclusive) with uniform probability, implement a function rand5() that returns an integer from 1 to 5 (inclusive) Solution Method 1 - Using rejection sampling The idea is to use rand7() to generate numbers from 1 to 7, and map these numbers to values between [1, 5]. We need to ensure that the probabilities remain uniform despite the discrepancy between the range of 7 and 5, and we can use acceptance-rejection method to avoid bias. ...
Problem On our special chessboard, two bishops attack each other if they share the same diagonal. This includes bishops that have another bishop located between them, i.e. bishops can attack through pieces. You are given N bishops, represented as (row, column) tuples on an M by M chessboard. Write a function to count the number of pairs of bishops that attack each other. The ordering of the pair doesn’t matter: (1, 2) is considered the same as (2, 1). ...
Problem A knight’s tour is a sequence of moves by a knight on a chessboard such that all squares are visited once. Given N, write a function to return the number of knight’s tours on an N by N chessboard. We have already see Knight’s Tour Problem Examples Example 1: Input: n = 5 Output: 1728 ...
Problem Implement a file syncing algorithm for two computers over a low-bandwidth network. What if we know the files in the two computers are mostly the same? Solution Method 1 - Fingerprint comparison 1. Initial Handshake: Each computer calculates a fingerprint (hash) for each file it possesses. This could be a checksum (MD5, SHA-1) or a stronger cryptographic hash (SHA-256). One computer (initiator) sends the list of file fingerprints to the other computer (responder). 2. Fingerprint Comparison: ...
Problem Given an undirected graph represented as an adjacency matrix and an integer k, write a function to determine whether each vertex in the graph can be colored such that no two adjacent vertices share the same color using at most k colors. Examples Example 1: --- title: Input Graph --- graph LR; 0 --- 1 & 2 & 3 1 --- 2 2 --- 3 ...
Problem Implement locking in a binary tree. A binary tree node can be locked or unlocked only if all of its descendants or ancestors are not locked. Design a binary tree node class with the following methods: is_locked, which returns whether the node is locked lock, which attempts to lock the node. If it cannot be locked, then it should return false. Otherwise, it should lock it and return true. unlock, which unlocks the node. If it cannot be unlocked, then it should return false. Otherwise, it should unlock it and return true. You may augment the node to add parent pointers or any other property you would like. You may assume the class is used in a single-threaded program, so there is no need for actual locks or mutexes. Each method should run in O(h), where h is the height of the tree. ...
Problem You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on. Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board. ...
Problem You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API: record(order_id): adds the order_id to the log get_last(i): gets the ith last element from the log. i is guaranteed to be smaller than or equal to N. You should be as efficient with time and space as possible. ...
Problem To estimate π using the Monte Carlo method, we’ll utilize the concept of randomly generating points within a square and determining how many fall inside a quarter circle. Monte Carlo Method Lets do the setup: Imagine a square with side length 2 centered at the origin, with coordinates ranging from (-1, -1) to (1, 1). Inside this square, there is a quarter circle of radius 1, also centered at the origin. The area of the square is 4 (since side length is 2), and the area of the quarter circle is (πr^2 / 4 = π/4) (since r=1). i.e. Let B be area of square, and A be area of circle $$ B = 4r^2 $$ ...