I was in an interview and there was a question asked that there is a List which has integers numbers in it. List has the size of 1 million records and all of them are integers.
My task is to find the duplicates with best runtime. I was not able to answer the correct answer as I have told him that i can achieve the same of finding the duplicate numbers in such a big list by making use of two loops but can this be done as fast as possible with best runtime?
You need to iterate over the integers and keep track of integers you've already seen. For this you need an efficient data structure which have good runtime complexity for add and contains operations.
For instance you can use a has set to track seen integers:
Set<Integer> duplicateIntegers = new LinkedHashSet<>();
Set<Integer> seenIntegers = new HashSet<>();
for (Integer integer : integers) {
if (!seenIntegers.add(integer)){
duplicateIntegers.add(integer);
}
}
Here we iterate over N integers, add it to seenIntegers and check if current integer is already there, which is amortized O(1). So at the end it is O(N) on time and O(N) on additional space.
However O(1) for HashSet.add is amortised (see here what it actually means). Since we deal with integers and they are not so many, we can achieve a honest-to-goodness O(1) using more additional space. We only need 2^32 bits which is just 512Mb. For this we can use BitSet. Actually, two BitSets because we need 2^32 bits but BitSet can only be initialized with max value of int which is 2^31-1.
BitSet seenNonNegativeIntegers = new BitSet(Integer.MAX_VALUE);
BitSet seenNegativeIntegers = new BitSet(Integer.MAX_VALUE);
Set<Integer> duplicateIntegers = new LinkedHashSet<>();
for (Integer integer : integers) {
int i = integer.intValue();
if (i >= 0) {
if (seenNonNegativeIntegers.get(i)) {
duplicateIntegers.add(integer);
}
seenNonNegativeIntegers.set(i);
} else if (i < 0) {
int index = -(i + 1);
if (seenNegativeIntegers.get(index)) {
duplicateIntegers.add(integer);
}
seenNegativeIntegers.set(index);
}
}
This is also O(N), but based on honest-not-amortised O(1). Theoretically this must be the most optimal solution from the runtime complexity point of view. Practically, however it might still be slower that HashSet because we have to do get and set instead of just one add.
On an interview I'd probably present the first solution, mentioning the second one and discussing runtime complexity vs. additional space requirements.
The easiest solution is to use HasMap, unordered_set.
def find_duplicates(a):
used = set()
yielded = set()
for x in a:
if x in used and x not in yielded:
yield x
yielded.add(x)
used.add(x)
public class CountArrayList extends ArrayList<YourType>{
private HashMap<YourType, Integer> count = new HashMap<>();
@Override
public boolean add(YourType element){
Integer i = count.get(element);
count.put(element, i == null ? 1 : ++i);
return super.add(element);
}
public int getItemCount(YourType element){
return count.get(element) == null ? 0 : count.get(element);
}
}
This class is not complete and you should override remove and other methods like add method to update count
