Interview Question
Country: United States
public class TestUtils {
public static void main(String[] args) {
// To store array elements with its count in names
Map<String, Long> map = new HashMap<String, Long>();
String[] names = { "A", "B", "C", "D", "A", "D" };
for (String string : names) {
if (!map.containsKey(string)) {
map.put(string, 1L);
} else if (map.containsKey(string)) {
synchronized (TestUtils.class) {
Long count = map.get(string);
count++;
map.put(string, count);
}
}
}
// Iterate map for duplicate elements and its count
Iterator it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pairs = (Map.Entry) it.next();
System.out.println(pairs.getKey() + " = " + pairs.getValue());
}
}
}
Output:-
D = 2
A = 2
B = 1
C = 1
Sample Code With Trie
public class TrieDuplicates {
public TrieDuplicates() {
super();
}
public static void main(String[] args) {
String[] str = {"IBM","ORACLE","GOOGLE","MICROSOFT","IBM","AMAZON","AMAZON","APPLE"};
TrieDuplicates td = new TrieDuplicates();
TrieDuplicates.Trie trie = td.new Trie();
for(String str1:str) {
trie.insert(str1);
}
trie.traverse();
trie.searchPattern("A");
}
class Trie {
private char ch;
private Trie[] trieArray;
private boolean word;
private Trie root;
private int now;
public Trie() {
this.setCh(' ');
this.setTrieArray(new Trie[26]);
}
public Trie(char ch) {
this.setCh(ch);
this.setTrieArray(new Trie[26]);
}
public void insert(String word) {
if (this.getRoot() == null)
this.setRoot(new Trie());
if(word==null || word=="") return;
Trie root = this.getRoot();
for (int i = 0; i < word.length(); i++) {
if (root.getTrieArray()[atoi(word.charAt(i))] == null) {
root.getTrieArray()[atoi(word.charAt(i))] = new Trie(word.charAt(i));
}
root = root.getTrieArray()[atoi(word.charAt(i))];
}
root.setWord(true);
root.setNow(root.getNow()+1);
}
/**
* To Print all duplicates with count
*/
public void traverse() {
char[] buf = new char[1024];
Trie root = this.getRoot();
print(root, 0, buf,false);
}
public void print(Trie root, int index, char[] buf ,boolean flag) {
if (root == null)
return;
if (root.isWord() &&( root.getNow()>1 || flag))
if(!flag)
System.out.println(new String(buf, 0, index)+"--->"+root.getNow());
else
System.out.println(new String(buf, 0, index));
for (int i = 0; i < 26; i++) {
if (root.getTrieArray()[i] != null) {
buf[index] = root.getTrieArray()[i].getCh();
print(root.getTrieArray()[i], index + 1, buf,flag);
}
}
}
/**
*
*This is for searching a specific pattern
* @param pattern
*/
public void searchPattern(String pattern) {
char[] buf = new char[1024];
Trie root = this.getRoot();
int index = 0;
for (int i = 0; i < pattern.length(); i++) {
if (root.getTrieArray()[atoi(pattern.charAt(i))] != null) {
buf[index++] = root.getTrieArray()[atoi(pattern.charAt(i))].getCh();
root = root.getTrieArray()[atoi(pattern.charAt(i))];
}
}
print(root, index, buf,true);
}
public void setCh(char ch) {
this.ch = ch;
}
public char getCh() {
return ch;
}
public void setTrieArray(Trie[] trieArray) {
this.trieArray = trieArray;
}
public Trie[] getTrieArray() {
return trieArray;
}
public void setWord(boolean word) {
this.word = word;
}
public boolean isWord() {
return word;
}
public void setRoot(Trie root) {
this.root = root;
}
public Trie getRoot() {
return root;
}
public int atoi(char ch) {
int i = 0;
if (ch >= 65 && ch <= 90)
i = ch - 65;
else if (ch >= 97 && ch <= 122)
i = ch - 97;
else
i = (int)ch;
return i;
}
public void setNow(int now) {
this.now = now;
}
public int getNow() {
return now;
}
}
}
public class CountDuplicates {
private static volatile Map<String,AtomicLong> countHolder = new ConcurrentHashMap<String, AtomicLong>();
static class CountIncrementor implements Runnable{
String key;
public CountIncrementor(String key) {
this.key = key;
}
@Override
public void run() {
synchronized (countHolder) {
if(countHolder.containsKey(key)){
AtomicLong count = countHolder.get(key);
count.incrementAndGet();
countHolder.put(key, count);
System.out.println("key : " + key + " count : " + count);
}else{
countHolder.put(key, new AtomicLong(1));
System.out.println("key : " + key + " count : " + 1);
}
}
}
}
public static void main(String[] args) throws InterruptedException {
String[] values = {"Cognigent", "Yahoo", "Google", "Google", "Cognigent", "Yahoo", "Google",
"JPMC", "Cognigent", "JPMC", "CapGemini", "Google"};
final int POOL_SIZE = values.length;
ThreadPoolExecutor service = (ThreadPoolExecutor) Executors.newFixedThreadPool(POOL_SIZE);
service.prestartAllCoreThreads();
for (int i = 0; i < values.length; i++) {
service.submit(new CountIncrementor(values[i]));
}
Thread.sleep(500);
service.shutdown();
System.out.println(countHolder.toString());
}
}
public void counter(){
//String[] array = {"IBM", "Amazon", "Google", "IBM"};
String[] array = { "A", "B", "A", "D", "A", "D" };
HashMap<String, Integer> map = new HashMap<String, Integer>();
int count = 1;
for(int i =0; i<array.length;i++){
if(map.size() == 0){
map.put(array[i], count);
}else{
if(map.containsKey(array[i])){
int cnt = map.get(array[i]);
cnt++;
map.put(array[i], cnt);
}else{
map.put(array[i], count);
}
}
}
for(String st:map.keySet()){
if(map.get(st)>1){
System.out.println("The string value is " +st+ " the count is " +map.get(st));
}
}
}
//i think it can be the simplest way of doing this-do reply=n_vashisth@yahoo.com if not correct
public void duplicate()
{
String[] given=new String[11];
given[0]="IBM";
given[1]="GOOGLE";
given[2]="AMAZON";
given[3]="IBM";
given[4]="BMC SOFTWARES";
given[5]="TCS";
given[6]="NAGGARO";
given[7]="MICROSOFT";
given[8]="BMC SOFTWARES";
given[9]="GOOGLE";
given[10]="AMAZON";
for(int i=0;i<given.length;i++)
{
for(int j=i+1;j<given.length;j++)
{
if(given[i].equals(given[j]))
System.out.println("Duplicate is "+given[j]);
}
}
}
A few known ways:
- Murali Mohan August 17, 20131. Sort the array and count the duplicates by checking adjacent elements.
2. Use a hashtable with string as key and counter as value, Store the keys and update their corresponding counters as the array is traversed. In the end print out the count of the duplicates by traversing the hashtable
3. Use a modified trie to store the strings along with a counter field. While traversing the array, update the counters of the trie for each of the string. Traverse the trie and print out the count of the duplicates.