## Yahoo Interview Question for Software Engineer / Developers

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

#include <stdio.h>

#define Max_Size 20

void sum_of_numbers_till_n(int a[],int index_till);
int main()
{
int n = 0,index_till=0;
int a[Max_Size];
while(1)
{
printf("Enter 'n' value : ");
scanf("%d",&n);
if(n==0) break;
a[0] = n;
sum_of_numbers_till_n(a,index_till);
printf("\n\n");
}
}

void sum_of_numbers_till_n(int a[],int index_till)
{
int i,j;
int start_v,end_v;
int b[Max_Size];

for(i=1;i<=(a[index_till]/2);i++)
{
start_v = i;
end_v = a[index_till]-i;

if(start_v == end_v)
return;

for(j=0;j<=index_till;j++)
{
if(start_v==a[j] || end_v==a[j])
{
return;
}
}

for(j=0;j<=(index_till-1);j++)
{
b[j] = a[j];
}

b[index_till] = start_v;
b[index_till+1] = end_v;

printf("\n");
for(j=0;j<=(index_till+1);j++)
printf("%d ",b[j]);

sum_of_numbers_till_n(b,index_till+1);
}
}

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

Doesn't work. Post pseudo code or algo. instead

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

compiled on PC .. Its working fine..

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

Example 9:

Here V - Valid,
DD - Digit duplicate
R - Repeat in other order

1,8 (V) --> 1,2,6 (V) -->1,2,1,5 (DD)
1,2,2,4 (DD)
1,3,5 (V) -->1,3,1,4 (DD)
1,3,2,3 (DD)
2,7 (V) --> 2,1,6 (R)
2,2,5 (DD)
2,3,4 (V)
3,6 (V) --> 3,1,5 (R)
3,2,4 (R)

4,5 (V) --> 4,1,4 (DD)
4,2,4 (R)
4,3,2 (R)

O/p: Only valid out put (Excluding DD and R)
1,8
2,7
3,6
4,5
1,2,6
1,3,5
2,3,4

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

This only works if the requirement is no duplicate numbers

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

``````this is Dynamic Programming question coin minimum denomination
How many ways you can get the denomination for given amount
int n = 10;
func_count(n, n);
int func_count( int n, int m )
{
if ( n == 0 )
return 1;
if ( n < 0 )
return 0;
if ( m <= 0 && n >= 1 )
return 0;
return (func_count(n, m - 1) + func_count(n - m, m));
}``````

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

how to get actual partitions from this??

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

try with n=100,

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

@Anonymous: good point. the algorithm is limited by datatype size i.e. for n >=38, you would already exceed 'double' datatype limit. because 38 can be represented as a sum of 38 1's, we need some other algo for just printing the integers as a sum rather than storing them. i.e. if for n=100 if we can print 100 1's rather than trying to build a datatype that stores 100 1's

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

A possible logic is can be as follows:=
number if ways we can print sum of n is :-
1 + all possible ways we can print n-1
2 + all possible ways we can print n-2 and so on...
drawback:= repeated series like in case of 5 both 1+1+3 and 3+1+1 will be printed.. can be avoided by keeping hash

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

Here is a pseudo code for the same

printAllSum(a,n){

if(n==0)
print a;
for(int i=1;i<=n;i++){
printAllSum(a,n-i);
remove(a,i);
}
}

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

its easy with n<=9 , try n= 15

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

I believe no polynomial time exists for this problem, as it can be converted to some NP-complete problem.

However, if it asks for "number of ways" you can make n from positive integers in the range 1 to n, polynomial time algorithm is doable (like one pointed before) with complexity O(n^2).

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

...

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

Isn't NP-Complete the other way around?

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

void printPossibleSum(int n, String st) {
if(n == 0) {
syso(st);
reutrn;
}
for(int i=1; i<=n; i++) {
printPossibleSum(n-i, st+i);
}

}

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

