Bloomberg LP Interview Question for Financial Software Developers Software Engineer / Developers






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

If you analyse the problem you will see first three digits (i.e. first half) range from 100 to 999 and the next three digits (i.e. second half) range from 001 to 999. Also the sum of digits in both half range from 1 to 27.
So first find out how many number in both sides where sum of digits is 1 or 2 or... 27.
Once you find the number of occurance then multiply the corresponding occurance from both sides. Finally add the mutiplied value to get the result.
Here is sample code to do this:

// Find out how many times the same sum of the digits occur between number 
// 'first' to 'last'.
//
void findOccurance(int first, int last, std::map<int, int>& occurance)
{
    for (int n=first; n<=last; ++n)
    {
        int sum = 0;
        int remain = n;
        while (remain)
        {
            sum += remain%10;
            remain /= 10;
        }
        occurance[sum] += 1;
    }
}

int totalOccurance()
{
	std::map<int, int> occurance100to999;
	std::map<int, int> occurance1to999;
    findOccurance(100,999, occurance100to999);
    findOccurance(1,99, occurance1to999); // get only the range 1 to 99

    // update occurance1to999 by adding occurance100to999 to it.
    std::map<int, int>::iterator itr0;
    for (itr0=occurance100to999.begin(); itr0 != occurance100to999.end(); ++itr0)
    {
        occurance1to999[itr0->first] += occurance100to999[itr0->first];
    }

	int sum = 0;
    std::map<int, int>::iterator itr1;
    std::map<int, int>::iterator itr2;
    for (itr1=occurance100to999.begin(), itr2=occurance1to999.begin(); itr1 != occurance100to999.end(); ++itr1,++itr2)
    {
        cout << itr1->first << "  " << itr1->second << " x " << itr2->second << " = " << itr1->second * itr2->second << std::endl;
		sum += itr1->second * itr2->second;
    }

    return sum;
}

- Shil November 26, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Shil, Your algorithm is correct, I have not gone through the program though. Just one thing you have to take care is the removing of those numbers which has leading zeros. Like for sum 1 (001..., 010...) and similarly for other sum.

Your approach is correct and in my opinion this is the way to go through.

- Shail January 26, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ohh I have missed that, you have already taken care of those numbers starting with zero. You algo is correct.

- Shail January 26, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Initial call : print("",0,0);
print(String a, int first3result, int last3result){
int len = a.length();
if(len<3){ // check if we are in first half of string
     for(int i=0; i<=9; i++){
     int firsthalfresult = first3result + i;
     String forward = a+i;
     print(forward, firsthalfresult, last3result); // only send result formed by placing new digit at this position at first half of our final digit.
     }
}
else if(len>=3 && len<6){ // we already have first 3 digits at its place, and placing last part of number in place.
     for( int i=0; i<=9 ; i++){
     int lasthalfresult = last3result+i;
     String forward = a+i;
     print(forward, first3result, lasthalfresult);
     }

  }
else if(len == 6){ // our final number has been created and we have sum of first 3 digits and last 3 digits
     if (first3result == last3result){
        System.out.println(a);
     }
  }
 }
}

The above function will print the number as string only if first three half result is equal to last three half result.

- Gurjinder November 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cool, thanks.
just an optimization,
in else if(len>=3 && len<6){
if first3result < last3result
return

- Anonymous November 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Above algorithm will also print strings like 00X00X which is invaled output

- GG January 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i=100000; i<999999; i++){
			int[] a = new int[6];
			int mod = i;
			for(int j=0; j<6; j++){
				a[j] = mod%10;
				mod = mod/10;
			}
			if(a[0] + a[1] + a[2] == a[3] + a[4] + a[5]){
				System.out.println(i);
			}
		}

- Anonymous November 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can optimize by pre-compute sum of three-digits number from 000,001,...,999 into table

- Anonymous November 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#define BITS_IN_HALF_INT 32 //2 * 8 .. int is 4 bytes

