Facebook Interview Question
SDE1sCountry: United States
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;
}
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,
Solution in python.
Cost O(n). (We update the variables once in the loop constant time computed n times => O(n))
- Fernando June 09, 2017