## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

A few known ways:

1. 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.

Comment hidden because of low score. Click to expand.
0

would u please elaborate how to do it with trie???

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sample Code With Trie

``````public class TrieDuplicates {
public TrieDuplicates() {
super();
}

public static void main(String[] args) {
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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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 {

final int POOL_SIZE = values.length;

for (int i = 0; i < values.length; i++) {
service.submit(new CountIncrementor(values[i]));
}

service.shutdown();

System.out.println(countHolder.toString());

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse the array and add each element to a Set. If the value is already in the set then the add() method will return false.

So keep track of how many times the add() call on the Set returned false.

Comment hidden because of low score. Click to expand.
0
of 0 vote

//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[2]="AMAZON";
given[3]="IBM";
given[4]="BMC SOFTWARES";
given[5]="TCS";
given[6]="NAGGARO";
given[7]="MICROSOFT";
given[8]="BMC SOFTWARES";
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]);
}
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.