int SumOf2HalfsAreEqual(int digits)
{
	if(digits%2 || digits > BITS_IN_HALF_INT)
	{
		printf("Invalid i/p\n");
		return -1;
	}
	else
	{
		int half = digits / 2;
		int num = 10, start = 1;
		
		while(half-- != 1)
		{
			start	=	num;
			num		=	num * 10;
		}

		printf("Number of half's equal in %d digit number are : %d\n",digits, num-start);

		return (num - start);
	}
}

- veen_viz November 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typo in last post!!
macro must be as below
#define BITS_IN_HALF_INT 16 //2 * 8 .. int is 4 bytes

- veen_viz November 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void first_half_equals_second_half()
{
for(int i = 100000; i <=999999; i++)
{
int first_half = i/1000;

int second_half = i%1000;

if (first_half == second_half )
cout <<i<<endl;
}
}

- jolly November 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wrong, Read the question again

e.g 112211

- Anonymous November 19, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void fNum()
{	
	int a,b,j,k;
	for(i=100000;i<=999999;i++)
	{
		a = i/1000;
		b = i%1000;
		j = Sum(a);
		k = Sum(b);
		if(j==k)
			print(i);
	}
	
}

int Sum(int a)
{
	int sum=0;
	while(a!=0)
	{
		sum = sum + a%10;
		a = a/10;
	}
	return sum;
}

- Anonymous November 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good solution and easy to understand

- Anonymous November 19, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

bad solution. not optimized. you shudnt be checking every number in a loop

- Anonymous November 20, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about an algorithm something like this,

1. traverse from 100 to 999. Take this is as the first half ( 100 000 to 999 999 )
2. for each of the above given number, find all possible combination
Say, for 100 the other half could be 100 / 010 / 001
for 101 the other half could be 110 101 011 200 020 002
for 102 the other half could be 111 120 012 102 210 201 021 300 030 003

still some more logics are needed. I still need to think

- Anonymous November 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the output of the above sample code:
Sum of digits, number of occurance in first half, number of occurance in second half, total occurance respectively.

1  1 x 3 = 3
2  3 x 6 = 18
3  6 x 10 = 60
4  10 x 15 = 150
5  15 x 21 = 315
6  21 x 28 = 588
7  28 x 36 = 1008
8  36 x 45 = 1620
9  45 x 55 = 2475
10  54 x 63 = 3402
11  61 x 69 = 4209
12  66 x 73 = 4818
13  69 x 75 = 5175
14  70 x 75 = 5250
15  69 x 73 = 5037
16  66 x 69 = 4554
17  61 x 63 = 3843
18  54 x 55 = 2970
19  45 x 45 = 2025
20  36 x 36 = 1296
21  28 x 28 = 784
22  21 x 21 = 441
23  15 x 15 = 225
24  10 x 10 = 100
25  6 x 6 = 36
26  3 x 3 = 9
27  1 x 1 = 1

The result is 50412
Note that there are 900K six digits numbers and only about 50K satify the condition.
The above implementation loop through only 1K numbers as opposed to 900K numbers.
However it still has room to improve the algorithm as you may notice the number of occurance follow a pattern.

- Shil November 26, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would do somethig like this:
For each number between 0 to 27, find the number of ways of 3 numbers adding to that number, square them and sum them all;

The way u find the number of ways of summing numbers is through polynomail multiplication.

- R December 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

One correction: you can't just square them. The first 3 digits are more restricted in that the leading digit cannot be 0.

- Bullocks December 30, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

another possible solution is as below
//NOTE i have not compiled this code.
multimap<int,int> multimap;

for(i = 1 to 9 )
for(j = 1 to 9)
for(k = 1 to 9)
{

multimap[i + j + k] = (i*100+j*10+k);

}
//internally multimaps store the data in sorted order based on key
//so all the digit additions values will be stored in sorted order
//now get the iterators to traverse the multimaps and check for same digit addition values
multimap::iterator it;
multimap::iterator it2 = multimap.begin();
it2++; //make it point to 2nd map entry
for(it = multimap.begin();it2 != multimap.end();it2++)
{

if(it.first() == it2.first())
{
cout<<it.second()<<it2.second();
}

}

- sachin323 December 21, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So you would release code in public without compiling and running it first? Not a healthy sign if you want to work for a reputable software house.

- Bullocks December 30, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a Python implementation. Got same answer 50412 as Shil:

