## A9 Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

1. generate int array A based on sample range from 1 ... N
2. generate all subsets of A of size K.
3. print results

complexity: O(2^n)

implementation:

``````public static void main(String[] args) {
int n = 4;
int k = 2;
int a[] = getArrayFromN(n);
List<List<Integer>> lists = generateSubsetsSizeM(a, k);
for (List<Integer> arrayList : lists) {
printList(arrayList);
System.out.println();
}
}

private static int[] getArrayFromN(int n) {
int j = 0;
int a[] = new int[n];

for(int i = 1; i <= n; i++) {
a[j] = i;
j++;
}
return a;
}

public static List<List<Integer>> generateSubsetsSizeM(int a[], int size) {
List<List<Integer>> result = new ArrayList<>();
int max = new Double(Math.pow(2, a.length)).intValue();
int k = 0, index = 0;

for(int i = 0; i < max; i++) {
k = i;
index = 0;

List<Integer> list = new ArrayList<>();
while(k > 0) {
if ((k & 1) > 0) {
}
k = k >> 1;
index++;
}
if (list.size() == size) {
}
}

return result;
}``````

// output for N = 4 and K = 2:
1 2
1 3
2 3
1 4
2 4
3 4

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

Complexity isn't really O(2^N). Rather, it's (N choose k), which comes down to O(n!/k!(n-k)!).Depending on what K is, it can be anywhere between O(n) to O(n!).

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

@Killedsteel when we generate a subset, each element has the “possibility” of either being in there or not. That is, for the first element, there are 2 choices. For the second, there are two, etc. So, doing 2 * 2 * ... * 2 n times gives us 2^n subsets. We will not be able to do better than this in time or space complexity.

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

Imagine that we would like to print all subsets. Then each integer from array 'int a[]' is member of the subset or not. This can be solved recursively by passing two additional arguments 'int lo' and 'String accum'. Given the index 'lo' we either add a[lo] to an accumulation string or not, increment 'lo' and perform recursive call. We stop and print the 'accum' string as soon as 'lo' is equal to the length of 'a'.

Now, given problem is essentially the same except one modification of the base case. We print the string if and only if its length is equal to 'k', the length of the subset.

A sample code is shown below:

``````public static void print(int K, int N) {
int[] a = new int[N];
for (int k=0; k<N; k++) 	a[k] = k+1;

print(a, K, 0, "");
}

private static void print(int[] a, int K, int lo, String s) {
if (s.length() == K)	System.out.println("'" + s + "'");
if (s.length() >= K)	return;
if (a.length == lo)		return;

print(a, K, lo+1, s);
print(a, K, lo+1, s+a[lo]);
}``````

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

Recursive Solution.
Time Complexity: O(2 ^ n)

``````package GraphSearch;

import java.util.ArrayList;
import java.util.List;

