VMWare Inc Interview Question
Software Engineer / Developersinstead of storing address of next node in ptr, we can XOR addresses of previous node and next node and store in ptr. Also two pointers will be required to store 1st and last node of the list. First node will contain address of 2nd node and last node will point out to 2nd last node.
We can create a function which can give the pointer to the previous node.Lets suppose there is function lastpointer() which will iterate the whole linked list till the desired position and will return the pointer previous to the desired location.
Any comments?
Are you thinking of using lastpointer() for each traversal in the opposite direction?? This may be an expensive solution in terms of cpu cost.
If you had more memory available, maybe you could remember the path on each lastpointer() invocation to avoid some cpu cost. But, there are other ways to remember things as has been proposed by others in this thread.
The idea I was thinking maybe a rule breakage, but....
I was thinking about allocating [sizeof(node) + size of a pointer] for each node in the list. The list pointer can continue to point to a struct *node, but the hidden pointer will contain a pointer to the previous node. Every insert and delete will now have to manipulate the hidden pointer.
The Crux is to use same node structure to create a doubly link list with single pointer..
We can make use of
doublyNode->ptr = (node *) malloc(sizeof(node) * 2);
doublyNode->ptr[0] = prevNode;
doublyNode->ptr[1] = nextNode;
CreateDoublyList(node *singleListNode, node **doublylistHead) {
if(singleListNode == NULL) {
*doublylistHead = NULL;
return;
}
node *doublyNode;
node *singlePrev = NULL;
int first = 1;
//Handling first node
tempNode = singleListNode->ptr;
doublyNode = singleListNode;
doubly->ptr = (node *) malloc(sizeof(node) * 2);
doublyNode->ptr[0] = singlePrev;
doublyNode->ptr [1] = tempNode;
singlePrev = doublyNode;
*doublylistHead = doublyNode;
while(doublyNode->ptr[1]) {
tempNode = doublyNode->ptr[1]->ptr;
doublyNode = doublyNode->ptr[1];
doublyNode->ptr = (node *) malloc(sizeof(node) * 2);
doublyNode->ptr[0] = singlePrev;
doublyNode->ptr[1] = tempNode;
singlePrev = doublyNode;
}
(*doublylistHead)->ptr[0] = doublyNode;
doublyNode->ptr[1] = (*doublylistHead);
}
You are using two pointers. Your solution doesn't answer the question. You have to store XOR of the prev node and the next node pointers and store it in the current node pointer (as addressed above by many others).
For e.g. let's say the nodes are the following:
Node1: data : 1 with address = 0x0001
Node2: data : 2 with address = 0x0101
Node3: data : 3 with address = 0x1000
Now your "single linked list" looks as follows:
(1, 0x0101) (2, 0x1001) (3, 0x1000)
Now if you have the head pointer i.e. 0x0001 you can access the next node with [prev XOR 0x0101] which is 0x0101 since prev is 0x0000. Then you are at node 2. Now to access the next node: prev now is 0x0001 XOR with node 2 0x1001 you get 0x1000 node 3. And the next one gives NULL you end your traversal.
An important XOR property:
If A ^ B = X, then,
X ^ A = B and
X ^ B = A
This is how we can encode both the current address and the next address as the data of the next node. We can XOR both the addresses as the data of the next node. To traverse back, we just need to extract the previous address of every node from the XOR'ed data using the above XOR property. This is O(n) with no extra space. But, we are changing the data in every node. This method can't be applied if we cannot tamper the node's data.
Actually, it's probably a good idea to sanitize your inputs:
void* single2double (node *head)
{
if(!head)
return;
node *temp = head;
while(temp->next)
{
temp->next->prev = temp;
temp = temp->next;
}
}
From where did you get "prev" link? In structure only data and "next" links are provided.
asshole! its a singly linked list! and you don't have the luxury to change the basic structure of it!
read the question carefully before bull shitting! :/
Here is the code:
# include<iostream>
using namespace std;
struct node
{
int data;
node *next;
};
void printFwd_dkXOR(node *head)
{
node *current=NULL;
node *back=NULL;
while(head!=NULL)
{
current=head;
cout<<head->data<<endl;
head=(node *)((int)(head->next)^(int)back);
back=current;
}
}
void printBacwd_dkXOR(node *tail)
{
node *current=NULL;
node *back=NULL;
while(tail!=NULL)
{
current=tail;
cout<<tail->data<<endl;
tail=(node *)((int)(tail->next)^(int)back);
back=current;
}
}
void push(node *(&head),int data)//using call by reference directly
{
node *new1=new node;
new1->data=data;
new1->next=head;
head=new1;
}
void insert_dkXOR(node *&head,node *&tail)
{
node *back=NULL;
for(int i=1;i<10;i++)
{
if(head==NULL)
{
push(head,i);
tail=head;
tail->next=NULL;
}
else
{
node *new1=new node;
new1->data=i;
new1->next=tail;
tail->next=(node *)((int)back^(int)new1);
back=tail;
//cout<<tail<<"tail->next: "<<tail->next<<endl;
tail=new1;
}
}
}
int main()
{
node *head=NULL;
node *tail=NULL;
insert_dkXOR(head,tail);
printFwd_dkXOR(head);
printBacwd_dkXOR(tail);
system("pause");
}
Note: you cannot implement XOR linked list with java because unreferenced nodes will be garbage collected!
The solution can be to use an array of type Node to keep a reference to each node to avoid garbage collected from picking them up.
But this would take a lot of extra space.
So implementation goes to C/C++ and other languages.
Wikipedia gives the answer for xor linked list:
- Erik April 20, 2009http://en.wikipedia.org/wiki/XOR_linked_list