Desafio 100 dias de Python

Seguindo a lógica, nos dias atuais, fala-se muito da falta de sentido em aprender a programar como os antigos faziam. Escrevendo cada linha de código na mão, mas como alguém já dizia, técnico sem ténica não produz nada.

Dito isso para começar bem o Dia 1 vou anotar os seguintes conceitos:

1. Lista

lista = [1,2,3]
lista.append(4) # Adiciona ao final da lista com O(1) amortizado
lista.pop() # retira o último item da lista com O(1)
lista[0] # Acesso por indice de custo O(1)
len(lista) # Tamanho da lista - O(1)

Apesar de parecerem séculos desde que se falava de Big O, ainda é uma metrica valida pra avaliação de performance do código. Apesar dos computadores atuais alguentarem funções O(nˆ2) até 100000 sem esforço, no dia a dia esse custo invisível pode se acumular e quando a IA comete esses erros de forma não tão direta, saber prováveis causas pode acabar ajudando a debugar problemas depois.

A lista em python é a estrutura base para um código pythonico, então é sempre bom revisitar as operações básicas já presentes lembrando a mágica que proporcionam de custo constante. Sendo operações como inserir (append) ao final da lista, a função pop para retirada do ultimo item da lista, chamada de indice com lista[i] e len as bases pra resolver qualquer problema básico de python.

> apesar de ser engraçado estas operações tratarem a lista como pilha se analisar 
a semantica.

2. Dicionários (hash maps)

Lembro até hoje de um dos primeiros vídeos engraçadinhos de programadores falando sobre o processo de entrevista em Big techs ser basicamente uma mini apresentação de 40 minutos explicando o porque que Hash Map é a solução pra todos os problemas.

freq = {}
for n in lista:
    freq[n] = freq.get(n,0) + 1

A demonstração a cima é um uso classíco do dicionário do python que serve pra lembrar que tudo em python é um objeto. Então com uma lista de chaves, conseguimos atribuir valores de frequência a essas chaves somando +1 toda vez que a chave aparece. A mágica dos dicionário ta no custo constante na hora de pesquisar um valor de chave, podendo ser útil em diversos problemas de comparação encontrados no leetcode.

3. Conjuntos (set)

Os elementos tem são tratados como chaves de uma tabela Hash ou seja, não guarda elementos repetidos, e apesar de enganar, ao guardar números inteiros ele parece ordena-los mas isso não é garantido, pois ele cálcula a posição do item no indice ao dividir o número inteiro pelo tamanho do set.

vistos = set(lista)
for n in vistos: # Tem custo constante O(1) vs lista O(n)

Justamente pela propriedade de seus elementos serem uma chave hash em operações de busca, loop, o custo para visitar os elementos dele é constante.

4. Slicing

Essa é a verdadeira abstração máxima do python, quando fala de um código Pythonic não tem como não lembrar das operações de substring com slicing.

lista[1:3]             # [2, 3]
lista[::-1]            # reverso

Você pode literalmente reverter uma lista com uma simples operação. Pra quem aprendeu a programar em C na faculdade isso é uma demonstração de abstração tão maluca que demora pra pegar. Pra utilizar de forma simples é só lembrar lista[inicio:fim:passo] e o resto é com a criatividade.

5. enumerate() — índice + valor ao mesmo tempo

Isso é a parte que falta quando você está acustumado com um for classicos nos moldes de C. Assim você consegue a informação de indice e valor ao passar pelo loop de forma bem mais direta.

for i, val in enumerate(lista):
    print(i, val)

Two sum

O problema mais básico do leetcode. A ideia é que o programa deve retornar os indices onde a soma dos dois elementos dão um valor alvo. Podendo assumir que todo input só tem uma solução e que não pode usar o mesmo elemento duas vezes (Nesse caso o mesmo elemento é referido ao indice e não ao valor necessáriamente). A resposta pode aparecer em qualquer ordem.

Analisando as restrições a gente pode ver até qual nível de complexidade da notação Big O a nossa solução pode passar. Existem várias formas de se resolver, sendo a forma gulosa a mais intuitiva (O(nˆ2)), porém da chegar no tempo ótimo de O(n) usando Hash e um raciocíneo simples da matemática.

Assumindo que só tem uma solução então podemos verificar o valor necessário para atingir o alvo fazendo:

complemento = alvo - num

O num é um valor da lista de números inputado, assim da pra descobrir qual outro valor é usado pra complementar ele. Qual estrutura com chave e valor e busca contante podemos usar pra resolver o problema? Sim uma Hash no caso do python, um dicionário.

def TwoSum(nums,alvo):
    visto = {}
    for i, num in enumerate(nums):
        complemento = alvo - num
        if complemento in visto:
            return [visto[complemento],i]
        visto[num] = i

A lógica é simples, usa um dicionário para guardar os elementos que já foram vistos da lista, se o complemento já tiver sido visto, então é só retornar aonde o complemento está na lista e o valor do indice atual. Se não tiver na lista, guarda no dicionário de elementos vistos. Ou seja com essa solução numa passada só (O(n)) é possível encontrar o resultado.

Oque eu aprendi hoje

Foi uma revisão direta e simples de ferramentas presentes no python, e já posso guardar um tipo de problema na minha mémoria, que é os problemas de alvo, no caso, como achar algo da forma mais direta e menos custosa. Nesse caso, a resposta quase que natural deve ser dicionário!

Mais pra frente em um próximo post eu revisito melhor o conceito de memoização.