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 →Unique Characters of Every Substring - Microsoft Top Interview Questions
Given a lowercase alphabet string s, return the sum of the number of characters that are unique in every substring of s. Mod the result by 10 ** 9 + 7. Constraints n ≤ 100,000 where n is the length of s Example 1 Input s = "aab" Output 6 Explanation Here are the substrings and their counts: "a" - 1 "a" - 1 "b" - 1 "aa" - 0 (since "a" is not unique) "ab" - 2 "aab" - 1 ("since "a" is not unique)
View Solution →Minimum Removals to Make Mountain List - Microsoft Top Interview Questions
You are given a list of integers nums. Return the minimum number of elements we can remove from nums such that the list becomes a mountain list. A mountain list is a list that is first strictly increasing and then strictly decreasing. Each of the increasing and decreasing parts should be non-empty. You can assume that a solution exists. Constraints n ≤ 100,000 where n is the length of nums Example 1 Input nums = [1, 6, 5, 7, 4] Output 1 Explanation We can re
View Solution →Maximum Stack - Microsoft Top Interview Questions
Implement a maximum stack with the following methods: MaximumStack() constructs a new instance of a maximum stack append(int val) appends val to the stack peek() retrieves the last element in the stack max() retrieves the maximum value in the stack pop() pops and returns the last element in the stack popmax() pops and returns the last occurrence of the maximum value in the stack You can assume that for peek, max, pop and popmax, the stack is non-empty when they are called.
View Solution →