Hi Everyone ,
I recently gave my telephonic interview for Google Bangalore(Backend Engineer)

1. Questiion :
   Check whether number is fibonacci or not.
   https://www.geeksforgeeks.org/check-number-fibonacci-number/
   But unfortunately I didn't knew this solution O(1) time
   I gave him O(n) solution

2. Question
   Follow up
   Find minimum number of fibonacci numbers whose sum is equal to given number K

But I had hard time explaining this solution to the interviewer since he didn't knew C++ (lower_bound api) :(
Overall I gave him a pseudo code explain whatever I was doing in my code.
Lastly we had some spare time for some chit chat about the kind of work i was doing in my company.
My Solution :

#include <bits/stdc++.h>
using namespace std;
int getCnt(int fibnacii) {
    
    map<int,int> s;
    int cnt = 0;
    int sum = fibnacii;
    int c = 0;
    int a = 0;
    int b = 1;
    
    while(c <= fibnacii) {
	    s[c]++;
	    c = a + b;
	    a = b;
	    b = c;
	}
    
    while(sum > 0) {
        
        auto it = s.lower_bound(sum);
        
        if(it->first > sum || it == s.end())
        it--;
        sum  = sum - it->first;
        cnt++;
        
        
    }
    return cnt;
}
int main() { 
    cout<<getCnt(28);
}