#define MAX_POINT 3
#define ARR_SIZE 100
#include<stdio.h>

/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size);

/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int n, int i)
{

/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
static int arr[ARR_SIZE];

if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= MAX_POINT; k++)
{
arr[i]= k;
printCompositions(n-k, i+1);
}
}
}

/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}

/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 and 3 of %d are\n", n);
printCompositions(n, 0);
getchar();
return 0;
}

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

fun(a[],0,0);//calling func

func(int a[],i,j)
{
if(sum of the array elements multiplied by (indices+1)==NUMBER)
print numbers

while(i<=NUMBER)
{
while(j<=NUMBER)
{
a[i]=j;
j++;
func(a[],i,j)

}
j=1;i++;
}
}

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

how about creating all the subset from the set {1, 2, 3,..., n} and then adding the elements of each subset to check whether the sum is n

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

import java.util.Vector;
public class SumOfPossibleV2 {
public static Vector<Integer> temp = new Vector<Integer>();
public static void breakDown(int n) {
for (int i = 1; i <= n / 2; i++) {
breakDown(i, n - i);
}
}
public static void breakDown(int min, int val) {
if (val >= min) {
Print();
if ((val - min) >= min) {
RemoveLast();
for (int i = min; i <= val / 2; i++) {
breakDown(i, val - i);
}
RemoveLast();
} else {
RemoveLast();
RemoveLast();
}
}
}
private static final String f = "%d ";
private static void Print() {
Return();
for(int i = 0; i < temp.size();i++){
Joint(temp.get(i));
}
}
private static void Joint(int val){
System.out.print(String.format(f, val));
}
private static void Return(){
System.out.println();
}
private static void Add(int item) {
}
private static void RemoveLast() {
temp.remove(temp.size() - 1);
}
}

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

``````static public void printPossibilities(int cur, int max) {
for(int i = cur; i > 0; i--) {
int meta = (cur - i);
System.out.print(meta + " + " + i + ", ");

if(meta > 1) {
String ret = "";

while(meta > 1) {
meta--;
for(int j = cur - i; j > meta; j--) {
ret += "1 + ";
}
ret += meta + " + " + i + ", ";
}

System.out.print(ret);
}

System.out.println();
}

}``````

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

Its a good solution, but I don't think it works for all cases. For eg, if n = 10, execution of this code does not produce 1 + 2 + 2 + 5, which is a valid solution ("all the ways in which n can be represented as sum of positive integers")

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

``````#include <iostream>

using namespace std;

static void print(int s[], int n);
static void partitionOfSize(int num, int size, int s[], int currentSize);

void generatePartitions(int num)
{
int *s;
s = new int[num];

for(int i = 2; i <= num; i++)
partitionOfSize(num, i, s, i);
}

void partitionOfSize(int num, int size, int s[], int currentSize)
{
int maxElement;

if(currentSize == 1)
{
s[size - currentSize] = num;
print(s, size);
return;
}
maxElement = num/currentSize;

for(int i = 1; i <= maxElement; i++)
{
if(size > currentSize && s[size - currentSize - 1] > i)
continue;
s[size - currentSize] = i;
partitionOfSize(num-i, size, s, currentSize-1);
}
}

void print(int s[], int n)
{
for(int i = 0; i < n; i++)
cout << s[i] << " ";

cout << "\n";
}``````

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

<pre lang="" line="1" title="CodeMonkey14744" class="run-this">#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int s,a,d,sum,i;
cout<<"enter the number\n";
cin>>s;
cout<<"\n";
for(d=1;d<=(s-2);d++)
{
for(a=1;a<=(s-1);a++)
{
sum=0;
i=a;
while(sum<s)
{
sum=sum+i;
i=i+d;
}
if(sum==s)
{
i=a;
sum=0;
while(sum<s)
{
sum=sum+i;
cout<<" "<<i;
i=i+d;
}
cout<<"\n";
}

}
}
getch();
}</pre><pre title="CodeMonkey14744" input="yes">
</pre>

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

