Google Interview Question
Country: Canada
Interview Type: Written Test
To solve it as stated before we can argue the solutions if the k elements have to be contiguous or not.
Let's start when the elements don't need to be contiguous. The naive solution is is to compute all the possible combinations of k elements and return the maximum sum. The cost for this solution is factorial (from the cost of computing the combinations, computing the sum of k elements is constant).
Code in Python:
from itertools import combinations
def getMaxKSum(s, k):
max_sum = 0; numbers = []
for c in combinations(s, k):
r = sum(c)
if r > max_sum:
max_sum = r
numbers = c
return r, numbers
We can improve the cost if we sort the array. In this case the cost would be nlogn from the cost of sorting the array. Solution in python
def getMaxKSum(s, k):
return sorted(s)[k:]
We can improve the cost even further using a heap. For this case the cost is nlogk. Solution in python
from heapq import nlargest
def getMaxKSum(s, k):
return nlargest(s, k)
If it has to be contiguous we can just create a window of k elements to traverse the array. The cost is linear. Functional solution in python
def get_chunks(s, k, step=1):
for x in xrange(0, len(s)-k+step, step):
yield s[x:x+k]
def getMaxKSum(s, k):
return max(map(sum, get_chunks(s, k)))
public static void main(String[] args) {
int k = 3;
Integer a[] = { 1, 2, 3, 4, 5, 6, 1, 2, 3 };
System.out.println("sds");
Queue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < k; i++) {
queue.add(a[i]);
}
for (int i = k; i <= a.length - 1; i++) {
if (a[i] > queue.peek()) {
int remove = queue.poll();
queue.add(a[i]);
}
}
System.out.println(queue);
}
public static void main(String[] args) {
int k = 3;
Integer a[] = { 1, 2, 3, 4, 5, 6, 1, 2, 3 };
System.out.println("sds");
Queue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < k; i++) {
queue.add(a[i]);
}
for (int i = k; i <= a.length - 1; i++) {
if (a[i] > queue.peek()) {
int remove = queue.poll();
queue.add(a[i]);
}
}
System.out.println(queue);
}
public class MaxSumSubArray {
public static int maxSum(int[] array) {
int maxSoFar = 0;
int maxEndingHere = 0;
for(int i = 0; i < array.length; i++) {
maxEndingHere += array[i];
if (maxSoFar < maxEndingHere) {
maxSoFar = maxEndingHere;
}
if (maxEndingHere < 0) {
maxEndingHere = 0;
}
}
return maxSoFar;
}
public static void main(String[] args) {
int[] array = {4, -1, 5, -5, 1};
System.out.println(maxSum(array));
}
}
int MaxSubarrayK(vector<int> const &a, int k) {
int max_sum = numeric_limits<int>::min();
if (k > 0 &&
k <= a.size())
{
int head = 0;
int sum = 0;
for (int i = 0; i < a.size(); ++i) {
sum += a[i];
int size = i - head + 1;
if (size >= k) {
if (size > k) {
sum -= a[head++];
}
max_sum = max(max_sum, sum);
}
}
}
return max_sum;
}
Does it need to be a contiguous subarray say (1,2,3,4,5,6,1,2,3) k = 3 = (4,5,6) or
- guilhebl June 21, 2017can it be a non-contiguous subarray? say (8,2,3,4,8,6,1,2,8) k = 3 = (8,8,8)
One possible implementation:
if K = N (size of array) return sum of array
else:
if contiguous: (easy case)
Build a subarray of size K starting from (0 ... k)
use 2 vars i and j i = 0, j = k
iterate from i ... n - k
check each element and current sum (removing previous element and adding new one)
return maxSUM
else (if non-contiguous):
use a Min Heap (PriorityQueue) of size K (insert first K elements into it)
iterate from 0 ... N-1
for each a[i] element compare if a[i] > queue.peek() // min element of queue
if greater then: queue.poll // remove min element and queue.add(a[i])
at the end return poll all remaining elements of queue ( Max K elements found )