class SubsetWithSizeK {
public static List<List<Integer>> subsetSizeK(int n, int k){
int[] nums = new int[n];
int idx = 0;
for(int i = 1; i <= n; i++){
nums[idx++] = i;
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> subset = new ArrayList<Integer>();
helper(result, subset, nums, k, 0);
return result;
}

private static void helper(List<List<Integer>> result, List<Integer> subset, int[] nums, int k, int pos){
if(subset.size() == k){
return;
}
for(int i = pos; i < nums.length; i++){
helper(result, subset, nums, k, i + 1);
subset.remove(subset.size() - 1);
}
}

public static void main(String[] args){
List<List<Integer>> res = subsetSizeK(4, 2);
for(List<Integer> list : res){
for(int i : list){
System.out.print(i);
}
System.out.println();
}
}
}``````

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

``````package GraphSearch;

import java.util.ArrayList;
import java.util.List;

class SubsetWithSizeK {
public static List<List<Integer>> subsetSizeK(int n, int k){
int[] nums = new int[n];
int idx = 0;
for(int i = 1; i <= n; i++){
nums[idx++] = i;
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> subset = new ArrayList<Integer>();
helper(result, subset, nums, k, 0);
return result;
}

private static void helper(List<List<Integer>> result, List<Integer> subset, int[] nums, int k, int pos){
if(subset.size() == k){
return;
}
for(int i = pos; i < nums.length; i++){
helper(result, subset, nums, k, i + 1);
subset.remove(subset.size() - 1);
}
}

public static void main(String[] args){
List<List<Integer>> res = subsetSizeK(4, 2);
for(List<Integer> list : res){
for(int i : list){
System.out.print(i);
}
System.out.println();
}
}
}``````

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

package GraphSearch;

import java.util.ArrayList;
import java.util.List;

class SubsetWithSizeK {
public static List<List<Integer>> subsetSizeK(int n, int k){
int[] nums = new int[n];
int idx = 0;
for(int i = 1; i <= n; i++){
nums[idx++] = i;
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> subset = new ArrayList<Integer>();
helper(result, subset, nums, k, 0);
return result;
}

private static void helper(List<List<Integer>> result, List<Integer> subset, int[] nums, int k, int pos){
if(subset.size() == k){
return;
}
for(int i = pos; i < nums.length; i++){
helper(result, subset, nums, k, i + 1);
subset.remove(subset.size() - 1);
}
}

public static void main(String[] args){
List<List<Integer>> res = subsetSizeK(4, 2);
for(List<Integer> list : res){
for(int i : list){
System.out.print(i);
}
System.out.println();
}
}
}

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

``````void print(const vector<int> &a)
{
for (int i = 0; i < a.size(); ++i) cout << a[i] << " "; cout << endl;
}

void dfs(int i, int cnt, int n, vector<int> &a)
{
if (cnt == 0)
{
print(a); return;
}

if (n - i + 1 < cnt) return;

a.push_back(i); dfs(i + 1, cnt - 1, n, a); a.pop_back();

dfs(i + 1, cnt, n, a);
}

void printKSetOfN(int n, int k)
{
assert(n > 0 && k > 0 && k <= n);

vector<int> a;

dfs(1, k, n, a);
}``````

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

what do you think of this solution ?

``````public static void printSubset(int k,int n) {
printSubsetRec(n,k,1,1,new int[k]);
}

private static void printSubsetRec(int n,int k,int i,int level, int[] out) {
if(level>k) {
for(int o:out) {
System.out.print(o+",");
}
System.out.print("\n");
return;
}

for(int L=i;L<=n-k+level;L++) {
out[level-1]=L;
printSubsetRec(n,k,L+1,level+1,out);
}
}``````

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

``````public static void printSubset(int k,int n) {
printSubsetRec(n,k,1,1,new int[k]);
}

private static void printSubsetRec(int n,int k,int i,int level, int[] out) {
if(level>k) {
for(int o:out) {
System.out.print(o+",");
}
System.out.print("\n");
return;
}

for(int L=i;L<=n-k+level;L++) {
out[level-1]=L;
printSubsetRec(n,k,L+1,level+1,out);
}
}``````

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

Recursive printout of k-combination of numbers 1 to n

``````void printComb(int start, int end, int k, vector<int>& line)
{
if(k == 0)
{
for(int j = 0; j < line.size(); j++)
cout << line[j] << " ";
cout << endl;
}
else
{
for(int i = start; i <= end; i++)
{
line.push_back(i);
printComb(i+1, end, k-1, line);
line.pop_back();
}
}
}``````

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

``````public class SubsetOfSizeKOutOfN {

public static void main(String[] args) {
SubsetOfSizeKOutOfN so = new SubsetOfSizeKOutOfN();
System.out.println(so.solution(4, 2));

}

public List<List<Integer>> solution(int n, int k) {
List<List<Integer>> ans = new ArrayList<>();
int[] num = new int[n];
for (int i = 0; i < num.length; i++) {
num[i] = i + 1;
}
int numOfSubset = 1 << n;
for (int i = 0; i < numOfSubset; i++) {
if (isSizeK(i, k, n)) {
List<Integer> s = getSubset(num, i, n);
}
}
return ans;
}

private List<Integer> getSubset(int[] num, int mask, int n) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) > 0) {
}
}
return subset;
}

private boolean isSizeK(int mask, int k, int n) {
int cnt = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) > 0) {
++cnt;
}
}
return cnt == k;
}
}``````

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.