Linkedin Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
C code: When top level call of following function will return, *ssc will contain subsets count which will add-up to k
void subsum(int k, int n, int nums[], int* ssc) {
for(int i = 0; i < n; i++) {
if(k == nums[i])
*ssc += 1;
else if(k > nums[i])
subsum(k - nums[i], n - i - 1, nums + i + 1, ssc);
}
}
Test Code:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int main(int argc, char** argv) {
int N = 10;
int k = 10;
if(argc > 1)
k = atoi(argv[1]);
if(argc > 2)
N = atoi(argv[2]);
int (*nums)[N] = malloc(sizeof(*nums));
printf("k: %d\n", k);
printf("subset: [");
srand(time(0));
for(int i = 0; i < N; i++) {
//(*nums)[i] = i;
(*nums)[i] = rand() % N;
printf("%d, ", (*nums)[i]);
}
printf("\b\b]\n");
int ssc = 0;
subsum(k, N, *nums, &ssc);
printf("subsets count: %d\n", ssc);
return 0;
}
C code:
Test Code:
- badboy May 02, 2018#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int main(int argc, char** argv) {
int N = 10;
int k = 10;
if(argc > 1)
k = atoi(argv[1]);
if(argc > 2)
N = atoi(argv[2]);
int (*nums)[N] = malloc(sizeof(*nums));
printf("k: %d\n", k);
printf("subset: [");
srand(time(0));
for(int i = 0; i < N; i++) {
//(*nums)[i] = i;
(*nums)[i] = rand() % N;
printf("%d, ", (*nums)[i]);
}
printf("\b\b]\n");
int ssc = 0;
subsum(k, N, *nums, &ssc);
printf("subsets count: %d\n", ssc);
return 0;
}