CareerCup

public class DuplicatesRemover<T> {
	
	public int remove(List<T> list) {
		if (list == null || list.size() < 2) {
			return list.size(); // nothing to do
		}
		
		Map<T, Boolean> map = new HashMap<>();
		for (T t : list) {
			if (map.get(t) == null) {
				map.put(t, true);
			}
		}
		
		list.clear();
		list.addAll(map.keySet());
		
		return list.size();
	}
		
}

O(N) time, O(N) space

public int removeDups(ArrayList<Integer> input) throws NullPointerException
	{
		if(input==null)
		{
			throw new NullPointerException();
		}
		if(input.isEmpty())
		{
			return 0;
		}
		HashMap<Integer,Boolean> mp=new HashMap<Integer,Boolean>();
		int size=mp.size();
		for(Integer x:input)
		{
			if(!mp.contains(x))
			{
				mp.put(x,true);
			}else
			{
				input.remove(x);
				size--;
			}
		}
		return size;
	}
//O(n) time complexity, O(n) space complexity.

def removeDuplicatesFromArray(arr):
	if arr == None:
		return 0

	n = len(arr)
	if n == 1:
		return n

	l = r = 0;
	dict = {}

	for el in arr:
		if dict.get(el) == None:
			dict[el] = True
			arr[r] = arr[l]
			r = r + 1

		l = l + 1

	arr = arr[:r]
	return r

long removeDuplicates(List<Integer> inputlist)
	{
		return inputlist.stream().distinct().count();
	}

Two approaches I can think:
1) O(1) space - Sort the array and traverse the array and count distinct elements. time O(nlogn)

2) O(n) space - use hashtable, traverse the array and put each element in hashtable if not present, count while doing that. time - O(n)

Can someone think of a solution with O(n) time and O(1) space?

private static int removeDuplicates(List<Integer> numbers) {
// your code goes here
List<Integer> newList = new ArrayList<>();
for (int number : numbers){
if(!newList.contains(number)) {
newList.add(number);
}
}
return newList.size();
}

public class RemoveDyplicate {

	public static void main(String[] args){
		int[] arr = {1, 1, 5, 3, 8, 3, 7, 32, 32} ;
		MapClass class1 = new MapClass();
		for(int i=0;i<arr.length;i++){
			if(!class1.get(arr[i])){
				class1.put(arr[i]);
			}
		}
		System.out.println(class1.count());
	}
	static class MapClass{
		int num;
		int count;
		int[] arr = new int[15];
		int total =0 ;
		MapClass map;
		StringBuilder builder = new StringBuilder();
		public String get(){
			for(int i=0;i<arr.length;i++){
				if(arr[i]!=0){
					builder.append(arr[i]+", ");
					count();
				}
			}
			return builder.toString();
		}
		public void put(int num){
			int hash = hashCode(num);
			while(arr[hash] != 0){
				hash = (hash+1) % 15;
			}
			arr[hash] = num;
		}
		public boolean get(int num){
			boolean flag = false;
			int hash = hashCode(num);
				while(arr[hash] != 0){
					if(arr[hash] == num){
						flag = true;
						break;
					}
					else{
						hash = (hash+1) %15;
					}
				}
			return flag;
		}
		public int size(){
			return total;
		}
		public int hashCode(int num){
			int hash = num % 13;
			return hash;
		}
		public int count(){
			int count = 0;
			for(int i=0;i<arr.length;i++){
				if(arr[i]!=0){
					count = count +1;
				}
			}
			return count;
		}
	}
}

Set<Integer > set = new HashSet<Integer>();
set.addAll(list);
return set.size();

Set<Integer > set = new HashSet<Integer>();
	set.addAll(list);
return set.size();

import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.TreeSet;

public class RemoveDupli {

