Microsoft Interview Question Software Engineer / Developers
Team: Cloud
Country: United States
Interview Type: In-Person
If extra memory is allowed then the hash table will work
1. Create a copy of an original list setting up only prev and next pointers
2. While doing #1 create a map keyed on nodes in original list and valued on corresponding nodes in cloned list
3. Iterate through both lists at the same time and set:
NodeInClonedList.random = map[NodeInOriginalList.random]
Without extra memory you have to modify the original list so the "prev" pointer would point to a cloned node.
My understanding is that you need to create exact copy of initial list - so at the end you'll have 2 separate lists - given and its copy. I used hash table which as key stores node from the initial list and as a value - corresponding node from the copy list. C# solution:
class DoubleLinkListNode<T>
{
public DoubleLinkListNode<T> Next { get; set; }
public DoubleLinkListNode<T> Prev { get; set; }
public DoubleLinkListNode<T> Random { get; set; }
public T Data { get; set; }
public DoubleLinkListNode(T data)
{
Next = Prev = Random = null;
Data = data;
}
public DoubleLinkListNode(T data, DoubleLinkListNode<T> randomNode)
{
Next = Prev = null;
Random = randomNode;
Data = data;
}
}
class DoubleLinkList<T>
{
public DoubleLinkListNode<T> Head { get; set; }
public DoubleLinkListNode<T> Tail { get; set; }
public DoubleLinkList()
{
Head = Tail = null;
}
public void AddItem(T data, DoubleLinkListNode<T> randomNode)
{
DoubleLinkListNode<T> newNode = new DoubleLinkListNode<T>(data, randomNode);
if (Tail == null)
{
Head = Tail = newNode;
}
else
{
Tail.Next = newNode;
newNode.Prev = Tail;
Tail = newNode;
}
}
public DoubleLinkList<T> Copy()
{
DoubleLinkList<T> listCopy = null;
Hashtable hashTable = null;
DoubleLinkListNode<T> current = null;
DoubleLinkListNode<T> listCopyNode = null;
if (Head != null)
{
hashTable = new Hashtable();
listCopy = new DoubleLinkList<T>();
current = Head;
while (current != null)
{
if (hashTable.Contains(current) == false)
{
listCopy.AddItem(current.Data, null);
hashTable.Add(current, listCopy.Tail);
}
else
{
listCopyNode = (DoubleLinkListNode<T>)hashTable[current];
listCopy.Tail.Next = listCopyNode;
listCopyNode.Prev = listCopy.Tail;
listCopy.Tail = listCopy.Tail.Next;
}
if (current.Random != null)
{
if (hashTable.Contains(current.Random) == false)
{
listCopyNode = new DoubleLinkListNode<T>(current.Random.Data);
hashTable.Add(current.Random, listCopyNode);
}
else
{
listCopyNode = (DoubleLinkListNode<T>)hashTable[current.Random];
}
listCopy.Tail.Random = listCopyNode;
}
current = current.Next;
}
}
return listCopy;
}
public void PrintListForward()
{
DoubleLinkListNode<T> current = null;
if (Head != null)
{
current = Head;
while (current != null)
{
Console.WriteLine("Node data: {0}, random node data: {1}",
current.Data,
(current.Random == null) ? "null" : current.Random.Data.ToString());
current = current.Next;
}
}
}
public void PrintListBackward()
{
DoubleLinkListNode<T> current = null;
if (Tail != null)
{
current = Tail;
while (current != null)
{
Console.WriteLine("Node data: {0}, random node data: {1}",
current.Data,
(current.Random == null) ? "null" : current.Random.Data.ToString());
current = current.Prev;
}
}
}
}
There is a neat trick to do this in constant space without modifying the input linked list.
It will require two passes however.
Pass 1:
-Create copy of each node. Set previous & next correctly in the new node
-To keep track of new node reference, use random reference of original node. However before you overwrite random reference of the original node, preserve it in the random reference of the new node, i.e.:
Node newNode = new Node(oldNode.value);
newNode.previous = last; last.next = newNode;
newNode.random = oldNode.random; //Preserving old node's random reference in the newly created node's random pointer
oldNode.random = newNode; //Keeping the new reference in the random reference of old Node
last = newNode;
Pass 2:
-Iterate over both lists together.
-For each node, restore the random reference in the original list. However before overwriting that, use the random reference of the newNode to retrieve corresponding random reference for the new node. i.e.:
Node oldRandom = newNode.random;
newNode.random = oldRandom.random; //oldRandom's random reference is pointing to the corresponding new node
oldNode.random = oldRandom; //restore the random reference of the old node so that input list is not modified
a solution in C++
typedef struct node {
node* next;
node* prev;
node* rand;
}
void copyLinkedList (node* src , node* dst) {
node* currS = src;
node* currD = dst;
node* prevD = NULL;
while (currS) {
currD = new node;
currD->prev = prevD;
currD->rand = currS->rand;
currS->prev = currD;
if (prevD) {
prevD->next = currD;
}
prevD = currD;
currS = currS->next;
}
//change rand pointer in dst
currD = dst;
while(currD) {
currD->rand = currD->rand->prev;
}
//return prev pointer in src
currS = src;
prevD = NULL;
while (currS) {
currS->prev = prevD;
prevD = currS;
currS = currS->next;
}
}
Node* clone(Node* head)
{
if(head == NULL)
return NULL;
Node* temp =head;
Node* sectemp = head;
Node* clonehead = NULL;
bool first =false;
while(head)
{
Node* clone = new Node();
if(head->prev == NULL) //it means the first node
{
clone->prev =NULL;
head->prev = clone; //change original->prv to the current clone node (basically, we assign a clone node for the current node, instead of using a hashtable)
}
else
{
//until now head->prev is still pointing to its previous node but after setting clone->prev we need to change it.head->prev->prev points to the previous node in cloned list
clone->prev = head->prev->prev;
clone->prev->next = clone;
head->prev = clone;
}
//to keep the head of the cloned list for second pass
if(!first)
{
clonehead = clone;
first = true;
}
head = head->next;
}
Node* res = clonehead;
//set the cloned list random pointer
while(clonehead)
{
clonehead->random = temp->random->prev;
clonehead = clonehead->next;
temp=temp->next;
}
//now fix the original list's prev pointer
first =false;
Node* lastnode =NULL;
while(sectemp)
{
if(!first)
{
sectemp->prev= NULL;
first =true;
lastnode = sectemp;
}
else
{
sectemp->prev = lastnode;
lastnode=sectemp;
}
sectemp =sectemp->next;
}
return res;
}
What do you think about that?
Node * clone, * prev;
if (head -> prev == null) {
clone = new Node();
clone -> prev = Null;
prev = clone;
head = head ->next;
}
While (head != Null) {
Node * clone = new Node();
clone -> prev = prev;
prev->next = clone;
prev = clone;
head = head-> next;
}
prev -> next = Null;
Here is the algorithm for this
We need to do two pass to the list, in one pass, we will create the new list, set its next and previous pointers, in the next run, we will set the random pointers
CloneList(List P)
List N = New Empty List;
// Node1 and Node2 are there is keep track of first node of each list.
Node1 = P.FirstNode;
Node2 = N.FirstNode; // this will be null
// This while loop will copy the old list to new list
While Node1 is not null
Create a new Node Node_New;
if Node2 is null then
Node2 = Node_New;Node2.Previous is Null;Node2.Next is null;
else
Node_New.Previous = Node2;
Node_New.Next is null
Node2.Next = New_New;
Node2 = Node_New;
Node2.Random = Node1.Random;
Node1.Random = Node2;
Node1 = Node1.Next;
Node1 = P.FirstNode;
Node2 = N.FirstNode;
// This while loop will set the random node to its correct value
While Node1 is not null
Node2.Random = Node2.Random.Random
Return List N;
Complexity
Time : O(N)
Space O(N) : Need to store the new list
A Solution in Objective C:
PS:
Node/DLL Structure: ...Node <- prev.(Node).next -> Node...
- (Node *)copyDLL:(Node *)p {
if (!p) {
return nil;
}
Node *clone = new Node;
clone.val = p.val;
clone.next = [self copyDLLNext:p.next];
if (clone.next) {
clone.next.prev = clone;
}
clone.prev = [self copyDLLPrev:p.prev];
if (clone.prev) {
clone.prev.next = clone;
}
return clone;
}
- (Node *)copyDLLNext:(Node *)p {
if (!p) {
return nil;
}
Node *clone = new Node;
clone.val = p.val;
clone.next = [self copyDLLNext:p.next];
if (clone.next) {
clone.next.prev = clone;
}
return clone;
}
- (Node *)copyDLLPrev:(Node *)p {
if (!p) {
return nil;
}
Node *clone = new Node;
clone.val = p.val;
clone.prev = [self copyDLLPrev:p.prev];
if (clone.prev) {
clone.prev.next = clone;
}
return clone;
}
To add the random requirement each time you create a copy node, add it to a hashmap.
- the one September 12, 2014After the copy ends start from the root of the copy, and assign each node a random node from the hashmap.