## Amazon Interview Question

Software Developers**Country:**United States

**Interview Type:**Phone Interview

I came up with below answer after modifying the Node class. The complexity is O(n) even though I might have to go through the entire list thrice. Correct me on complexity if I am wrong.

```
public class Node
{
public int Value {get;set;}
public Node Next{get;set;}
public Node Random{get;set;}
public int NodeCountFromHead {get;set;}
}
static Node DeepCopy(Node sourceHead)
{
if(sourceHead == null)
return null;
int index = 1;
sourceHead.NodeCountFromHead = index;
Node sourceCurrent = sourceHead;
Node destHead = new Node {Value = sourceHead.Value, Next = null};
Node destCurrent = destHead;
while(sourceCurrent.Next != null)
{
sourceCurrent.Next.NodeCountFromHead = ++index;
destCurrent.Next = new Node{Value = sourceCurrent.Next.Value, Next = null, Random = null, NodeCountFromHead = index};
sourceCurrent = sourceCurrent.Next;
destCurrent = destCurrent.Next;
}
// second loop to set the Random node values
sourceCurrent = sourceHead;
destCurrent = destHead;
while(sourceCurrent != null)
{
destCurrent.Random = GetNthNode(destHead, sourceCurrent.Random.NodeCountFromHead);
sourceCurrent = sourceCurrent.Next;
destCurrent = destCurrent.Next;
}
return destHead;
}
static Node GetNthNode(Node destHead, int nodeCountFromHead)
{
Node current = destHead;
int index = 1;
while (index != nodeCountFromHead)
{
current = current.Next;
}
return current;
}
```

Here is how we will do this in two moves.

Complexity is O(n) + O(1).

- sonesh April 20, 2017