Nervouser na entrevista

Um tempo atrás, durante a etapa técnica de uma entrevista de emprego, tive que resolver alguns probleminhas em call com o supervisor do setor. Problemas clássicos: árvore binária, palíndromo, etc., porém, já um tanto nervouser, me atrapalhei justamente no problema mais fácil (rly?), implementar Fibonacci.

Não lembro exatamente, mas a questão era alguma coisa assim:

Implemente um programa que escreva a sequência de Fibonacci até um determinado número.

além disso, a lista deveria ser formatada assim -> “0,1,1,2,3,5…”

Perceba como esse problema é diferente de:

Implemente um programa que escreva um determinado termo da sequência de Fibonacci

O primeiro problema pede uma lista de termos da sequência de Fibonacci até um número máximo N.

O segundo problema pede o valor do termo N da sequência de Fibonacci.

¿Estás en duda? No se adelante

Ao invés de parar um tempo pra refletir sobre o que o problema pedia, um pouco encabulado de parecer inapto a resolver um problema (que eu julgava) trivial, começei a escrever.

Rapidamente implementei algo mais ou menos assim:

from functools import lru_cache

@lru_cache()
def fib(nth_fib_number):
    if nth_fib_number < 1:
        return None
    if nth_fib_number in [1, 2]:
        return 1
    else:
        return fib(nth_fib_number-1) + fib(nth_fib_number-2)

if __name__ == '__main__':
    N = 100
    print(fib(N))

Percebendo que o programa calculava e printava o termo N da sequência e não a sequência até o termo N, tentei remendar:

from functools import lru_cache

@lru_cache()
def fib(nth_fib_number):
    ...

if __name__ == '__main__':
    N = 100
    lista = []
    for i in range(1, N):
        termo = fib(i)
        if termo > N:
            break
        else:
            lista.append(str(termo))
    print(','.join(lista))

Ok, funciona. Mas…

  • Como não sabia até qual termo calcular para chegar no máximo N, usei o próprio N como range, pois fib(N) >= N. Porém tive que usar uma condicional e um break para parar a iteração (q horror).
  • Só não é totalmente ineficiente pois o @lru_cache está sendo usado para evitar recalcular os termos já calculados na iteração anterior. Mesmo assim, por conta do cache, mais memória é utilizada sem necessidade. (para esse problema)

Big soluço elegante

Depois da entrevista, percebendo que a minha solução não era boa o suficiente, decidi buscar como resolver o problema de uma maneira mais eficiente. Encontrei o seguinte código:

def fib(max):
    a, b = 0, 1
    while a < max:
        yield str(a)
        a, b = b, a + b

if __name__ == '__main__':
    N = 100
    print(','.join(list(fib(N))))

O código acima é bem mais simples, elegante e não recalcula valores desnecessariamente.

  • A função fib retorna um objeto gerador, e o corpo da função define sua lógica de funcionamento.
  • A cada loop (while a < max), a função retorna (ou gera) um novo componente dessa sequência, utilizando a keyword yield
  • A linha 5 especifica a lógica por trás da sequência de Fibonacci: o próximo número da sequência é a soma dos dois anteriores.

Um detalhe

Poderia parar por aqui, com essa implementação bonita utilizando yield, mas existe um detalhe interessante:

Nessa implementação, assim como na anterior (desde que use alguma forma de memo/cache) os valores calculados ficam armazenados em memória. No caso da implementação recursiva, ficam armazenados no cache da função/decorator lru_cache (que não é acessível diretamente), além de armazenados na variável “lista” para posterior formatação.

Esta última implementação, que utiliza yield, também armazena a totalidade dos dados em memória, pois cria uma lista a partir do gerador: list(fib(N)). Dado que é apenas necessário escrevermos a lista e não armazená-la, o código acima poderia ser ajustado da seguinte forma:

def fib(max):
    ...

if __name__ == '__main__':
    N = 100
    ger = fib(N)
    num = next(ger)
    while True:
        print(num, end="")
        try:
            num = next(ger)
            print(",", end="")
        except StopIteration:
            print()
            break

Ou, se uma vírgula sobrando no final não for problema…

def fib(max):
    ...

if __name__ == '__main__':
    N = 100
    ger = fib(N)
    for number in ger:
        print(number, end=',')

Ok, agora sim. Escrevemos a sequência de Fibonacci, separada por vírgula, até um número máximo N, sem recalcular valores ou armazenar dados desnecessariamente. Ufa. Pena que ficou mais feio :(

Lições do dia

  • Reler a questão é útil
  • Geradores e yield são divertidos

até maix 😊