Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
public class Number
{
public static String next(int start, int limit,int num,String str,int initialLimit)
{
if(str == null)
{
str = Integer.toString(start);
}
else
{
str = str + ' '+Integer.toString(start);
}
limit--;
if(limit == 0)
{
System.out.println(str);
}
for(int i=start+1;i<=num;i++)
{
if((num -i >= limit -1) && (limit >0))
{
next(i,limit,num,str,initialLimit);
next(i,initialLimit,num,null,initialLimit);
}
}
return str;
}
public static void main(String args[])
{
int n=5;
int k=3;
String str =null;
next(1,k,n,str,k);
}
}
bool used[N];
char output[K+1];
void rassclot(int fill, int prev)
{
if(fill == K) { print output; return; }
for(i=prev+1; i<=N; i++)
{
if(used[i]) continue;
output[fill]=i;
rassclot(fill+1, i);
}
}
Call function using rassclot(0, -1).
public class Combinations {
public static List<String> combinations(int n, int k) {
List<String> list = new ArrayList<String>();
boolean flag = false;
List<Integer> cur = new ArrayList<Integer>(k);
for (int i = 0; i < k; i++) {
cur.add(i + 1);
}
list.add(cur.toString());
for (int i = k - 1; i >= 0; i--) {
while (cur.get(i) < (n - (k - i) + 1)) {
cur.set(i, cur.get(i) + 1);
for (int j = i + 1; j < k; j++) {
cur.set(j, cur.get(j - 1) + 1);
}
list.add(cur.toString());
}
}
return list;
}
public static void main(String[] args) {
List<String> list = combinations(5,3);
for(String s : list) {
System.out.println(s);
}
}
}
public static ArrayList<ArrayList<Integer>> findCombinations(int n, int k){
if (k>n)
return null;
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> line = new ArrayList<Integer>();
if (k==0){
res.add(line);
return res;
}
if (n==k){
for (int i=1; i<=n; i++)
line.add(i);
res.add(line);
return res;
}
res.addAll(findCombinations(n-1, k));
for (ArrayList<Integer> e:findCombinations(n-1, k-1)){
e.add(n);
res.add(e);
}
return res;
}
JavaScript implementation
// Printing all possible sub sets having only 3 elements out of 5
var items = [];
for (var index = 0; index < 5; index += 1) {
items.push(index);
}
var results = [];
function print(prefix, position, len) {
for (var index = position + 1; index < items.length; index += 1) {
var newItem = prefix.slice();
newItem.push(items[index]);
if (newItem.length == len) {
results.push(newItem);
}
if (newItem.length <= len - 1) {
print(newItem, index, len);
}
}
}
print([], -1, 3);
void print_subset(int *A, int K)
{
int i;
for(i=0; i<K; i++)
fprintf(stderr, "%d ", A[i]);
fprintf(stderr, "\n");
}
void print_combination(int *A, int *B, int k, int pos, int start, int N, int K)
{
int i;
assert(k>=0 && k<N);
assert(pos >=0 && pos<N);
assert(start >=0);
if(k==0){
print_subset(B, K);
return;
}
if(start >= N)
return;
for(i=start; i<N; i++){
B[pos] = A[i];
print_combination(A, B, k-1, pos+1, i+1, N, K);
}
}
A non-recursive solution in Python:
It (theoretically) takes O(1) space since no stack is used. I am using a set "sets" to store all subsets rather than printing them.
def getSet(ss):
s = ""
for k in range(0, len(ss) - 1):
s = s + str(ss[k]) + " "
return s + str(ss[len(ss) - 1])
def subsets(N, K):
sub_set = [0 for k in range(0, K + 1)]
pos = 1
sets = []
sub_set[0] = 0
while pos != 0:
if sub_set[pos] >= N + 1:
sub_set[pos] = 0
pos = pos - 1
else:
if sub_set[pos] == 0:
sub_set[pos] = sub_set[pos - 1] + 1
else:
sub_set[pos] += 1
if pos == K:
if (sub_set[K] < N + 1) and (sub_set[K] != 0):
sets.append(getSet(sub_set[1:]))
else:
pos += 1
return sets
A non-recursive solution in Python:
It (theoretically) takes O(1) space since no stack is used. I am using a set "sets" to store all subsets rather than printing them.
def getSet(ss):
s = ""
for k in range(0, len(ss) - 1):
s = s + str(ss[k]) + " "
return s + str(ss[len(ss) - 1])
def subsets(N, K):
sub_set = [0 for k in range(0, K + 1)]
pos = 1
sets = []
sub_set[0] = 0
while pos != 0:
if sub_set[pos] >= N + 1:
sub_set[pos] = 0
pos = pos - 1
else:
if sub_set[pos] == 0:
sub_set[pos] = sub_set[pos - 1] + 1
else:
sub_set[pos] += 1
if pos == K:
if (sub_set[K] < N + 1) and (sub_set[K] != 0):
sets.append(getSet(sub_set[1:]))
else:
pos += 1
return sets
using namespace std;
void choose(const char *A, int n, int k, std::string prefix)
{
if (A == NULL || n < 0 || k < 0) return;
if (k == 0) {
cout << prefix << endl;
return;
}
std::string next_prefix("");
for (int i = 0; i <= n - k; i++) {
next_prefix = prefix + A[i];
choose(&A[i+1], n - i - 1, k - 1, next_prefix);
}
}
function max(a,b) {
if (a>b) {
return a;
}
return b;
}
function printMe(n,k, ans) {
var i,j;
if (ans.length === 0) {
i = 1;
} else {
i = ans[ans.length-1]+1;
}
var j1 = (i + k -1) <n ? (i + k -1) : n;
var j2 = n - k +1;
j = max(j1,j2);
for (;i<=j;i++) {
ans.push(i);
if ( ans.length === k ) {
console.log(ans.join(''));
} else {
printMe(n,k,ans);
}
ans.pop();
}
}
printMe(9,7,[]);
#include<stdio.h>
#include<stdlib.h>
int *last_combo;
int* next_combo(int *src, int* combo, int maxsize, int combosize)
/*
* 0 1 2 3 4 5
* 0 1 2
*/
{
if (combosize == 1)
{
if (combo[0] == maxsize-1)
return NULL;
else {
combo[0]++;
return combo;
}
}
if(combo[combosize-1] < maxsize-1)
{
combo[combosize-1] = combo[combosize-1] + 1;
} else if (memcmp(combo,last_combo,combosize)){
combo = next_combo(src,combo,maxsize-1,combosize-1);
combo[combosize-1] = combo[combosize-2] + 1;
}
return combo;
}
int main()
{
int *a;
int *combo;
int size = 3;
int src_size=6;
int i,j;
combo = (int*)malloc(sizeof(int)*size);
last_combo = (int*)malloc(sizeof(int)*size);
a = (int*)malloc(sizeof(int)*src_size);
memset(a,0,src_size);
memset(combo,0,size);
memset(last_combo,0,size);
for(i=0; i<src_size;i++)
{
a[i] = i;
}
for(i=0; i<size;i++)
{
combo[i] = a[i];
}
for(i=src_size-1,j=size-1; j>=0;i--,j--)
{
last_combo[j] = a[i];
}
printf("\n***********************************\n");
for(i=0; i<size;i++)
{
printf("%d",combo[i]);
}
for(i=0; i<size;i++)
{
printf("%d",last_combo[i]);
}
printf("\n************* START ***************\n");
printf("\n");
while (memcmp(combo,last_combo,size))
{
combo = next_combo(a, combo, src_size, size);
printf("\n");
for(i=0; i<size;i++)
{
printf("%d",combo[i]);
}
}
return 0;
}
------------------------------
Storing binaries <<< done
Listing build files... done
Checking for application data... done
Running:
------------------------------
***********************************
012
345
************* START ***************
013
014
015
023
024
025
034
035
045
123
124
125
134
135
145
234
235
245
345
In scala this is very simple:
def combs(in:List[Int], left:Int, cur:List[Int]):Unit = {
// if we do not have sufficient to return a combination, then return what we have
if (in.size >= left) {
left match {
case 0 => println(cur.reverse.mkString(" "))
case a => {
in match {
case h::t => {
combs(t, left - 1, h :: cur)
combs(t, left, cur)
}
}
}
}
}
}
yielding the following output:
scala> combs(List(1,2,3,4,5), 3, List.empty[Int])
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
scala>
<pre class=" language-java">
<code class=" language-java">
public class CombinationsK {
// print all subsets that take k of the remaining elements, with given prefix
public static void comb1(String s, int k) { comb1(s, "", k); }
private static void comb1(String s, String prefix, int k) {
if (s.length() < k) return;
else if (k == 0) System.out.println(prefix);
else {
comb1(s.substring(1), prefix + s.charAt(0), k-1);
comb1(s.substring(1), prefix, k);
}
}
// print all subsets that take k of the remaining elements, with given prefix
public static void comb2(String s, int k) { comb2(s, "", k); }
private static void comb2(String s, String prefix, int k) {
if (k == 0) System.out.println(prefix);
else {
for (int i = 0; i < s.length(); i++)
comb2(s.substring(i + 1), prefix + s.charAt(i), k-1);
}
}
// read in N and k from command line, and print all subsets of size k from N elements
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
int k = Integer.parseInt(args[1]);
String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
String elements = alphabet.substring(0, N);
comb1(elements, k);
System.out.println();
comb2(elements, k);
}
}
</code>
</pre>
Pure mathematics: C(n,k) = C(n-1, k) + C(n-1, k-1). The items that make up C(n-1, k) are results of select k from n-1 while the items that make up C(n-1, k-1) are select k-1 from n-1. The later needs to append with n to make k elements in selection.
Implementation in Java:
public static List<List<Integer>> combination(int n, int k) {
if (n<k) throw new IllegalArgumentException();
if (k==1) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
for (int i=1; i<=n; i++) {
List<Integer> list = new ArrayList<Integer>();
list.add(i);
ret.add(list);
}
return ret;
}
if (k==n) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
for (int i=1; i<=n; i++) {
list.add(i);
}
ret.add(list);
return ret;
}
List<List<Integer>> combo1 = combination(n-1, k);
List<List<Integer>> combo2 = combination(n-1, k-1);
for (List<Integer> list:combo2) list.add(n);
combo1.addAll(combo2);
return combo1;
}
}
Same implementation in Scala
def combination(n:Int, k:Int):Seq[Seq[Int]] = {
require(n>=k && k>=0)
(n, k) match {
case (_, 1) => (1 to n).map(Seq(_))
case (_, `n`) => Seq((1 to n))
case _ => {
var combo1 = combination(n-1, k)
var combo2 = combination(n-1, k-1).map(l=>l:+n)
combo1++combo2
}
}
}
public IEnumerable<string> GenerateSubsets(int n, int k)
{
int[] a = new int[k];
List<string> result = new List<string>();
GenerateSubsets(n, k, 1, 0, a, result);
return result;
}
private void GenerateSubsets(int n, int k, int start, int index, int[] a, List<string> result)
{
if (k == 0)
return;
int end = n - k + 1;
for (int i=start; i <= end; i++)
{
a[index] = i;
if (k == 1)
{
var sb = new StringBuilder();
foreach (var item in a)
sb.Append(item);
result.Add(sb.ToString());
}
GenerateSubsets(n, k-1, i+1, index+1, a, result);
}
}
public IEnumerable<string> GenerateSubsets(int n, int k)
{
int[] a = new int[k];
List<string> result = new List<string>();
GenerateSubsets(n, k, 1, 0, a, result);
return result;
}
private void GenerateSubsets(int n, int k, int start, int index, int[] a, List<string> result)
{
if (k == 0)
return;
int end = n - k + 1;
for (int i=start; i <= end; i++)
{
a[index] = i;
if (k == 1)
{
var sb = new StringBuilder();
foreach (var item in a)
sb.Append(item);
result.Add(sb.ToString());
}
GenerateSubsets(n, k-1, i+1, index+1, a, result);
}
}
Call with start = 1, array aof size k, pos = 0.
- Anonymous February 19, 2014void subset(int start, int n, int k, int *a, int pos) { int i, j; if(!k) { for(j = 0; j < pos; j++) cout<< a[j] <<"\t"; cout<<"\n"; return; } for(i = start; i <= n-k+1; i++) { a[pos] = i; subset(i + 1, n, k-1, a, pos+1); } }