A maioria dos problemas de entrevista é um padrão conhecido dentro de uma história nova. O caminho mais rápido até o padrão certo é ler as restrições antes da história: qual é o tamanho de n, os dados estão ordenados, eles mudam, e a pergunta é sobre um único trecho contíguo, sobre muitos intervalos quaisquer ou sobre uma única passada?
Alguns sinais são confiáveis. “Contíguo” mais “mais longo” ou “mais curto” aponta para uma janela deslizante. “Muitos totais de intervalo sobre dados fixos” aponta para somas de prefixos. “Muitas atualizações de intervalo, lidas uma vez no final” aponta para um array de diferenças. Um array ordenado mais uma condição sobre pares aponta para dois ponteiros. “Visto antes” em uma única passada aponta para um mapa hash. Uma ordem natural com uma escolha que nunca bloqueia as escolhas seguintes aponta para uma regra gulosa, mas só quando você consegue enunciar o argumento de troca.
Cada pergunta nomeia uma restrição que descarta as outras opções. Encontre-a e depois confira sua resposta.
Leia primeiro as restrições; elas descartam a maioria dos padrões.