Cenário: par que soma um alvo num array ordenado
Pergunta
Dado um array JÁ ORDENADO de inteiros e um alvo, encontre se existe um par de elementos que soma exatamente o alvo. Como você resolve em melhor que O(n²)?
Resposta esperada
Como o array está ordenado, use dois ponteiros: um no início, um no fim. Some os dois. Se a soma for maior que o alvo, mova o ponteiro da direita pra dentro (diminui a soma); se for menor, mova o da esquerda (aumenta). Se igual, achou. Termina quando os ponteiros se cruzam. É O(n) tempo, O(1) espaço extra. Sem a ordenação prévia, a alternativa é um hash set: para cada x, checar se (alvo − x) já foi visto — também O(n) tempo, mas O(n) espaço. Mencionar os dois e o trade-off de espaço é a resposta completa.
Por que perguntam isso
Cenário clássico de 'reconheça o padrão'. O detalhe que separa pleno de júnior: aproveitar a ordenação já dada em vez de gastar O(n log n) reordenando ou cair no hash set por reflexo.