## Google Interview Question for Software Engineers

• 2

Country: United States

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

Calulcate Array sum[n] where for example sum[8] = input[8] + input[7] + input[6] for k = 3

Calculate Array maxFromLeft[n] where for example maxFromLeft[8] = max (sum[0], sum[1], ..., sum[8])

Calculate Array maxFromRight[n] where for example maxFromLeft[8] = max(sum[8], sum[9], ..., sum[n])

Now iterate over sum[n] and at each iteration consider intermediateSum[i] = maxFromLeft[i] + sum[i] + maxFromRight[i]

Answer: Max( intermediateSum[i] ) where i -> 0 to n - 1

Complexity: O(n)

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

Here is a working dynamic programming iterative solution in C++11.
The solution is O(ranges*data_size) because it does not fully recalculate all following maximums in the row in a loop, but instead just compares value starting at that element with maximum of the previous element. Otherwise the solution would be O(ranges*data_size*data_size). Size complexity is also O(ranges*data_size).
I have not implemented any protection against invalid inputs.

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>

std::pair<int, std::vector<std::pair<int, int>>> max_ranges(const std::vector<int>& data, int ranges, int range_size) {
std::vector<std::vector<int>> cache(ranges + 1, std::vector<int>(data.size()));
std::vector<std::vector<int>> came_from(ranges + 1, std::vector<int>(data.size(), -1));
std::vector<std::vector<int>> starting_from(ranges + 1, std::vector<int>(data.size(), -1));

int last_valid = data.size() - range_size;
std::vector<int>  range_at(last_valid + 1);
range_at[0] = std::accumulate(data.begin(), data.begin() + range_size, 0);
for(int i = 1; i < range_at.size(); ++i)
range_at[i] = range_at[i - 1] - data[i - 1] + data[i + range_size - 1];

cache[1][last_valid] = range_at[last_valid];
starting_from[1][last_valid] = last_valid;
for(int i = last_valid - 1; i >= 0; --i) {
if(range_at[i] >= cache[1][i+1]) {
cache[1][i] = range_at[i];
starting_from[1][i] = i;
} else {
cache[1][i] = cache[1][i+1];
starting_from[1][i] = starting_from[1][i+1];
}
}

for(int range = 2; range <= ranges; ++range) {
last_valid -= range_size;
cache[range][last_valid] = cache[range-1][last_valid + range_size] + range_at[last_valid];
came_from[range][last_valid] = last_valid + range_size;
starting_from[range][last_valid] = last_valid;
}

last_valid = data.size() - range_size;
for(int range = 2; range <= ranges; ++range) {
last_valid -= range_size;
for(int start = last_valid - 1; start >= 0; --start) {
int new_val = range_at[start] + cache[range-1][start + range_size];
if(new_val >= cache[range][start+1]) {
cache[range][start] = new_val;
came_from[range][start] = starting_from[range-1][start + range_size];
starting_from[range][start] = start;
} else {
cache[range][start] = cache[range][start+1];
came_from[range][start] = came_from[range][start+1];
starting_from[range][start] = starting_from[range][start+1];
}
}
}

std::vector<std::pair<int, int>> ranges_res;
for(int range = ranges, cf = 0; range >= 1; --range) {
ranges_res.emplace_back(starting_from[range][cf], starting_from[range][cf] + range_size - 1);
cf = came_from[range][cf];
}

return {cache[ranges][0], std::move(ranges_res)};
}

int main() {
std::vector<int> data = {1, 2, 1, 2, 6, 7, 5, 1};

auto res = max_ranges(data, 3, 2);
std::cout << "Max sum: " << res.first << std::endl;
for(const auto& pr : res.second)
std::cout << pr.first << ", " << pr.second << std::endl;

return 0;
}``````

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

why can't we find window os size k with largest sum 3 times omitting those numbers from the list each time

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

why can't we find window of maximum sum with k numbers 3 times and omitting those numbers from the list in each iteration. It would have the complexity of O(3n)

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

If I understand your proposed solution correctly :

nums = [1,2,1,2,6,7,5,1]

First iteration : picks 6,7 and ignore (6,7)
Second iteration : picks 5,1 and ignore (5,1)
Third iteration : picks 1,2 and ignore (1,2)

Sol : 13 + 6 + 3 = 22. But the actual solution is 23.

Please let me know if I am missing something here.

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

I dont think that works.

think of array [ 1, 2, 2, 1, 2, 1 ], with k = 2
the *only* solution is [ 1, 2 ] [ 2, 1 ] [2, 1]
but if you try to find the best 2-length, it will find [2, 2], and then cannot do the rest.

The first is only acceptable if the others are good too!

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

Find 3 biggest intervals, recurse on non intersecting, find max sum.

``````public static void main(String[] args) throws Exception {
Scanner in = new Scanner(new FileReader("test.txt"));
int n = in.nextInt();
int k = in.nextInt();
int arraySize = in.nextInt();
int[] a = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
a[i] = in.nextInt();
}

