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);
}
}

- ch.v.suresh February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Troll February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

compiled on PC .. Its working fine..

- ch.v.suresh February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This only works if the requirement is no duplicate numbers

- weiwuwei March 30, 2013 | Flag
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));
}

- Anonymous February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how to get actual partitions from this??

- XYZ February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

try with n=100,

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Troll February 15, 2011 | Flag
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

- Anonymous February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is a pseudo code for the same


printAllSum(a,n){

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

- Anonymous February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 15, 2011 | Flag
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).

- buried.shopno February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

...

- GekkoGordan February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isn't NP-Complete the other way around?

- Sankalp November 22, 2011 | Flag
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);
}

}

- Anonymous February 16, 2011 | Flag Reply
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;
}

- shashank7android February 16, 2011 | Flag Reply
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++;
}
}

- dinesh February 16, 2011 | Flag Reply
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

- Anonymous March 10, 2011 | Flag Reply
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) {
Add(min);
Add(val);
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) {
temp.add(item);
}
private static void RemoveLast() {
temp.remove(temp.size() - 1);
}
}

- chendi.cd March 18, 2011 | Flag Reply
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();
		}
				
	}

- Eddie April 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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")

- Jane April 26, 2011 | Flag
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";
}

- vikas tandi July 28, 2011 | Flag Reply
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>

- Anonymous August 30, 2011 | Flag Reply
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}

- neeraj.fullwithattitude September 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- neeraj.fullwithattitude September 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- neeraj.fullwithattitude September 17, 2011 | Flag
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);
}

}

- Anonymous January 04, 2012 | Flag Reply
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,[]);

- Tintin April 09, 2012 | Flag Reply
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;
}
}
}


}

- Scott May 07, 2012 | Flag Reply
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();
}

- root July 22, 2012 | Flag Reply
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

- Aashish July 22, 2012 | Flag Reply
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;
}

- Anand July 27, 2012 | Flag Reply
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.

- Supreeth August 20, 2012 | Flag Reply
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)
                                        AL.add(1);
                        }
                        result.addAll(templist);
                }
                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>();
                        templist.add(i);
                        templist.add(input-i);
                        result.add(templist);
                }
                return result;
        }
}

This probably should work.

- bob bobson October 03, 2012 | Flag Reply
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

- Anonymous March 17, 2014 | Flag Reply
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

- Anonymous March 17, 2014 | Flag Reply
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);
        }
    }
}

- LuoZheng03 March 18, 2014 | Flag Reply
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!!!!

- XYZ February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can u explain the logic?

- Tom February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

apply for facebook, they looking great coder like u.

- root July 22, 2012 | Flag
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).

- raj February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

U r the real hero..go for google

- XYZ February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- doubt February 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- wrong one February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- wrong one February 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

roflllllllllllllll

- son_of_a_thread August 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

apply for facebook, they looking great coder like u.

- cool July 22, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More