Google

Jul 11, 2012

Can you write Java code by asking the right questions?

Core Java Coding Questions and Answers for beginner to intermediate level

Q1 Q2 Q3 Q4 Q5 Q6




Q. How will you go about writing code for counting the number of repeated words in the order of decreasing count for a given text input?

For example, input text = "The third-rate mind is only happy when it is thinking with the majority. The second-rate mind is only happy when it is thinking with the minority. The first-rate mind is only happy when it is thinking."

A. As mentioned before, the interviewer is not expecting you to come up with the perfect solution. He/she will be more interested in finding out the following:

1. Can you write pseudo code?
2. Do you analyze the requirements properly by asking the right questions?
3. Can you write basic code by referring to the Java API, etc?
4. Do you write unit tests?

Let's look at these in more etail.

1.Can you write pseudo code?
  • tokenize the input text into words
  • build a map<word, count> to store the individual words and its relevant count
  • iterate through the tokenized words and if the word is already stored, increment its count and if not already stored, store it with the count of 1.
  • sort the map by count in decrementing order
  • loop through the sorted map and print the "word" and its count.

2.Do you analyze the requirements properly by asking the right questions?
  • How are the words tokenized? by whitespace character only, white space and punctuations, how about URLs? , etc, The regular expression can be used for splitting the text. [ignore URL to keep it simple]
  • Are there any common words that need to be ignored? For example, 'the', 'a', 'or', 'and', etc. [yes]
  • Is it case sensitive? Should word and WORD be treated as the same word? [yes]

3.Can you write basic code by referring to the Java API, etc?
  • Use regex to split string into tokens
  • Use a Map that has o(1) look up to save the tokens and increment the count
  • Use a custom comparator to sort the map by its count in descending order. This means most repeated words at the top.




Here is the sample code --  DuplicateCounter

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public final class DuplicateCounter {

 private static final String REGEX_TO_SPLIT_TEXT_BY_WHITESPACE_AND_PUNCTUATION = "([.,!?:;'\"-]|\\s)+";
 private static final String[] WORDS_TO_IGNORE = {"is", "the", "a", "or", "and"};  // keep it short for demo

 public Map<String, Integer> processGivenText(String text) {
  //pre-condition check
  if(text == null) {
   throw new IllegalArgumentException("The input text cannot be null ");
  }

  //split the text into words
  String[] tokenizedWords = text.split(REGEX_TO_SPLIT_TEXT_BY_WHITESPACE_AND_PUNCTUATION);
  
  Map<String, Integer> readWords = new HashMap<String, Integer>(100);
  
  for (String word : tokenizedWords) {
   word = word.toLowerCase(); // make it case insensitive
   
   //if one of the words to be ignored, move on to the next word
   if(Arrays.asList(WORDS_TO_IGNORE).contains(word)){
    continue;
   }
   
   if (readWords.containsKey(word)) {
    int count = readWords.get(word);
    readWords.put(word, count + 1); // store incremented count
   } else {
    readWords.put(word, 1);
   }
  }

  // return the sorted LinkedMap 
  return sortByValue(readWords);
  
 }
 
 
 /**
  * Sort the given map by its value i.e. count as opposed to key
  * @param unsortedMap
  * @return
  */
 private Map<String, Integer> sortByValue(Map<String, Integer> unsortedMap) {
      List<Map.Entry<String, Integer>> sortedKeyList = new LinkedList<Map.Entry<String, Integer>>(unsortedMap.entrySet());
   //anonymous inner class to sort using a Comparator
      Collections.sort(sortedKeyList, new Comparator<Map.Entry<String, Integer>>() {
   @Override
   public int compare(Entry<String, Integer> e1, Entry<String, Integer> e2) {
    return -e1.getValue().compareTo(e2.getValue());
   }
       
      });

     //LinkedHashmap maintains the order in which the elements were added 
     Map<String, Integer> sortedMap = new LinkedHashMap<String, Integer>(unsortedMap.size());
     for (Entry<String, Integer> entry : sortedKeyList) {
      sortedMap.put(entry.getKey(), entry.getValue());
  }
  
     return sortedMap;
 } 
}



Note that sorting a map by its values as opposed to its key is a bit tricky and it is done via the sortByValue method shown above.

Here is the sample main method that makes use of the class DuplicateCounter
    public static void main(String[] args) {
  Map<String, Integer> sortedByCountWords = new DuplicateCounter()
    .processGivenText("The third-rate mind is only happy when it is thinking with the majority. The second-rate mind is only happy when it is thinking with the minority. The first-rate mind is only happy when it is thinking.");

  // print word and its counts
  for (Map.Entry<String, Integer> entry : sortedByCountWords.entrySet()) {
   System.out.format("word '%s' counted  %s  time(s) \n", entry.getKey(), entry.getValue());
  }
 }
 
The output will be something like
word 'when' counted  3  time(s) 
word 'only' counted  3  time(s) 
word 'thinking' counted  3  time(s) 
word 'rate' counted  3  time(s) 
word 'happy' counted  3  time(s) 
word 'mind' counted  3  time(s) 
word 'it' counted  3  time(s) 
word 'with' counted  2  time(s) 
word 'second' counted  1  time(s) 
word 'majority' counted  1  time(s) 
word 'third' counted  1  time(s) 
word 'minority' counted  1  time(s) 
word 'first' counted  1  time(s) 

4.Do you write unit tests?

It is imperative to write both positive and negative test cases to test  your functionality.


import java.util.Map;


import java.util.Map;
import junit.framework.Assert;
import org.junit.Test;


public class DuplicateCounterTest {
 
 private static final String INPUT_TEXT = "The third-rate mind is only happy when it is thinking with the majority." + 
                                          "The second-rate mind is only happy when it is thinking with the minority." + 
                                     "The first-rate mind is only happy when it is thinking.";
 
 private static final String  word1 = "third";
 private static final String  word2 = "rate";
 private static final String  word3 = "thinking";
 private static final String  word4 = "is";
 
 
 @Test
 public void testPositiveScenario() {
  DuplicateCounter dc = new DuplicateCounter();
  Map<String, Integer> sortedByCountWords = dc.processGivenText(INPUT_TEXT);
  
  Assert.assertTrue(sortedByCountWords.size() == 13);
  
  Assert.assertTrue(sortedByCountWords.get(word1) == 1);  
  Assert.assertTrue(sortedByCountWords.get(word2) == 3);
  Assert.assertTrue(sortedByCountWords.get(word3) == 3);
 }
 
 @Test
    public void testNegativeScenario() {
     DuplicateCounter dc = new DuplicateCounter();
  Map<String, Integer> sortedByCountWords = dc.processGivenText(INPUT_TEXT);
  
  Assert.assertNull(sortedByCountWords.get(word4)); 
 }

}

Coding questions can reveal a lot about a candidate and his/her ability to write code.

Labels:

3 Comments:

Anonymous Anonymous said...

Thanks! Really helpful!

9:06 AM, September 06, 2012  
Anonymous Anonymous said...

using utility package
Input is:"hello abcdef ABCDEF"
now I want output as
a-f
A-F

11:09 PM, November 21, 2012  
Blogger Unknown said...

Question is not very clear.
You can try using the isUpperCase(char c) in the Character class.

12:52 AM, January 09, 2014  

Post a Comment

Subscribe to Post Comments [Atom]

<< Home