Compressed Vector Product - Facebook Top Interview Questions
You are given two integer lists a and b where each list represents a vector in run-length encoded form. For example, a vector [1, 1, 1, 1, 2, 2, 2, 2, 2] is represented as [4, 1, 5, 2]. (There are 4 ones and 5 twos.) Return the dot product of the two vectors a and b. The dot product of a vector [x1, x2, ..., xn] and [y1, y2, ..., yn] is defined to be x1 * y1 + x2 * y2 + ... + xn * yn. Constraints 1 ≤ n ≤ 200,000 where n is the length of a 1 ≤ m ≤ 200,000 where m is the len
View Solution →Eat Bananas in K Hours - Facebook Top Interview Questions
You are given a list of integers piles and an integer k. piles[i] represents the number of bananas on pile i. On each hour, you can choose any pile and eat r number of bananas in that pile. If you pick a pile with fewer than r bananas, it still takes an hour to eat the pile. Return the minimum r required such that you can eat all the bananas in less than or equal to k hours. Constraints n ≤ 100,000 where n is the length of piles n ≤ k Example 1 Input piles = [6, 4, 3]
View Solution →Length of the Longest Path in an N-Ary Tree - Facebook Top Interview Questions
You are given a two-dimensional list of integers edges representing an n-ary tree. Each element in edges contains [u, v] meaning that u is the parent of v. Return the length of the longest path in the tree. Constraints 1 ≤ n ≤ 100,000 where n is the length of edges Example 1 Input edges = [ [1, 2], [1, 3], [1, 4], [4, 5] ] Output 4
View Solution →Longest Consecutively Increasing Substring - Facebook Top Interview Questions
You are given a string s containing lowercase alphabet characters as well as "?". For each "?" you must either delete it or replace it with any lowercase alphabet character. Return the length of the longest consecutively increasing substring that starts with "a". Constraints 1 ≤ n ≤ 100,000 where n is the length of s Example 1 Input s = "bca???de" Output 5 Explanation We can turn s into "bcabcde" and "abcde" is the longest consecutively increasing substring th
View Solution →Matrix Rectangular Sums - Facebook Top Interview Questions
Given a two-dimensional list of integers matrix and an integer k, return a new matrix M of the same dimensions where M[i][j] is the sum of all numbers sum(matrix[r][c]) for all (i - k ≤ r ≤ i + k, j - k ≤ c ≤ j + k) Constraints n, m ≤ 250 where n and m is the number of rows and columns in matrix Example 1 Input matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] k = 1 Output [ [12, 21, 16], [27, 45, 33], [24, 39, 28] ]
View Solution →