Vdopia Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Phone Interview

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

For input a = 173, b=10000003210005, my answer is 1246892717288.
Look at my implementation first, ignore below explanation.

Suppose the input is 64 bits.
We can see that there are only 9 Fibonacci numbers less than 64: 1, 2, 3, 5, 8, 13, 21, 34, 55.

My solution uses combinatorial formula.

The number C of all numbers of length N bits and have bit sum of R is:
C(N,R) = N_choose_R = N! / (R! * (N-R)!);

This can be efficiently computed using "Pascal Triangle" without overflow.

The hard part is how to count the answer for all numbers that less than a number Y.
Lets take a concrete example:

Count the number of numbers less than Y=106 that have bit sum of R=3.

Y = 106 = 1101010 in binary; N = 7 bits.
R = 3

Consider numbers in following forms Y1, Y2, Y3, Y4:

Y 	= 1101010
Y1	= 0xxxxxx	// turn first 	'1' off
Y2 	= 10xxxxx	// turn second 	'1' off
Y3	= 1100xxx	// turn third 	'1' off
Y4 	= 110100x	// turn last 	'1' off
where x can be any bit.

Then, numbers in forms of Y1, Y2, Y3, Y4 have 3 properties:
1. All are less than Y;
2. They are non-overlap;
3. They cover all possible numbers less than Y.

Thus, now I have to count how many numbers in each form that satisfy the requirement
For Y1: there are C(6,3) such numbers;
For Y2: there are C(5,2) such numbers;
For Y3: there are C(3,1) such numbers;
For Y4: There are C(1,0) such numbers;

The final answer is: there are C(6,3) + C(5,2) + C(3,1) + C(1,0) = 34 numbers that less than 106 and have bit sum of 3.

To answer the original question, we have to do for all 9 Fibonacci numbers.
And a trick:
[a,b] = [0, b+1) - [0,a)

EDITED:

Time complexity: O(log b * log log b)
Reasons:
Number of bits in the number b is n = log b
Number of Fibonacci numbers that are less than n is O(log n).

CODE:

#include <iostream>
#include <string.h>

//typedef unsigned long long ull;

using namespace std;

unsigned long long a,b; // must be >=0
unsigned long long NCR; // number of combinations N_choose_R

const int nFibo = 9;
int Fibo = {1, 2, 3, 5, 8, 13, 21, 34, 55};

//--------------------------------------
void PascalTriangle(int Nmax){  // Pascal Triangle is the best for avoiding overflow!
memset(NCR,0,sizeof(NCR));
NCR = 1;

for(int i = 2; i<=Nmax; i++){
for(int j = 1; j<=i; j++){
NCR[i][j] = NCR[i-1][j-1] + NCR[i-1][j];
};
};
/*
for(int i = 1; i<=Nmax; i++){
for(int j = 1; j<=i; j++) cout <<NCR[i][j]<<" ";
cout <<endl;
}
*/
};

//--------------------------------------
unsigned long long NCR_Of(int n, int r){
return NCR[n+1][r+1];
}

//--------------------------------------
string binaryOf(unsigned long long x){
string ans = "";
if (x ==0) return "0";
while(x>0){
int bit = x%2;
x = x/2;
ans = char('0'+bit) + ans;
}
return ans;
}

//--------------------------------------
unsigned long long countResult(unsigned long long X){
// count the number of (numbers that are less than X) and (their bit-sums are fibonacci)
string bin = binaryOf(X);
int n = bin.length();

unsigned long long ans = 0;

for(int k = 0; k<nFibo; k++){// for each fibo number:
if (n<Fibo[k]) break;
int remainBits = Fibo[k];
for(int i = 0; i<n; i++){// for each bit
if (remainBits <0) break;
int remainLen = n - i-1;
if (bin[i] == '1'){
ans += NCR_Of(remainLen, remainBits);   //number of answers if turn this bit off.
remainBits--;   //
}
}; // for i
}; //for k
return ans;
}

// My Solution:
//--------------------------------------
unsigned long long solve(unsigned long long a, unsigned long long b){
if (a>b) return 0;
return countResult(b+1) - countResult(a);
}

// Naive solution: loop and count:
//--------------------------------------
int sumBits(long x){
string b = binaryOf(x);
int res = 0;
for (int i = 0; i<b.length(); i++)
res += b[i]=='1'?1:0;
return res;
}

//--------------------------------------
bool isFibo(int x){
for(int i = 0; i<nFibo; i++)
if (Fibo[i] == x) return true;
return false;
}

//--------------------------------------
long solve_Naive(long a, long b){
long res = 0;
for(long i =a; i<=b; i++){
int s = sumBits(i);
if (isFibo(s)) res++;
};

return res;
}

//--------------------------------------
int main()
{
PascalTriangle(65);
cin >>a>>b;
cout <<"answer by MY solution       = " <<solve(a,b)<<endl;
cout <<"answer by Naive solution    = " <<solve_Naive(a,b)<<endl;
return 0;
}

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

It might be helpful to use the fact that: Y&(Y-1) equals to turn-off the Y's right most 1 bit (i.e. Y4), and we may get the position of the turned-off bit by: Y ^ (Y&(Y-1)).

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

public int createFibo(int a, int b, List<Integer> fibo)
{

int count =0;
int num = a;
int bitsum=0;

while(num!=0)
{
bitsum =+ numToBitSum(num);
num = num/10
}

while(a <= b)
{
if(fibo.contains(bitsum))
{
count++;
}
a++;
}

return count;
}

public int numToBitSum(int num)
{
if(num!=0)
{
return num%10;
}

}

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

You are missing the point you cannot store 1000000321005 & ot will take a lot of time to run.

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.