Soluções para os mais diversos problemas do dia a dia e otimização de algoritmos.
- Lógica;
- Capacidade de interpretação de problemas;
- Capacidade de interpretação de um código legado;
- Capacidade de otimizar a resolução de problemas e;
- Resolver problemas/Otimizar algoritmos sob pressão.
Siga as instruções abaixo para executar o projeto em sua máquina local:
- Clone este repositório utilizando o seguinte comando:
git clone https://[email protected]:priscilaSartori/project-algorithms.git
- Acesse o diretório do projeto:
cd project-algorithms
- Crie e ative o ambiente virtual para o projeto
python3 -m venv .venv && source .venv/bin/activate
- Instale as dependências:
python3 -m pip install -r dev-requirements.txt
- Execute os testes:
python3 -m pytest
Você trabalha na maior empresa de educação do Brasil. Certo dia, a pessoa Product Manager (PM)
quer saber qual horário tem a maior quantidade de pessoas estudantes acessando o conteúdo da plataforma. Com esse dado em mãos, a pessoa PM saberá qual é o melhor horário para disponibilizar os materiais de estudo para ter o maior engajamento possível.
O horário de entrada e saída do sistema é cadastrado no banco de dados toda vez que uma pessoa estudante entra e sai do sistema. Esses dados estarão contidos em uma lista de tuplas (permanence_period
) em que cada tupla representa o período de permanência de uma pessoa estudante no sistema com seu horário de entrada e de saída.
Seu trabalho é descobrir qual o melhor horário para disponibilizar os conteúdos de estudo. Para isso, utilize a estratégia de resolução de problemas chamada força bruta
em que a função desenvolvida por você será chamada várias vezes com valores diferentes para a variável target_time
e serão analisados os retornos da função.
👀 De olho na Dica: O melhor horário será aquele no qual o contador retornado pela função for o maior
Clique aqui para ver um exemplo.
# Nos arrays temos 6 estudantes
# estudante 1 2 3 4 5 6
permanence_period = [(2, 2), (1, 2), (2, 3), (1, 5), (4, 5), (4, 5)]
target_time = 5 # saída: 3, pois a quarta, a quinta e a sexta pessoa estudante ainda estavam estudando nesse horário.
target_time = 4 # saída: 3, pois a quinta e a sexta pessoa estudante começaram a estudar nesse horário e a quarta ainda estava estudando.
target_time = 3 # saída: 2, pois a terceira e a quarta pessoa estudante ainda estavam estudando nesse horário.
target_time = 2 # saída: 4, pois a primeira, a segunda, a terceira e a quarta pessoa estudante estavam estudando nesse horário.
target_time = 1 # saída: 2, pois a segunda e a quarta pessoa estudante estavam estudando nesse horário.
Para esse exemplo, depois de rodar a função para todos esses `target_times`, julgamos que o melhor horário é o `2`, pois esse retornou `4`, já que 4 estudantes estavam presentes nesse horário!
-
Este requisito será testado executando milhares de vezes sobre várias entradas com o tamanho variável. Tais execuções no avaliador irão determinar de maneira empírica, através de cálculos, a complexidade assintótica do seu algoritmo.
- O tempo de execução do código na sua máquina pode variar em relação ao avaliador, mas o cálculo será feito em cima do comportamento, e não do tempo de execução. Ainda assim, o que vale é o resultado do avaliador, e não o local. Na dúvida, busque ajuda do time de instrução.
-
O algoritmo deve utilizar a solução iterativa;
-
Caso o
target_time
passado seja nulo, o valor retornado pela função deve serNone
(considere o horário 0 como um horário válido); -
O código deve ser feito dentro do arquivo
challenges/challenge_study_schedule.py
.
🤖 Clique aqui para ver o que será verificado pelo avaliador.
-
1.1 - Retorne a quantidade de estudantes presentes para uma entrada específica;
-
1.2 - Retorne
None
se empermanence_period
houver alguma entrada inválida; -
1.3 - Retorne
None
setarget_time
recebe um valor vazio; -
1.4 - A função deverá, por meio de análise empírica, se comportar (no avaliador remoto em sua Pull Request) como no máximo O(n), ou seja, com complexidade assintótica linear.
Implemente em: tests/encrypt/test_encrypt.py
Durante a dinâmica em grupos de um processo seletivo, a empresa contratante definiu um desafio em duplas, e cada pessoa terá um papel. A primeira pessoa deve criar uma função de criptografia, e a segunda pessoa deve implementar os testes da função implementada pela primeira pessoa.
Você fará o papel da segunda pessoa nessa dinâmica, ou seja: deve implementar os testes de uma função de criptografia.
Esse teste deve se chamar test_encrypt_message
, e ele deve garantir que a função de criptografia encrypt_message
deve respeitar uma lógica específica.
🧠 Entenda a lógica da função de criptografia
- Recebe uma string
message
e um inteirokey
como parâmetros - Se
key
emessage
não possuírem os tipos corretos, uma exceção deve ser lançada - Se
key
não for um índice positivo válido demessage
, retorna a stringmessage
invertida - Se
key
for ímpar:- divide
message
no índicekey
, inverte os caracteres de cada parte, e retorna a união das partes novamente com"_"
entre elas
- divide
- Se
key
for par:- divide
message
no índicekey
, inverte a posição das partes, inverte os caracteres de cada parte, e retorna a união das partes novamente com"_"
entre elas
- divide
Veja alguns exemplos:
📌 Como seu teste é avaliado
O teste da Trybe irá avaliar se o seu teste está passando conforme seu objetivo, e confirmará se ele está falhando em alguns casos que deve falhar. Para estes testes que esperemos que falhe, o requisito será considerado atendido quando a resposta do Pytest forXFAIL(Expected Fail)
ao invés de PASS
ou FAIL
.
🤖 O que será verificado pelo avaliador
- O teste rejeita implementações que invertem a lógica de "par ou ímpar";
- O teste rejeita implementações que não aplicam a regra de índice positivo válido;
- O teste rejeita implementações que aplicam ordenação ao invés de inversão;
- O teste rejeita implementações que não validam o tipo das entradas;
- O teste aprova implementações corretas.
Escreva uma função que irá determinar se uma palavra é um palíndromo ou não. A função irá receber uma string de parâmetro e o retorno será um booleano, True
ou False
.
Mas o que é um palíndromo?
Um palíndromo é uma palavra, frase ou número que mantém seu sentido mesmo sendo lido de trás para frente. Por exemplo,
"ABCBA"
.
Clique aqui para ver um exemplo.
word = "ANA"
# saída: True
word = "SOCOS"
# saída: True
word = "REVIVER"
# saída: True
word = "COXINHA"
# saída: False
word = "AGUA"
# saída: False
-
O algoritmo deve ser feito utilizando a solução recursiva;
-
Não se preocupe com a análise da complexidade desse algoritmo;
-
Se for passado uma string vazia, retorne
False
; -
O código deve ser feito dentro do arquivo
challenges/challenge_palindromes_recursive.py
.
🤖 Clique aqui para ver o que será verificado pelo avaliador.
-
3.1 - Retorne
True
se a palavra passada por parâmetro for um palíndromo; -
3.2 - Retorne
False
se a palavra passada por parâmetro não for um palíndromo; -
3.3 - Retorne
False
se nenhuma palavra for passada por parâmetro.
Faça um algoritmo que consiga comparar duas strings, ordená-las e identificar se uma é um anagrama da outra. Ou seja, sua função irá receber duas strings de parâmetro e o retorno da função será uma tupla ()
com a primeira string ordenada, a segunda string ordenada e um booleano, True
ou False
representando se são anagramas.
O algoritmo deve considerar letras maiúsculas e minúsculas como iguais durante a comparação das entradas, ou seja, ser case insensitive.
Mas o que é um anagrama?
"Um anagrama é uma espécie de jogo de palavras criado com a reorganização das letras de uma palavra ou expressão para produzir outras palavras ou expressões, utilizando todas as letras originais exatamente uma vez."
Clique aqui para ver um exemplo.
first_string = "amor"
second_string = "roma"
# saída: ('amor', 'amor', True)
# Explicação: Nesse caso a palavra 'amor' ordenada continua 'amor' e 'roma' ordenado vira 'amor, além disso a função é True, pois a palavra "roma" é um anagrama de "amor".
first_string = "pedra"
second_string = "perda"
# saída: ('adepr', 'adepr', True)
# Explicação: Nesse caso o retorno também é True. Na palavra "pedra", trocamos o "d" de lugar com o "r" e formamos "perda", sendo assim um anagrama e temos as duas strings ordenadas.
first_string = "pato"
second_string = "tapo"
# saída: ('aopt', 'aopt', True)
first_string = "Amor"
second_string = "Roma"
# saída: ('amor', 'amor', True)
# Explicação: Nesse caso o retorno da função é True, pois a palavra "Roma" é um anagrama de "Amor" independente da letra "R" e "A" serem maiúsculas.
# Agora vamos pra um exemplo em que não existe um anagrama
first_string = "coxinha"
second_string = "empada"
# saída: ('achinox', 'aademp', False)
-
Este requisito será testado executando milhares de vezes sobre várias entradas com o tamanho variável. Tais execuções no avaliador irão determinar de maneira empírica, através de cálculos, a complexidade assintótica do seu algoritmo.
- O tempo de execução do código na sua máquina pode variar em relação ao avaliador, mas o cálculo será feito em cima do comportamento, e não do tempo de execução. Ainda assim, o que vale é o resultado do avaliador, e não o local. Na dúvida, busque ajuda do time de instrução;
-
Utilize algoritmos de ordenação para realizar este requisito.
- Utilize qualquer algoritmo que quiser (Selection sort, Insertion sort, Bubble sort, Merge sort, Quick sort ou TimSort), desde que atinja a complexidade
O(n log n)
. ⚠️ Você deverá implementar sua própria função de ordenação, ou seja, o uso de funções prontas não é permitido.- Exemplos de funções não permitidas: sort, sorted e Counter;
- Utilize qualquer algoritmo que quiser (Selection sort, Insertion sort, Bubble sort, Merge sort, Quick sort ou TimSort), desde que atinja a complexidade
-
⚠️ Não será permitido realizar nenhuma importação neste arquivo! -
A função retorna
True
caso uma string seja um anagrama da outra independente se as letras são maiúsculas ou minúsculas; -
A função retorna
False
caso uma string não seja um anagrama da outra; -
O código deve ser feito dentro do arquivo
challenges/challenge_anagrams.py
.
🤖 Clique aqui para ver o que será verificado pelo avaliador.
-
4.1 - Retorne
True
se as palavras passadas por parâmetro forem anagramas; -
4.2 - Retorne
False
se as palavras passadas por parâmetro não forem anagramas; -
4.3 - Retorne
False
se alguma das palavras passadas por parâmetro for uma string vazia; -
4.4 - A função deverá, por meio de análise empírica, se comportar (no avaliador remoto em sua Pull Request) como no máximo O(n log n), ou seja, com complexidade assintótica linearítmica.
-
4.5 - Retorne
True
se as palavras passadas forem anagramas sem diferenciar maiúsculas e minúsculas.
Dada um array de números inteiros contendo n + 1
inteiros, chamado de nums
, em que cada inteiro está no intervalo [1, n]
.
Retorne apenas um número duplicado em nums
.
Clique aqui para ver um exemplo.
nums = [1, 3, 4, 2, 2]
# saída: 2
nums = [3, 1, 3, 4, 2]
# saída: 3
nums = [1, 1]
# saída: 1
nums = [1, 1, 2]
# saída: 1
nums = [3, 1, 2, 4, 6, 5, 7, 7, 7, 8]
# saída: 7
-
Caso não passe nenhum valor ou uma string ou não houver números repetidos retorne
False
; -
Este requisito será testado executando milhares de vezes sobre várias entradas com o tamanho variável. Tais execuções no avaliador irão determinar de maneira empírica, através de cálculos, a complexidade assintótica do seu algoritmo.
- O tempo de execução do código na sua máquina pode variar em relação ao avaliador, mas o cálculo será feito em cima do comportamento, e não do tempo de execução. Ainda assim, o que vale é o resultado do avaliador, e não o local. Na dúvida, busque ajuda do time de instrução;
-
O array montado deve:
-
Ter apenas números inteiros positivos maiores do que 1;
-
Ter apenas um único número repetindo duas ou mais vezes, todos os outros números devem aparecer apenas uma vez;
-
Ter, no mínimo, dois números.
-
-
O código deve ser feito dentro do arquivo
challenge_find_the_duplicate.py
.
👀 De olho na Dica: ordene o array.
🤖 Clique aqui para ver o que será verificado pelo avaliador.
-
5.1 - Retorne o número repetivo se a função receber como parâmetro uma lista com números repetidos;
-
5.2 - Retorne
False
se a função não receber nenhum parâmetro; -
5.3 - Retorne
False
se a função receber como parâmetro uma string; -
5.4 - Retorne
False
se a função receber como parâmetro uma lista sem números repetidos; -
5.5 - Retorne
False
se a função receber como parâmetro apenas um valor; -
5.6 - Retorne
False
se a função receber como parâmetro um número negativo; -
5.7 - A função deverá, por meio de análise empírica, se comportar (no avaliador remoto em sua Pull Request) como no máximo O(n log n), ou seja, com complexidade assintótica linearítmica.
Resolva o mesmo problema apresentado no requisito 2 - Palíndromos
, porém dessa vez utilizando a solução iterativa.
-
Este requisito será testado executando milhares de vezes sobre várias entradas com o tamanho variável. Tais execuções no avaliador irão determinar de maneira empírica, através de cálculos, a complexidade assintótica do seu algoritmo.
- O tempo de execução do código na sua máquina pode variar em relação ao avaliador, mas o cálculo será feito em cima do comportamento, e não do tempo de execução. Ainda assim, o que vale é o resultado do avaliador, e não o local. Na dúvida, busque ajuda do time de instrução;
-
O algoritmo deve utilizar a solução iterativa;
-
O código deve ser feito dentro do arquivo
challenge_palindromes_iterative.py
.
🤖 Clique aqui para ver o que será verificado pelo avaliador.
-
6.1 - Retorne
True
se a palavra passada como parâmetro for um palíndromo, executando uma função iterativa; -
6.2 - Retorne
False
se a palavra passada como parâmetro não for um palíndromo, executando uma função iterativa; -
6.3 - Retorne
False
se nenhuma palavra for passada como parâmetro, executando uma função iterativa ; -
6.4 - A função deverá, por meio de análise empírica, se comportar (no avaliador remoto em sua Pull Request) como no máximo O(n), ou seja, com complexidade assintótica linear.