## Google Interview Question

Country: Canada
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
2
of 2 vote

Does it need to be a contiguous subarray say (1,2,3,4,5,6,1,2,3) k = 3 = (4,5,6) or
can 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 )

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``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);``

``}``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``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);``

``}``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

For the non contiguous part, I think the largest sum would be of the largest k elements in the array. Just use sorting or heap data structure to solve.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Non-contiguous subarrays are usually referred to as Subsequences.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More