## Samsung Interview Question for Software Developers

Country: India
Interview Type: Written Test

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

Basically, this is a combinatorics problem combined with dynamic programming.
So, compute the delta=sum(MAX)-sum(MIN) for all k subsets that can be made and the smallest one is the solution.
Because the array/list is circular, the maximum number of elements that can be used in a subset with the last element from the list is n-k, so I used another list b that generates all list that can be made.

Below is the brute-force approach, but using dynamic programming the complexity can be improved considerably. That is, if a split has been already computed, then there is no need to do it again, instead, first time must be recorded in a table.

Anyway, the complexity of the brute-force solution below is ~O(k*2^n).

Plus, if the table is implemented as a self-balancing binary tree(i.e. red-black tree), then the lookup is improved to logarithmic.

``````subset(S, b, k, sol, min)
if size(S) == k then
if sum(S) <= n then

// we have a candidate solution here (k subsets from list b)
// if the candidate's delta is less than the current known one, then update
delta = do_delta(b, S) // delta does MAX-MIN for split S
if delta < min then
min = candidate
sol = S

// now lets generate another solution
// first pop the head of the stack until it can be incremented thus
// to generate another candidate solution
POP(S)
POP(S)
subset (S, b, k, sol, min)
else if sum(S) < n then
subset (S, b, k, sol, min)
else
POP(S)

do_dMaxMin(b, k)
let min = infinity // minimum delta: sum(MAX)-sum(MIN)
let sol = NIL // the solution (the split)
let S = NIL // a stack
call subset(S, b, k, sol, min)
return (sol, min)

MAIN:
input: let a be the list of numbers
input: let k be the number of subsets
let b be the current list of numbers
let sol to be the best split
let min to be the minimum delta

sol = NIL
min = infinity
b = a
for i=0 to n-k do
if i>0 then
// this moves i elements from the beginning of a to the end of it (since a is circular)
b = concat(a[i+1:n], a[1:i])

// lets see the candidate solution
(candidate_sol, candidate_delta) = do_dMaxMin(b,k)
if (candidate_delta < min) then
sol = candidate_sol
min = candidate_delta
return (sol, min)``````

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.