Interview Question
Country: United States
public class CheckDuplicatesInJavaArray {
public static void main(String args[]) {
String[] withDuplicates = new String[] {"one","two","three","one"};
String[] withoutDuplicates = new String[] {"one","two","three"};
System.out.println("Checking array with duplicate using Set and List: " + checkDuplicateUsingAdd(withDuplicates));
System.out.println("Checking array without any duplicate using Set and List: " + checkDuplicateUsingAdd(withoutDuplicates));
}
/*
* Since Set doesn't allow duplicates add() return false
* if we try to add duplicates into Set and this property
* can be used to check if array contains duplicates in Java
*/
public static boolean checkDuplicateUsingAdd(String[] input) {
Set tempSet = new HashSet();
Map<String, Integer> tempMap = new HashMap<String, Integer>();
boolean flag = false;
for (String str : input) {
if (!tempSet.add(str)) {
tempMap.put(str, tempMap.get(str) + 1);
flag = true;
} else {
tempMap.put(str, 1);
}
}
for(Map.Entry<String, Integer> entry : tempMap.entrySet()){
System.out.println(entry.getKey() + "/" + entry.getValue());
}
return flag;
}
}
Performance will be much faster this way.
Simple Ternary Search Tree for removing duplicates
public class TernarySearchTreeWithDups {
public TernarySearchTreeWithDups() {
super();
}
public static void main(String[] args) {
TernarySearchTreeWithDups ternarySearchTreeWithDups = new TernarySearchTreeWithDups();
String[] strs = {"GOOGLE","AMAZON","GOOGLE","AMAZON","MICROSOFT","IBM","IBM"};
TernarySearchTree ternarySearchTree = ternarySearchTreeWithDups.new TernarySearchTree();
for(String str:strs) {
ternarySearchTree.insert(str);
}
ternarySearchTree.traverse();
}
class TernarySearchTree {
private TernarySearchTree left;
private TernarySearchTree right;
private TernarySearchTree middle;
private char ch;
private TernarySearchTree root;
private int now;
private boolean word;
public TernarySearchTree() {
this.setCh(' ');
}
public TernarySearchTree(char data) {
this.setCh(data);
}
public void insert(String s) {
TernarySearchTree root = this.getRoot();
if(root==null) {
root = new TernarySearchTree(s.charAt(0));
this.setRoot(root);
}
insertNode(root,0,s);
}
public TernarySearchTree insertNode(TernarySearchTree root,int index,String data) {
if(root==null) {root = new TernarySearchTree(data.charAt(index));}
if(root.getCh() > data.charAt(index)) {
root.setLeft(insertNode(root.getLeft(),index,data));
}
else if(root.getCh() < data.charAt(index)) {
root.setRight(insertNode(root.getRight(),index,data));
}
else {
if(index == data.length()-1) {root.setWord(true);root.setNow(root.getNow()+1);}
else {
root.setMiddle(insertNode(root.getMiddle(),index+1,data));
}
}
return root;
}
public void traverse() {
char[] buffer = new char[1024];
if(this.getRoot()==null) return;
print(root,0,buffer);
}
public void print(TernarySearchTree root,int index,char[] buffer) {
if(root==null) return;
print(root.getLeft(),index,buffer);
buffer[index] = root.getCh();
if(root.isWord() && root.getNow()==1) System.out.println(new String(buffer,0,index+1));
print(root.getMiddle(),index+1,buffer);
print(root.getRight(),index,buffer);
}
public void setLeft(TernarySearchTree left) {
this.left = left;
}
public TernarySearchTree getLeft() {
return left;
}
public void setRight(TernarySearchTree right) {
this.right = right;
}
public TernarySearchTree getRight() {
return right;
}
public void setMiddle(TernarySearchTree middle) {
this.middle = middle;
}
public TernarySearchTree getMiddle() {
return middle;
}
public void setCh(char ch) {
this.ch = ch;
}
public char getCh() {
return ch;
}
public void setRoot(TernarySearchTree root) {
this.root = root;
}
public TernarySearchTree getRoot() {
return root;
}
public void setNow(int now) {
this.now = now;
}
public int getNow() {
return now;
}
public void setWord(boolean word) {
this.word = word;
}
public boolean isWord() {
return word;
}
}
}
Just thought of another way of doing it ->
class DuplicateStrings{
public static void main(String[] args){
String[] s = {"IBM","Google","Amazon","Google","HP","IBM","Oracle","IBM","HP"};
int duplicate = 0;
String[] sc = s.clone();
for(int i=0; i<s.length;i++)
for (int j=i+1;j<sc.length;j++)
if ((s[i]==sc[j])&&(s[i]!="NULL")){
duplicate++;
sc[j]="NULL";
}
System.out.println("Total duplicates - "+duplicate);
}
}
- Anonymous August 19, 2013