Google Interview Question
Software EngineersCountry: United States
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;
}
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)
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.
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) {
candidates.add(candidate);
} else {
if(candidates.peek().sum < candidate.sum) {
candidates.poll();
candidates.add(candidate);
}
}
}
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) {
nonIntersecting.add(candidate);
} else {
intersecting.add(candidate);
}
}
int globalSum = 0;
List<Interval> results = new ArrayList<>();
if(nonIntersecting.size() == n)
return nonIntersecting;
else if(nonIntersecting.size() > 0) {
List<Interval> newExclude = new ArrayList<>();
newExclude.addAll(exclude);
newExclude.addAll(nonIntersecting);
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;
results.addAll(nonIntersecting);
}
}
for (int i = 0; i < intersecting.size(); i++) {
Interval candidate = intersecting.get(i);
List<Interval> newExclude = new ArrayList<>();
newExclude.addAll(exclude);
newExclude.add(candidate);
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;
results.add(candidate);
}
}
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);
}
}
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))
}
}
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)})");
}
Console.ReadLine();
}
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)
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
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.
Calulcate Array sum[n] where for example sum[8] = input[8] + input[7] + input[6] for k = 3
- sameer March 18, 2017Calculate 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)