Empresa engajada
Pergunta de entrevista da empresa LinkedIn
Given an array break it down into k subsets with each subset's sum equaling a constant M. For e.g. [4, 2, 1, 3, 2, 3, 5] and k=4 you should return true because that whole array can be broken down into {4,1}, {2,3}, {2,3}, {5} which equal to a sum of 5. Imagine how confused you would be if you are thinking on a solution and he forgot that last integer 5 in that array for about 10 minutes.
Resposta da entrevista
Sigiloso
I have tried a hashmap based solution and he is not interested in it because he knows the answer. I came up with an algorithm that uses combinations of those integers which does the job but it's inefficient which I have already pointed out. I came up with permutations based solution which works but I would find sums of all permutations and see if a certain sum occurs exactly or more than given k which also works he is not interested in. So he gave the answer of forming trees of permutations to find if there can be k number of equal sums. All this in one hour with pseudo code. I was very tired after this interview.