Directi Interview Question for Developer Program Engineers


Country: India
Interview Type: Phone Interview




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

int Count(int n, int r, int g, int b)
{
    vector<int> fact(n+1);
    fact[0] = 1;
    for (int i = 1 ; i <= n ; i++) {
        fact[i] = fact[i-1]*i;
    }

    int remain = n - (r + g + b);
    int sum = 0;

    for (int i = 0 ; i <= remain ; i++) {
        for (int j = 0 ; j <= remain-i ; j++) {
            int k = remain - (i+j);
            sum = sum + fact[n] / (fact[i+r]* fact[j+g]*fact[b+k]);
        }
    }
    return sum;
}

- Himanshu Sahu July 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static int count(int n, int r, int g, int b){
         int count = 0;
         int x = n - (r+g+b);
         if(x==0)
         return fact(n)/(fact(r)*fact(g)*fact(b));
         
         for(int i=0; i<=x; i++){
             for(int j=0; j<=x-i; j++){
                 for(int k=0; k<=x-i-j; k++){
                     int p = r + i;
                     int q = g + j;
                     int s = b + k;
                     if(n == p+q+s)
                     count = count + fact(n)/(fact(p)*fact(q)*fact(s));
                 }
             }
         }
         return count;
     }
     
     public static int fact(int n){
         int count = 1;
         for(int i=2; i<=n; i++){
             count = count*i;
         }
         return count;
     }

- prynkdhk November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

int Count(int n, int r, int g, int b)
{
    vector<int> fact(n+1);
    fact[0] = 1;
    for (int i = 1 ; i <= n ; i++) {
        fact[i] = fact[i-1]*i;
    }

    int remain = n - (r + g + b);
    int sum = 0;

    for (int i = 0 ; i <= remain ; i++) {
        for (int j = 0 ; j <= remain-i ; j++) {
            int k = remain - (i+j);
            sum = sum + fact[n] / (fact[i+r]* fact[j+g]*fact[b+k]);
        }
    }
    return sum;
}

- Anonymous July 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

int Count(int n, int r, int g, int b)
{
    vector<int> fact(n+1);
    fact[0] = 1;
    for (int i = 1 ; i <= n ; i++) {
        fact[i] = fact[i-1]*i;
    }

    int remain = n - (r + g + b);
    int sum = 0;

    for (int i = 0 ; i <= remain ; i++) {
        for (int j = 0 ; j <= remain-i ; j++) {
            int k = remain - (i+j);
            sum = sum + fact[n] / (fact[i+r]* fact[j+g]*fact[b+k]);
        }
    }
    return sum;
}

- Anonymous July 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

int Count(int n, int r, int g, int b)
{
    vector<int> fact(n+1);
    fact[0] = 1;
    for (int i = 1 ; i <= n ; i++) {
        fact[i] = fact[i-1]*i;
    }

    int remain = n - (r + g + b);
    int sum = 0;

    for (int i = 0 ; i <= remain ; i++) {
        for (int j = 0 ; j <= remain-i ; j++) {
            int k = remain - (i+j);
            sum = sum + fact[n] / (fact[i+r]* fact[j+g]*fact[b+k]);
        }
    }
    return sum;
}

- Himanshu Sahu July 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not sure if this is the right solution but it give the right answer for the example.

Basically, distribute the 'extra' (i.e n - r - g - b) into the three types and for each such distribution calculate the number of permutations using multiset permutations.

package com.algo;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class StringOfSizeN {

	private static final int numberOfWays(int r, int g, int b, int n) {

		if (r + g + b > n) {
			return -1;
		}

		int extras = n - (r + g + b);

		List<List<Integer>> rgbs = getPartitions(extras, 3);

		int sum = 0;
		for (List<Integer> list : rgbs) {
			int R = r + list.get(0);
			int G = g + list.get(1);
			int B = b + list.get(2);
			sum += getCombosCount(n, R, G, B);
		}

		return sum;
	}

	private static int getCombosCount(int n, int r, int g, int b) {
		return factorial(n) / (factorial(r) * factorial(g) * factorial(b));
	}

	private static Map<Integer, Integer> factorialCache = new HashMap<Integer, Integer>();

	private static int factorial(int i) {

		if (i <= 1) {
			return 1;
		}

		if (factorialCache.containsKey(i)) {
			return factorialCache.get(i);
		} else {
			int f = i * factorial(i - 1);
			factorialCache.put(i, f);
			return f;
		}

	}

	private static List<List<Integer>> getPartitions(int extras, int n) {

		if (n == 1) {
			List<List<Integer>> l = new ArrayList<>();
			List<Integer> l2 = new ArrayList<>();
			l2.add(extras);
			l.add(l2);
			return l;
		}

		List<List<Integer>> allPartitions = new ArrayList<>();
		for (int r = 0; r <= extras; r++) {
			List<List<Integer>> l = getPartitions(extras - r, n - 1);
			for (List<Integer> list : l) {
				List<Integer> copy = new ArrayList<>(list);
				copy.add(r);
				allPartitions.add(copy);
			}
		}

		return allPartitions;
	}

	public static void main(String[] args) {
		System.out.println(StringOfSizeN.numberOfWays(1, 1, 1, 4));
	}
}