Can be easily solved using recursion.

for sum(30)

print(1,29);
sum(30) = sum(29) + {1}<-My Stack
print(1,1,28);
sum(29) = sum(28) + {1,1}

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

If u want me 2 write the code, let me know

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

N is the number given.
int stack[N];

sum(int n, int index)
{
if(n==0)
{
print stack;//use a while loop till index -1
return;
}

else
{
for all i=1 to ceil((float)n/2))
{
stack[index] = i;
print stack and n-i; // all elements of stack and n-i
sum(n-i, index+1);
}
}
}

initially call sum(N,0)

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

1) a number can be represented with sum of 2 digits,3 digits, 4 digit ... maximum digits can be number its self.. where number will be 1+1+1+1+.............1(n times)

2) value of each digit can go max to num/ no of digits... after this cases will get repeated

The approached I use is kind of DP

int path[],int len,int num
// get all the possible combination of digits
for(int digits=2;digits<=num;digits++)
{
evaluate(path,len,num,digits)
}

// function to find all possible solution for a given number of digits in representing sum
void evaluate (int path[], int len , int num, int digit)
{
if(digit==0||num==0)
{
print path[0 to len]
if(num!=0)
print num

return
}

for(int i=0; i<=num/digit;i++)
{
path[len]=i;
evaluate(path,len+1,num-i,digit-1);
}

}

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

#here is the python code

``````def main(num,arr):
if num==0:
print arr;
return;

for i in range(1,num+1):
main(num-i,arr+[i])

# num hold the integer n
num = 4;
main(num,[]);``````

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

public static void printNum(int n){
int [] array=new int [n];
sum_num(n,0,array,0,0);
}

private static void sum_num(int n,int cur,int [] array, int count,int next){
if (n==cur){
for (int i=0;i<count;i++){
System.out.print(array[i]+",");
}
System.out.println();
}else if (cur>n){
return;
}else{
for (int i=1;i<n;++i){
if (i<next){
continue;
}
cur+=i;
array[count]=i;
sum_num(n,cur,array,count+1,i);{
cur-=i;
}
}
}

}

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

//Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers.

#include<stdio.h>
//#include<conio.h>
void printall(int n,char str[],int index)
{
if(n==0)
{
printf("%s\n",str);
return;
}
if(n<0)
return;
int i;
for(i =1;i<=n;i++)
{
str[index-1] = i+48;
str[index] = '\0';
index = index+1;

printall(n-i,str,index);
index--;
}

}

int main()
{
int n;
printf("enter a number n\n");
scanf("%d",&n);
// fflush(stdin);
char str[200];
printall(n,str,1);
// getchar();
}

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

A recursive approach:

``````void print(int* res,int depth)
{
int i;
for(printf("\n"),i=0;i<depth;printf("%d ",res[i]),++i);
}

void foo(int sum,int N,int* res,int depth)
{
int i;
if(sum<0) return;
if(!sum)
print(res,depth);
else
for(i=1;i<N;i++)
if(!depth || i>=res[depth-1])
{
res[depth]=i;
foo(sum-i,N,res,depth+1);
}
}``````

Complete code here: ideone.com/z2rcm

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

#include<stdio.h>
#include<conio.h>
void printall(int n,char str[],int index)
{
if(n==0)
{
printf("%s\n",str);
return;
}
if(n<0)
return;
for(int i =1;i<=n;i++)
{
str[index-1] = i+48;
str[index]='\0';
index = index+1;

printall(n-i,str,index);
index--;
}

}

int main()
{
int n;
printf("enter a number n\n");
scanf("%d",&n);
fflush(stdin);
char str[100];
printall(n,str,1);
getchar();
return 0;
}

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

