## Bloomberg LP Interview Question for Financial Software Developers

• 1
of 1 vote

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

for(i=1;i<28;i++) a[i]=0;
for(i=1;i<1000;i++) a[(i%100)+((i/10)%10)+(i/100)]++;
result=0;
for(i=1;i<28;i++){ result += a[i]*a[i]; }

return result;

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

pls change typo: (i%10)+((i/10)%10)+(i/100)

result will be 55251

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

what if the question was for some 100 digits . I don't think ur algorithm would then be feasible in that case. U can solve this problem using dynamic programming in O(logN) time .

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

can anyone explain what this a[(i%100)+((i/10)%10)+(i/100)]++; means by breaking it down ... thanks ?

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

@Roshan，what a nice solution!!

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

still @Roshan, I think you miss 000000, which should also be a winning number

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

Nice solution!

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

28 must be all possible results from 3 digit-sum. the second line is the sum. whenever the result is i, a[i]++
for each sum result, all possible 6 digits are a[i]*a[i]. Sum all them

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

``````import java.util.HashMap;
import java.util.TreeMap;
import java.util.Map.Entry;

public class Lottery1 {
static HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>(40);
static double possibility = 0;

public static void main(String[] args) {
prepareMap();
countPossibility();
System.out.println("Possibility = " + possibility+"\n Means that each 20th combination wins.");
TreeMap<Integer, Integer> tm = new TreeMap<Integer, Integer>(sumMap);
System.out.println("Sorted possibilities of each sum variant:\n" + tm);
}

static void countPossibility() {
for (Entry<Integer, Integer> sumEntry : sumMap.entrySet()) {
possibility += Math.pow((double) sumEntry.getValue() * 0.001, 2);
}
}

static void prepareMap() {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
for (int j2 = 0; j2 < 10; j2++) {
int sum = i + j + j2;
addToMap(sum);
}
}
}
}

static void addToMap(int sum) {
Integer i = sumMap.get(sum);
if (i == null) {
i = 0;
}
i++;
sumMap.put(sum, i);
}

}``````

Possibility = 0.05525200000000001
Means that each 20th combination wins.
Sorted possibilities of each sum variant:
{0=1, 1=3, 2=6, 3=10, 4=15, 5=21, 6=28, 7=36, 8=45, 9=55, 10=63, 11=69, 12=73, 13=75, 14=75, 15=73, 16=69, 17=63, 18=55, 19=45, 20=36, 21=28, 22=21, 23=15, 24=10, 25=6, 26=3, 27=1}

Sorted possibilities show that there is some sort of thing like pascal triangle can be applied to the task. The question can be solved in pure combinatorial analysis..

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

For next 10 elements it's straightforward progression of pascal's triangle third line:
>>0=1, 1=3, 2=6, 3=10, 4=15, 5=21, 6=28, 7=36, 8=45, 9=55,
And then pascal's progression fails:
>> 10=63, 11=69, 12=73, 13=75,
should be 66, 78 ..

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

it doesn't fail actually, after sum>9, only one of the digits can be zero i.e. the number goes down by

``````[don't have a clear explanation for why this pattern happens but it's the same pattern for 4th row]
pascalRowNumber*pascalRow(0)
for ex: if Row ==> 0=1, 1=3, 2=6, 3=10, 4=15, 5=21, 6=28, 7=36, 8=45, 9=55,
10=(66-3*Row(0))--> 63
11=(78-3*Row(1))--> 69
12=(91-3*Row(2))--> 73
13=(105-3*Row(3))-->75
14=(this is the mid point so it starts going down repeating)
=Row(27-13)
15=Row(27-15)=Row(12)-->73.
so on..``````

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

.....

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

I know its the least efficient, but I told him to run the loop of all numbers between 0 and 999,999 and take the sums, and add 1 to a counter if the sums are equal.

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

you mean a 6 digit number and sum of first 3 digits == last 3 digits??

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

yup

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

Quick question: When was your interview? Is this a question from the onsite interview?

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

okay finally understood where my pascal was behaving wrong. here's the code using pascal method verified against bruteforce method.
Output:
Final Probability using Pascal triangle method: 0.055252. . Number of iterations: 29
Final Probability using brute force method: 0.055252. . Number of iterations: 1000000

