VMWare Inc Interview Question for Interns


Country: India
Interview Type: Phone Interview




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

I was wondering if O(n) algorithm is possible.
Assume the input is a sequence of length "n" with numbers chosen from the set {1,2,3,...,n}.

Let's assume there is an algorithm which goes through f(n) elements of the array and has "S" states. From state Si, we observe the input and based on its value we can go to another state Sj. After "f(n)" observations, we have tried at S^f(n) routes. If at some point we conclude that the remaining sequence is acceptable, then the algorithm terminates.

There is a total of n^n sequences. We must be able to differentiate between any two sequence so S^f(n) >= n^n. if f(n) = O(n), then S = Omega(n) and therefore, log2(S) = Omega(log(n)). If S = O(1), then f(n) = Omega(n log(n)).

I am not sure if my argument is correct, but my conclusion is that we either need O(log(n)) memory, or O(nlog(n)) iterations.

- Ehsan August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Some specification on the range of nos? Otherwise I don' think that it can be done.

- alex August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

yesss..i also don't think its possible with the constraints given

- Amit August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

not possible but wat did u answer and wat was interviewer's comment?

- OTR August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Note: If the value type is integer than we can use following algorithm to remove all duplicates in O(n) complexity.
Algorithm:
============

Node pre = null;
removeDuplicates(LinkedList list){
    Node tmp  = start;
    integer bitarray = 0;
    while(tmp ! = null){
        integer x = 1; // 0000 0001
        integer value = temp.value;
        /***********
           Left shift inter x (1) by number of places equals to value
           If value =4, After below operation x will become 0000 1000
        ***********/
        x = x << num;
        /*****************************
          Bitwise and operation to add above result in a bitarray.
        ********************************/
        if((bitarray & x) != 0){
     	     System.out.println("Duplicate found in given linked list: " + num);
     	     /**************************
     	        It will delete current node with O(1) time complexity and will return next node;
     	        We can't delet last node by using below operation so we need to check it.
     	     *******************************/
     	     if(temp.next == null){
     	          pre.next == null;
     	          return list;
     	     } else {
     	     	 pre = tmp;
     	         list.delete(tmp); 
     	     }
        } else {
     	     bitarray = bitarray | x;
     	     pre = tmp;
     	     tmp = tmp.next();
        }
     }
} 

deleteNode(LinkedList list, Node node){
   /************************************************************************************
     We are copieng values from next node to current node, and will remove next node;
   ************************************************************************************/
   
   Node tmp = node.next;
   node.value = tmp.value; 
   node.next = tmp .next;
   tmp.next == null;
   tmp = null;
}

- Ajeet August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The idea is no different with Avneetsingh114's solution

- Anonymous August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No!!. It is different , we are not using extra space O(n), but we are using O(1) space, simple integer as a bit array ...:)

- Ajeet August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

at first x was 1, and first encountered number was 4.
then x = x << 4;
1 << 4 becomes 16 , which is 0001 0000 ???

- amber August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It does not depends on value of X. It depends on index\place of bit 1 in X. Suppose following numbers are given .. 2, 3 4, 4. So in third iteration it will be something like ...0000011100. So in fourth iteration we can easily check with & operator that 4 is duplicate ...
0 1 = 0
1 0 = 0
1 1 = 1 - Duplicate

- Ajeet August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

All you are doing in your strategy is using a bit array as a type of sparse array to hold the found values in the linked list. This violates the constraint that no extra space be used. What if your integers were large numbers, or negative? Your strategy quickly breaks down.

- bearvarine August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not going to work because as an example the shift of an integer for value of 1 and value of 33 is the same . so it will seem like a duplicate when it is not?

- Rahul February 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done i think, using following approach. Not tried though.

void deleteDuplicate (list *head)
{
	int isListChanged = 0, count = 0;
	list *temp, *temp1, *prev;

	temp = temp1 = NULL;
	do
	{
		count++;
		isListChanged = 0;
		temp = temp1 = head; 
		do
		{
			 for (i=0;i<count;i++)
			{
				temp1 = temp1->next;
			}
			if (temp->data == temp1->data) isListChanged = removeNode(temp1);
			temp = temp->next;
		}while(temp1);
	} while (isListChanged);
}

Basically, Idea is to use two pointers, one is temp which runs only to next every time, and other pointer is temp1 moves to by 2 in first iteration, 3 in second iteration, 4 in fourth and so on, until see some node in list is removed.

- Varun August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This fails. If you take the case of 10 nodes where node 0 and node 9 are the same, the algorithm exits after it compares neighboring nodes and doesn't find a duplicate.

