As I go through interviews while looking for jobs, I often come home and revisit the questions as a learning experience. Here is an interview question that I often encounter: Given an array of integer where the elements (entries) are not sorted, write a function to return a new array with the duplicate entries removed. For example, if the original array is:
1,2,3,1,2,3
then the function should return:
1,2,3
The first time I tackled this problem, I did not make use of Java’s collections framework. As the result, the code are long, hard to read, and hard to maintain. When the interviewer asked me to improve the code, I finally thought of using the collections framework, but what kind of collection should I use? The interview was kind enough to provide me with a reference book for my research. To solve this problem, I need a collection that provides fast look-up, retains the original insertion order, and ignores the insertion of duplicate entries. As it turns out, Java collection framework does provide a collection that fit my demand and it is called LinkedHashSet. Using LinkedHashSet, I was able to simplify the code’s logic. For a complete listing of my code, follow the link here.
Hi, i’m a kid from Italy, i’m 10 years old. I’m tryng to compile your solution (removing duplicates in a java array) but i still cannot understand how your class “RemoveDuplicatesEntries” can works if it hasn’t got any method-Main.
Please can you write a little example (like mine posted below) where an Integer array, or better a String array, are initialized with duplicate values and then we can applicate your solution?
Thanks so much,
Giordano
public class prova
{
public static void main(String[] args)
{
int[] an_array = {0,1,2,3,3,3,4,1,5,6,7,5};
int[] tmp = new int[an_array.length];
for (Integer i : an_array)
System.out.print(i + " ");
// ? RemoveDuplicatesEntries ?
// CAN YOUR RemoveDuplicatesEntries WORKS ALSO WITH Strings array, chars array, Lists, Queues, Stacks... ??
}
}
“Grazie mille!!” (Thanks one thousand time)
Comment by Giordano — February 12, 2008 @ 1:29 pm
How to call removeDuplicates()?
The easiest way is to move removeDuplicates() into your class prova and call it as follow:
int[] tmp = removeDuplicates(an_array);
My solution does not work with other kind of array or collection.
Comment by wuhrr — February 12, 2008 @ 5:27 pm
Better not use an static array, but some collection class. Example:
List l = …
for (int i = 1; i < l.size();) {
if (l.subList(0,i-1).contains(l.get(i)))
l.remove(i);
else
i++;
}
Awefull slow on lists with lot of elements (especially on linked lists). But works fine for <1000 elements..
Comment by imi — May 19, 2009 @ 5:01 am
Use collections, for example,
public static void main(String[] argz) {
try {
String[] policyNumbers = new String[] { “12345678″, “16018189″
, “12345678″, “16018189″, ” 12345678″, ” 16018189 “};
String[] refinedPolicies = removeDuplicates(policyNumbers);
log(“refinedPolicies size:” + refinedPolicies.length);
} catch (Exception e) {
e.printStackTrace();
}
}
private static String[] removeDuplicates(String[] stringArray){
if( stringArray == null && stringArray.length == 0){
return stringArray;
}
ArrayList stringArrayList = new ArrayList();
String trimmedString = null;
for( int i=0; i0){
if( !stringArrayList.contains(trimmedString)){
stringArrayList.add(trimmedString);
}
}
}
String[] refinedStringArray = new String[stringArrayList.size()];
stringArrayList.toArray(refinedStringArray);
return refinedStringArray;
}
Comment by Podanga — June 25, 2009 @ 8:54 am
Note that the above code does not require any exception handling (in the main method) as there won’t be any checked exceptions thrown in this scenario.
Comment by Podanga — June 25, 2009 @ 8:56 am
The code above wouldn’t compile, here the code that works:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MergeStrings {
public static void main(String[] argz) {
try {
String[] policyNumbers = new String[6];
policyNumbers[0] = “12345678?;
policyNumbers[0] = “16018189?;” +
“, “12345678?, “16018189?, “12345678?, “16018189″};
String[] refinedPolicies = removeDuplicates(policyNumbers);
log(“refinedPolicies size:” + refinedPolicies.length);
} catch (Exception e) {
e.printStackTrace();
}
}
private static String[] removeDuplicates(String[] stringArray){
if( stringArray == null && stringArray.length == 0){
return stringArray;
}
ArrayList stringArrayList = new ArrayList();
String trimmedString = null;
for( int i=0; i0){
if( !stringArrayList.contains(trimmedString)){
stringArrayList.add(trimmedString);
}
}
}
String[] refinedStringArray = new String[stringArrayList.size()];
stringArrayList.toArray(refinedStringArray);
return refinedStringArray;
}
}
Comment by Earl — December 2, 2009 @ 7:36 pm