Deep copy of a linked list, with an extra pointer to a random node.

Question

Anónimo · Accepted Answer

The solution is not straightforward. 
1. Insert a copy node between the original node and the next node of the original one. For example,
original linkedlist is 1->2->3. After inserted nodes, it looks like 1->1->2->2->3->3.
2. Iterate through the linkedlist. For every copy node, we deep copy the next pointer and random pointer based on the original one. 
The time complexity is O(N) where N is the length of the linkedlist.

Anónimo · Answer

Why can't you just walk through the linked list, and at each node, create a new node with the same item and append it to the duped list? 

Also, could you clarify what you mean by "with an extra pointer to a   random node". What exactly is the question asking?

Anónimo · Answer

There's quite an extended back and forth in actual interviews for questions like this, so nothing quite like real practice.


The Prepfully Addepar  Software Engineer Intern experts have actually worked in this role, so they're able to do an honest-to-God accurate mock, which really puts you through the paces.


prepfully.com/practice-interviews

Addepar

Pregunta de entrevista de Addepar

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo