Etapa 1: entenda a pergunta.
É realmente importante saber exatamente o que esta pergunta está fazendo. Algumas perguntas que poderíamos fazer ao entrevistador são:
- O que exatamente queremos retornar? (A: O nó que se cruza).
- Isso significa que podemos assumir que as listas vinculadas sempre se cruzam? (A: Sim)
É sempre importante entender a questão antes de pensar na abordagem da solução.
Etapa 2: discuta as vantagens e desvantagens de diferentes soluções.
Uma solução imediata é percorrer as duas listas vinculadas ao mesmo tempo até chegar a um cruzamento. Neste exemplo, faríamos uma ponteiro nos nós 2 e 7, e atravessar cada um deles um por um até chegarmos a um nó comum.
No entanto, como você deve ter notado, isso não funcionará, pois os comprimentos das duas LinkedLists podem diferir. O que queremos fazer é essencialmente “cortar” a parte inicial do LinkedListNode mais longo e iterar repetidamente.
Esse seria o tipo de conversa com o entrevistador.
Etapa 3: escreva o código.
Abaixo está o método para conseguir isso.
Nós fazemos uso de métodos auxiliares aqui. Nós usamos getKthNode() para obter o k-ésimo nó da lista vinculada fornecida. Isso é útil ao percorrer a lista vinculada mais longa para “cortar” nós extras.
Nós também usamos getTailAndSize() que captura o comprimento e o último nó da lista fornecida. Isso é útil porque, definitivamente, precisamos do tamanho para comparar os comprimentos das listas. Também precisamos das caudas porque, se as caudas das duas listas são desiguais, elas não se cruzam.
Observe que quando dizemos “desigual”, queremos dizer que os dois nós não fazem referência à mesma objeto. Mesmo que eles possam ter o mesmo valor e parecer idênticos, devem fazer referência ao mesmo LinkedListNode para contar como igual. (Você pode encontrar mais informações sobre este aqui.)
Voltando à questão, se encontrarmos o caso em que as caudas são desiguais, retornamos um valor com falha (nulo).
Etapa 4: teste o código.
Abaixo estão alguns bons casos de teste que podemos adicionar. Uma regra prática útil para casos de teste é a seguinte:
- Caso vazio / nulo
- Considerando as opções no meio / começo / fim
- Tamanhos iguais ou diferentes
Essa estratégia não se aplica apenas às perguntas do LinkedList – isso funcionaria para matrizes, Strings e essencialmente qualquer outra estrutura de dados.
Para esta pergunta, nossos testes do LinkedList seriam os seguintes:
- Duas listas vinculadas que se cruzam no começo / meio / fim
- Ambos / uma lista vinculada é nula (deve retornar nula)
- As listas vinculadas têm o mesmo / tamanho diferente
Foram realizadas!
Mais perguntas:
Interessado em invadir a Ciência da Computação? Ansioso para expandir sua base de conhecimento e aprender coisas novas? Gosta de resolver problemas?
Se então, SWEPrep pode ser o boletim para você. Inscreva-se para obter instruções de entrevista totalmente explicadas, comumente fornecidas em entrevistas de engenharia, de Matrizes a Programação dinâmica. As perguntas saem semanalmente e também são categorizadas por assunto e dificuldade. O post acima é um guest post do autor, Sameer Khoja.
Se inscrever para ter acesso completo ao boletim. Nunca perca uma atualização.