Pregunta ¿Cómo responderías a esta pregunta sobre la entrevista de django?


Hace poco hice una pregunta de programación para una entrevista previa para cierta compañía. Las preguntas fueron:

Cree una aplicación django, impulsada por pruebas, por supuesto, para mostrar la secuencia de Fibonacci al mundo. La aplicación debe tomar un número de índice y mostrar la secuencia resultante de Fibonacci. Además, debe haber una página que muestre las secuencias generadas más recientes. Además, Fibonacci es un poco impaciente y no quiere esperar por siempre, así que asegúrese de tomar medidas para asegurarse de que su servidor web funcione de manera eficiente.

Se me ocurrió lo siguiente:

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})

La "última" vista es mi segunda versión porque la primera versión no funcionó de manera consistente. La versión original almacenó el resultado de "índice" en ÚLTIMA VEZ. LO ÚLTIMO fue originalmente una lista de secuencias fib (listas) en lugar de una lista de valores recientes de N.

Supongo que mi pregunta principal es: ¿es malo almacenar la secuencia fib más grande generada durante el tiempo de ejecución en el archivo views.py? Sé que esto no es persistente, pero las instrucciones nunca dieron detalles sobre cómo deberían hacerse las cosas. ¿Qué piensan ustedes, y cómo habrían abordado el problema?

¡Gracias chicos!


7
2017-09-18 20:26


origen


Respuestas:


A pesar de la fórmula bien conocida para el cálculo en O(1) falla para números grandes (es decir, 100).

Haría lo siguiente por lo de 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

Y para los últimos números, crearía un modelo.

from django.db import models

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

Y para la vista, simplemente haría esto:

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})

Usar modelos para recuperar las últimas n entradas es bastante simple.


4
2017-09-18 22:51



Cada ecuación de recuperación lineal se puede resolver directamente. En el caso de fibonacci, la ecuación es

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

La solución a esto es:

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

Usa esta fórmula directa. Para saber cómo llegar, busque la resolución de ecuación lineal de recuperación. P.ej. aquí.

Debido a los errores de punto flotante, debe redondear el resultado al entero más cercano.


3
2017-09-18 20:34