Cenário: detectar ciclo numa lista encadeada
Pergunta
Como você detecta se uma lista encadeada tem um ciclo (um nó que aponta de volta pra um nó anterior), usando espaço constante?
Resposta esperada
Algoritmo de Floyd (lebre e tartaruga): dois ponteiros partem do início, um anda 1 passo por iteração, o outro anda 2. Se existe ciclo, o ponteiro rápido eventualmente alcança o lento dentro do ciclo e eles se encontram — retorna verdadeiro. Se o rápido chega ao fim (null), não há ciclo. É O(n) tempo e O(1) espaço. A alternativa óbvia — guardar cada nó visitado num hash set e checar repetição — também é O(n) tempo mas O(n) espaço, o que viola a restrição do enunciado. Saber os dois e escolher o de Floyd pela restrição de espaço é a resposta esperada.
Por que perguntam isso
Pergunta de nível sênior porque a solução com hash set vem fácil e está 'certa' — o desafio é o candidato lembrar da restrição de espaço e conhecer Floyd. Se ele descrever a intuição de por que os ponteiros se encontram, é sinal forte.