Projeto Algorithms

Quarto projeto do módulo de Ciência da Computação do curso de desenvolvimento web da Trybe

Contexto

Ao longo do bloco desse projeto, estudamos temas importantes dentro da Ciência da Computação, como: complexidade de algorítmos, recursividade e algorítmos de ordenação. Aprendemos superficialmente a identificar se um algorítmo apresenta complexidade constante, linear, quadrática, exponencial ou fatorial e como otimizar algorítmos de alto custo computacional. Além disso, conhecemos alguns algorítmos de ordenação e busca, com seus respectivos melhores casos, piores casos e casos médios.

Objetivo do projeto

Para fixar os conteúdos de algoritmos, o principal objetivo desse projeto é a resolução de problemas e otimização algoritmos. Muitos dos problemas apresentados são similares aos que aparecem em entrevistas de processos seletivos do tipo whiteboard, conhecidos por ocorrerem no processo de contratação de grandes companhias (Google, Amazon, Facebook, etc).

Principais habilidades desenvolvidas nesse trabalho

• Utilizar diferentes estruturas de dados
• Treinar análise de complexidade de algoritimos
• Praticar interpretação de problemas;
• Resolver problemas de forma otimizada;
• Analisar corretamente a ordem de complexidade de um algoritmo.
• Praticar funções recursivas
• Praticar algoritmos de ordenação e algoritmos de busca

Tecnologia utilizada

• - Python

---

Lista de requisitos propostos pela Trybe:

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. Um certo dia, sua/seu PM quer saber qual horário tem a maior quantidade de pessoas acessando o conteúdo da plataforma ao mesmo tempo. Com esse dado em mãos, o/a PM saberá qual é o melhor horário para disponibilizar os materiais de estudo para ter o maior engajamento possível no sistema.

Toda vez que uma pessoa estudante abre o sistema, é cadastrado no banco de dados o horário de entrada. Da mesma forma funciona quando o estudante sai do sistema, é cadastrado no banco de dados o horário de saída. Esses dados estarão contidos em uma lista de tuplas (permanence_period) onde cada tupla representa o período de permanência de uma pessoa estudante com seu horário de entrada e de saída

Seu trabalho é descobrir qual o melhor horário para disponibilizar os conteúdos. Para achar o horário, será utilizada força bruta. Ou seja, para achar o melhor horário, a função que você desenvolver será chamada várias vezes com valores diferentes para a variável target_time, e serão analisados os retornos da função.

Dica: Quando vou saber qual o melhor horário? Quando o contador retornado pela função for o maior.

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.

Dica: use um algoritmo de, no máximo, complexidade O(n)

• 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);

• Código deve ser feito dentro do arquivo challenges/challenge_study_schedule.py.

2 - Palíndromos (Recursividade)

Dado uma string, determine se ela é um palíndromo ou não. Escreva uma função que irá determinar se uma string é um palíndromo ou não. Um palíndromo é uma string, uma palavra, em que não faz diferença se ela é lida da esquerda para a direita ou vice-versa, pois ela mantêm o mesmo sentido. Por exemplo, "ABCBA".

Curiosidade: Existem frases palíndromas também, porém nesse exercício iremos fazer uma função que identifique apenas as palavras palíndromas.

Exemplos:

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 analise da complexidade desse algoritmo;

• Se for passado uma string vazia, retorne False;

• Código deve ser feito dentro do arquivo challenges/challenge_palindromes_recursive.py.

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? Vamos ver sua definição para entendermos melhor:

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

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 onde 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 8.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.

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;

• Código deve ser feito dentro do arquivo challenges/challenge_anagrams.py.

Bônus:

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

Dada um array de números inteiros contendo n + 1 inteiros, chamado de nums, onde cada inteiro está no intervalo [1, n].

Retorne apenas um número duplicado em nums.

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.

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.

• Código deve ser feito dentro do arquivo challenge_find_the_duplicate.py.

Dica: Ordene o array.

5 - Palíndromos (Iteratividade)

Resolva o mesmo problema, apresentado no requisito dois, 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.

Dica: use um algoritmo de, no máximo, complexidade O(n)

• Algoritmo deve utilizar a solução iterativa;

• Código deve ser feito dentro do arquivo challenge_palindromes_iterative.py.

---

Ir para a lista de projetos