``````#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
//!computes sum of digits of a three digit number
inline long sumofdigits(const long& val){
return ((val/100) + ((val%100)/10)+val%10);
}
int main(){
int sumOfDigits=0,numOfDigits = 3, maxOfDigit=9;
double totalSum = 0,triVal=0,k=0,totalNumbersWithEqualSum = 0,numOfIters=0;
long totalNumLotTickets = 1000000; //0 to 999999
vector<long> thirdRowPascal(15,0);
for(;k<15;++k,++numOfIters) //take 14 values of 3rd row of pascal triangle
thirdRowPascal[k]=((k+1)*(k+2)/2);
for(;sumOfDigits<14;++sumOfDigits,++numOfIters){
if(sumOfDigits>9)	//if sum>9 then two digits cannot be zero at same time so
triVal = pow((double)(thirdRowPascal[sumOfDigits]-3*thirdRowPascal[sumOfDigits-10]),2);
else
triVal = pow((double)thirdRowPascal[sumOfDigits],2);
totalSum+=triVal;
}cout<<"Final Probability using Pascal triangle method:"<<(totalSum*2)/totalNumLotTickets
<<". Number of iterations: "<<numOfIters<<endl;
//verification using brute force method
vector<long> totalSums(28,0);long firstdig=0,lastdig=0;numOfIters=0;
for(long ii=0;ii<totalNumLotTickets;++ii,++numOfIters){
firstdig = ii/1000;	lastdig = ii%1000;
if(sumofdigits(firstdig)==sumofdigits(lastdig))
++totalNumbersWithEqualSum;
}cout<<"Final Probability using brute force method:"<<totalNumbersWithEqualSum/totalNumLotTickets
<<". Number of iterations: "<<numOfIters<<endl;
}``````

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

Am trying a really faster method here.
sum of squares of third row of pascal triangle with some modification /1000000,
= 55252/1000000 = .055252
Detailed Explanation:
so we want how many numbers are there such that given abcdef a+b+c = d+e+f where a,b,c,d,e,f <= 9 --> a+b+c <= 27.

``````No. of ways of writing 3 digits whose sum is 0
000. total ways of writing 6 digit numbers whose sum is 0 -> 1
No. of ways of writing 3 digits whose sum = 1
001,010,100. total ways of writing a 6 digit number whose sum of 1st 3 digits = 1 is 3*3-> 9
No. of ways of writing 3 digits whose sum = 2
011,101,110,002,200,020, total -> 6*6 -> 36
No. of ways of writing 3 digits whose sum = 3
111,,210,201,120,102,012,021,300,030,003 -> 10*10 = 100
No. of ways of writing 3 digits whose sum = 4
112,121,211,310,301,103,031,013,120,220,202,022,400,040,004 -> 15*15 = 225
so on upto sum = 9
I can see a pattern
1 + 9 + 36 + 100 + 225... which is squares the of third row of pascal triangle. but this pattern goes upto sum = 9 and then goes down to sum=1
but when sum=10, one digit cannot be zero at all so we'll have (pascalTri(10)-3*1)^2 ways
when sum=11, we'll have (pascalTri(11)-3*3)^2 numbers
when sum=12, we'll have (pascalTri(12)-3*6)^2 numbers
... and when sum=14, it starts going down repeating in the reverse order i.e.
(Number of 6 digit numbers whose sum =14) === (Number of 6 digit numbers whose sum =13)
...
(Number of 6 digit numbers whose sum =25) === (Number of 6 digit numbers whose sum =2)
(Number of 6 digit numbers whose sum =26) === (Number of 6 digit numbers whose sum =1)``````

Feel free to ask questions/ Thanks

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

ok, can you explain what you did in words?

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

the first post is code, second post is explanation. it gives explanation with clear example, I dont know how else I can explain. If you have any questions please feel free to ask, I will answer them. thanks

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

..

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

Anyone going to explain what the code means?

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

Hi,
Search in wiki 'pascal triangle' that should explain how blueskin.neo's solutions works, but regarding code you should do it your self...

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

Hi Everyone,

I came up with the following solution to the above problem. The combinations form a very weird series. Below is the code for it. Let me know if this can be done in a more efficient time.

``````#include<stdio.h>
#include<stdlib.h>

#define MAX_SUM 27
#define NDIGIT 3
#define C0 1

