CareerCup

you could do it with a hashtable.

i think if extra space is acceptable. use hashset.
O(n)

he cannot explain, because he doesnt know either

only even number of times if a number is repeated then xoring will return zero , if it is odd number of times then it wont be zero , using hash table would be fine

Do it with hash table.

public static List<Node> getDupNodes(Node n)
{
HashSet<Node> h = new HashSet<Node>();
while (n.next != null)
{
if ((n.data % 2 != 0) && (h.Contains(n)))
{
//do nothing///
}
else
{
h.Add(n);
}
n = n.next;
}
return h.ToList<Node>();

}

@to the people suggesting for hash table

range is not given how much big table will u take
foe eg list conatains
1 2 3 4 2 5 6 5 7 8 10000 u will need an array of 1000 size

You could ask the interviewer about the range of numbers. If range of numbers are given then you can use a bitmap to record occurrences. Usually if range is small then there is a constant memory space required which is not the case with hash tables. Hence you can have a solution that is technically O(n) in both space and time complexity.

<pre lang="" line="1" title="CodeMonkey6518" class="run-this">package com.DataStructures;

import java.util.HashMap;

public class RemoveDuplicateFromLinkedList {

HashMap<Integer, Character > map=new HashMap<Integer, Character>();

public void removeDuplicates(LinkedListNodeInt current){

LinkedListNodeInt previous=null;
while(current!=null){
if(map.containsKey(current.value)){
if(current.value%2!=0)
previous.link=current.link;
else
previous=current;
}
else{
map.put(current.value,' ');
previous=current;
}
current=current.link;
}
}
public static void main(String args[]){
RemoveDuplicateFromLinkedList obj=new RemoveDuplicateFromLinkedList();
LinkedListNodeInt node=new LinkedListNodeInt();
node.insert(1);
node.insert(2);
node.insert(5);
node.insert(60);
node.insert(3);
node.insert(5);
node.insert(60);
node.insert(5);
obj.removeDuplicates(node.link);
node.traverse();
}
}
</pre><pre title="CodeMonkey6518" input="yes">
</pre>

public LinkedList<Integer> deleteDuplicates(LinkedList<Integer> duplicateList)
{
LinkedList<Integer> nonduplicateList = new LinkedList<Integer>();
HashSet<Integer> distinctList = new HashSet<Integer>();

for(Integer i : duplicateList )
{
if((i%2 == 0))
{
nonduplicateList.add(i);
}
else if(!nonduplicateList.contains(i))
{
distinctList.add(i);
nonduplicateList.add(i);
}
}

return nonduplicateList;
}

public LinkedList<Integer> deleteDuplicates(LinkedList<Integer> duplicateList)
	{
		LinkedList<Integer> nonduplicateList = new LinkedList<Integer>();
		HashSet<Integer>  distinctList = new HashSet<Integer>();
		
		for(Integer i : duplicateList )
		{
			if((i%2 == 0))
			{
				nonduplicateList.add(i);
			}			
			else if(!nonduplicateList.contains(i))
			{
				distinctList.add(i);
				nonduplicateList.add(i);
			}
		}
				
		return nonduplicateList;
	}

use a xor process on all the data