Snapshottable List - Google Top Interview Questions
Implement a data structure with the following methods: SnapshottableList(int size) which instantiates the list with the given size. The initial value of each element is 0. void set(int idx, int val) which sets the value at index idx to val. int snapshot() which returns the number of times snapshot was called previously. int get(int idx, int snapshotId) which returns the value at index idx after we took snapshot snapshotId. You can assume that snapshotId is valid. Constraints
View Solution →Split String with Same Distinct Counts - Google Top Interview Questions
You are given a lowercase alphabet string s. Return the number of ways to split the string into two strings such that the number of distinct characters in each string is the same. Constraints 1 ≤ n ≤ 100,000 where n is the length of s Example 1 Input s = "abaab" Output 2] = hs.size(); } Explanation We can split it by "ab" + "aab" and "aba" + "ab"
View Solution →Square Submatrix Sum Below Target - Google Top Interview Questions
You are given a two-dimensional list of non-negative integers matrix and a non-negative integer target. Return the area of the largest square sub-matrix whose sum is less than or equal to target. If there's no such matrix, return 0. Constraints 1 ≤ n, m ≤ 250 where n and m are the number of rows and columns in matrix Example 1 Input matrix = [ [3, 2, 1], [2, 0, 7], [1, 1, 9] ] target = 10 Output 4 Explanation This sub-matrix sums to 10:
View Solution →Stacks - Google Top Interview Questions
Given a list of list of positive integers stacks, you can take any stack(s) in stacks and pop any number of elements. Return the maximum sum that can be achieved such that all stacks have the same sum. Constraints n * m ≤ 500,000 where n and m are the number of rows and columns in stacks Example 1 Input stacks = [ [2, 3, 4, 5], [4, 5, 2, 3, 3], [9, 1, 1, 1] ] Output 9 Explanation Here are the operations we can take Pop [5] from the fi
View Solution →Stack Sequence - Google Top Interview Questions
Given a list of distinct integers pushes, and another list of integers pops, return whether this is a valid sequence of stack push and pop actions. Constraints n ≤ 100,000 where n is the length of pushes m ≤ 100,000 where m is the length of pops Example 1 Input pushes = [0, 1, 4, 6, 8] pops = [1, 0, 8, 6, 4] Output True Explanation We can first push [0, 1], then pop both off. Then push [4, 6, 8] and then pop them all off. Example 2 Input pushes = [1,
View Solution →