Google Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
8
of 10 vote

Can you please explain the problem little bit more?

- kathirkarthick12 November 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Clear problem statement:

We are given n stacks of different sizes. We can perform k pop operations. Each operation can be done on any stack and in any order. The element popped is added to the result. What is the maximum result we can obtain after performing k operations?

EX:
S1=[1,1,100,3]
S2=[2000,2,3,1]
S3=[10,1,4]

k = 3

the maximum sum of the 3 numbers in the above stacks is 3+100+4=107.

for k = 4 the answer would have been 2000 + 2 + 3 + 1

- Rajat.nitp July 21, 2020 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

function select (M, stacks, selections) {
  var selecteds = []
  if (!M) {
    return selections
  } else {
    var _stacks = stacks
    var stacks = []
    for (var i = 0; i < _stacks.length; ++i) {
      stacks[i] = _stacks[i].slice()
    }
    var _selections = selections
    for (i = 0; i < stacks.length; ++i) {
      var stack = stacks[i]
      var popped = stack.pop()
      selections = _selections.slice()
      selections.push(popped)
      selecteds.push(select(M - 1, stacks, selections))
    }
    var local_max = 0;
    var local_selected = null
    for (i = 0; i < selecteds.length; ++i) {
      var selected = selecteds[i]
      var sum = 0
      for (var j = 0; j < selected.length; ++j) {
        sum += selected[j]
      }
      if (sum > local_max) {
        local_max = sum
        local_selected = selected
      }
    }
    return local_selected
  }
}
function selectMaximum (M, stacks) {
  var selected = select(M, stacks, [])
  var sum = 0
  for (var i = 0; i < selected.length; ++i) {
    sum += selected[i]
  }
  console.log(selected, sum)
}

selectMaximum(3, [[1,1,100,3],[2000,2,3,1],[10,1,4]])

- srterpe December 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

***********************Explanation***********************
We have two options from given stack -> i) Do not take any element from ith stack
ii) Take elements from ith stack.