List<Interval> intervals = getBiggestIntSum(a, n, k, new ArrayList<>());
}

static List<Interval> getBiggestIntSum(int[] a, int n, int k, List<Interval> exclude) {
Queue<Interval> candidates = new PriorityQueue<>(n);
int left= 0;
int right = 0;
int sum = 0;
while(right < a.length) {
if(right-left <k) {
sum += a[right];
right++;
} else {
boolean intersects = false;
Interval candidate = new Interval(left, right - 1, sum);
for(Interval exc : exclude) {
if (exc.intersects(candidate)) {
intersects = true;
break;
}
}
if(!intersects) {
if(candidates.size() < n) {
} else {
if(candidates.peek().sum < candidate.sum) {
candidates.poll();
}
}
}
sum -= a[left];
left++;
}
}

List<Interval> candidatesList = candidates.stream().collect(Collectors.toList());
if(candidatesList.size() == 1)
return candidatesList;

List<Interval> intersecting = new ArrayList<>();
List<Interval> nonIntersecting = new ArrayList<>();
for (int i = 0; i < candidatesList.size(); i++) {
Interval candidate = candidatesList.get(i);
boolean intersects = false;
for (int j = i+1; j < candidatesList.size(); j++) {
if(candidate.intersects(candidatesList.get(j))) {
intersects = true;
break;
}
}
if(!intersects) {
} else {
}
}

int globalSum = 0;
List<Interval> results = new ArrayList<>();

if(nonIntersecting.size() == n)
return  nonIntersecting;
else if(nonIntersecting.size() > 0) {
List<Interval> newExclude = new ArrayList<>();
List<Interval> tmpResults = getBiggestIntSum(a, n - nonIntersecting.size(), k, newExclude);
int tmpSum = tmpResults.stream().mapToInt(o -> o.sum).sum() + nonIntersecting.stream().mapToInt(o-> o.sum).sum();
if(tmpSum > globalSum) {
globalSum = tmpSum;
results = tmpResults;
}
}

for (int i = 0; i < intersecting.size(); i++) {
Interval candidate = intersecting.get(i);
List<Interval> newExclude = new ArrayList<>();
List<Interval> tmpResults = getBiggestIntSum(a, n -1, k, newExclude);
int tmpSum = tmpResults.stream().mapToInt(o -> o.sum).sum() + candidate.sum;
if(tmpSum > globalSum) {
globalSum = tmpSum;
results = tmpResults;
}
}

return results;
}

static class Interval implements Comparable<Interval> {
int left;
int right;
int sum;

public Interval(int left, int right, int sum) {
this.left = left;
this.right = right;
this.sum = sum;
}

public boolean intersects(Interval interval) {
if(left <= interval.left) {
if(right >= interval.left)
return true;
} else {
if(left <= interval.right)
return true;
}
return false;
}

@Override
public int compareTo(Interval o) {
return Integer.compare(sum, o.sum);
}
}``````

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

Thanks! Good solution sameer. Just a minor correction

intermediateSum[i] = maxFromLeft[i-k] + sum[i] + maxFromRight[i+k]
When considering the max from right and left, we should eliminate the elements that are already a part of the sum[i], such that there is no overlap.

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

``````object MaxWindowSum {

def getMax(numbers: Seq[Int], k: Int): Seq[Seq[Int]] = {
val sums = (0 to (numbers.size - k)).map(i => (i, (i to (i+k-1)).map(numbers(_)).sum)).toList
val sortedSums = sums.sortBy(_._2).reverse

val solution = getMaxInternal(sortedSums, k, 3)
getSolutionWindows(solution, numbers, k)
}

private def checkSolution(solution: Seq[(Int, Int)], n: Int): Seq[(Int, Int)] = if (solution.size == n) solution else Seq()

private def getMaxInternal(idxAndNumber: Seq[(Int,Int)], k: Int, n: Int): Seq[(Int, Int)] = {
val theBest = idxAndNumber.lift(0)
if (theBest.isDefined && idxAndNumber.size >= n) {
if(n == 1) {
//if you are looking for one value only then just take the best
Seq(theBest.get)
} else {
val (rest, overlapped) = idxAndNumber.drop(1).partition(el => {
val dist = math.abs(theBest.get._1 - el._1)
dist >= k
})
val firstSolution = getMaxInternal(rest, k, n - 1) ++ theBest
val firstSolutionValue = calcValue(firstSolution)

if (!overlapped.isEmpty || firstSolution.size < n) {
//check solution for intersected windows
val alternativeSolution = getMaxInternal(idxAndNumber.drop(1), k, n)
val alternativeSolutionValue = calcValue(alternativeSolution)

if (firstSolutionValue >= alternativeSolutionValue)
checkSolution(firstSolution, n)
else {
checkSolution(alternativeSolution, n)
}
} else
checkSolution(firstSolution, n)
}
} else {
//just nothing more to select - no solution
Seq()
}
}

private def calcValue(solution: Seq[(Int,Int)]): Long = solution.map(_._2).sum

private def getSolutionWindows(solution: Seq[(Int, Int)], numbers: Seq[Int], k: Int): Seq[Seq[Int]] =
solution.sortBy(_._1).map(el => numbers.slice(el._1, el._1 + k))

def main(args: Array[String]) {
val solution = getMax(Seq(2,2,4,4,2,2,1,1,1,1,1,1,1,1,1,2,1,2,1,1,1), 3)
//    val solution = getMax(Seq(1,2,1,2,6,7,5,1), 2)
println("solution: %s, value: %d".format(solution, solution.map(_.sum).sum))
}

}``````

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