public class PrintSum {

public static void main(String[] args) {

printSum (5, "");
}

private static void printSum(int n, String prefix) {
if(n <= 0) {
System.out.println(prefix);
return;
}
for(int i = 1; i <= n; i++) {
String temp = "";
if(prefix.length() == 0)
temp = i + "";
else
temp = "," + i;
printSum(n-i, prefix + temp);
}
}
}

I need to solve this by DP. Just wanna check opinion before I proceed further.

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

``````import java.util.*;
import java.lang.*;

class Main
{
public static void main (String[] args) throws java.lang.Exception
{
int input=5;
System.out.println(getRep(input));
}
public static ArrayList<ArrayList<Integer>> getRep(int input)
{
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
for (int i=1; i<input; ++i)
{
ArrayList<ArrayList<Integer>> templist=get2Rep(input-i);
for (ArrayList<Integer> AL: templist)
{
for (int j=0; j<i; ++j)
}
}
return result;
}
public static ArrayList<ArrayList<Integer>> get2Rep(int input)
{
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
for (int i=1; i<input; ++i)
{
ArrayList<Integer> templist=new ArrayList<Integer>();
}
return result;
}
}``````

This probably should work.

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

void partition(int n, int m = 0)
{
int i;
// if the partition is done
if(n == 0){
// Output the result
for(i = 0; i < m; ++i)
printf("%d ", list[i]);
printf("\n");
return;
}
// Do the split from large to small int
for(i = n; i > 0; --i){
// if the number not partitioned or
// willbe partitioned no larger than
// previous partition number
if(m == 0 || i <= list[m - 1]){
// store the partition int
list[m] = i;
// partition the rest
partition(n - i, m + 1);
}
}
}

This one is much easier to understand

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

void partition(int n, int m = 0)
{
int i;
// if the partition is done
if(n == 0){
// Output the result
for(i = 0; i < m; ++i)
printf("%d ", list[i]);
printf("\n");
return;
}
// Do the split from large to small int
for(i = n; i > 0; --i){
// if the number not partitioned or
// willbe partitioned no larger than
// previous partition number
if(m == 0 || i <= list[m - 1]){
// store the partition int
list[m] = i;
// partition the rest
partition(n - i, m + 1);
}
}
}

This one is much easier to understand

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

This is the simplest recursion algorithm I can find,
I checked, and it works. Please tell me if you have any questions.

``````void partition(int n, int m = 0)
{
int i;
// if the partition is done
if(n == 0){
// Output the result
for(i = 0; i < m; ++i)
printf("%d ", list[i]);
printf("\n");
return;
}
// Do the split from large to small int
for(i = n; i > 0; --i){
// if the number not partitioned or
// willbe partitioned no larger than
// previous partition number
if(m == 0 || i <= list[m - 1]){
// store the partition int
list[m] = i;
// partition the rest
partition(n - i, m + 1);
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

void find(int n,int arr[],int idx)
{
if(n==0)
{
print(arr,idx);
return;
}

int k=idx>0?arr[idx-1]:1;
for(int i=k;i<=n;i++)
{
arr[idx]=i;
if(n-i >=0){
called++;
find(n-i,arr,idx+1);}
}
}

I still don't know thw complexity of this one...someone tell me!!!!

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

Can u explain the logic?

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

apply for facebook, they looking great coder like u.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

int find_parts(int n)
{
for(int i=1; i<=n-2; i++){
for(int j=i+1; j<=n-1; j++){
for(int k=j+1; k<=n; k++)
{
if((i+j+k) == n)
printf ("*** %d+%d+%d=%d\n", i, j, k, n);
}
}
}
return 0;
}

Time complexity using this approach is O(n^3).

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

U r the real hero..go for google

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

Do you think it will work when sum of 4 or more nos equals 'n'?

E.g. If n is 30, will this print 26,1,1,1,1 or 5,5,5,5,10?

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

this will not even print the combination 2 2 fo n=4

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

this will not even print the combination 2 2 for n=4

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

roflllllllllllllll

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

apply for facebook, they looking great coder like u.

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.