Como melhorar suas estruturas de dados, algoritmos e habilidades para resolver problemas

Fabian Terh Blocked Desbloquear Seguir Seguindo 3 de janeiro Fonte: Arafat Khan

Este post baseia-se em minhas experiências pessoais e desafios sobre o passado na escola, que eu entrei com quase nenhum conhecimento de DSA (estruturas de dados e algoritmos) e estratégias de resolução de problemas. Como programador autodidata, eu estava muito mais familiarizado e confortável com programação geral, como programação orientada a objetos, do que com as habilidades de resolução de problemas exigidas em questões de DSA.

Este post reflete minha jornada ao longo do período e os recursos aos quais me voltei para melhorar rapidamente minhas estruturas de dados, algoritmos e habilidades para solução de problemas.

Problema: Você conhece a teoria, mas fica preso em aplicações práticas

Eu enfrentei essa questão no início do semestre, quando não sabia o que não sabia , o que é um problema particularmente pernicioso. Eu entendi a teoria bem o suficiente – por exemplo, o que uma lista encadeada era, como funcionava, suas várias operações e suas complexidades de tempo, os ADTs (tipos de dados abstratos) que ela suportava e como as operações da ADT eram implementadas.

Mas como não sabia o que não sabia, não consegui identificar lacunas na compreensão de suas aplicações práticas na solução de problemas.

Os diferentes tipos de perguntas

Um exemplo de uma questão de estruturas de dados: descreva como você poderia inserir um nó em uma lista vinculada e declarar a complexidade do tempo.

E aqui está uma questão de algoritmos: procure por um elemento em uma matriz ordenada rotacionada e informe a complexidade do tempo.

Finalmente, uma questão de solução de problemas, que considero estar em um “nível mais alto” do que os dois anteriores, pode descrever brevemente um cenário e listar os requisitos do problema. Em um exame, ele pode solicitar uma descrição da solução. Na programação competitiva, pode ser necessário submeter o código de trabalho sem fornecer explicitamente quaisquer estruturas de dados ou algoritmos. Em outras palavras, espera-se que você aplique as estruturas de dados e os algoritmos mais aplicáveis para resolver o problema da maneira mais eficiente possível.

Como você pode melhorar suas estruturas de dados, algoritmos e habilidades para resolver problemas?

Eu uso principalmente três sites para prática: HackerRank , LeetCode e Kattis . Eles são muito semelhantes, especialmente os dois primeiros, mas não idênticos. Eu acho que cada site tem um foco ligeiramente diferente, cada um dos quais é imensamente útil à sua maneira.

Eu categorizaria vagamente as habilidades necessárias para a solução de problemas em:

  1. conhecimento de estruturas de dados
  2. conhecimento de algoritmos
  3. conhecimento da aplicação de estruturas de dados e algoritmos

Os dois primeiros poderiam ser considerados os "primitivos", ou blocos de construção, que vão para o terceiro, que é saber o que aplicar para um cenário específico.

Conhecimento de estruturas de dados

A esse respeito, achei o HackerRank um recurso valioso. Ele tem uma seção dedicada às estruturas de dados , que você pode filtrar por tipo, como matrizes, listas vinculadas, árvores (balanceadas), pilhas e assim por diante.

As perguntas não são tanto sobre resolução de problemas, mas sobre como trabalhar com estruturas de dados. Por exemplo:

  1. arrays: rotação de array , manipulação de array
  2. listas encadeadas: invertendo uma lista encadeada , detecção de ciclo
  3. trees: troca de nó , validação de BST

Você entendeu a ideia. Algumas das perguntas podem não ser diretamente aplicáveis na solução de problemas. Mas eles são ótimos para a compreensão conceitual, que é extremamente importante em qualquer caso.

O HackerRank não tem “soluções modelo” livremente acessíveis, embora a seção de discussões seja geralmente cheia de dicas, pistas e até trechos de código. Eu descobri que eles são adequados até agora, embora você possa ter que percorrer o código uma linha de cada vez em um IDE para realmente entender alguma coisa.

Conhecimento de algoritmos

O HackerRank também possui uma seção de algoritmos , embora eu prefira o LeetCode para isso. Eu achei a variedade de problemas do LeetCode muito mais ampla, e eu realmente gosto que muitos problemas tenham soluções com explicações e até complexidades de tempo.

Um ótimo ponto de partida seria as 100 perguntas mais gostosas do LeetCode. Algumas perguntas que achei ótimas:

Ao contrário das questões de estruturas de dados, o foco aqui não é muito sobre como trabalhar ou manipular estruturas de dados, mas sim como fazer algo . Por exemplo, o problema de “mesclagem de contas” é principalmente sobre a aplicação de algoritmos UFDS padrão. O problema “pesquisando em uma matriz ordenada rotacionada” apresenta uma reviravolta na pesquisa binária. E às vezes você aprende uma técnica totalmente nova de solução de problemas. Por exemplo, a solução “ janela deslizante ” para o problema da “subsequência crescente contínua mais longa”.

Conhecimento da aplicação de estruturas de dados e algoritmos

Finalmente, eu uso Kattis para melhorar minhas habilidades gerais de resolução de problemas. O Kattis Problem Archive tem um monte de problemas de programação de várias fontes, como competições de programação competitiva, em todo o mundo.

Kattis pode ser incrivelmente frustrante porque não há soluções oficiais ou um fórum de discussão (ao contrário do HackerRank e LeetCode). Além disso, os casos de teste são privados. Eu tenho um punhado de problemas Kattis pendentes que não posso resolver – não porque eu não conheço a solução, mas porque não consigo descobrir o bug.

É o meu site menos preferido entre os três para praticar e aprender, e eu não gastei muito tempo com isso.

Outros recursos

O Geeksforgeeks é outro recurso muito valioso para aprender sobre estruturas de dados e algoritmos. Eu gosto de como ele fornece trechos de código em vários idiomas, geralmente C ++, Java e Python, que você pode copiar e colar no seu IDE para percorrer linha por linha.

Finalmente, há o velho e confiável Google, que o levaria a GeeksForGeeks a maior parte do tempo, e o Youtube, por explicações visuais.

Conclusão

No final do dia, no entanto, não há atalhos. Você só precisa mergulhar de cabeça – comece a escrever código, depurar código e ler o código correto de outras pessoas para descobrir onde, como e por que você errou. É difícil, mas você melhora a cada tentativa e fica mais fácil à medida que melhora.

Eu não estou nem perto do nível de competência que quero ser, mas definitivamente percorri um longo caminho desde que comecei. 🙂