VMWare Inc Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
6
of 6 vote

Wikipedia gives the answer for xor linked list:

http://en.wikipedia.org/wiki/XOR_linked_list

- Erik April 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Erik. Appreciate your help.

- sk_seeker April 20, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's Fantastic !

- Anonymous May 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent !!!

- Anonymous June 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

instead 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.

- Nikhil April 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain how XOR helps here?? If I were to guess, I would say that somehow you can extract both the current and prev pointer from the XOR'ed value. But, how?? Please clarify. Thanks in advance.

- sk_seeker April 20, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Biker April 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sk_seeker April 20, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are you assuming the list is circular ?

- acoader April 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Implement using hash table.

Traverse the linked list and make hash map of pointer to node to its previous pointer.

- Erik April 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- sk_seeker April 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use the 'data' field in linked list to store the address of previous node.

- Erik April 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can also be done using a Stack. Fill all the elements in a linked list into a Stack. nth element from the last of the linked list can be accessed by reading nth element from the top of the stack.

Any comments?

- Nick April 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we cant use any other form of data structure than one mentioned in question.
>>struct node { int data, struct node *ptr}.

- Erik April 21, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pranav this interview was for fulltime position or intern position

- CUNOMARD May 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess the XOR solution works.
or as Erik said we can always encode the address of the previous node along with the content of the node.

- anand June 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As mentioned by Erik, the sol. is mentioned in wikipedia using XOR. http://en.wikipedia.org/wiki/XOR_linked_list

@CUNOMARD, This was for internship at VMWARE

- Pranav October 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I could not understand. Can anyone explain step by step? Erik?

- particularraj November 02, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ddd

- ddd November 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);


}

- Hurray! November 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Calista December 29, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Helper April 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void* single2double (node *head)
{
node *temp = head;
while(temp->next)
{
temp->next->prev = temp;
temp = temp->next;
}
}

- Jash November 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Jash November 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

From where did you get "prev" link? In structure only data and "next" links are provided.

- anshuman.ssi January 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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! :/

- Anonymous July 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As per the question, I have to create a new doubly link list, whose node->data are same as mentioned single link list.

Am I right?

- stranger November 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");

}

- Anubhav June 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Kartik Agarwal September 08, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More