## Google Interview Question for Software Engineers

• 1
of 1 vote

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?

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]])``````

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;

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

public static void main(String s[]){
stacks = new ArrayList<>();
stacks = new ArrayList<>();
stacks = new ArrayList<>();

Integer sum[] = new Integer;
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;

}

}``````

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

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

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

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!

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;
}

}``````

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

What is the runtime complexity of this solution?

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

problem not clear

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

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]])``````

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]])``````

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]])``````

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.

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

It will not work.

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

Find 3 element max.

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.

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
}``````

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!

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!

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)-1)
for i in range(1,len(v)):
s = ''
for j in range(1,len(v)):
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)):
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()``````

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;
stacks.push(1); stacks.push(1); stacks.push(100); stacks.push(3);
stacks.push(2000); stacks.push(2); stacks.push(3); stacks.push(1);
stacks.push(10); stacks.push(1); stacks.push(4);
find_max(stacks, 3, arr, 3);
std::cout << "Max =" << find_max_sum(arr,3) << std::endl;
return 0;
}

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))``````

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[-n:])

# Assume no term is picked form the first stack
max_sum = find_max_sum(s_arr[1:], n)

first_stack = s_arr
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)``````

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

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

this is knacksack problem!

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];
}``````

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];
}``````

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.