Microsoft Interview Question Software Engineer / Developers
Team: Bing
Country: India
Interview Type: In-Person
Question not clear, if linked list is singly linked nothing can be done. If it is doubly linked ... cannot think beyond please provide a sample.
Here is a pseudo code
List* cloneList(List *p)
{
List cloneHead();
List* clonePtr = &cloneHead;
HashTable hTable();
char *curp = NULL;
//copy the next pointers and add the original list node address as key in hash table and clone node address as value in list
for(curp = p; curp != NULL; curp = curp->next)
{
clonePtr->next = copyNode(curp);
hTable.insert((long)curp, (long)clonePtr->next);
clonePtr = clonePtr->next;
}
clonePtr->next = NULL;
// set the random pointers for the clone list
for(clonePtr = cloneHead.next, curp = p; curp != NULL; curp = curp = curp->next)
{
List *node = hTable.search((long)curp->rand_ptr);
clonePtr->rand_ptr = node;
clonePtr = clonePtr->next;
}
return cloneHead.next;
}
List* copyNode(List *p)
{
List *node = new List();
node->data = p->data;
node->next = p->next;
node->rand_ptr= NULL;
return node;
}
There is a way by which it can be done even with randomised pointer locations, but the original list will be destroyed...
First we make a new list where next node points correctly and the random pointer points to the corresponding rand node of the original list.
That is:-
ptr_new->rand=ptr->rand
In the next step we traverse both lists simultaneously and realign the random pointers in the original list to their new list nodes.
That is:-
ptr->rand=ptr_new
In the third step we do a similar simultaneous traversal and assign the random pointer as
new_ptr->rand = new_ptr->rand->rand
The problem with this method as i said before is that the original list is destroyed...
class Node {
public:
int key;
Node* next;
Node* rand;
};
class List {
public:
Node* head;
List() {
head = NULL;
}
Node* newNode(Node* node) {
Node* newNode = new Node();
newNode->key = node->key;
newNode->rand = node->rand;
node->next = newNode;
return newNode;
}
List clone() {
Node *iter = head, *curr = NULL, *tail = NULL, *temp;
List clone;
while (iter != NULL) {
curr = iter;
iter = iter->next;
temp = newNode(curr);
if (list.head == NULL) {
tail = clone.head = temp;
} else {
tail->next = temp;
tail = temp;
}
1. clone the list without considering random pointers. For each node, add an entry
- Anonymous December 06, 2011to a hashmap: old_addr -> clone_addr
2. use the hashmap to set up the random pointers