If you fix the algorithm to go through all possible values of count, then you aren't in O(n).

- bh September 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

If all the values are integer then its possible to do it in O(n) time without using extra space.
Steps:
- Declare a variable say test.
- Start traversing the linked list and do a XOR of 'test' with the value in that node.
- If the result is '0' that means 'test' has been XOR'd with the same value before, so just delete that node(which is gonna take O(1) time), and retain the original value of the test.
- Else update the value of 'test' with the new XOR'd value and retain the node.
- Go to the next node in the linked list and repeat the above steps till the end of the list.

In the end we are left with the linked list with non-repeated elements.

I hope thats helpful.

- Prabhjeet August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice approach. But won't the time complexity be O(n2) since there will be two loops, one for each element and the other for taking xor of all the other elements? Please correct me if I am mistaken.

- alex August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Alex.
There will be only one loop traversing the list. While traversing the list, I am updating the value of variable 'test' (depending on the conditions mentioned) and using the same value as the current value for the next traversed nodes.

So I am traversing the entire list only once, which makes it O(n).

- Prabhjeet August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This works only if the list is sorted? The problem says unsorted list

- Srinivasa August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

suppose 5 4 5 elements ,
at first xor give - 101 then 001(101 ^ 100) and 100(001 ^ 101) dis is not zero ?
xor will only delete duplicates

- Avneetsingh114 August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, 5xor4xor5 doesn't give 0.

- alex August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

3 XOR 2 XOR 1 = 0.

- Ehsan August 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question has some ambiguity so the problem solver will have to clarify at least one fact.

The ambiguity is whether the idea of "repeated elements" means repeated adjacent to each other, or repeated anywhere in the list. The former case is solvable in O(n) but the latter case is essentially a sorting problem (due to the fact that building a hashtable or map is not allowed) so it probably can't be solved in less than O(n*log(n)).

The most straightforward solution is to simply use a nested loop, the outer loop pointing at each value in the linked list; and the inner loop pointing to each remaining value in the list. If a duplicate is found, you have to remove the duplicate node, which requires careful work with pointers. The downside is that complexity is O(n^2). The following C++ code ran successfully on VS2012.

#include <iostream>   // cout
#include <Windows.h>  // Sleep ()

using namespace std;

struct node 
{
    int val;
    node * next;

    node (int new_val) : val (new_val), next (nullptr)
    {
    }

    ~node ()
    {
        if (next)  delete next;
    }

    void removeNext ()
    {
        if (next)
        {
            if (next->next)
            {
                node * n = next;

                next = next->next;

                n->next = nullptr;

                delete n;
            }
            else
            {
                delete next;

                next = nullptr;
            }
        }
    }

    void printList ()
    {
        int i = 0;

        node * n = this;

        while (n)
        {
            cout << i << ": " << n->val << endl;

            n = n->next;

            i++;
        }
    }
};


void removeDups (node * root)
{
    node * c = root;

    while (c)
    {
        node * x = c;

        while (x)
        {
            if (x->next  &&  c->val == x->next->val)
            {
                x->removeNext ();
            }
            else
            {
                x = x->next;
            }
        }

        c = c->next;
    }
}


void main (int argc, char ** argv)
{
    node * root;

    node * cur_node;

    root = cur_node = new node (2);

    cur_node->next = new node (4);

    cur_node = cur_node->next;
    cur_node->next = new node (6);

    cur_node = cur_node->next;
    cur_node->next = new node (4);

    cur_node = cur_node->next;
    cur_node->next = new node (2);

    cur_node = cur_node->next;
    cur_node->next = new node (2);


    cout << "Original singly linked list:" << endl;

    root->printList ();

    removeDups (root);

    cout << "After dups are removed:" << endl;

    root ->printList ();

    Sleep (30000);
}

- bearvarine August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm not sure but this is what I came up with. Since you can't use any extra space, you use the space given to you. How? You divide the list into processed parts and non-processed part. The processed part is from head to tail, this sub-list is where we linearly maintain uniqueness. The non process part is from tail to end of the list.

You start with tail at the beginning of the list. As you go through each node, you check if the node is already in the sub list [head, tail], if not increase the tail since the node is unique and that it includes the current node in this processed list that we are maintaining to be unique. If it is already in there, we delete the current node and check the next one. Notice how we aren't incrementing tail because the current node was a duplicate and we only want unique nodes in the sub list of [head,tail].

The time complexity is O(n). Space is O(1). Can anyone confirm if I did this right? Thoughts?

// Search if the object is already in the list of unique characters that's been searched
boolean isUniqueSearchSubList(Node head, node tail, Node obj){
	Node current = head;
	while ( current != tail.next ){
		if ( current == obj ) // we found a duplicate!
			return false;
		current = current.next
	}
	return true;
}