    public static void main(String[] args) {
        int arr[] = new int[10];
        Scanner sc = new Scanner(System.in);
        System.out.println("ENTER THE VALUE OF AN ARRAY");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        LinkedHashSet t = new LinkedHashSet();
        for (int i = 0; i < arr.length; i++) {
            t.add(arr[i]);
        }
         HashSet t1 = new HashSet();
        for (int i = 0; i < arr.length; i++) {
            t1.add(arr[i]);
        }
         TreeSet t2 = new TreeSet();
        for (int i = 0; i < arr.length; i++) {
            t2.add(arr[i]);
        }
        System.out.println("linkedhash set");
        System.out.println(t);
        System.out.println("hashset");
        System.out.println(t1);
        System.out.println("treeset");
        System.out.println(t2);

}

class NoDuplicatePredicate<T> implements Predicate<T> {

        private final HashSet<T> seen = new HashSet();

        @Override
        public boolean test(T t) {
            if (seen.contains(t)) {
                return true;
            } else {
                seen.add(t);
                return false;
            }
        }

    }

    int removeDuplicates(List input) {
        NoDuplicatePredicate ndp = new NoDuplicatePredicate();
        input.removeIf(ndp);
        return input.size();
    }

class NoDuplicatePredicate<T> implements Predicate<T> {

        private final HashSet<T> seen = new HashSet();

        @Override
        public boolean test(T t) {
            if (seen.contains(t)) {
                return true;
            } else {
                seen.add(t);
                return false;
            }
        }

    }

    int removeDuplicates(List input) {
        NoDuplicatePredicate ndp = new NoDuplicatePredicate();
        input.removeIf(ndp);
        return input.size();

}

Python 2 rulez

def removeDuplicates(lst):
return len(set(lst))

1) Assumption: Input Number Order can be changed
2) Assumption: Ignore the numbers beyond the returned 'n' index
3) Do a bubble sort with a twist that you can check if the prev Bubble was same as current Bubble and just eat the duplicate

int removeDuplicates(List<int> list) {
    int b = 0, i = 0;
    int temp = 0;
    int n = list.size();
  
    for (b = 0; b < n; b++) {
        for (i = b+1; i < n; i++) {
            if (list[b] > list[i]) {
                temp = list[b];
                list[b] = list[i];
                list[i] = temp;
            } else if (list[b] == list[i]) {
               list[i] = list[n-1];
               n = n -1;
            }
        }
    }
    // TODO: How do we truncate the list from list.size() to n?

    return n;
}

public static int removeDuplicate(List numbers){

Collections.sort(numbers);
System.out.println("numbers = " + numbers);

for(int i = 1; i<numbers.size();i++){
if (numbers.get(i-1) == numbers.get(i)) {
numbers.remove(i);
i--;
}
}

System.out.println("numbers = " + numbers);

return numbers.size();
}

and public static int removeDuplicate(List numbers){

        Collections.sort(numbers);
        System.out.println("numbers = " + numbers);

        for(int i = 1; i<numbers.size();i++){
            if (numbers.get(i-1) == numbers.get(i)) {
                numbers.remove(i);
                i--;
            }
        }

        System.out.println("numbers = " + numbers);

        return numbers.size();

}

and

public static int removeDuplicate(List numbers){

if(numbers.isEmpty() || numbers.size() < 2){
return numbers.size(); // do nothing
}
Collections.sort(numbers);
System.out.println("numbers = " + numbers);

for(int i = 1; i<numbers.size();i++){
if (numbers.get(i-1) == numbers.get(i)) {
numbers.remove(i);
i--;
}
}

System.out.println("numbers = " + numbers);
return numbers.size();
}

and

#include <iostream>
#include <list>
#include <map>

int removeDuplicate(std::list<int> & integerList) {
    std::list<int>::iterator    iteratorOfIntegerList;
    std::map<int, bool>         integerMap;
    
    iteratorOfIntegerList = integerList.begin();
    
    while (iteratorOfIntegerList != integerList.end()) {
        if (integerMap[*iteratorOfIntegerList] == false) {
            integerMap[*iteratorOfIntegerList] = true;
        } else {
            integerList.erase(iteratorOfIntegerList);
        }
        iteratorOfIntegerList++;
    }
    
    return (int)integerList.size();
}

