Unique Paths to Go Home - Google Top Interview Questions
You are given a two-dimensional list of integers edges where each element contains [u, v, distance] representing a weighted undirected graph. You are currently at node 0 and your home is the largest node. You can go from u to v if it's immediately connected and the shortest distance from u to home is larger than the shortest distance from v to home. Return the number of unique paths possible to go from node 0 to home. Mod the result by 10 ** 9 + 7. Constraints 1 ≤ n ≤ 100,000 where n is
View Solution →Virtual Array - Google Top Interview Questions
Implement a virtual array which implements the following methods: void set(int start, int end) which sets the values in the array from [start, end] inclusive to true. boolean get(int idx) which returns true if it is set, otherwise false. Bonus: solve using \mathcal{O}(k)O(k) space total where k is the number of disjoint intervals. Constraints 0 ≤ start ≤ end < 2 ** 31 0 ≤ n ≤ 100,000 where n is the number of calls to set and get Example 1 Input methods = ["constructor"
View Solution →Walled Off 👽 - Google Top Interview Questions
You are given a two-dimensional integer matrix containing 0s and 1s where 0 represents empty space and 1 represents a wall. Return the minimum number cells that need to become walls such that there's no path from the top left cell to the bottom right cell. You cannot put walls on the top left cell and the bottom right cell. You are only allowed to travel adjacently (no diagonal moves allowed), and you can't leave the matrix. Constraints 2 ≤ n, m ≤ 250 where n and m are the number of row
View Solution →Maximal Rectangle
Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 6 Explanation: The maximal rectangle is shown in the above picture. Example 2: Input: matrix = [["0"]] Output: 0 Example 3: Input: matrix = [["1"]] Output: 1 Constraints: rows == matrix.length cols == matrix[i].length 1 <= row, cols <
View Solution →Count and Say
The count-and-say sequence is a sequence of digit strings defined by the recursive formula: countAndSay(1) = "1" countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string. To determine how you "say" a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate eve
View Solution →