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

- Fernando June 09, 2017 | Flag Reply
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;
    	}

- nomadicdude July 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You should return current, not temp from method - next()

- Madhura August 05, 2019 | Flag
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;
 }

- CRSJ June 09, 2017 | Flag Reply
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;
		fibo.add(0);
		fibo.add(1);
		for(int i=2;i<end;i++){
			fibo.add(fibo.get(i-2)+fibo.get(i-1));
		}
		
		for(int i:fibo)
			System.out.print(i+",");
	}
}

- ea June 09, 2017 | Flag Reply
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);
}
}

- Jin June 14, 2017 | Flag Reply
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);
	}

}

- Jin June 14, 2017 | Flag Reply
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);

- jaylu June 26, 2017 | Flag Reply
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,

- prudent_programmer March 18, 2018 | Flag Reply


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