How would you answer this django interview question?

Question

I recently asked a pre-interview programming question for a specific company. There were questions:

Build a django application, of course, check to display the Fibonacci sequence in the world. The application should accept the index number and display the resulting Fibonacci sequence. In addition, there should be a page with the most recently created sequences. Also, Fibonacci is a little impatient and doesn't want to wait forever, so make sure you take steps to make sure your web server is working 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 "last" view is my second version, because the first version does not work sequentially. The original version saved the result from the "index" in LATEST. LATEST was originally a list of sequences (lists), not a list of recent N values.

I assume that my main question is: is it inconvenient to store the largest file sequence generated at runtime in the views.py file? I know this is not persistent, but the instructions never gave details on how everything should be done. What do you guys think and how would you approach the problem?

Thanks guys!

Answer 1

Despite the well-known calculation formula in O(1) , it fails for large numbers (i.e. 100).

I would do the following for fibonacci:

 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 last 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 presentation, 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 retrieve the last n records is pretty simple.

Answer 2

Each linear recurrence equation can be solved directly. In the case of fibonacci equation

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

The solution to this:

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

Use this direct formula. To get to it, find a solution to the linear recurrence equation. For example. here .

Due to floating point errors, you must round the result to the nearest integer.