## Facebook Interview Question for SDE1s

Country: United States

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

Solution in python.
Cost O(n). (We update the variables once in the loop constant time computed n times => O(n))

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

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

I think the interviewer is looking for a Iterator class with functions like hasNext() and next(). Otherwise it is too simple for an FB interview. You can google search Iterator definitions .., the code snippet
is for Java

``````//class variables
long current = 1;
long prev = 0;

public void reset () {
current = 1;
prev = 0;
}

@Override
public boolean hasNext() {
//will always have a next
//alternatively you could get some brownie points by returning false when you
//reach the largest positive 'long' number
return true;
}

@Override
public Long next() {
long temp = current;
current = prev + current;
prev = temp;
return temp;
}``````

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

``````#include <stdio.h>

int main(void) {
int i, v1 = 1, v2 = 0;
int element;

scanf("%d", &element);

for (i = 0; i < element; ++i) {
v2 += v1;
v1 = v2 - v1;
printf("%d ", v2);
}

return 0;
}``````

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

``````import java.util.ArrayList;

public class Fibonacci {

public static void main(String[] args) {

ArrayList<Integer> fibo=new ArrayList<>();
int end=10;
for(int i=2;i<end;i++){
}

for(int i:fibo)
System.out.print(i+",");
}
}``````

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

public class Fibo {
int n;

int fiboSum(int n){
if(n <= 2)
return 1;
else
return fiboSum(n-2) + fiboSum(n-1);
}

public static void main(String[] args) {
Fibo fb = new Fibo();
int num = 9;
int result = fb.fiboSum(num);
System.out.println("num " + num + " is : " + result);
}
}

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

``````public class Fibo {
int n;

int fiboSum(int n){
if(n <= 2)
return 1;
else
return fiboSum(n-2) + fiboSum(n-1);
}

public static void main(String[] args) {
Fibo fb = new Fibo();
int num = 9;
int result = fb.fiboSum(num);
System.out.println("num " + num + " is : " + result);
}``````

}

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

using recursion

``````var act = 1;
var limit = 8;

function fib (x, prev) {
console.log(act);
act = x+prev;
prev = x;
if(act <= limit) {
fib(act, prev);
}
}

fib(1,0);``````

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

Assuming we have to implement next() and hasNext() methods (just like traditional iterators), I propose the following solution. I am using a deque since removing/adding elements to the front or back of the structure is O(1). I also assume in the implementation that the user specifies the limit or the first 'n' fibonacci numbers that he wishes to see.

Solution:

``````from collections import deque
class FibonacciIterator:
def __init__(self, limit):
self.results = deque([0, 1])
self.curPos = 0
self.limit = limit

def hasNext(self):
return self.curPos < self.limit

def next(self):
firstNum = self.results.popleft()
self.curPos += 1
self.results.append(self.results[0] + firstNum)
return firstNum``````

Test Code:

``````f = FibonacciIterator(15) # Want the first 15 fib numbers
while f.hasNext():
print(f.next(),end=', ')
print()
# Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,``````

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.