## Facebook Interview Question for SDE1s

• 0

Country: United States

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

``````public class GetFibonacciNumbers {
public static void main(String[] args) {
int[] given = new int[] {3, 6, 7, 9, 2};
int[] output = getFibonnaciNumbers(given);
printArray("given", given);
printArray("output", output);
}

private static void printArray(String name, int[] given) {
StringBuilder sb = new StringBuilder(name);
sb.append(": ");
for(int i=0; i < given.length; i++) {
if (i > 0)
sb.append(", ");
sb.append(given[i]);
}
System.out.println(sb);
}

private static int[] getFibonnaciNumbers(int[] given) {
int[] output = new int[given.length];
int index = 0;
for(int x : given) {
int nearestFib = getNearestFibonacciNumber(x);
if (x == nearestFib)
output[index++] = x;
}
return output;
}

private static int getNearestFibonacciNumber(int given) {
int fN = 1;
int fNPrev = 1;
while(fN < given) {
int temp = fN;
fN = fN + fNPrev;
fNPrev = temp;
}
System.out.println("Neartest to " + given + " is " + fN);
return fN;
}
}``````

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

We keep cache of calculated Fib numbers and run through the array. If next elem in array greater then last calculated in cache - we calc all fib numbers till next and check if it's in cache

``````public static List<int> getFibNumbers(int[] nums)
{
int lastFib = 1;
int nextFib = 1;
int temp;
HashSet<int> cache = new HashSet<int>();
var result = new List<int>();
foreach (var item in nums)
{
while (item > nextFib)
{
temp = lastFib;
lastFib = nextFib;
nextFib = temp + lastFib;
}
}
return result;
}``````

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

#!/usr/bin/python
import math
def isPerfectSqr(n):
x = int(math.sqrt(n))
return x*x == n

def isFibonacci(num):
#5n**2+4 or 5n**2-4 should be true
first = 5*num**2 + 4
second = 5*num**2 - 4
if (isPerfectSqr(first) or isPerfectSqr(second)):
return True
else:
return False

def fibonacci(input_list):
result = []
for num in input_list:
if isFibonacci(num):
result.append(num)
return result

if __name__ =='__main__':
input_list = [4, 2, 8, 5, 20, 1, 40, 13, 23]
#output: [2, 5, 1, 8, 13]

print fibonacci(input_list)

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

There are two standard version of Fibonacci series -
1) 0,1,1,2,3,5,8....
2) 1,1,2,3,5,8.....

We will use first in our problem.
1- Find max in the array - O(n)
*max number will be used to generate Fibonacci series to the number max. In given example the max is 40.
2- Generate Fibonacci to the number max and store it in hashset/hashmap. in our eg. the fibset will be (0,1,2,3,5,8,13,21,34)
3- Traverse array again if the number is present in hashset/hashmap then add it to the list.
4- Return list

Time complexity - O(n)

``````public class FibonacciSubset {

private static ArrayList<Integer> findNumbers(int[] ar){

int max = findMax(ar);
ArrayList<Integer> list = new ArrayList<>();
Set<Integer>  fibset = fiboNumbers(max);
for(int i=0;i<ar.length;i++){
if(fibset.contains(ar[i])){
}
}
return list;
}

private static int findMax(int[] ar) {
int max= ar[0];
for(int i=1;i<ar.length;i++){
max = max > ar[i] ? max : ar[i];
}
return max;
}

private static Set<Integer> fiboNumbers(int max) {
HashSet<Integer> fibset = new HashSet<>();
int f = 0,s =1;
int res = f + s;
while(res < max){
f = s;
s = res;
res = f + s;
}
return fibset;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] ar = {4,2,8,5,20,1,40,13,23};
ArrayList<Integer> list = findNumbers(ar);

for(int i=0;i<list.size();i++){
System.out.print(list.get(i) + " ");
}
}

}``````

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

``````/*
Showing Idiomatic ZoomBA
*/
input = [4,2,8,5,20,1,40,13,23]
#(m,M) = minmax(input)
fib = seq ( 0, 1 ) -> { \$.item[-1] + \$.item[-2 ] }
while ( fib.next <= M );
result = input & fib.history
println(result)``````

Now the result:

``````➜  wiki git:(master) ✗ zmb tmp.zm
[ 1,2,5,8,13 ]
➜  wiki git:(master) ✗``````

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

Solution in Python

``````from itertools import takewhile

def fib():
a = 0; b = 1
while True:
yield a
temp = a
a = b
b += temp

def getFibNumbers(nums):
m = max(nums)
s = set(takewhile(lambda x: x < m,
fib()))
return s.intersection(nums)``````

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

Using a Math property to check is a number is Fibonacci, O(n)
A number is fibbonaci if (5*n2 + 4) or (5*n2 – 4) is a perfect square

``````public static List<int> GetFibonacciSequence(int[] a)
{
var list = new List<int>();

if (a == null)
return list;

foreach (var n in a)
if (IsFibonacci(n))

return list;
}

//A number is fibbonaci if (5*n2 + 4) or (5*n2 – 4) is a perfect square
public static bool IsFibonacci(int n)
{
int f = (5 * n * n);
int f1 = f + 4;

if (IsPerfectSquare(f1))
return true;

int f2 = f - 4;
if (IsPerfectSquare(f2))
return true;

return false;
}

public static bool IsPerfectSquare(int n)
{
int sqrt = (int)Math.Sqrt(n);
return sqrt * sqrt == n;
}``````

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

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApp1
{
class Program
{
static bool isfib(int n)
{
int x = 5 * n * n + 4;
int y = 5 * n * n - 4;
int sx = (int)Math.Sqrt(x);
int sy = (int)Math.Sqrt(y);
if (sx * sx == x)
return true;
else if (sy * sy == y)
return true;
else
return false;
}
static void Main(string[] args)
{
int []arr = { 4, 2, 8, 5, 20, 1, 40, 13, 23 };
for (int i = 0; i < arr.Length; i++)
{
if (isfib(arr[i]))
Console.WriteLine(arr[i]);
}
}
}
}

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

1. store the input numbers in a Map<Integer,Boolean> initially assigned to false.
2. find the maxNum present in the input array
3. find all the fibonacci numbers until the maxNum. If any of the intermediate fibonacci numbers are present in the map, assign a true value.
4. traverse through the input array and add the numbers that have true in the map.

``````public static List<Integer> getFibNumbers(int[] nums){
if(nums==null || nums.length==0)
return result;

Map<Integer,Boolean> fiboMap = new HashMap<>();
int maxNum=Integer.MIN_VALUE;
for(int num: nums){
fiboMap.put(num, false);
maxNum = Math.max(maxNum, num);
}
findFibo(maxNum, fiboMap);
for(int num: nums){
if(fiboMap.get(num)){
}
}
return result;
}
private static void findFibo(int maxNum, Map<Integer, Boolean> fiboMap){
int dp1=0, dp2=1, dp3=0;

while(dp3<maxNum){
dp3=dp1+dp2;
dp1=dp2;
dp2=dp3;
if(fiboMap.containsKey(dp3)){
fiboMap.put(dp3,true);
}
}
}``````

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.