int main(){
register int TOTAL = 0;
int mid = MAX_SUM/2;
int curr;
int prev_val = {C0, NDIGIT};

for(int sum=2; sum<=mid; sum++){
curr = (prev_val - prev_val) + 1 + prev_val;
TOTAL += 2*(prev_val*prev_val);
prev_val = prev_val;
prev_val = curr;
}

TOTAL += 2*(prev_val*prev_val) + 2*(prev_val*prev_val);

printf("Winning Tickets = %d\n", TOTAL);
return 0;
}``````

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

This is the only method I could come up with that is covering all the possible combinations.

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

Max sum is 27 and thats a start. For 0 there is only 1 possibility 000. For 1 there r 3 001,010,100. For 2 110,101,011,200,020,002 so 6.Working this way i cud find a series. for 3 it s 10,for 4 it is 15, for 5 it is 21.Hence total possibilities wud be(1^2+3^2+6^2...+((28*29)/2)^2)

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

catalan number or a modified pascal triangle. This question is a duplicate

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

careercup.com/question?id=6670706
blueskin's solution works well. look for catalan number or pascal triangle

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

How catalan? What is the connection?

Pascal numbers yes, as the answer can be written in terms of binomial coefficients, but that is like saying combinatorics or something vague like that.

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

This solution is excellent, how did you come up with it?

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

``````1. 3 digits sum minimum, MIN_SUM = 0
2. 3 digits dum Maximum ,  MAX_SUM = 27
3. let us take an Array A = {0,1,2,3,4,5,6,7,8,9}
4. for Each sum From MIN_SUM to MAX_SUM
find all 3 -digit combinations  which gives above sum .

/* program to find no of lottery  tickets */

void Sum( int *A, int i, int digit, int  *count, int Psum, int sum )
{
if( digit <= 0 || psum > sum || i >= 10 )
{
return;
}
else if (psum == sum )
{
*count += 1;
return;
}
else
{
sum( A, i,   digit-1, count, sum, psum + A[i] ) ;
sum( A, i+1, digit-1, count, sum, psum + A[i] ) ;
sum( A, i,   digit,   count, sum, psum  ) ;
}
}

int main()
{
long int count=0;
long int CumulativeSum = 0;
int i = 0;

for( i = 0; i<= 27 ; i++ )
{
count = 0;

sum(A, 0, 3, &count, i, 0 );

CumulativeSum += *count ;
}

printf(" Totla number of combinations = %l \n", CumulativeSum );
return;
}``````

Incase , if you find any bug, please let me know.

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

Brute force may works.

``````int a,count=0;
for(int i=0;i<=999999;i++)
{
for(int j=0;j<6;j++)
{
a[j]=i%(10^(j+1));
i /= 10;
}
if((a+a+a)==(a+a+a))
count++;``````

}

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

@Roshan ... Great Solution Buddy

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

01718881819

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

55252

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

Draw a distribution of sums in the range [0,27] for any three digit number, and you'll figure that the number of cases that adds up to i are (i+1)*(i+2)/2. We have 1000 cases per side, which means 1M total cases: squaring every number of cases that adds to a certain sum will provide the result.

``````public static int cases() {
int total = 0;
for (int i=0; i<14; i++)
total += (int) Math.pow(i*(i+1)/2, 2);
return total*2;
}``````

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

``````public void LotteryTest()
{
var values = new Dictionary<int, int>();
for (int i = 0; i < 1000; i++)
{
string valueString = i.ToString().PadLeft(3, '0');
var value = Convert.ToByte(valueString.ToString()) + Convert.ToByte(valueString.ToString()) + Convert.ToByte(valueString.ToString());
if (!values.ContainsKey(value))
{
values.Add(value, 1);
}
else
{
values[value]++;
}
}
var total = values.Sum(v => v.Value * v.Value); //combination of left 3 and right 3
}``````

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

``````n = 9 * (enter the number of digits);
int b[n] = { 2,3,4,6,7,8,9,...n};
int a[n];
a = 1;
for(int i =1;i<=n;i++)
{
a[i] = a[i-1] + b[i-1];
}
for(i = 0;i<n;i++)
{
int result  += a[i] * a[i];
}
return (result);``````

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

Its a combinatorial problem:
break into 2 parts :
first and last 3 digit
1 digit - 10 possible values
2 digits - 100 possible values
3 digits - 1,000 possible values

so 10^n ,n = digit
3 digit = 1,000
we compare it against the same values which would be 1,000

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

Dude... 330600 is also a winning entry (this doesn't come under 1000 possible values you mentioned)

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

Wrong!!! here u only taking as no like 543543...where 543444 is also correct

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