Optimal code without using for, while and if

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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 :)