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 sum = 0;
for (int i = 0; i < a.size(); ++i) {
sum += a[i];
int size = i - head + 1;
if (size >= k) {
if (size > k) {
}
max_sum = max(max_sum, sum);
}
}
}
return max_sum;
}``````

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.

### 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.