- Anonymous September 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As a follow up solution of glebstepanov1992's solution. This is definitely a permutation problem. We also have to do determine how many R, G and B we have. And they sum up to the size n. For each case where r + g + b = n, we have (N!/(r! * g! * b!) solutions.

- ravio September 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

solution in python.......

no of ways= fact(n)/(fact(p)*fact(q)*fact(s))

where p,q,s are no of characters of 3 types

# your code goes here
r=int(raw_input())
g=int(raw_input())
b=int(raw_input())
n=int(raw_input())

fact=[]
fact.append(1);
for i in range(1,1001):
	fact.append(fact[i-1]*i)
	
def getPartitions(e,n):
	l=[]
	if n==1:
		p=[]
		p.append(e);
		l.append(p)
		return l
	for i in range(0,e+1):
		lt=getPartitions(e-i,n-1);
		for j in lt:
			j.append(i);
			l.append(j);
	return l
	
	
def ways(r,g,b,n):
	sum=0;
	l=getPartitions(n-r-g-b,3)
	for i in l:
		p=r+i[0]
		q=g+i[1]
		r=b+i[2]
		print i
		sum+=(((fact[n]/fact[p])/fact[q])/fact[r])	
	return sum	
	
print ways(r,g,b,n);

- harshit.knit October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;


public class RGB {
public static HashMap<Integer,Long> factorialCache=new HashMap();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
int r=2,g=2,b=1,n=5;
int e=n-(r+g+b),count=0;
//System.out.print("e="+e);
factorialCache.put(1,Long.parseLong("1"));
for(int i=2;i<=n;i++)
{
long f=i*factorialCache.get(i-1);
	factorialCache.put(i,f);
}
//System.out.print("e="+factorialCache.get(6));
for(int i=0;i<=e;i++)
{
	for(int j=0;j<=e;j++)
	{
		//for(int k=0;k<=e;k++)
		{
			int k=e-(i+j);
			if(k<0) continue;
			else
			count+=ways(r+i,g+j,b+k,n);
		}
			
	}
}
System.out.print(count);
}

	
	public static long ways(int r,int g,int b,int n)
	{
		
		
		return ((factorialCache.get(n)/factorialCache.get(r))/factorialCache.get(g))/factorialCache.get(b);
	}
	
	
	
	
	
	
	
	
	
	
}

- Arnab November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
import java.io.*;

public class answer {

public static int fact(int n){
int factorial =1;
int i=1;
while (i<n+1){
factorial = factorial*i;
i++;
}
return factorial;
}

public static int ways(int n, int a, int b) {
return fact(n)/(fact(n-a-b)*fact(a)*fact(b));
}

public static void main (String args[]){
Scanner sc = new Scanner (System.in);
int n= sc.nextInt();
int a= sc.nextInt();
int b= sc.nextInt();
int c= sc.nextInt();
int ans = ways(n,a,b)+ ways(n,b,c) + ways(n,c,a);
System.out.println("Total no. of ways= "+ ans);
}
}

- SyD November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int Count(int n, int r, int g, int b)
{
    vector<int> fact(n+1);
    fact[0] = 1;
    for (int i = 1 ; i <= n ; i++) {
        fact[i] = fact[i-1]*i;
    }

    int remain = n - (r + g + b);
    int sum = 0;

    for (int i = 0 ; i <= remain ; i++) {
        for (int j = 0 ; j <= remain-i ; j++) {
            int k = remain - (i+j);
            sum = sum + fact[n] / (fact[i+r]* fact[j+g]*fact[b+k]);
        }
    }
    return sum;
}

- himanshu006.iiita July 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

N!/(k1! * k2! * ... * kn!) isnt it? permutation with repeatitions.

- glebstepanov1992 September 04, 2014 | Flag Reply


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