Facebook Interview Question
Developer Program EngineersCountry: United States
Questions to ask the interviewer
- does the array contain negative numbers.
- are we trying to find the sum of consecutive numbers in a subarray.
- if it's not consecutive, construct a min heap using priority queue.
The code below is to find the sum of consecutive numbers in a subarray using the sliding window method.
Time: O(N)
Space: O(1)
public int maxSumSubArray(int[] input, int k) {
int n = input.length;
if(k > n || k == n) return 0;
int sum = input[0];
for(int i = 1; i < k; i++) {
sum += input[i];
}
int maxSum = sum;
for(int i = k; i < n; i++) {
sum = sum - input[i - k] + input[i];
if(sum > maxSum) {
maxSum = sum;
}
}
return maxSum;
}
Right. The question can be interpreted in many ways, so something to discuss with the interviewer.
I assumed the subset would be of consecutive elements. My solution is a O(n) way of finding K consecutive elements.
If the ask is "max of any k numbers", then using a min heap (klogn + n) is the most optimal way.
Taking into account fi they want:
- to find the max sum of consecutive numbers
- the array contains negative numbers
- sum array length may be less than or equal to a size K
int MaximumSum(int[] arr, int subLength){
var maxSum = 0;
var currentSum = 0;
for(int i = 0; i < arr.Length + subLength; i ++){
if(i < arr.Length){
currentSum += arr[i];
}
var startIndex = i - subLength;
if(startIndex >= 0){
currentSum -= arr[startIndex];
}
maxSum = Math.Max(maxSum, currentSum);
}
return maxSum;
}
int MaximumSum(int[] arr, int subLength){
var maxSum = 0;
var currentSum = 0;
for(int i = 0; i < arr.Length + subLength; i ++){
if(i < arr.Length){
currentSum += arr[i];
}
var startIndex = i - subLength;
if(startIndex >= 0){
currentSum -= arr[startIndex];
}
maxSum = Math.Max(maxSum, currentSum);
}
return maxSum;
}
Expected O(n)
int maxSum(int[] a, int k) {
quickPartition(a, k);
int sum = 0;
for(int i = 0; i < k; i++)
sum += a[i];
return sum;
}
void quickPartition(int[] a, int k) {
int st = 0;
int en = a.length;
while(st < en) {
int p = partition(a, st, en);
if(p == k)
return;
if(p < k)
st = p;
else
en = p;
}
}
int partition(int[] a, int st, int en) {
swap(a, st, st + new Random().nextInt(en - st));
int p = st;
for(int i = st + 1; i < en; i++)
if(a[i] >= a[st])
swap(a, i, ++p);
swap(a, st, p);
return p + 1;
}
void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
@O(N) approach
I like the solution, but this is O(N * log(N))
You essentially have to scan the entire array for the first partition, then continue to half it until p == k.
I like the solution, and studied it for a while to make sure I knew exactly what you were doing. But this method contains a certain amount of luck to find the right number which has K elements greater than it. In theory, this could loop forever.
I like the solution, but this is O(N * log(N))
You essentially have to scan the entire array for the first partition, then continue to half it until p == k.
I like the solution, and studied it for a while to make sure I knew exactly what you were doing. But this method contains a certain amount of luck to find the right number which has K elements greater than it. In theory, this could loop forever.
Modification of QuickSelect to partition by the kth largest element and sum the larger elements left from it. Runtime same as with QuickSelect, O(N)
In scala:
object MaxSubsetSum extends App {
val list = Array(8, -5, 3, 7, 9 ,0)
println(largestSubsetSum(3, 0, list.length - 1))
def swap(from: Int, to: Int): Unit = {
val temp = list(to)
list(to) = list(from)
list(from) = temp
}
def partition(left: Int, right: Int, pivot: Int): Int = {
var index = left
var i = left
swap(pivot, right)
while (i < right) {
if (list(i) > list(right)) {
swap(i, index)
index += 1
}
i += 1
}
swap(right, index)
index
}
def largestSubsetSum(k: Int, left: Int, right: Int): Int = {
val v = partition(left, right, (right - left) / 2)
if (v == k) list.take(k).sum
else if (v < k) largestSubsetSum(k, v + 1, right)
else largestSubsetSum(k, left, v - 1)
}
}
public int sumK(int[] list, int k) {
if (k > list.length) return ERROR;
int sum = 0, maxSum = 0, l = 0;
for (int i = 0; i < k; i++) {
sum += list[i];
}
maxSum = sum;
for (int j = k; j < list.length; j++, l++) {
sum = sum + list[j] - list[l];
if (sum > maxSum) maxSum = sum;
}
return maxSum;
}
We can find K largest elements, using a min heap, and find sum of the K largest elements. O(N * log K) time and O(K) space.
- Alex December 16, 2017