Recursively searching for max total of sums in the remaining sub-array for each sum in the present array.

``````static void Main(string[] args)
{
int[] arr = new int[] { 1, 2, 1, 2, 6, 7, 5 };
int w = 2; // window size
int c = 3; // window count

int[] startPositions;
var sum = Sum(arr, w, c, out startPositions, 0);
Console.WriteLine(\$"Positions: ({string.Join(", ", startPositions)}), sum = {sum}");
for (var i = 0; i < startPositions.Length; i++)
{
var elements = new int[w];
for (var j = 0; j < w; j++)
elements[j] = arr[startPositions[i] + j];

Console.WriteLine(\$"Sum #{i + 1}: ({string.Join(", ", elements)})");
}
}

public static int Sum(int[] arr, int wsize, int wcount, out int[] startPositions, int currentwcount)
{
//Console.WriteLine(\$"Searching for max {wcount - currentwcount} sums in sub-array: {string.Join(", ", arr)}");
var maxSum = 0;
startPositions = new int[0];
currentwcount++;
if (arr.Length < wsize)
return 0;
var maxIndex = new int[] {  };
for (var i = 0; i + wsize <= arr.Length; i++)
{
var startPos = new int[] { i };
var currentSum = 0;
for (var j = i; j <  i + wsize; j++)
currentSum += arr[j];
if (currentwcount == wcount)
{
if (currentSum > maxSum)
{
maxSum = currentSum;
maxIndex = startPos;
}
}
else if (currentwcount < wcount) // when to exit from recursion
{
//Console.WriteLine(\$"Looking for sum #{currentwcount} in ({string.Join(", ", arr)}) i={i}, max={currentSum}");
// take sub-array between the current window end and the end of the array and find max-sum combinations in it
var subArray = new int[arr.Length - i - wsize];
for (int j = i + wsize, jj = 0; j < arr.Length; j++, jj++)
subArray[jj] = arr[j];
int[] subMsxStartPositions;
var maxSubSum = Sum(subArray, wsize, wcount, out subMsxStartPositions, currentwcount);
var currentSumWithSubSum = currentSum + maxSubSum;
if (currentSumWithSubSum > maxSum)
{
//Console.WriteLine(\$"Found new max total of this array ({string.Join(", ", arr)})={currentSum} and sub-array ({string.Join(", ", subArray)})={maxSubSum}, new MAX = {currentSumWithSubSum}");
maxSum = currentSumWithSubSum;
maxIndex = new int[subMsxStartPositions.Length + 1];
maxIndex[0] = i;
for (var ii = 0; ii < subMsxStartPositions.Length; ii++)
maxIndex[ii + 1] = subMsxStartPositions[ii] + i + wsize;
}
}
}
startPositions = maxIndex;
return maxSum;
}``````

Output:

Positions: (0, 3, 5), sum = 23
Sum #1: (1, 2)
Sum #2: (2, 6)
Sum #3: (7, 5)

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

``````def three_subs(arr):
max_so_far = 0
max_till_now = 0
m = [0]
curr_index = 0
new_introduced = True
for item in arr:
max_till_now += item
if max_till_now < 0:
max_till_now = 0
if not new_introduced:
curr_index += 1
m.append(0)
new_introduced = True
else:
m[curr_index] = max(m[curr_index], max_till_now)
new_introduced = False
return m

arr = [-1, -2, 3, 4, 5, -700, 1, 2, 8, -100, 4, 5, -200, 99]
print three_subs(arr)``````

I think it is just a small modification to Kadane's algorithm

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

``````def three_subs(arr):
max_so_far = 0
max_till_now = 0
m = [0]
curr_index = 0
new_introduced = True
for item in arr:
max_till_now += item
if max_till_now < 0:
max_till_now = 0
if not new_introduced:
curr_index += 1
m.append(0)
new_introduced = True
else:
m[curr_index] = max(m[curr_index], max_till_now)
new_introduced = False
return m

arr = [-1, -2, 3, 4, 5, -700, 1, 2, 8, -100, 4, 5, -200, 99]
print three_subs(arr)``````

It is a small modification to Kadane's algo, I feel.

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.