How would you answer this django interview question?

I recently did a programming question for a pre-interview for a certain company. The questions was:

Create a django app, test driven of course, to display Fibonacci's sequence to the world. The app should take an index number and display the resulting Fibonacci sequence. Additionally, there should be a page that shows the most recent generated sequences. Also, Fibonacci is a bit impatient and doesn’t want to wait around forever, so make sure you take steps to make sure your webserver 开发者_C百科runs efficiently.

I came up with the following:

from django.views.generic.simple import direct_to_template
from django.http import Http404

LARGEST_SEQUENCE = [0,1] 
LARGEST = 1 
LATEST = []

def fib(n): 
    """Calculate the nth fibonacci sequence""" 
    global LARGEST
    if n > LARGEST: 
        while n > LARGEST: 
            next = LARGEST_SEQUENCE[LARGEST] + LARGEST_SEQUENCE[LARGEST-1] 
            #print 'appending ', next
            LARGEST_SEQUENCE.append(next)   
            LARGEST += 1  
        return LARGEST_SEQUENCE 
    else: 
        return LARGEST_SEQUENCE[0:n+1] 

def latest(request):
    results=[]
    for n in LATEST:
        result = fib(n)
        results.append((n,result))
    return direct_to_template(request, 'latest.html', {'results':results})

def index(request):
    if request.method=="POST":
        try:
            n=int(request.POST.get('n'))
        except:
            return Http404
        result = fib(n)
        if len(LATEST) >=  5:
            LATEST.pop()
        LATEST.insert(0,n)
    else:
        result = None
    return direct_to_template(request, 'base.html', {'result':result})

The "latest" view is my 2nd version because the 1st version didn't work consistently. The original version stored the result from "index" in LATEST. LATEST was originally a list of fib sequences (lists) instead of a list of recent values of N.

I guess my main question is, is it bad to store the largest fib sequence generated during runtime in the views.py file? I know this isn't persistent, but the instructions never really gave details on how things should be done. What do you guys think, and how would you have approached the problem?

Thanks guys!

Every linear reccurence equation can be solve directly. In fibonacci's case the equation is

f_n+2 = f_n+1 + f_n
f_1 = 1
f_2 = 1

The solution to this is:

f_n = 1/sqrt(5) * ((1+sqrt(5))/2)^n - 1/sqrt(5) * ((1-sqrt(5))/2)^n

Use this direct formula. For how to get to it look for linear reccurence equation solving. E.g. here.

Because of floating point errors, you should round the result to the nearest integer.

Despite the well-know formula for computation in O(1) it fails for large numbers (ie 100).

I would do the next for the fibonacci thing:

def fib(n):
    "Complexity: O(log(n))"
    if n <= 0:
        return 0
    i = n - 1
    (a, b) = (1, 0)
    (c, d) = (0, 1)
    while i > 0:
        if i % 2:
            (a, b) = (d * b + c * a,  d * (b + a) + c * b)
        (c, d) = (c * c + d * d, d * (2 * c + d))
        i = i / 2
    return a + b

And for the lastes numbers, I would create a model.

from django.db import models

class Fibonacci(models.Model):
    parameter = models.IntegerField(primary_key=True)
    result = models.CharField(max_length=200)
    time = models.DateTimeField()

And for the view I would just do this:

from models import Fibonacci

def index(request):
    result = None
    if request.method=="POST":
        try:
            n=int(request.POST.get('n'))
        except:
            return Http404
        try:
            result = Fibonacci.objects.get(pk=n)
            result.time = datetime.now()
        except DoesNotExist:
            result = str(fib(n))
            result = Fibonacci(n, result, datetime.now())
        result.save()
    return direct_to_template(request, 'base.html', {'result':result.result})

Using models to retrive the last n entries is pretty simple.