Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Non-recursive solution: (in PHP as per the question)-
<?php
function find_sum($n) {
$array[1] = array("1");
for ($i=2; $i <= $n; $i++) {
$array[$i] = array();
for ($j=1; $j < $i; $j++) {
foreach ($array[$j] as $el) {
array_push($array[$i], $el.",".($i-$j));
}
}
array_push($array[$i], $i);
}
return $array[$n];
}
$n = 4;
$res = find_sum($n);
foreach ($res as $str) {
if ($n == 1 || $str != $n)
print "(".$str.")\n";
}
?>
output:
(1,3)
(1,1,2)
(2,2)
(1,2,1)
(1,1,1,1)
(2,1,1)
(3,1)
i am not sure what is going on here, "List<List<Integers> tempList = getCombinations (val --);". someone help me?
I forgot for T(3) we have to explicitly add {3} .
so for T(3) we have (2,1 ), (1,2 ),(1,1,1) and (3)also...
I am here giving only an idea...
this to be done using dynamic programming......
1 will have{1}
2 will have {1,1}.{2}
as base conditions.....
now T(n) will be
temporaryset=null;
for(i=1;i<n;i++)
temporaryset=temoraryset union T(i) union T(n-i)(element wise union);
//eg;T(3)=T(2) union T(1) union T(1) union T(2)
so (2,1),(1,1,1) (1,2);
then for T(4) and like that continue...
I was asked the same question in Amazon.. I gave this solution.
Why so complicated solutions ?
Here is simplest solution I wrote
public static void ways(int n) {
waysUtil(n,"", n);
}
public static void waysUtil(int no, String str, int orig) {
if(no == 0) {
System.out.println(str);
return;
}
if(no < 0) {
return;
}
for(int i = 1; i < orig ; i++) {
waysUtil(no - i, str + i, orig);
}
}
List <List<Integer> getCombinations (int num)
{
List <List<Integer>> allCombinations = new ArrayList<Integer>();
int val = num;
int i = 1;
while (val > 0)
{
List<Integers> temp1 = new ArrayList<Integer>();
temp1.add (i++);
List<List<Integers> tempList = getCombinations (val --);
int j = 0;
for (List<Integer> subList : tempList)
{
temp1.addAll(subList);
}
allCombinations.add(temp1);
}
return allCombinations;
}
}
Another recursive solution here: (but I am not sure if the running time is acceptable)
public static ArrayList<String> allAdds(int num) {
ArrayList<String> ret = new ArrayList<String>();
if(num == 1){
ret.add(""+num);
return ret;
}
for(int i = 1; i<num; i++) {
for(String j:allAdds(num-i))
ret.add(i+" + "+j);
}
ret.add(""+num);
return ret;
}
We can optimize this further by memorizing all the results already produced,
private HashMap<Integer, ArrayList<String>> addSeqs =
new HashMap<Integer, ArrayList<String>>();
public ArrayList<String> allAdds(int num) {
ArrayList<String> ret = new ArrayList<String>();
if(num == 1){
ret.add(""+num);
return ret;
}
for(int i = 1; i<num; i++) {
ArrayList<String> all = addSeqs.get(num-i);
if (all == null) {
all = allAdds(num-i);
addSeqs.put(num-i, all);
}
for(String j:all)
ret.add(i+" + "+j);
}
ret.add(""+num);
return ret;
}
public static HashSet<ArrayList<Integer>> getSequences(int n) {
@SuppressWarnings("unchecked")
HashSet<ArrayList<Integer>>[] list = (HashSet<ArrayList<Integer>>[]) new HashSet[n + 1];
for (int i = 0; i < list.length; i++) {
list[i] = new HashSet<ArrayList<Integer>>();
}
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(0);
list[0].add(arr);
arr = new ArrayList<Integer>();
arr.add(1);
list[1].add(arr);
if (n > 1) {
arr = new ArrayList<Integer>();
arr.add(1);
arr.add(1);
list[2].add(arr);
}
if (n <= 2)
return list[n];
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
int t = i - j;
for (ArrayList<Integer> s : list[j]) {
ArrayList<Integer> tmp = new ArrayList<Integer>(s);
tmp.add(t);
list[i].add(tmp);
}
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.add(t);
tmp.add(j);
list[i].add(tmp);
}
}
return list[n];
}
Here is an alogrithm
An Array of n numbers starting from 1..n sorted positive numbers only
Now we need to find the sum K
clearly the sum will comprise of elements before K in array
here is a backtracking solution
Target = K ;
Int [k] Index =0;
Index[0]=0;
sum =0
Public void solve(Int target,int sum,int[]Index,int n, int []Array)
{
if (Sum= target)
{
Print ( Array,Index,n);
}
for(int i= index[n];i<k;i++)
{
Index[n+1]=i;
solve(target,sum+Array[i],Index,n+1, Array);
}
}
//This program generates all combinations of set whose sum is equal to the a given number
import java.util.ArrayList;
public class AllSetOfNumberSumToN {
static ArrayList<String> result=new ArrayList<String>();
static String str="1111111";
static int number=7;
public static void main(String [] args){
result.add(str);
generateNumber();
for(String s:result)
{
System.out.println(s);
}
System.out.println("The total number sets are :"+result.size());
}
//function to generate all sets whose sum is equal to the a given number
private static void generateNumber(){
int count=0,i=1,sum=0;
while(count<result.size()){
i=1;sum=0;
String str= result.get(count);
StringBuilder s1=new StringBuilder();
Character c1=str.charAt(0);
Character c2=null;
if(Integer.parseInt(c1.toString())<=number/2&&str.length()>number/2)
c2=str.charAt(1);
else{
count++;
if(count<result.size())
{
continue;
}
else
return;
}
sum =sum+Integer.parseInt(c1.toString());
if(c1!='1')
{
s1.append(c1);
}
else
{
result.remove(0);
sum=0;
}
while(c2!=null&& c2!='1'&&i<str.length())
{
i++;
sum=sum+Integer.parseInt(c2.toString());
s1.append(c2);
if(i<str.length())
c2=str.charAt(i);
}
String s2=s1.toString();
c1=str.charAt(i-1);
int partialSum=Integer.parseInt(c1.toString());
while(true)
{
s1=new StringBuilder(s2);
if(sum+partialSum<=number){
s1.append(partialSum);
int sum_total=sum+partialSum;
while(sum_total<number)
{
s1.append(1);
sum_total++;
}
result.add(s1.toString());
partialSum++;
}
else
break;
}
count++;
}
}//end of function
}
public static HashSet<ArrayList<Integer>> allSequences(int N, HashMap<Integer, HashSet<ArrayList<Integer>>> cache){
if(N == 1){
HashSet<ArrayList<Integer> > h = new HashSet<ArrayList<Integer> >();
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
h.add(list);
return h;
}
HashSet<ArrayList<Integer> > allSequence = new HashSet<ArrayList<Integer> >();
for(int i = 1;i < N; i++){
HashSet<ArrayList<Integer>> set = null;
if(cache.containsKey(i)){
set = cache.get(i);
}else{
set = allSequences(i, cache);
cache.put(i, set);
}
for(ArrayList<Integer> list : set){
ArrayList<Integer> l = new ArrayList<Integer>();
l.add(N - i);
l.addAll(list);
allSequence.add(l);
}
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(N);
allSequence.add(list);
}
return allSequence;
}
void GetAllSequences(int n)
{
int n1 = 0;
int n2 = 0;
if(n > 1)
{
for(int i=1;i<n;i++)
{
if(i == 1)
{
printf("(");
for(int t=0;t<n;t++)
{
if(t==0)
printf("1");
else
printf(",1");
}
printf(")\n");
}
else
{
n1 = n - i;
n2 = n - n1;
printf("(%d,%d)\n",n2,n1);
if(n2 == (n-1)) //last number swap
printf("(%d,%d)\n",n1,n2);
}
}
}
else
{
printf("s:%d",n);
}
}
#!/usr/bin/python
def partition(cur,pos,m,n):
#prints all unique partitions of a number (lexicographic order)
if n==0:
print cur[:pos]
return
for i in range(m,n+1):
cur[pos]=i
partition(cur,pos+1,i,n-i)
def apart(cur,pos,n): #this solves the given question
#prints all paritions of a number (no order)
if n==0:
print cur[:pos]
return
for i in range(1,n+1):
cur[pos]=i
apart(cur,pos+1,n-i)
if __name__=='__main__':
n=5
#partition([0]*n,0,1,n)
apart([0]*n,0,n)
to make it simple:
void allSums(int val) {
if (val == 0) { cout << endl; return; }
for (int i = 0 ; i < val ; ++i) {
cout << i << " ";
allSums(val-i);
}
}
void dfs(int arr[], int &cnt, int sum)
{
if (sum<0) return;
if (sum==0) {
for (size_t i=0; i<cnt; ++i) {
cout<<arr[i]<<" ";
}
cout<<endl;
}
for (int i=1; i<=sum; ++i) {
arr[cnt++]=i;
dfs(arr, cnt, sum-i);
cnt--;
}
}
void solve(int n)
{
int arr[100];
int cnt=0;
for (int i=1; i<n; ++i) {
cnt=0;
arr[cnt++]=i;
dfs(arr, cnt, n-i);
}
}
void PrintS(int n, string& s)
{
if (n == 1 ) {
cout << s << 1 << endl;
return;
}
for (int i=1; i < n; i++) {
char t[64];
sprintf(t, "%d", i);
int len = s.size();
s.append(t);
PrintS(n-i, s);
s.erase(len);
}
}
Recursive solution in C#.
static void PrintSequences(int x)
{
List<int> seq = new List<int>();
FindSeqRec(x, seq);
}
static void FindSeqRec(int x, List<int> seq)
{
if (x == 0)
{
if (seq.Count > 1)
PrintSequence(seq);
return;
}
for (int j = 1; j <= x; ++j)
{
seq.Add(j);
FindSeqRec(x - j, seq);
seq.RemoveAt(seq.Count - 1);
}
}
static void PrintSequence(List<int> seq)
{
StringBuilder b = new StringBuilder("{");
foreach (int x in seq)
{
b.Append(x);
b.Append(",");
}
if (b.Length > 1)
b.Remove(b.Length - 1, 1);
b.Append("}");
System.Console.WriteLine(b.ToString());
}
public static void NumberSum(int number, string suffix)
{
for (int i = 0; i < number; i++)
{
if (i == 0)
{
System.Console.WriteLine(number + " " + suffix);
}
else
{
int temp = number - i;
NumberSum(i, temp.ToString() + " " + suffix);
}
}
}
function sequence($num,$array,&$mainarray){
for($i=1;$i<$num;$i++){
if(array_sum($array) + $i ==$num){
$temparray = $array;
array_push($temparray,$i);
array_push($mainarray,$temparray);
break;
}elseif(array_sum($array) + $i<$num){
$temparray = $array;
array_push($temparray,$i);
sequence($num,$temparray,$mainarray);
}
}
}
$mainarray = array();
$temp = array();
sequence($n,$temp,$mainarray);
void mysum(int n,int currentN,int sum,vector<int>v, set<vector<int>>&result){
if(currentN>=n) return;
sum += currentN;
if(sum == n){
v.push_back(currentN);
result.insert(v);
return;
}else if(sum<n){
v.push_back(currentN);
}
else {
return;
}
for( int i =currentN; i<n; ++i){
mysum(n,i,sum,v,result);
}
}
set<vector<int>> sumSequencesToN(int n){
set<vector<int>> result;
if(n==0){
vector<int>v;
result.insert(v);
}
if(n==1){
vector<int> tempv;
tempv.push_back(1);
result.insert(tempv);
return result;
}
for( int j =1; j<=n/2; ++j){
vector<int>tempv;
mysum(n,j,0,tempv,result);
}
return result;
}
public class SequencesSum {
public static void main(String args[]){
Sequences(10);
}
static void Sequences(int n){
int j=1;
StringBuffer seq = new StringBuffer();
seq.append("(");
for(int i=1;i<n;i++){
seq.append("(");
seq.append(i);
seq.append(",");
seq.append(n-i);
seq.append(")");
}
seq.append("(");
while(j<=n){
seq.append(1);
if(j!=n)
seq.append(",");
j++;
}
seq.append(")");
seq.append(")");
System.out.println(seq);
}
}
Simple php code
function sumSequence($num, $seed=1)
{
$resultArray = array();
if($num == 0)
{
//end of the road
$resultArray[] = array();
}
elseif($num == 1)
{
//trailing 1
$resultArray[] = array(1);
}
else
{
for($i = $seed; $i <= $num; $i++)
{
$temp = sumSequence($num - $i, $i);
foreach($temp as $row)
{
//Add $i to the begining of each array
array_unshift($row, $i);
$resultArray[] = $row;
}
}
}
return $resultArray;
}
$start = 5;
$result = sumSequence($start);
print_r($result);
function sumSequence($num, $seed=1)
{
$resultArray = array();
if($num == 0)
{
//end of the road
$resultArray[] = array();
}
elseif($num == 1)
{
//trailing 1
$resultArray[] = array(1);
}
else
{
for($i = $seed; $i <= $num; $i++)
{
$temp = sumSequence($num - $i, $i);
foreach($temp as $row)
{
//Add $i to the begining of each array
array_unshift($row, $i);
$resultArray[] = $row;
}
}
}
return $resultArray;
}
$start = 5;
$result = sumSequence($start);
print_r($result);
function sumSequence($num, $seed=1)
{
$resultArray = array();
if($num == 0)
{
//end of the road
$resultArray[] = array();
}
elseif($num == 1)
{
//trailing 1
$resultArray[] = array(1);
}
else
{
for($i = $seed; $i <= $num; $i++)
{
$temp = sumSequence($num - $i, $i);
foreach($temp as $row)
{
//Add $i to the begining of each array
array_unshift($row, $i);
$resultArray[] = $row;
}
}
}
return $resultArray;
}
$start = 5;
$result = sumSequence($start);
print_r($result);
Recursive calls.
- Shu January 24, 2013public static LinkedList<LinkedList<Integer>> getSumPaths(int number){ if(number == 0){ LinkedList<LinkedList<Integer>> lls = new LinkedList<LinkedList<Integer>>(); lls.add(new LinkedList<Integer>()); return lls; } LinkedList<LinkedList<Integer>> toreturn = new LinkedList<LinkedList<Integer>>(); for(int i = 1; i <= number; i ++){ LinkedList<LinkedList<Integer>> llreturn = getSumPaths(number - i); for(LinkedList<Integer> ls : llreturn){ ls.add(i); toreturn.add(ls); } } return toreturn; }