Company/Google

Problem You are in an infinite 2D grid where you can move in any of the 8 directions: (x,y) to (x+1, y), (x - 1, y), (x, y+1), (x, y-1), (x-1, y-1), (x+1,y+1), (x-1,y+1), (x+1,y-1) ...

Problem You are given an N by M 2D matrix of lowercase letters. Determine the minimum number of columns that can be removed to ensure that each row is ordered from top to bottom lexicographically. That is, the letter at each column is lexicographically later as you go down each row. It does not matter whether each row itself is ordered lexicographically. For example, given the following table: ...

Problem You are given an integer n and an array of unique integers blacklist. Design an algorithm to pick a random integer in the range [0, n - 1] that is not in blacklist. Any integer that is in the mentioned range and not in blacklist should be equally likely to be returned. Optimize your algorithm such that it minimizes the number of calls to the built-in random function of your language. ...

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 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 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 $$ ...