void removeDuplicate(){

	if ( head == null || head.next == null ) return; // check empty and 1 element list
	
	Node prev = head;
	Node current = head.next;
	Node tail = head; // the end of the list of unique characters we gone through

	while ( current != null ) {

		// check if the current node is already in the list of unique objects ( head to tail )
		if ( isUniqueSearchSubList( head, tail, current ) == true ){ 
			tail = tail.next; // unique so include it in the list by incrementing tail
			current = current.next 
		}else{
			// delete the current one
			prev.next = current.next;
			current = current.next;
		}
	}
}

- kier August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will not be O(n) becuase initially sublist's size is 1 then 2 and increases linearly. Everytime we traverse through sublist. So It would be 1+2+3+4+....+n = n*(n+1)/2. So It would be O(n2) according to me.

- kaushalv27 August 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I found another error in this code:
The line "if ( current == obj )" is not correct. You are comparing node address not the value. BTW you did great job. This code will work for all datatypes. All you need is to use templates.
The corrected code and results are attached:


// Search if the object is already in the list of unique characters that's been searched
bool LinkedList::isUniqueSearchSubList(Node *tail, Node *obj)
{
Node *current = head;
while ( current != tail->next )
{
// if ( current == obj ) // we found a duplicate!
// you are comparing nodes not the actual value, the code
// should be changed to
if ( current->data == obj->data ) // we found a duplicate!
return false;
current = current->next;
}
return true;
}

void LinkedList::RemoveDuplicate()
{

if ( head == NULL || head->next == NULL ) return; // check empty and 1 element list

Node *prev = head;
Node *current = head->next;
Node *tail = head; // the end of the list of unique characters we gone through

while ( current != NULL ) {

// check if the current node is already in the list of unique objects ( head to tail )
if ( isUniqueSearchSubList(tail, current ) == true )
{
tail = tail->next; // unique so include it in the list by incrementing tail
prev = current; // added this line
current = current->next;
} else {
// delete the current one
prev->next = current->next;
current = current->next;
}
}
}

Result:
Before: 1 3 7 5 8 8 8 2 3 4 5 5 6 7 7 7 9 8 9 3 2 10 1
After: 1 3 7 5 8 2 4 6 9 10

