## Goldman Sachs Interview Question for Applications Developers

Country: India

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

Here you go.
[ geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/ ]

I particularly did not like the dp thing. It won't work at all for any practical problems.

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

``````def solve( my_list ){
// 0 is left partition, 1 is right partition
// a bit pattern of size(my_list) = n signifies the selection
// 0 1 0 1 0  --> pick the 0 for left, 1 for right
// 1 2 3 4 5 --> left : [1,3,5], right : [2,4]
// this is the bitmap trick
n = size(my_list)
N = 2 ** n
// infinity with null, lame!
min_diff = { 'value' : num('inf') , 'partitions' : null }
for ( my_num :  [1:N] ){
string_rep = str(my_num,2) // in binary
string_rep = '0' ** ( n - size(string_rep) ) + string_rep
// partition them using when 0 comes left, 1 comes right
#(left_items, right_items ) = partition ( [0:n] ) where { string_rep[\$.o] == _'0' }
left_sum = sum ( left_items )
right_sum = sum ( right_items )
// this is pretty straight forward
diff =  #|left_sum - right_sum |
if ( diff < min_diff.value ){
min_diff.value = diff
min_diff.partitions = [ left_items, right_items]
}
}
min_diff // return
}

l = [1,2,3,4,5]
md = solve( l )
println( md )``````

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

what's practical and not exponential, e.g. with a small error? Any approximation algo?

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.