Facebook Interview Question
Web:
www.facebook.com
|
HQ:
Menlo Park, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
349 Interview Reviews |
Back to all Facebook Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Facebook:
Jan 24, 2012
You are given a set of numbers 0 - n. Given a k, print all subsets of size k. Give the time complexity of the algorithm.
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (6)
Mar 18, 2012
static void Main(string[] args)
{
GetNKCombinations(10, 6);
foreach (List<int> s in combinations)
{
System.Console.Write("[");
foreach(int i in s)
System.Console.Write(" "+i);
System.Console.Write(" ]\n");
}
System.Console.ReadLine();
}
static List<List<int>> combinations = new List<List<int>>();
public static void GetNKCombinations(int N, int K)
{
if (N < K)
return;
Combine(N, K, new List<int>(), 0);
}
private static void Combine(int N, int K, List<int> result, int startIndex)
{
if (result.Count == K)
{
List<int> l = new List<int>();
l.AddRange(result);
combinations.Add(l);
return;
}
for (int i = startIndex; i <= N; i++)
{
result.Add(i);
Combine(N, K, result, i + 1);
result.RemoveAt(result.Count - 1);
}
}
{
GetNKCombinations(10, 6);
foreach (List<int> s in combinations)
{
System.Console.Write("[");
foreach(int i in s)
System.Console.Write(" "+i);
System.Console.Write(" ]\n");
}
System.Console.ReadLine();
}
static List<List<int>> combinations = new List<List<int>>();
public static void GetNKCombinations(int N, int K)
{
if (N < K)
return;
Combine(N, K, new List<int>(), 0);
}
private static void Combine(int N, int K, List<int> result, int startIndex)
{
if (result.Count == K)
{
List<int> l = new List<int>();
l.AddRange(result);
combinations.Add(l);
return;
}
for (int i = startIndex; i <= N; i++)
{
result.Add(i);
Combine(N, K, result, i + 1);
result.RemoveAt(result.Count - 1);
}
}
Helpful Answer?
Yes |
No
Inappropriate?
Mar 18, 2012
Sorry...
public static void GetNKCombinations(int N, int K)
{
if (N+1 < K)
return;
Combine(N, K, new List<int>(), 0);
}
public static void GetNKCombinations(int N, int K)
{
if (N+1 < K)
return;
Combine(N, K, new List<int>(), 0);
}
Helpful Answer?
Yes |
No
Inappropriate?
Apr 1, 2012
A basic search problem.
Helpful Answer?
Yes |
No
Inappropriate?
1 of 1 people found this helpful
May 3, 2012
Here's an elegant recursive solution in Java. The method itself is under 10 lines of code:
import java.io.*;
public class PrintSets {
public static void main(String[] args) {
StringBuffer out = new StringBuffer();
int k = 2;
int[] in = {1, 2, 3, 4, 5};
printSets(k, in, out, 0);
}
public static void printSets(int k, int[] in, StringBuffer out, int startIndex) {
if (out.length() == k) {
System.out.println(out.toString());
return;
}
for(int i = startIndex; i <= in.length-(k-out.length()); i++) {
out.append(in[i]);
printSets(k, in, out, startIndex+(i-startIndex)+1);
out.setLength(out.length()-1);
}
}
}
import java.io.*;
public class PrintSets {
public static void main(String[] args) {
StringBuffer out = new StringBuffer();
int k = 2;
int[] in = {1, 2, 3, 4, 5};
printSets(k, in, out, 0);
}
public static void printSets(int k, int[] in, StringBuffer out, int startIndex) {
if (out.length() == k) {
System.out.println(out.toString());
return;
}
for(int i = startIndex; i <= in.length-(k-out.length()); i++) {
out.append(in[i]);
printSets(k, in, out, startIndex+(i-startIndex)+1);
out.setLength(out.length()-1);
}
}
}
Helpful Answer?
Yes |
No
Inappropriate?
May 4, 2012
Whoops - the following line:
printSets(k, in, out, startIndex+(i-startIndex)+1);
Can be simplified to:
printSets(k, in, out, i+1);
printSets(k, in, out, startIndex+(i-startIndex)+1);
Can be simplified to:
printSets(k, in, out, i+1);
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Facebook Interview
1 of 6 people found this helpful
by wqj: