3
\$\begingroup\$

I presented a code solution to a startup as part of their interview polity.

The problem statement is to find the frequency of words occurring in a sentence. I got the code rejected saying, "Evaluating code is always subjective, but people generally leave a "fingerprint" with their design approach and the nature of their code (comments, tests, multiple solution paths, validation). The hiring manager has a high bar, and has rejected many working solutions because he didn't like the approach or the number of trees used or linear scaling vs. ^2 scaling."

I have pasted my solution. The hiring manager specified not to use collection API. I would like some opinions as to how I would have improved the code.

import java.io.*;
import java.util.*;

class FreqWord {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new
        InputStreamReader(System. in ));
        String str[] = new String[30];
        StringTokenizer st;
        int i = 0, j, k, ctr, size = 0;
        System.out.println(" Enter the String :");
        String str1 = br.readLine();
        st = new StringTokenizer(str1, " \n");
        while (st.hasMoreTokens()) {
            str[i] = st.nextToken();
            size++;
            i++;
        }
        System.out.println("\n-------------");
        System.out.println("\nWord" + "\t" + "freq");
        System.out.println("\n-------------");
        for (i = 0; i < size; i++) {
            ctr = 0;
            for (j = i; j < size; j++) {
                if (str[j].equals(str[i])) ctr++;
            }
            for (k = i - 1; k >= 0; k--) {
                if (str[k].equals(str[i])) {
                    ctr = 0;
                    break;
                }
            }
            if (ctr != 0) {
                System.out.println(str[i] + "\t" + ctr);
            }
        }
        System.out.println("\n------------");
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Proper indentation would be a good start. \$\endgroup\$ – Robert Harvey Oct 31 '13 at 17:12
  • 3
    \$\begingroup\$ I hope you didn't present it like that. Please, please, please format and indent your code appropriately. No-one is going to take the time to look through your code and make suggestions if you can't be bothered to make it presentable in the first place. \$\endgroup\$ – Chris Mantle Oct 31 '13 at 17:12
  • \$\begingroup\$ Does "not to use collection api" include Guava? Multiset could do this in a few lines of code. \$\endgroup\$ – azz Oct 31 '13 at 17:15
  • 1
    \$\begingroup\$ I'm confused by the requirements between your title (not using if, for, or while) and hiring manager limitation (not using Collections. Plus your code has both if and while. So, what is the exact and complete task here? \$\endgroup\$ – PM 77-1 Oct 31 '13 at 17:29
  • \$\begingroup\$ It seems that using split() method can simplify the code a bit. \$\endgroup\$ – PM 77-1 Oct 31 '13 at 17:33
10
\$\begingroup\$

I am not a fan of this type of interview process... but ... you can assume that you need to differentiate yourself from the other candidates in some way.

Your solution may work, but does not show much in the way of 'clever' algorithms. You do the minimum to get the answer right, but not in the best way.

Things I think you could do better are:

  1. Do not load the entire document in to memory. It may be large. Instead, use a mechanism for counting the words in a streaming way. It will save memory.
  2. What about handling mixed-case words "The quick brown fox jumped over the sleeping dog" has the word 'the' twice, note the words 'The' and 'the' once each.
  3. Consider a faster method for processing the data than a linnear scan through the words. A binary search and adding data to a sorted array would differentiate you.

EDIT: I took the liberty of copying and running the code, and it does not work. I changed the code to be:

BufferedReader br = new BufferedReader(new
    InputStreamReader(new FileInputStream(new File("src/FreqWord.java"))));

and this produced the result:

 Enter the String :

-------------

Word    freq

-------------
import  1
java.io.*;  1

------------

This is obviously not correct, so I will take a moment and write what I consider to be a 'good' solution. This will also answer the comment below about the Binary Search.

EDIT 2: Here's an answer that demonstrates the three issues I mentioned (just the main method), and as a bonus it gets the right answer.... :

public static void main(String[] args) throws IOException {
    // show you know the Java7 language changes...
    try (BufferedReader br = new BufferedReader(new InputStreamReader(
            new FileInputStream(new File("src/FreqWord.java"))))) {
        int wordcount = 0; // the number of unique words we have

        String [] wordvalues = new String[32];
        int [] counts = new int[32];

        String line = null;
        // Using regular expressions is a differentiator
        final Pattern pattern = Pattern.compile("\\w+");
        while ((line = br.readLine()) != null) {
            // Only keep one line at a time in memory.
            Matcher matcher = pattern.matcher(line);
            while (matcher.find()) {
                // use toLowerCase() to show a grasp of the problem
                String word = matcher.group().toLowerCase();
                // use BinarySearch to order the words, which is faster than a scan.
                int ip = Arrays.binarySearch(wordvalues, 0, wordcount, word);
                if (ip < 0) {
                    // word we have not yet seen.
                    ip = -ip - 1;
                    if (wordcount == wordvalues.length) {
                        // grow the word array by about 25% each time we need to.
                        wordvalues = Arrays.copyOf(wordvalues, wordcount + 1 + (wordcount >>>2));
                        counts = Arrays.copyOf(counts, wordvalues.length);
                    }
                    // insert the word in sorted order.
                    System.arraycopy(wordvalues,  ip, wordvalues,  ip+1, wordcount-ip);
                    System.arraycopy(counts, ip, counts, ip+1, wordcount-ip);
                    wordvalues[ip] = word;
                    wordcount++;
                }
                counts[ip]++;
            }
        }
        // output the words in alphabetical order.
        System.out.println("\n-------------");
        System.out.println("\nWord" + "\t" + "freq");
        System.out.println("\n-------------");
        for (int i = 0; i < wordcount; i++) {
            System.out.println(wordvalues[i] + "\t" + counts[i]);
        }
        System.out.println("\n------------");
    }
}
\$\endgroup\$
  • \$\begingroup\$ You may have a point here. \$\endgroup\$ – PM 77-1 Oct 31 '13 at 17:35
  • \$\begingroup\$ I agree with most of your suggestions. Although I am not sure how using a binary search would help here since, according to the javadoc: "If the range contains multiple elements equal to the specified object, there is no guarantee which one will be found". (docs.oracle.com/javase/6/docs/api/java/util/…) \$\endgroup\$ – Francis Oct 31 '13 at 17:56
  • \$\begingroup\$ I have updated with an example of how I think Binary Search is useful.... which should make it clear. \$\endgroup\$ – rolfl Oct 31 '13 at 18:30
6
\$\begingroup\$

I think that one of the problems here is related to what the hiring manager said:

comments, tests, multiple solution paths, validation

are missing. You need to make your code more readable ...

Moreover, it isn't a good OOP practice to put all your business logic in your main method: use the OO features! Your code will become more readable, understandable and clean (especially if you use good names of variables and methods).

\$\endgroup\$
1
\$\begingroup\$

You are writing Java code which is supposed to be OO in a procedural fashion.

No thought was put into class design, or separating logic from output.

There are 0 comments in the code, variable names are cryptic.

\$\endgroup\$
1
\$\begingroup\$

I would try to split the sentence into individual words using a regex and then sort the resulting array. This would make counting words much more easy.

Here`s an example of what I have in mind:

// Splitting on punctuation and whitespace
String[] words = sentence.split("[\\p{Punct}\\s]+");
Arrays.sort(words);

// count initialized to 1 since if the array length is greater 
// then 0, then there is at least one word...
int count = 1;
for (int i = 0; i < words.length; i++) {
    if (i+1 < words.length && words[i].equalsIgnoreCase(words[i+1])) {
        count++;
    }
    else {
        System.out.println(words[i] + ": " +count);
        count = 1;
    }
}
\$\endgroup\$
1
\$\begingroup\$

Without for, while and if you have only do-while and switch. I doubt that using only them will improve your code quality.

Your code has O(N*N) (N=number of words) running time and uses assumption that there exist no sentence longer than 30 words. Both things makes your design rather poor.

  1. Here is a very simple way to acheive O(NlogN) complexity. You should copy all words into array, which runs in O(N), sort the words array +O(NlogN) and count adjacent duplicates +O(N) = O(NlogN) complexity

  2. You should reallocate and copy array if its default capacity is overflowed. Always allocate 2 times more space than previously and you will need only O(logN) reallocations and O(NlogN) object copying operations.

  3. And if you can quickly implement balanced search tree or hash map (which is much simpler) on the interview - of course, do it. With it you can store much less temporary data (unique words, their counts and node references only).

  4. If you really believe in "Map is not Collection" argument - of course, just use HashMap instead of all the tricks :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy