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.

- Murali Mohan August 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dt August 17, 2013 | Flag
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

- Vinod Sreepathi August 18, 2013 | Flag Reply
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) {
        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;
        }
    }
}

- Prakash August 19, 2013 | Flag Reply
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 {
		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());
		
	}
}

- Anonymous August 24, 2013 | Flag Reply
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));
}

}
}

- Anonymous August 28, 2013 | Flag Reply
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.

- Anonymous October 21, 2013 | Flag Reply
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[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]);
}
}
}

- Anonymous October 24, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More