/project-algorithms

⌨️ Projeto de aprendizado de lógica de programação em Python, aplicando conceitos de otimização de algoritmos.

Primary LanguagePython

Boas-vindas ao repositório do projeto Algorithms!

Esse é um projeto voltado ao aprendizado de construção de algoritmos em Python.

🚵 Habilidades exercitadas:

  • 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.

Instruções de instalação

  1. Clone o repositório Use o comando: git clone git@github.com:MikaelaBraga/project-algorithms.git

  2. Entre na pasta do repositório que você acabou de clonar:

  • cd project-algorithms
  1. Crie o ambiente virtual para o projeto
  • python3 -m venv .venv && source .venv/bin/activate
  1. Instale as dependências
  • python3 -m pip install -r dev-requirements.txt

Estrutura do projeto

  .
  ├── challenges
  │   ├──🔹 challenge_anagrams.py
  │   ├──🔹 challenge_find_the_duplicate.py
  │   ├──🔹 challenge_palindromes_iterative.py
  │   ├──🔹 challenge_palindromes_recursive.py
  │   └──🔹 challenge_study_schedule.py
  ├──🔸 dev-requirements.txt
  ├──🔸 pyproject.toml
  ├──🔸 README.md
  ├──🔸 requirements.txt
  ├──🔸 setup.cfg
  ├──🔸 setup.py
Legenda:
  🔸 Arquivos que não podem ser alterados.
  🔹 Arquivos a serem alterados para realizar os requisitos.

Vale mencionar que desenvolvi apenas o código contido na pasta challenges. Todos os scripts e configurações na raíz do projeto são fornecidos pela Trybe.

Requisitos Obrigatórios

1 - Número de estudantes estudando no mesmo horário (Algoritmo de busca)

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 10.000 vezes sobre uma mesma entrada. Tais execuções no avaliador devem acontecer integralmente em menos de 0.02 segundos. O tempo de execução do código na sua máquina pode variar em relação ao avaliador, então é importante levar somente ele em consideração. 👀 De olho na Dica: Use um algoritmo de, no máximo, complexidade O(n).

  • O algoritmo deve utilizar a solução iterativa;

  • Caso o target_time passado seja nulo, o valor retornado pela função deve ser None (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 em permanence_period houver alguma entrada inválida;

  • 1.3 - Retorne None se target_time recebe um valor vazio;

  • 1.4 - A função poderá, em menos de 0.02s, ser executada 10.000 vezes para uma entrada pequena (tempo da execução do avaliador no Pull Request).

2 - Palíndromos (Recursividade)

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". :warning: Neste projeto iremos focar somente em palavras palíndromas e não em frases ou números.

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.

  • 2.1 - Retorne True se a palavra passada por parâmetro for um palíndromo;

  • 2.2 - Retorne False se a palavra passada por parâmetro não for um palíndromo;

  • 2.3 - Retorne False se nenhuma palavra for passada por parâmetro.

3 - Anagramas (Algoritmo de ordenação)

Faça um algoritmo que consiga comparar duas strings 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á um booleano, True ou False.

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: True
# Explicação: Nesse caso o retorno da função é True, pois a palavra "roma" é um anagrama de "amor".


first_string = "pedra"
second_string = "perda"
# saída: 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.  


first_string = "pato"
second_string = "tapo"
# saída: True


first_string = "Amor"
second_string = "Roma"
# saída: 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: False

  • Este requisito será testado executando 10.000 vezes sobre uma mesma entrada. Tais execuções no avaliador devem acontecer integralmente em menos de 2 segundos. O tempo de execução do código na sua máquina pode variar em relação ao avaliador, então é importante levar somente ele em consideração. 👀 De olho na dica: use um algoritmo de, no máximo, complexidade O(n log n);

  • 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). Ou seja, preste bastante atenção na escolha do algoritmo e na implementação do mesmo; ⚠️ 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;

  • 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.

  • 3.1 - Retorne True se as palavras passadas por parâmetro forem anagramas;

  • 3.2 - Retorne False se as palavras passadas por parâmetro não forem anagramas;

  • 3.3 - Retorne False se alguma das palavras passadas por parâmetro for uma string vazia;

  • 3.4 - Execute a função, somando 10.000 execuções para uma entrada pequena, em menos que 8.2s (tempo da execução do avaliador no Pull Request);

  • 3.5 - Retorne True se as palavras passadas forem anagramas sem diferenciar maiúsculas e minúsculas.

Requisitos Bônus

4 - Encontrando números repetidos (Algoritmo de busca)

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 10.000 vezes sobre uma mesma entrada. Tais execuções no avaliador devem acontecer integralmente em menos de 0.01 segundos. O tempo de execução do código na sua máquina pode variar em relação ao avaliador, então é importante levar somente ele em consideração. 👀 De olho na Dica: use um algoritmo de, no máximo, complexidade O(n log n).

  • 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.

  • 4.1 - Retorne o número repetivo se a função receber como parâmetro uma lista com números repetidos;

  • 4.2 - Retorne False se a função não receber nenhum parâmetro;

  • 4.3 - Retorne False se a função receber como parâmetro uma string;

  • 4.4 - Retorne False se a função receber como parâmetro uma lista sem números repetidos;

  • 4.5 - Retorne False se a função receber como parâmetro apenas um valor;

  • 4.6 - Retorne False se a função receber como parâmetro um número negativo;

  • 4.7 - Execute a função, somando 10.000 execuções para uma entrada pequena, em menos que 0.01s (tempo da execução do avaliador no Pull Request).

5 - Palíndromos (Iteratividade)

Resolva o mesmo problema apresentado no requisito 2 - Palíndromos, porém dessa vez utilizando a solução iterativa.

  • Este requisito será testado executando 10.000 vezes sobre uma mesma entrada. Tais execuções no avaliador devem acontecer integralmente em menos de 0.005 segundos. O tempo de execução do código na sua máquina pode variar em relação ao avaliador, então é importante levar somente ele em consideração. 👀 De olho na Dica: use um algoritmo de, no máximo, complexidade O(n).

  • 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.

  • 5.1 - Retorne True se a palavra passada como parâmetro for um palíndromo, executando uma função iterativa;

  • 5.2 - Retorne True se a palavra passada como parâmetro for um palíndromo, executando uma função iterativa;

  • 5.3 - Retorne False se nenhuma palavra for passada como parâmetro, executando uma função iterativa ;

  • 5.4 - Execute a função, somando 10.000 execuções para uma entrada pequena, em menos que 0.005s (tempo da execução do avaliador no Pull Request).