We will use dp here.
Definition of dp -> choose j elements from ith stack.
State of dp -> dp[i][j] = max(dp[i][j], dp[i-1][0,1,2...k]+(sum of top j elements from stack i)

**********************Code*************************
int sum(int stackI[], int p, int n)
{
int j=n-1;
int sumOfTopElement=0;
while(p)
{
sumOfTopElement += stackI[j--];
p--;
}
}
void solution(int stack[][],int K)
{
int dp[stack.size()][K+1];
memset(dp, 0, sizeof dp);
for(int k=1;k<=K;k++)
{
if(stack[0].size()>=k)
dp[i][k]=sum(stack[0],k,stack[0].size());
}
for(int i=1;i<n;i++)
{
for(int k=1;k<=K;k++)
{
dp[i][k]=dp[i-1][k];
for(int j=1;j<=k;j++)
{
if(stack[i].size()>=j)
dp[i][k]=max(dp[i][k],dp[i-1][k-j]+sum(stack[i],j,stack[i].size()));
}
}
}
}

- nikitakumari01021998 July 21, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be solved in O(M.N^2) using dynamic programming.
equation would be

recurr(n,sum) = for(i in 1 to m) {max( recurr(n + 1, sum(i)+1) + stacks[i].get(sum[i]))};

public class A {
    static List<Integer> stacks[] = new ArrayList[3];

    static int N = 3, m = 3;
    static Map<String, Integer> map = new HashMap<>();

    public static void main(String s[]){
        stacks[0] = new ArrayList<>();
        stacks[0].add(3);
        stacks[0].add(100);
        stacks[0].add(1);
        stacks[0].add(1);
        stacks[1] = new ArrayList<>();
        stacks[1].add(1);
        stacks[1].add(3);
        stacks[1].add(2);
        stacks[1].add(2000);
        stacks[2] = new ArrayList<>();
        stacks[2].add(4);
        stacks[2].add(1);
        stacks[2].add(10);

        Integer sum[] = new Integer[3];
        for(int i = 0;i<sum.length;i++)
            sum[i] = -1;

        System.out.println(recurr(0, sum));

    }

    public static int recurr(int n, Integer sum[]){
        if(n == N){
            return 0;
        }
        String s = Arrays.toString(sum) + n;
        if(map.containsKey(s)){
            return map.get(s);
        }
        int max = 0;
        for(int i = 0;i<sum.length;i++){
            sum[i]++;
            if(stacks[i].size() > sum[i]) {
                max = Math.max(recurr(n + 1, sum) + stacks[i].get(sum[i]), max);
            }
            sum[i]--;
        }
        map.put(s,max);
        return max;

    }





}

- Paras November 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please explain your understanding of this problem? It does not make any sense to me as stated. Thanks!

- Terio November 30, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Problem can be reduced to knapsack. Weight of the item is number of times needed to pop the stack. Value is the sum of items popped till item reached. Gives O(M * total number of items) solution

- Anonymous November 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Could you please explain your understanding of this problem? It does not make any sense to me as stated. Thanks!

- Terio November 30, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem cannot be reduced to knapsack since if we take a deep element from the stack, all elements above it become unavailable. This does not happen in knapsack problem.

- Rajat.nitp July 21, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Easy recursive solution. I use the variable "currentStack" in order to avoid repeated states (for example poping from the first stack and then the second one is the same as poping from the second one and then from the first one).

private List<Stack<Integer>> stacks;
private int stacksSize;
private int m, sum;
private int max;
private int currentStack;


public int getMaximumSum(Stack<Integer>[] stacks, int m){
	this.max = Integer.MIN_VALUE;
	this.stacks = stacks;
	this.stacksSize = stacks.length;
	this.m = m;
	this.currentStack = 0;


	getMaximumSum();


	return max;


}


public void getMaximumSum(){
	if(m == 0){
		if(sum > max)
			max = sum;
	}else{
		int aux = currentStack;
		for(int i = currentStack; i < stacksSize; i++){
			Stack stack = stacks[i];
			currentStack = i;
			if(!stack.isEmpty()){
				m--;
				int num = stack.pop();
				sum += num;
				getMaximumSum();
				sum -= num;
				m++;
			}


		}
		currentStack = aux;
	}


}

- libertythecoder November 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the runtime complexity of this solution?

- Shivam May 15, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

problem not clear

- vijay November 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a typo : the maximum sum of the 3 numbers in the above stacks is 3+100+4=107.
sorry for that

- Anonymous November 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

upar hi edit karna tha na..question invalid samjh liye..mujhe google me pucha

- kumarswamy April 26, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks bhai , paras bhai..gazab

- thanks_bhai May 09, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Q: Given N stacks. Each stack contains Si elements.
#    Find the max sum of M numbers in N stacks
#
# Ex: S = [1, 200, 1, 2, 3]
#     200 is max, but you must traverse 3, 2, 1 first.
#
# What is a better solution?


def sum_of_stacks(stacks):

    maximum_values = []

    for stack in stacks:
        maximum_values.append(find_max(stack))
        
    return sum(maximum_values)


def find_max(stack):
    is_maximum_value = 0
    
    for i in stack:
        if i > is_maximum_value:
            is_maximum_value = i
            
    return is_maximum_value

print sum_of_stacks([[1, 8, 100, 3], [2000, 2, 3, 1], [10, 1, 4]])

- Tom Cusack December 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Q: Given N stacks. Each stack contains Si elements.
#    Find the max sum of M numbers in N stacks
#
# Ex: S = [1, 200, 1, 2, 3]
#     200 is max, but you must traverse 3, 2, 1 first.
#
# What is a better solution?


def sum_of_stacks(stacks):

    maximum_values = []

    for stack in stacks:
        maximum_values.append(find_max(stack))

    return sum(maximum_values)


def find_max(stack):
    is_maximum_value = 0

    for i in stack:
        if i > is_maximum_value:
            is_maximum_value = i

    return is_maximum_value

print sum_of_stacks([[1, 8, 100, 3], [2000, 2, 3, 1], [10, 1, 4]])

- Tom Cusack December 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using Python to achieve this in O(N * M) time, where N is the number of stacks, and M is the size of the array.

def sum_of_stacks(stacks):

    maximum_values = []

    for stack in stacks:
        maximum_values.append(find_max(stack))

    return sum(maximum_values)


def find_max(stack):
    is_maximum_value = 0

    for i in stack:
        if i > is_maximum_value:
            is_maximum_value = i

    return is_maximum_value

print sum_of_stacks([[1, 8, 100, 3], [2000, 2, 3, 1], [10, 1, 4]])

- Tom Cusack December 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What I understand, you can pick N numbers from all the stacks together.

Does the following algorithm work?

1. Maintain a Maxheap of size N (We can get maximum N numbers).
2. Initially get one value from each stack into the heap.
3. When the heap is full of size N, extract the max. If the extracted value is from stack Si, pop another value from Si and put it again into the heap.
4. Repeat 3 until get maximum N numbers.

Complexity: total 2N heap pop() and 2NLogN for heap insert and extraction.

- prosun.csedu December 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will not work.

[1,100,1,2]
[2,3,4,5]

Find 3 element max.

- Rashid November 17, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

To make the question more clear, the m number should come from any stacks not only one stack. To reach the deep stack element, you need to choose the element before. [200,1,2,3], if you want to choose 200, you need make 1,2,3 as a part of the m number, not just pop out.

- jeffrey December 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution using a greedy algorithm in Java where A is the list of stacks

Public static int maxSum(Arraylist<Stack<Integer>> A){
	Sum = 0;
	for (int i=0; i<A.size; i++){
		Sum = sum + maxStack(A.get(i))
	}
	Return sum
}
Public static int maxStack(Stack<Integer> s){
	Int max = s.pop();
	Int temp;
	while (s != null){
		if( (temp = s.pop()) > max){
			Max = temp
	}
}
Return max 
}

- buck mcgraw December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

does not work. max value can be down the one stack

- ladis wasrom May 09, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@prosun csedu ,this is a good approach, however it wunt work in this problem, for the very simple reason that ur being greedy!
what if my frst element of say th stack is never max, n is never extraxted, however, the sec element of that stack was some 2000 or so, that covers all other stacks' top elements that were greater than frst elemnt of kth stack? in that case ur algo gives out wrong output!

- Kashish December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@prosun csedu ,this is a good approach, however it wunt work in this problem, for the very simple reason that ur being greedy!
what if my frst element of say th stack is never max, n is never extraxted, however, the sec element of that stack was some 2000 or so, that covers all other stacks' top elements that were greater than frst elemnt of kth stack? in that case ur algo gives out wrong output!

- Kashish December 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python 2.7 implementation

def knapsack(items,weights,maxWeight):
    # Create the V and Keep tables
    v = [ [0 for col in range(maxWeight+1)] for row in range(len(items)) ]
    keep = [ [0 for col in range(maxWeight+1)] for row in range(len(items)) ]
    
    # Build the V and Keep tables
    print "Printing the V table"
    print '0\t'*(len(v[0])-1)
    for i in range(1,len(v)):
        s = ''
        for j in range(1,len(v[0])):
            if j-weights[i] >= 0:
                if v[i-1][j-weights[i]] + items[i] > v[i-1][j]:
                    keep[i][j] = 1
                v[i][j] = max(v[i-1][j], v[i-1][j-weights[i]] + items[i])
            else:
                v[i][j] = v[i-1][j]
            s += str(v[i][j]) + "\t"
        print s
    print "Maximum possible attainable sum = %s.\n" % (v[i][j])
    
    # Printing the Keep table
    print "Printing the Keep table"
    for i in range(1,len(v)):
        s = ''
        for j in range(1,len(v[0])):
            s += str(keep[i][j]) + "\t"
        print s
                
    # Use the keep table to find which elements contributed to this
    path = []
    while i > 0 and j > 0:
        if keep[i][j] == 1:
            path.append(i)
            j -= weights[i]
            i -= 1
        else:
            i -= 1
    print "\nThe elements considered for maxsums : %s.\n" % ([items[x] for x in path]) 
        

def main():
    # Define the input    
    items   = [ 0, 3, 1, 4, 103, 4, 5, 104, 6, 15 ]
    weights = [ 0, 1, 1, 1, 2,   2, 2, 3, 3, 3 ]
    maxWeight = 3

    #items   = [ 0, 5, 3, 4 ]
    #weights = [ 0, 3, 2, 1 ]
    #maxWeight = 5


    knapsack(items,weights,maxWeight)


    
if __name__ == '__main__':
    main()

- Sam December 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <stack>
#include <vector>

using namespace std;
typedef std::stack<int> Stack;
typedef std::vector<int> Array;

void find_max (Stack stacks[], int N, Array &arr, int M) {
arr.resize(M+1, 0);
for (int i = 0; i < N; ++i) {
int index = 0;
int sum = 0;
while (!stacks[i].empty()) {
sum += stacks[i].top(); ++index;
if (arr[index] < sum) arr[index] = sum;
stacks[i].pop();
}
} //end of all stacks iteration
}

int find_max_sum (Array &arr, int M) {
int max_sum = 0;
for (int ind = 0; ind < M/2; ++ind) {
int first = ind;
int last = M - first;
if (arr[first] + arr[last] > max_sum) max_sum = arr[first] + arr[last];
}
return max_sum;
}

int main()
{
Array arr;
Stack stacks[3];
stacks[0].push(1); stacks[0].push(1); stacks[0].push(100); stacks[0].push(3);
stacks[1].push(2000); stacks[1].push(2); stacks[1].push(3); stacks[1].push(1);
stacks[2].push(10); stacks[2].push(1); stacks[2].push(4);
find_max(stacks, 3, arr, 3);
std::cout << "Max =" << find_max_sum(arr,3) << std::endl;
return 0;
}

- Anonymous December 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DP Approach

from pythonds.basic import Stack

def maxSum_NStack(stacks,M):
    database = []
    #sum = 0
    for i in range(M):
        toPop = 0
        for j in range(1,len(stacks)):
            if stacks[j].peek()>stacks[toPop].peek():
                toPop = j
        if i==0:
            database.append(stacks[toPop].pop())
        else:
            database.append(database[-1] + stacks[toPop].pop())
    return(database[-1])

x = [
        [1, 8, 100, 3],
        [2000, 2, 3, 1],
        [10, 1, 4]
    ]

stacks = []
for i in range(len(x)):
    stacks.append(Stack())
    for j in range(len(x[i])):
        stacks[i].push(x[i][j])

print(maxSum_NStack(stacks,5))

- vishal.gupta4081 December 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

s1 = [1,1,100,3]
s2 = [200,2,3,1]
s3 = [10,1,4]

def find_max_sum(s_arr, n):
    if n == 0:
        return 0
    
    if len(s_arr) == 1:
        return sum(s_arr[0][-n:])
    
    # Assume no term is picked form the first stack
    max_sum = find_max_sum(s_arr[1:], n)
    
    first_stack = s_arr[0]
    for i in range(1,n+1): 
        stack_sum = sum(first_stack[-i:])
        rem_sum = find_max_sum(s_arr[1:], n-i)
        if stack_sum + rem_sum > max_sum:
            max_sum = stack_sum + rem_sum
    
    return max_sum


print find_max_sum([s1,s2,s3], 3)

- Nitish Garg December 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create array of size M*N
Take M elements from each stack, store in the array.
Sort the array.
Take elements from (M*N)-M-1 to M*N-1 , find its SUM. that is max sum

- Suneer January 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is knacksack problem!

- tiandiao123 October 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int maxSum(int[][] array,int m){
        int[][] sums = new int[array.length][];
        for(int i=0;i<array.length;i++){
            sums[i] = new int[array[i].length];
            int count = 0;
            for(int j=array[i].length-1;j>=0;j--){
                count+=array[i][j];
                sums[i][j] = count;
            }
        }
        
        int[][] dp = new int[array.length+1][m+1];
        for(int i=1;i<=array.length;i++){
            for(int j=1;j<=m;j++){
                
                dp[i][j] = dp[i-1][j];
                for(int k=array[i-1].length-1;k>=array[i-1].length-1-(j-1);k--){
                         int count = array[i-1].length-k;
                         dp[i][j] = Math.max(dp[i][j],dp[i][j-count]+sums[i-1][k]);
                }
                
            }
        }
        return dp[array.length][m];
    }

- tiandiao123 October 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a typical knapsack problem, here is my java implementation:

public static int maxSum(int[][] array,int m){
        int[][] sums = new int[array.length][];
        for(int i=0;i<array.length;i++){
            sums[i] = new int[array[i].length];
            int count = 0;
            for(int j=array[i].length-1;j>=0;j--){
                count+=array[i][j];
                sums[i][j] = count;
            }
        }
        
        int[][] dp = new int[array.length+1][m+1];
        for(int i=1;i<=array.length;i++){
            for(int j=1;j<=m;j++){
                
                dp[i][j] = dp[i-1][j];
                for(int k=array[i-1].length-1;k>=array[i-1].length-1-(j-1);k--){
                         int count = array[i-1].length-k;
                         dp[i][j] = Math.max(dp[i][j],dp[i][j-count]+sums[i-1][k]);
                }
                
            }
        }
        return dp[array.length][m];
    }

- tiandiao123 October 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Clear problem statement:

We are given n stacks of different sizes. We can perform k pop operations. Each operation can be done on any stack and in any order. The element popped is added to the result. What is the maximum result we can obtain after performing k operations?

EX:
S1=[1,1,100,3]
S2=[2000,2,3,1]
S3=[10,1,4]

k = 3

the maximum sum of the 3 numbers in the above stacks is 3+100+4=107.

for k = 4 the answer would have been 2000 + 2 + 3 + 1

- Rajat.nitp July 21, 2020 | 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