Available inPortugueseEnglishFrenchGermanHindiRussianSpanish
Padrões de entrevista de código (Blind 75)
Leia um problema inédito da Blind 75, nomeie a técnica que ele pede e a invariante que torna essa escolha correta, antes de escrever uma linha de código. Para quem já resolveu setenta problemas do LeetCode ou mais e ainda trava diante de um enunciado nunca visto; Big-O é pressuposto, sintaxe não é ensinada. Sessenta e quatro cartões ligam dez famílias de técnicas aos problemas que as exigem.
Um array ordenado, achar dois elementos que somam um alvo, e o enunciado exige “O(1) extra space”. Nomeie a técnica para a qual isso aponta.
Two pointers convergindo das duas pontas
— A ordenação faz o trabalho que um hash map faria.
Source
Três pistas se combinam: a entrada chega ordenada, a resposta é um par, e o limite de espaço proíbe um hash map. “Sorted array” é a entrada já em ordem; “O(1) extra space” é memória extra constante, e aparece também como “in-place” e “without using extra memory”. Comece um índice em cada ponta: soma grande demais, puxe o da direita; pequena demais, avance o da esquerda. Cada passo aposenta um índice de vez, então a varredura é O(n) sem memória nenhuma. Costuma ser confundido com: o hash map de uma passada, que é a resposta certa quando o array não está ordenado e o espaço é livre, já que ordenar antes custaria um O(n log n) que ali ninguém pediu.