Quando trocar um loop de busca por um hash map
Pergunta
Você precisa checar repetidamente se um valor existe numa coleção. Quando vale a pena usar um hash map (dicionário/objeto) em vez de percorrer um array, e qual é o custo dessa troca?
Resposta esperada
Percorrer um array pra achar um valor é O(n) por busca; um hash map (Set/Map, dict) responde em O(1) médio. Se você faz muitas buscas sobre a mesma coleção, montar um Set uma vez (O(n)) e consultar em O(1) troca um custo total de O(n·m) por O(n+m). O preço é memória extra (o índice) e a perda da ordem/duplicatas, além do pior caso teórico O(n) sob colisões ruins de hash — raro na prática. Para poucas buscas ou coleções minúsculas, o array simples é mais legível e não compensa a estrutura extra.
Por que perguntam isso
O padrão 'transforme em hash set primeiro' resolve uma fração enorme dos problemas de entrevista (two-sum, deduplicação, interseção). Bom sinal: o candidato pergunta quantas buscas serão feitas antes de decidir.