- azizahmad45 September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// you are missing line prev = current;
if ( isUniqueSearchSubList( head, tail, current ) == true ){
tail = tail.next; // unique so include it in the list by incrementing tail
prev = current; // it will work if you add this line
current = current.next ;
.........

- azizahmad45 September 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@azizahmad45
Just wanted to check if prev pointer is required??? I think tail pointer is enough and prev can be avoided without affecting the result. In the else part we can do:
tail.next = current.next;
current = current->next;

- Rakesh Roy October 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

simplest possible code and approach:


while(current !=NULL)

{
prev = current;
head = current->next;

while(head != NUll)
{
if(current->info != head->info)
{head=head->next;}
else
prev->next = head->next
free(head)
head= prev->next;
}

current = current->next;
}

- ajay September 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ajay, did you read the problem statement? Your code does not address the problem of removing duplicate values in a singly-linked list in O(n) time complexity without using any additional space. Most significantly your code is O(n^2) not O(n).

- Michael September 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's one approach which although not generic, but can accurately delete repetitive nodes with time complexity O(n) in a single linked list having maximum 4k nodes (4096 nodes.)

void deleteRepeatingNodes(node_t * head)
{
    long int row = 0, col = 0;
    char rshift = 0, cshift = 0;
    node_t *prev = NULL;

    if (head == NULL)
        return head;

    while (head) {
        rshift = (head->data / 65) ? (head->data/64 - 1): 0;
        cshift = (head->data % 65) ? (head->data%64 - 1): 0;

        if (row & (1<<rshift) && col & (1<<cshift)) {
            prev->next = head->next;
            free(head);
            head = prev->next;
        } else {
            row |= 1<<rshift;
            col |= 1<<cshift;

            prev = head;
            head = head->next;
        }
    }

    return;
}

- Akshay Mishra November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please explain this.

- SJ November 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please explain this ?

- Anil January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

One correction in above:

rshift = (head->data / 65) ? (head->data/65 - 1): 0;
cshift = (head->data % 65) ? (head->data%65 - 1): 0;

- Akshay Mishra November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can store the value we got from node in array by its value as array index keep the value of that index to some negative value and whenever we go to the next node we will keeps its value as array index and check whether it is positive or not if it isn't we will delete that node

- vinodh December 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Akshay is right in principle. however, the limit is not on number of nodes. it is rather on data. idea is to set bit flag for already seen values. the maximum we can do in C++ with this scheme is 64bit X 64bit (2d matrix)(unsigned long long) which is 4096. here is how I did it:

void LinkedList::RemoveDuplicates()
{
	class IntMap
	{
	private:
		unsigned long long m_Rows;
		unsigned long long m_Cols;
	public:
		IntMap()
		{
			this->m_Rows = 0;
			this->m_Cols = 0;
		}
		bool Contains(int data)
		{
			int quotient = (int)floor(data / 63.0F);
			int remainder = data % 63;
			unsigned long long rowMask = 1 << quotient;
			unsigned long long colMask = 1 << remainder;

			return (this->m_Rows & rowMask) == rowMask &&
				   (this->m_Cols & colMask) == colMask;
		}

		void Set(int data)
		{
			int quotient = (int)floor(data / 63.0F);
			int remainder = data % 63;
			unsigned long long rowMask = 1 << quotient;
			unsigned long long colMask = 1 << remainder;

			this->m_Rows |= rowMask;
			this->m_Cols |= colMask;
		}
	} intMap;

	Node* current = this->m_Start;
	Node* previous = NULL;
	while(NULL != current)
	{
		if(!intMap.Contains(current->m_Data))
		{
			intMap.Set(current->m_Data);
			previous = current;
			current = current->m_Next;
		}
		else
		{
			current = this->DeleteNode(current, previous);
		}
	}
}
LinkedList::Node* LinkedList::DeleteNode(LinkedList::Node* node, LinkedList::Node* previous)
{
	if(NULL == node)
	{
		return NULL;
	}

	if(this->m_Start == node)
	{
		this->m_Start = node->m_Next;
	}
	else if(NULL != previous)
	{
		previous->m_Next = node->m_Next;
	}

	Node* next = node->m_Next;
	--this->m_Count;
	delete node;

	return next;
}

Please note that we can extend the data limit by adding another dimension, e.g. 64x64x64. so, the data limit would be extended to 262144 and you can then add another dimension if needed.

- asim.ghaznawi February 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<Integer> findDuplicatesLinkedList(LinkedList<Integer> sequence){
	//	List<Integer> result = new ArrayList<Integer>();
		int bitarray = 0;
		Iterator<Integer> iterator = sequence.iterator();
		
		while(iterator.hasNext()){
			Integer num = iterator.next();
			int x = 1;
			x = x << num;
			
			if((bitarray & x) != 0){
				System.out.println("Duplicate found in given linked list: " + num);
				iterator.remove();
			} else {
				bitarray = bitarray | x;
			}
		}
		System.out.println(sequence);
		return null;

}

- Anonymous March 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solved in O(n) with memory O(1). Solved using a bit vector i.e set the bit position of int value to 1. However only work for Integers i.e values from 0-31.

public void removeDuplicates(MyNode<Integer> current)
	{
		if(current == null)
		{
			return;
		}
		
		MyNode<Integer> temp = current;
		int buffer = 0;
		int offset = 1; 
		
		buffer = buffer | offset<<temp.data;
		
		while(temp.next != null)
		{			
			if( buffer>>temp.next.data == 1)
			{
				MyNode<Integer> temp1 = temp.next;
				temp.next = temp.next.next;
				temp1.next = null;				
				continue;
			}
			else{
				buffer = buffer | offset<<temp.next.data;
			}
			
			temp = temp.next;
		}

}

- Anonymous May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solved in O(n) with memory O(1). Solved using a bit vector i.e set the bit position of int value to 1. However only work for Integers i.e values from 0-31.

public void removeDuplicates(MyNode<Integer> current)
	{
		if(current == null)
		{
			return;
		}
		
		MyNode<Integer> temp = current;
		int buffer = 0;
		int offset = 1; 
		
		buffer = buffer | offset<<temp.data;
		
		while(temp.next != null)
		{			
			if( buffer>>temp.next.data == 1)
			{
				MyNode<Integer> temp1 = temp.next;
				temp.next = temp.next.next;
				temp1.next = null;				
				continue;
			}
			else{
				buffer = buffer | offset<<temp.next.data;
			}
			
			temp = temp.next;
		}

}

- obaidsalikeen May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is O(n). I am traversing the list only once and no extra space. But the problem is this code works for numbers less than 32. With a little sensible modifications it can be made to work for the greater numbers. I might be wrong about O(n) but for sure traversing it only once. Positive and worthwile suggestions are welcome :)

// Program to remove the duplicate elements from the linked list //

#include<stdio.h>
#include<stdlib.h>

