Google Interview Question
Software EngineersCountry: United States
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
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]])
***********************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()));
}
}
}
}
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;
}
}
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
Could you please explain your understanding of this problem? It does not make any sense to me as stated. Thanks!
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;
}
}
a typo : the maximum sum of the 3 numbers in the above stacks is 3+100+4=107.
sorry for that
# 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]])
# 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]])
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]])
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.
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
}
@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!
@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!
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()
#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;
}
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))
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)
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];
}
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];
}
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
Can you please explain the problem little bit more?
- kathirkarthick12 November 28, 2016