Last active
September 9, 2016 15:21
-
-
Save deyindra/d36ba4ba081a7eba0c1c6c96bcede950 to your computer and use it in GitHub Desktop.
Write A Custom List which will not allow any duplicate and perform add, contains, delete and random operation in O(1) time
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class CustomList<T> { | |
private Map<T, Value<T>> map = new HashMap<T, Value<T>>(); | |
private List<Value<T>> list = new ArrayList<>(); | |
private static final Random RANDOM = new Random(); | |
public boolean add(T object){ | |
Value<T> value = map.get(object); | |
//This mean key does not exists | |
if(value==null){ | |
value = new Value<>(object,list.size()); | |
//O(1) | |
map.put(object,value); | |
//Amortize Operarion O(1) | |
list.add(value); | |
return true; | |
} | |
return false; | |
} | |
public boolean contains(T object){ | |
return map.containsKey(object); | |
} | |
public void delete(T obj){ | |
//O(1) | |
Value v = map.remove(obj); | |
if(v != null){ | |
int index = v.index; | |
Value<T> lastValue = list.get(list.size()-1); | |
lastValue.index = index; | |
list.set(index,lastValue); | |
list.remove(list.size()-1); | |
} | |
} | |
public T getRandom(){ | |
int index = RANDOM.nextInt(list.size()); | |
return list.get(index).object; | |
} | |
private class Value<E>{ | |
private E object; | |
private int index; | |
public Value(E object, int index) { | |
this.object = object; | |
this.index = index; | |
} | |
@Override | |
public String toString() { | |
return "Value{" + | |
"object=" + object + | |
", index=" + index + | |
'}'; | |
} | |
} | |
@Override | |
public String toString() { | |
return "CustomList{" + | |
"map=" + map + | |
", list=" + list + | |
'}'; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment