Google Interview Question
SDE1sCountry: United States
function isPerfectSquare(num) {
let s = Math.floor(Math.sqrt(num));
return (s*s === num);
}
function isFibonacci(num) {
return (isPerfectSquare(5*num*num + 4) || isPerfectSquare(5*num*num - 4));
}
function findRandomFibNum(min, max) {
let rnum = Math.floor(Math.random() * (max - min + 1)) + min;
if (isFibonacci(rnum)) {
return rnum;
}
else {
return findRandomFibNum(min, max);
}
}
console.log(findRandomFibNum(20, 22));
public int fib(int min, int max) {
fib.add(0);
fib.add(1);
int i = 2;
int minIndex = 0;
while(fib.get(i - 1) < max) {
fib.add(fib.get(i - 1) + fib.get(i - 2));
if(fib.get(i) <= min) {
minIndex = i;
}
i++;
}
for(int j = 0; j <= minIndex; j++) {
fib.remove(0);
}
System.out.println(fib);
return fib.get((int) (Math.random() * fib.size()));
}
public static void main(String[] args) {
Solution27 solution = new Solution27();
System.out.println(solution.fib(100, 1000000000));
}
public static void main(String[] args) {
int result = getNumber(5,40);
System.out.println(" ");
System.out.println(result);
}
private static int getNumber(int i, int j) {
int result[] = fib(20);
int rnd = 0;
while(result[rnd]<i || result[rnd]>j)
rnd = new Random().nextInt(result.length);
return result[rnd];
}
private static int[] fib(int n){
int[] result = new int[n];
int first=0;
result[0] = first;
int second=1;
result[1] = second;
int third=0;
int i=3;
while(i<=n){
third=first+second;
first=second;
second=third;
result[i-1] = third;
i++;
}
return result;
}
#include <iostream>
using namespace std;
int64_t RandomFib(int64_t start, int64_t end)
{
int64_t prev_prev = 0;
int64_t prev = 0;
int64_t rnd = -1;
int zero_count = 0;
int count = 0;
while (true)
{
int n = prev_prev + prev;
if (n == 0)
{
if (++zero_count == 2)
{
n = 1;
}
}
if (n >= end)
{
break;
}
if (n >= start)
{
++count;
if (rand() % count == 0)
{
rnd = n;
}
}
prev_prev = prev;
prev = n;
}
return rnd;
}
int main()
{
srand(time(NULL));
cout << RandomFib(5, 9) << "\n";
return 0;
}
- dmitry.labutin April 27, 2017