struct node{
int no;
struct node* next;
};

typedef struct node* Nodep;

Nodep makeLinkedList(int);
void printList(Nodep);

int main(){
int i,num,t=0;
printf("How many nodes you want in the linked list??\n");
scanf("%d",&num);
Nodep head = makeLinkedList(num);
Nodep temp = head;
Nodep p = head->next;
t = t|1<<(head->no-1);
while(p!=NULL){
if(t&1<<(p->no-1)){
p = p->next;
if(p == NULL){
temp->next = NULL;
break;
}
}
else if(temp->next == p){
temp = temp->next;
t = t | 1<<(p->no-1);
p = p->next;
}
else{
temp->next = p;
t = t | 1<<(p->no-1);
if(p->next == NULL){
temp->next = p;
}
temp = p;
p = p->next;
}
}
printf("\nThe linked list after removing duplicate nodes is:\n");
printList(head);
return 0;
}

Nodep makeLinkedList(int n){
int exec = 1,i;
Nodep start,p;
printf("Enter the numbers:\n");
for(i = 0;i<n;++i){
if(exec){
p = (Nodep)malloc(sizeof(struct node));
start = p;
p->next = NULL;
scanf("%d",&p->no);
exec = 0;
}
else{

Nodep q = (Nodep)malloc(sizeof(struct node));
q->next = NULL;
scanf("%d",&q->no);
p->next = q;
p = p->next;
}
}
return start;
}

void printList(Nodep head){
while(head->next!=NULL){
printf("%d ",head->no);
head = head->next;
}
printf("%d",head->no);
}

- swpnl.borse June 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Node removeDuplicatesFromUnsortedLinkedListWithoutExtraSpace(Node head){
		if(head == null || head.next == null)
			return head;

		Node prev = head;
		Node curr = head.next;
		Node temp = prev;

		while(prev.next!=null){
			if(curr != null){
				if(prev.data == curr.data){
					temp.next = curr.next;
					curr = curr.next;
				}else {
					temp = curr;
					curr = curr.next;
				}
			}else{
				prev = prev.next;
				curr = prev.next;
				temp = prev;
			}
		}
		return head;
	}

- Setu August 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Keep 3 pointers ( head, first,temp and last ) pointing to the head , last node and temporary first node.
2. Initialize temp to head and first to head
3. Initialize last->next = temp
4. Run from temp to last deleting all nodes that have the same value as the temp node. Once temp = last, move first forward and set temp to first.
5. Move temp node forward.
6. Readjust the last node to point to the temp node.
7. Repeat from step 4 till first is equal to last.

I think this should achieve required deletion in amortized O(n) . Please feel free to poke holes in this algo..

- Saurabh August 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Saurabh,
I did not understand your algorithm .could you please explain it in more detailed way.Thanks

- sschaitanya0709 February 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

taking array and initialize every element to unvisited , while traveling when no. is unvisited we mark that index (taking no. as index) visited , and when we found visited then delete that node .

- Avneetsingh114 August 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but this is linked list..right?

- OTR August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can we not take hash value of each element as index of array ?

- Avneetsingh114 August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hash table or even an array,,would be considered extra space!!

- chauhanshiksha1 August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Take a dictionary, the keys in the dictionary will be the values in the linked list.
Start traversing the linked list, add the value of the node as key in dictionary and value of dictionary will be one. Now whenever a second element is added in the list first the list value is compared with the keys, if that key exists, the value value corresponding to that key is incremented by 1 in the dictionary and we can now delete that particular node from the list, else if the key does not exist we can go on add the key in dictionary.

eg: - List elemets - 1, 4, 6, 9, 1
1 -> so add in dictionary with key as 1 and value as one.
go forward in the list and pick up the nest element now. next element is 4. so search the keys in dictionary to find whether 4 exists in dictionary if not add it
4 -> so add in dictionary with key as 4 and value as one.
6 -> so add in dictionary with key as 6 and value as one.
9 -> so add in dictionary with key as 9 and value as one.
1-> key exist , increment value by 1 delet the node.

- Shivangi Wahie September 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

What if we apply multithreading

- Nilotpal September 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

c#

//Removing duplicates from the list
public void RemoveDuplicate()
{
Dictionary<T, int> theDictionary = new Dictionary<T, int>();
Node<T> cur = head;

theDictionary.Add(head.Data, 1);
while (cur.Next != null)
{
if (!theDictionary.ContainsKey(cur.Next.Data))
{
theDictionary.Add(cur.Next.Data, 1);
cur = cur.Next;
}
else
{
cur.Next = cur.Next.Next;
}
}
}

- Andrey K. April 11, 2014 | 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