Vdopia Interview Question for Software Engineer / Developers


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[66][66]; // number of combinations N_choose_R

const int nFibo = 9;
int Fibo[9] = {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][1] = 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;
}

- ninhnnsoc May 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- koegent May 13, 2014 | Flag
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;
  }

}

- debo May 11, 2014 | Flag Reply
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.

- Anonymous May 11, 2014 | 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