def equal_digit_sums():
    dists = {}
    for i in range(1000):
        digits = [int(d) for d in str(i)]
        dsum = sum(digits)
        if dsum not in dists:
            dists[dsum] = [0,0]
        dists[dsum][0 if len(digits) == 3 else 1] += 1
    def prod(dsum):
        t = dists[dsum]
        return (t[0]+t[1])*t[0]
    return sum(prod(dsum) for dsum in dists)

print(equal_digit_sums())

- Bullocks December 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int count = 0;
     for(int i = 100000; i< 999999; i++){
	if(i/1000 == i%1000){
	    count ++;
	}
     }
    System.out.println(count);

- Snehal March 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correct version:

public class SumOfFirstThreeSameAsLastThree {
	
	public static void main(String[] args) {
		int count = 0;
		for(int i = 100000; i< 999999; i++){
			if(sumOfDigits(i/1000) == sumOfDigits(i%1000)){
				System.out.println(i);
				count ++;
			}
		}
		System.out.println(count);
	}
	
	public static int sumOfDigits(int n){
		int sum = 0;
		while(n!=0){
			sum += n%10;
			n = n/10;
		}
		return sum;
	}
}

- snehal.kumar March 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a math based one in C++.

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;

int main() {

for(int i = 1; i< 999999; i++) {
int num_digits = int(log(i)/log(10.0))+1;
int high = 1;
if (num_digits>3)
high = int(pow(10.0, num_digits-3));

if((i/high) == i%1000)
cout << i << endl;
}
return 0;
}

- Mustafa March 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Apparently this just gives numbers where first 3 digits are equal to the last 3. This is a wrong solution.

- Mustafa March 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry for the formatting. Here is the formatted one:

#include <cstdio>
 #include <cmath>
 #include <iostream>
 using namespace std;
 
 int main() {
 
  for(int i = 1; i< 999999; i++) {
    int num_digits = int(log(i)/log(10.0))+1;
    int high = 1;
    if (num_digits>3)
      high = int(pow(10.0, num_digits-3));
    
    if((i/high) == i%1000)
       cout << i << endl;
  }
  return 0;
}

- Mustafa March 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Of course log(10) should be taken out of the loop and calculated once.

- Mustafa March 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Apparently this just gives numbers where first 3 digits are equal to the last 3. This is a wrong solution.

- Mustafa March 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the real solution for the correct question. Sorry for reposts.

#include <cstdio>
 #include <cmath>
 #include <iostream>
 using namespace std;
 
 int main() {
 
  for(int i = 1; i< 999999; i++) {
    int num_digits = int(log(i)/log(10.0))+1;
    int power = 1;
    if (num_digits>3)
      power = int(pow(10.0, num_digits-3));
    
    int high = i/power;
    int low = i%1000;
    int sum_high = high/100 + (high%100)/10 + (high%10);
    int sum_low = low/100 + (low%100)/10 + low%10;
    if(sum_high==sum_low)
       cout << i << endl;
  }
  return 0;
}

- Mustafa March 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can do it using hash table.
for ( int i=0 to 9){
for( int j =0 to 9){
for(int k =0 to 9){
int v = i+j+k;
// Now hash this value v
}
}
}

Now we know that hash table will be having keys between 0 and 27.
Now for each key retrieve the corresponding set of numbers and their combination will give you the result.

- Amit March 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

28 keys...hash table...wow...

- Anonymous March 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I didn't get the use of Hash her? Without using sum, I can find out all combinations of three numbers with sum between 1 to 27, if I have to find all combinations.

- Vikas March 23, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int digit_sum(int i)
{
sum = i/100 + (i%100)/10 + i%10;
}


for(i = 100001, i<999999, i++)
{
if( digit_sum(i%1000) == digit_sum(i/1000) )
cout << i << endl;
}

