Google Interview Question Software Engineers
Country: India
Interview Type: Phone Interview
DP ?
dp(n,r,k) = min(dp(n-1,f-Sn%f,k-1),dp(n-1,r,k-1));
Base Case
if(k==n)
{dp(n,r,k) = { x = Sum(S0…Sn),if( x%f) == r , dp(n,r,k) = x else dp(n,r,k) =INT.MAX }}
@krbchd
Just wondering if it should be k and not k-1 in the right parameter to min?
..dp(n,r,k) = min(dp(n-1,f-Sn%f,k-1),dp(n-1,r,k));
c++, implementation
typedef long long INT64;
void minimumDividableSum(vector<int>& arr, int K, int F, int idx, INT64 sum, INT64& answer) {
if (K == 0) {
if (sum != 0 && sum % F == 0 && (answer == -1 || answer > sum)) {
answer = sum;
}
return;
}
if (answer != -1 && sum > answer) return;
if (idx >= arr.size()) return;
minimumDividableSum(arr, K - 1, F, idx + 1, sum + arr[idx], answer);
minimumDividableSum(arr, K, F, idx + 1, sum, answer);
}
INT64 solve(vector<int>& arr, int K, int F) {
INT64 answer = -1;
if (K > arr.size()) return answer;
minimumDividableSum(arr, K, F, 0, 0, answer);
return answer;
}
This is my initial thought , I think there should be a better solution:
- Find maximum possible sum of k elements max_sum ( basically add k largest elements ).
- now fill the boolean DP matrix of N x k x max_sum in bottom up manner ( dp[i][j][k] represents whether it is possible to pick j elements out of first i elements that sum up to k )
- now find the smallest multiple M of F such that dp[n][k][M] is true.
Complexity - O(N.k.max_sum) plus O(log_base_F(max_sum))
This is my initial thought , I think there should be a better solution:
- Find maximum possible sum of k elements max_sum ( basically add k largest elements ).
- now fill the boolean DP matrix of N x k x max_sum in bottom up manner ( dp[i][j][k] represents whether it is possible to pick j elements out of first i elements that sum up to k )
- now find the smallest multiple M of F such that dp[n][k][M] is true.
Complexity - O(N.k.max_sum) plus O(log_base_F(max_sum))
In Java, iterative, but following same recursive logic as by @kyduke
public class MatchsticksSum {
public static int getSum(int[] boxes, int F, int K) {
int[][][] memo = new int[K+1][F][boxes.length+1];
for (int i = 0; i<=boxes.length; i++) {
for (int k = 0; k<=K; k++) {
for (int f = 0; f < F; f++) {
if (i<k) {
memo[k][f][i] = Integer.MAX_VALUE;
continue;
}
if (k==0) {
if (f==0) {
memo[k][f][i] = 0;
} else {
memo[k][f][i] = Integer.MAX_VALUE;
}
continue;
}
if (k==1 && i==1) {
if (boxes[i-1]%F==f) {
memo[k][f][i] = boxes[i-1];
} else {
memo[k][f][i] = Integer.MAX_VALUE;
}
continue;
}
int remIdx = (f>=boxes[i-1] % F)?(f-boxes[i-1] % F):(F+(f - boxes[i-1]%F));
if (memo[k-1][remIdx][i-1] != Integer.MAX_VALUE) {
memo[k][f][i] = Math.min(memo[k-1][remIdx][i-1] + boxes[i-1]
,memo[k][f][i-1]);
} else {
memo[k][f][i] = memo[k][f][i-1];
}
}
}
}
int res = memo[K][0][boxes.length];
return res==Integer.MAX_VALUE?-1:res;
}
}
I found the edge cases in this problem really kept me on my toes. I'm not 100% happy with my solution -- it's more geared towards simplicity than efficiency (believe it or not), but I'm happy enough to share it with the world. It treats matchboxes as integers and prints out the value of the matchboxes chosen, not their index.
I assume the time complexity is O(C(n, k) ⋅ n).
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <cassert>
using namespace std;
template <typename I0, typename I1, typename T = typename iterator_traits<I0>::value_type>
T count_matches(I0 f_matchbox, I0 l_matchbox, I1 f_combination)
{
// Not the most efficient method but straight-forward.
return inner_product(f_matchbox, l_matchbox, f_combination, 0); // O(n)
}
// Select K matchboxes such that M % F == 0 and minimize(M)
// Requires random access iterators to non-const matchbox range.
template <typename I, typename O>
O minimize_M_multiple_F(I first, I last, O result, size_t F, size_t K)
{
assert(F != 0);
assert(K < last - first && K != 0);
using matchbox_t = typename iterator_traits<I>::value_type;
sort(first, last, greater<matchbox_t>()); // O(n lg n) time.
auto const n = last - first;
vector<bool> combination; // O(n) bits space.
combination.resize(n);
fill(combination.rbegin(), combination.rbegin() + K, true);
bool searching = true;
size_t M = count_matches(first, last, begin(combination));
while (M == 0 && searching) // Get past the zero edge case.
{
searching = next_permutation(begin(combination), end(combination));
M = count_matches(first, last, begin(combination));
}
size_t target = F;
while (searching && M % F)
{
target = M - M % F + F; // Simplifies inner loop condition.
do
{
searching = next_permutation(begin(combination), end(combination));
M = count_matches(first, last, begin(combination));
}
while (searching && M < target);
}
if (M % F == 0)
{
for (size_t i = n; i > 0; i--)
if (combination[i-1])
*result++ = first[i-1];
}
return result;
}
int main(int argc, char **argv)
{
if (argc < 3)
exit(EXIT_FAILURE);
using matchbox_t = int;
vector<matchbox_t> matchboxes = {0, 0, 1, 2, 2, 7, 12};
vector<matchbox_t> answer;
auto const F = strtoul(argv[1], nullptr, 10);
auto const K = strtoul(argv[2], nullptr, 10);
answer.reserve(K);
minimize_M_multiple_F(begin(matchboxes), end(matchboxes), back_inserter(answer), F, K);
for (auto matchbox : answer)
cout << matchbox << " ";
cout << endl;
}
Here is the C++ solution running at K*N^(k-1)*log N, which I am not really proud of.
#include<math.h>
#include<set>
#include<vector>
#include<climits>
#include<iostream>
using namespace std;
int find_sum(int target, int prev, vector<int>& inputs, set<int>& selected, set<int>& hash, int left)
{
if (left == 1)
{
set<int>::iterator found;
if((found=hash.find(target-prev))!= hash.end())
{
if (selected.find(*found)== selected.end())
return target;
else INT_MIN;
} else
return INT_MIN;
}
for (int i = 0; i < inputs.size(); i++)
{
if (selected.find(inputs[i])== selected.end())
{
selected.insert(inputs[i]);
prev += inputs[i];
if (find_sum(target, prev, inputs, selected, hash, left-1)!= INT_MIN)
return target;
selected.erase(inputs[i]);
prev -= inputs[i];
}
}
return INT_MIN;
}
int pickMatch(vector<int> inputs, int k, int f)
{
int result = INT_MIN;
int target = f;
int i = 1;
set<int> hashmap;
for (int i = 0; i < inputs.size(); i++)
hashmap.insert(inputs[i]);
for(int i = 1; i <= k; i++)
{
set<int> selected;
result = find_sum(f*i, 0, inputs, selected ,hashmap, k);
if (result != INT_MIN)
return result;
}
return -1;
}
int main()
{
vector<int> inputs;
inputs.push_back(1);
inputs.push_back(2);
inputs.push_back(3);
inputs.push_back(4);
inputs.push_back(5);
cout<< "found = " <<pickMatch(inputs, 3, 5) << endl;
return 1;
}
public int minMatch(int[] S, int K, int F) {
int n = S.length;
int[][][] mincount = new int[n][K + 1][F];
int sum[] = new int[n];
sum[0] = S[0];
for (int i = 1; i < n; i++) {
sum[i] = sum[i - 1] + S[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= K; j++) {
Arrays.fill(mincount[i][j], Integer.MAX_VALUE);
}
}
mincount[0][0][S[0] % F] = S[0];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i && j < K; j++) {
for (int m = 0; m < F; m++) {
if (j == 0) {
mincount[i][j][m] = mincount[i - 1][j][m];
if (S[i] % F == m) {
mincount[i][j][m] = Math.min(mincount[i][j][m], S[i]);
}
continue;
}
int r = m - S[i] % F < 0 ? F + m - S[i] % F : m - S[i] % F;
mincount[i][j][m] = Math.min((mincount[i - 1][j - 1][r] + S[i] < 0 ? Integer.MAX_VALUE : mincount[i - 1][j - 1][r] + S[i]), mincount[i - 1][j][m]);
}
}
}
my little attempt
int matchSticks(const vector<int> &s, int f, int k) {
vector<vector<int>> dp((k+1)*(s.size()+1));
// pos = (ki*k)+i;
for ( int i = 0; i < k+1; ++i ) {
// initialize
dp[i*(s.size()+1)] = {0};
}
for ( int i = 0; i < s.size(); ++i ) {
for ( int j = 0; j < std::min(k,i)+1; ++j ) {
int pos = (j*(s.size()+1))+i;
int pos1 = pos+1;
int pos2 = pos1+(s.size()+1); // next row
for ( int v = 0; v < dp[pos].size(); ++v ) {
dp[pos1].push_back(dp[pos][v]);
dp[pos2].push_back(dp[pos][v]+s[i]);
}
}
}
int minVal = numeric_limits<int>::max();
for ( int v = 0; v < dp.rbegin()->size(); ++v ) {
int val = (*dp.rbegin())[v];
if ( val %f == 0 && val < minVal ) {
minVal = val;
}
}
return minVal;
}
my attempt
int matchSticks(const vector<int> &s, int f, int k) {
vector<vector<int>> dp((k+1)*(s.size()+1));
// pos = (ki*k)+i;
for ( int i = 0; i < k+1; ++i ) {
// initialize
dp[i*(s.size()+1)] = {0};
}
for ( int i = 0; i < s.size(); ++i ) {
for ( int j = 0; j < std::min(k,i)+1; ++j ) {
int pos = (j*(s.size()+1))+i;
int pos1 = pos+1;
int pos2 = pos1+(s.size()+1); // next row
for ( int v = 0; v < dp[pos].size(); ++v ) {
dp[pos1].push_back(dp[pos][v]);
dp[pos2].push_back(dp[pos][v]+s[i]);
}
}
}
int minVal = numeric_limits<int>::max();
for ( int v = 0; v < dp.rbegin()->size(); ++v ) {
int val = (*dp.rbegin())[v];
if ( val %f == 0 && val < minVal ) {
minVal = val;
}
}
return minVal;
}
This is my initial thought, I think there should be a better solution
- goldfinch November 19, 2015-Find maximum sum of k elements max_sum ( basically add k largest elements )
-now fill the Boolean DP matrix of N x k x max_sum in bottom-up manner ( dp[i][j][k] representing whether it is possible to pick j from i elements that sum upto k )
-Now find the smallest multiple m of F such that dp[n][k][m] is true.
-Complexity would be O(N.k.max_sum) plus O(log_base_k(max_sum))