Sem cache: descontos herdados
Por que isso importa "Ele repete o trabalho, então lembre das respostas" é um dos hábitos mais fortes em programação, humana ou de IA. Às vezes o trabalho não precisa ser repetido de jeito nenhum.
A formam uma árvore: Jardim fica sob Casa, Ferramentas sob Jardim, e assim por diante. Um gerente de marketing pode definir um desconto em qualquer categoria, e ele se aplica a tudo abaixo dela, a menos que uma categoria mais próxima defina a sua própria. O checkout busca o desconto efetivo para milhares de categorias de uma só vez.
Os dados
parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25} # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]A correção óbvia para caminhadas repetidas na árvore é um cache. Neste problema, caches são proibidos. Procure por uma forma que nunca repita o trabalho desde o início.
Escreva effective_discounts(parents, own, queries). parents mapeia cada categoria para seu pai, ou None para uma categoria de nível superior (pode haver várias, e o dicionário não está em nenhuma ordem específica). own mapeia algumas categorias para seu próprio desconto. Para cada categoria em queries, retorne o desconto da categoria mais próxima em seu caminho para o topo, começando por ela mesma, que tenha um em own; 0 se nenhuma tiver. Regra: sem cache ou memo: nenhum functools cache decorators, nenhum nome contendo "cache" ou "memo", e nenhuma resposta de trabalho para fora, pois as consultas pedem e mantêm elas (um memo com outro nome). Percorra a árvore inteira primeiro, depois leia as consultas. Orçamento: no máximo 500.000 passos (steps()) para 3.000 categorias, árvores de até algumas centenas de níveis de profundidade, e 20.000 buscas.
Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição
Este exercício abre em breve
Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.
Este navegador está bloqueando cookies para learn.floati.life, então as lições que você terminou aqui não podem abrir em ordem. Permita cookies para este site e recarregue.