Victor Breder
(Comp 19):
Hoje estou na Microsoft São Paulo como engenheiro de
software. No processo de admissão, praticar programação
competitiva, problemas de estruturas de dados e algoritmos, é
a peça central.
Devo ter feito quase uma dúzia de problemas semelhantes aos do
Leetcode ou do Interview Bit em cenários de
entrevista. Geralmente um problema por entrevista, mas às
vezes dois, um simples e outro depois mais calibrado para quão
fácil você resolveu o primeiro.
Concretamente, alguns problemas que já caíram em entrevista
para mim:
1. Dada uma lista de números inteiros e um número objetivo T.
Retorne a lista de todos os pares que somados totalizam T. Tem
solução em O(n) se o map/hashtable for O(1).
2. Dado um tabuleiro de Sudoku parcialmente preenchido
e com solução possível, retorne todas as soluções possíveis
(para a configuração dada). Uma solução possível envolve DFS
com pruning/backtracking.
3. Fingindo que estamos fazendo um sistema de compilação /
build system. Dada uma lista de dependências: objeto_1 depende
de fonte_1, fonte_2; objeto_2 depende de objeto_1, etc...
(objetos podem depender de outros objetos ou de fontes), me dê
uma ordem de compilação que satisfaz as dependências. A
solução envolveria montar o grafo de dependências e retornar
uma ordenação topológica.
Ter a intuição para a análise de complexidade sem pausar
muito, eu acho que serve como um diferencial positivo na
percepção do entrevistador.
No trabalho, não vai ser explicitamente requerida sempre a
análise. Frequentemente envolve mais evitar soluções com
complexidade ruim, do que achar uma solução espertíssima com
complexidade menor. Em ambiente de engenharia, as outras
pessoas (e você mesmo no futuro) têm que conseguir entender e
alterar o código, então por via de regra a solução que entra é
a solução mais simples que não é desnecessariamente
ineficiente.
Problema que já vi no trabalho:
Temos uma lista de alunos A (sistema da escola - "a verdade")
e uma lista de alunos B (sistema do meu app). Temos que
determinar a diferença, isto é, encontrar quais alunos foram
adicionados (e colocar no app), quais alunos foram retirados
(tirar o acesso do app), quais alunos mudaram a informação
(quem é o responsável, telefone de contato).
Alguém menos cauteloso poderia, para cada aluno da lista A,
iterar toda a lista B sem perceber que isto seria O(n^2).
Alguém que estudou complexidade e CTC-12 saberia que basta
ordenar as duas listas em O(n log n), depois manter um
ponteiro em cada lista e ir avançando o ponteiro da lista A, o
ponteiro da lista B, ou ambos, em O(n). A diferença do tempo
de relógio que levaria, dependendo da quantidade de alunos,
seria várias ordens de grandeza (e ainda mais, na prática, os
bancos de dados como Postgres ou MySQL deixam
os registros em alguma variante de B-tree, então já
estão pré-ordenados pela forma que índices são implementados -
outra informação que você entende naturalmente se você
compreende CTC-12 e bancos de dados).
Outro caso comum de engenheiros júnior tropeçarem:
Tenho uma lista S e quero remover os elementos listados em uma
lista R.
A biblioteca padrão oferece S.Remove(x), onde x é um elemento
a ser removido.
Um estudante de CTC-12 saberia que S é implementado como uma
array, então toda remoção envolveria deslocar os demais
elementos da array, em O(n). Se você iterar por cada elemento
de R e chamar S.Remove(r), você está fazendo um código O(n^2)
sem perceber.
(A alternativa mais rápida em complexidade, eu acho, seria
transformar R em uma hash table/hash set para que fosse O(1)
verificar a existência de um elemento, depois ir iterando
sobre S e marcando cada elemento para remoção ou não, e
finalmente reconstruindo o S sem os elementos removidos em
O(n).)
Assim, admito que no trabalho você nunca implementaria nenhuma
estrutura de dados (além de uma eventual fila ou stack) que já
não estivesse na biblioteca padrão, que é o que eu imagino ser
a resistência mais comum, no estilo "nunca vou implementar
busca de Dijkstra".
Ainda que seja verdade, o "porém" é que qualquer sistema de
software real com o qual você vai ter que trabalhar foi
escrito e projetado por outras pessoas que já entendiam bem
estes conceitos. Se você já não tiver a bagagem, não vai ter
escrito em nenhum lugar o porquê das decisões que foram
feitas. Saber estruturas de dados e algoritmos é tido (na
minha opinião) como um vocabulário fundamental que só vai ser
esperado de você e pressuposto que você, no ambiente
profissional, entenda.