int main(int argc, const char * argv[]) {
    std::list<int> integerList;
    
    integerList.push_back(21);
    integerList.push_back(10);
    integerList.push_back(24);
    integerList.push_back(2);
    integerList.push_back(21);

    
    std::cout << "Before removing duplicates" << std::endl;
    for (std::list<int>::iterator iteratorOfIntegerList = integerList.begin(); iteratorOfIntegerList != integerList.end(); iteratorOfIntegerList++) {
        std::cout << *iteratorOfIntegerList << ' ';
    }
    std::cout << std::endl;
    
    std::cout << "The size of removed duplicate integer list is " << removeDuplicate(integerList) << std::endl;
    
    std::cout << "After removing duplicates" << std::endl;
    for (std::list<int>::iterator iteratorOfIntegerList = integerList.begin(); iteratorOfIntegerList != integerList.end(); iteratorOfIntegerList++) {
        std::cout << *iteratorOfIntegerList << ' ';
    }
    std::cout << std::endl;
    
    return 0;
}

Set set=new HashSet(ListObject);
    return k.size();

Sort and remove duplicate

vector<int> dedup(vector<int> arr){
	
	sort(arr.begin(), arr.end());
	
	int slow = 0;
	for(int i = 0; i < arr.size(); i++){
		if(arr[slow] != arr[i]){
			arr[++slow] = arr[i];
		}
	}
	
	arr.resize(slow+1);
	return arr;
}

public static int removeDuplicates(int[] numbers){
            Dictionary<int, int> hashNum = new Dictionary<int, int>();

            foreach (var i in numbers)
            {
                if (hashNum.ContainsKey(i))
                {
                    hashNum.Remove(i);
                }
                else
                {
                    hashNum.Add(i, i);
                }
            }

            return hashNum.Count;
        }

How about this:

public static void main (String[] args) throws java.lang.Exception {
List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 2, 3, 4, 4, 5, 6));
System.out.println(removeDuplicates(numbers)); // 6
}

public static int removeDuplicates(List<Integer> numbers) {
HashSet<Integer> hs = new HashSet<>(numbers);
numbers.clear();
numbers.addAll(hs);
return numbers.size();
}

package test;

public class RemoveDuplicates {
	
	
	Data [] bucketsData = new Data[10];
	int number = 1, counterFinal;
	int INDEX_DATA = 0;
	
	public static void main(String[] args) {
		
		RemoveDuplicates removeDuplicates = new RemoveDuplicates();
		
		removeDuplicates.addData(21);
		removeDuplicates.addData(10);
		removeDuplicates.addData(24);
		removeDuplicates.addData(2);
		removeDuplicates.addData(21);
		
		removeDuplicates.counter();

	}
	
	
	public class Data {
		
		int key;
		Data next = null;
		
		Data(int key){
			this.key = key;
		}
		
		public boolean equals(Object object){
			
			if (object instanceof Data){
				
				return key == ( ((Data) object).key);
				
			}
			
			return false;		
			
		}
		
	}
	
	public void counter(){
		
			Data data = bucketsData[INDEX_DATA];
			
			while (data!=null){
				
				
				data = data.next;
				++counterFinal;
				
			}
			
		System.out.println(counterFinal);
		
	}
	
	public void addData(int key){
		
		Data  data = bucketsData[INDEX_DATA];
		
		Data newData = new Data(key);
		
		if (data == null){
			
			bucketsData[INDEX_DATA]  = newData;
			number++;
			
		}else{
			
			while (data!=null){
				
				if (data.key == key){
					return;
				}
				
				data = data.next;
				
			}
			
			newData.next = bucketsData[INDEX_DATA];
			bucketsData[INDEX_DATA] = newData;
			number++;
			
		}
		
	}
}

public static int removeDuplicates(int[] input) {
        int len = input.length;
        int[] tmp = new int[len];
        int totalRemaining = 0;
        for (int i = 0; i < len; i++) {
            int vInputItem = input[i];
            int idx = vInputItem % len;
            int v = tmp[idx];
            if (v != vInputItem) {
                tmp[idx] = vInputItem;
                totalRemaining++;
            }
        }
        return totalRemaining;

}