- Naren Narayana March 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SumOfFirstThreeSameAsLastThree {
    public static void main(String[] args) {
        for (int i = 0; i < 999999; i++)
            if (checkSum(i))
                System.out.println(i);
    }
    public static boolean checkSum(int n) {
        // only 6 digits or more
        if (n < 100000)
            return false;

        int begin = n / 1000, last = n % 1000;
        // if the begin or last numbers are zero, there is no point to have a sum
        if (begin == 0 || last == 0)
            return false;

        int sum1 = 0, sum2 = 0;
        while (begin != 0 || last != 0) {
            sum1 += begin % 10;
            begin = begin / 10;
            sum2 += last % 10;
            last = last / 10;
        }
        return sum1 == sum2;
    }

}

- wsoethe March 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this can be done this way.

Count = 0
for ( int i=0 to 9){
    for( int j =0 to 9){
        for(int k =0 to 9){
            if ( all i , j and k are different ) {
                   count+= (!3*!3)
            }
            else if (any two are same) {
                   count+= ( (!3)/!2 *(!3)/!2 )
            }
            else if (all are same) {
                  count+= ( (!3)/!3 *(!3)/!3 )
            }
       }
   }
}

- Anonymous April 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check this out

printNo(int len,String no,int sum)
{
    if(len==0){print no;}
    if(len>3)
    {
      for(int i=0;i<9;i++){
        if(len==6) continue;
        for(int i=0;i<9;i++)
        {
            sum+=i;
            no='0'+i;
            printNo(len-1,no,sum);
        }   
        else
        { 
           for(int i=0;i<9;i++)
            {
                if(i>sum) break;
                if(i + (len-1)*9 < sum) continue;
                no += '0' + i;
                sum-=i;
                printNo(len-1,no,sum);
            }
        }
   
      }
    }
}

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

Opps a typo
printNo(int len,String no,int sum)
{
if(len==0){print no;}
if(len>3)
{
for(int i=0;i<9;i++){
if(len==6) continue;
if(len>3){
for(int i=0;i<9;i++)
{
sum+=i;
no='0'+i;
printNo(len-1,no,sum);
}
}
else
{
for(int i=0;i<9;i++)
{
if(i>sum) break;
if(i + (len-1)*9 < sum) continue;
no += '0' + i;
sum-=i;
printNo(len-1,no,sum);
}
}

}
}
}

- godLikeNoob April 25, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem can be solved very easily by dynamic programming by just keeping track of which position are we filling currently and what is the sum of the digits filled till now.
int dp[6][28];
void init(){
for(int i=0;i<6;i++) for(int j=0;j<=27;j++) dp[i][j]=-1;
}
int no_solutions(int index=0,int sum=0){
if(index==6) return sum==0;
if(sum<0) return 0;

int &ans = dp[index][sum];
if(ans!=-1) return ans;
ans=0;
for(int i=((index==0)?1:0);i<10;i++){
if(index>2)
ans+=no_solutions(index+1,sum-i);
else
ans+=no_solutions(index+1,sum+i);
}
return ans;
}
main(){
init();
cout<<no_solutions()<<endl;
}

As we can see the code takes 10*27*6=1620 iterations to run The code can be very easily modified for a general n digit number!

- python.c.madhav August 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
	int sum_1[27] = {0};
	int sum_2[27]= {0};
	
	for(int ii=1001; ii<2000; ii++)
	{
		int real_number = ii - 1000;
		int third = real_number/100;
		int second = (real_number%100)/10;
		int first = (real_number%100)%10;
		
		int s = third + second + first;
		
		if(ii-1000>=100)
		{
			sum_2[s-1]++;
		}
		
		sum_1[s-1]++;
	}
	
	int total = 0;
	for(int j=0; j<27; j++)
	{
		total += sum_1[j]*sum_2[j];
	}
	
	printf("%d\n", total);

}

- Sean February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
	int sum_1[27] = {0};
	int sum_2[27]= {0};
	
	for(int ii=1001; ii<2000; ii++)
	{
		int real_number = ii - 1000;
		int third = real_number/100;
		int second = (real_number%100)/10;
		int first = (real_number%100)%10;
		
		int s = third + second + first;
		
		if(ii-1000>=100)
		{
			sum_2[s-1]++;
		}
		
		sum_1[s-1]++;
	}
	
	int total = 0;
	for(int j=0; j<27; j++)
	{
		total += sum_1[j]*sum_2[j];
	}
	
	printf("%d\n", total);

}

- Sean February 24, 2012 | 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