Google Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
6
of 6 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)

- sameer March 18, 2017 | Flag Reply
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;
}

- losmi March 14, 2017 | Flag Reply
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

- rishabh mittal March 15, 2017 | Flag Reply
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)

- mittalrishabh March 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Vijay March 16, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- NoName March 16, 2017 | Flag
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) {
                        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);
        }
    }

- ak_domi March 16, 2017 | Flag Reply
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.

- dontknow March 18, 2017 | Flag Reply
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))
  }

}

- kryzoo.m March 20, 2017 | Flag Reply
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)})");
    }
    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)

- goabove1970 March 20, 2017 | Flag Reply
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

- Abhishek June 15, 2017 | Flag Reply
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.

- abhishek6498 June 15, 2017 | Flag Reply


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