Program to compress a string of characters

Question

I was given this small task in an interview recently. I'm usually terrible at coding questions in interviews, because with the time constraint and the lack of google I usually overthink and rush stuff and just end up with a mess of a program.

The task was to write a program that would compress the length of string, and compare the length of the compressed string to the input string and return whichever one is smaller. Example would be: input string "aaabcccc" would be compressed to "a3b1c4".

I essentially split the string into a charArray and then counted each occurrence of a character and stored them into a hashmap, and looped through the map to build the new string. Just from a learning perspective, was there a better way to do this? I was given ~10 minutes to write it as well, it more to assess how I would solve the problem as opposed to the code itself. But regardless, I'd like a review of it:

import java.util.HashMap;
import java.util.Map.Entry;

public class Compressor {

    public static void main(String args []) {

        String randomString = "aaabccccc";

        HashMap<Character, Integer> map = countCharacters(randomString);    
        String compressedString = createCompressedString(map);

        if(randomString.toCharArray().length < compressedString.toCharArray().length) {
            System.out.println(randomString);
        }
        else {
            System.out.println(compressedString);
        }       
    }

    /**
     * Create hasmap to store character and count of occurrence
     * @param s
     * @return
     */
    private static HashMap<Character, Integer> countCharacters(String s) {

        HashMap<Character, Integer> characterCount = new HashMap<Character, Integer>();
        char[] characterArray = s.toCharArray();

        for(Character c : characterArray) {
            int newCount;
            Integer count = characterCount.get(c);
            if(count == null) {
                newCount = 1;
            }
            else {
                newCount = count + 1;
            }           
            characterCount.put(c, newCount);
        }

        return characterCount;      
    }

    /**
     * Convert hashmap into a string
     * @param map
     * @return
     */
    private static String createCompressedString(HashMap<Character, Integer> map) {

        String newString = "";
        for (Entry<Character, Integer> entry : map.entrySet()) {
            Character key = entry.getKey();
            Integer value = entry.getValue();

            newString += "" + key + "" + value;
        }

        return newString
    }
}

Answer 1

For better performance you should be able to eliminate the Hashmap and use a StringBuilder to count and build the compressed string in one operation:

public static String Compress(String input)
{
    StringBuilder sb = new StringBuilder();
    int i = 0;
    int limit = input.length() - 1;
    char next = '\0';
    while (i < limit)
    {
        int count = 1;
        next = input.charAt(i++);
        while (i <= limit && next == input.charAt(i))
        {
            count++;
            i++;
        }
        sb.append(next);
        sb.append(count);
    }
    if(i == limit)
    {
        sb.append(input.charAt(i));
        sb.append(1);
    }
    return sb.toString();
}

Caveat: This code won't work with the full unicode set

Answer 2

I think I can see overthink and rush. If the code presented was created with a run-of-the-mill IDE in 10 minutes, I don't think mess.

The first consequence of rush is, in my eyes, fatal:
How is anyone (say, a maintenance programmer) to know if this code works as specified if the code doesn't include its functional specification?
(Once you've put down the specification, check with the "customer" by any means.)

You included (scanty) doc comments for countCharacters() and createCompressedString() - one for the class or a method built from the two mentioned (the class's main business function - if I didn't have a problem with the name Compressor, it might be compress(), alternatively, the class extending UnaryOperator<String>, apply()) would have been essential.
Introducing the methods mentioned avoids open coding and allows giving a meaningful name to what they achieve. It shows determination to use procedural decomposition. (Passing around Maps/histograms instead of introducing an instance data member hints at less concern with OO analysis & design.)

I'm a bit at odds with the naming shown - starting with compress for something impossible to decompress. For brevity:
Histogram for Compressor; histogram for compressedString, countCharacters(), its characterCount, and newString; characters for characterArray - and I'd rather not name things used once where the name doesn't give the (non-apparent) interpretation (to an extent, newCount does in countCharacters()).

In combination with coding against interfaces and using conditional expressions:

class Histogram {
    /** For a string, prints each character and its occurrence count
     *  without any delimiters. */
    public static void main(String args []) {
        String randomString = 0 < args.length ? args[0] : "aaabccccc";

        String linearised = linearHistogram(text);
        System.out.println(text.length() < linearised.length()
            ? text : linearised);
    }

    /** Creates a <code>String</code> containing each character present
     *  in <code>String text</code> and its occurrence count,   
     *  without any delimiters. */
    static String linearHistogram(String text) {
        return histogram(histogram(text));
    }

    /** Creates <code>Map</code> from character to count of occurrence */
    static Map<Character, Integer> histogram(String s) {
        return histogram(s, new java.util.LinkedHashMap<>());
    }

    /** Adds character counts from <code>s</code> to <code>histogram</code> */
    static Map<Character, Integer>
    histogram(String s, Map<Character, Integer> histogram) {
        for(Character c : s.toCharArray()) {
            Integer count = histogram.get(c);
            histogram.put(c, count == null ? 1 : count + 1);
        }

        return histogram;      
    }

    /** Converts histogram from <code>Map</code> to <code>String</code>
     * @param histogram map char to count
     * @return <code>String</code> concatenation of characters and counts
     *  from <code>histogram</code>
     */
    static String histogram(Map<Character, Integer> histogram) {
        StringBuilder linearised = new StringBuilder();
        for (Entry<Character, Integer> entry : histogram.entrySet())
            linearised.append(entry.getKey()).append(entry.getValue());

        return linearised.toString();
    }
}

There's exactly one reason the doc comment of histogram(String s) doesn't claim The Map returned iterates in the order the characters are added: I don't know by heart what effect a put() has on an insertion-ordered LinkedHashMap if the key was mapped before (and wouldn't bother in 10 minutes of an interview).

Note the package visibility of methods. If I wanted methods usable from other packages, I'd define an interface.

---

You provide a helpful position to assume being tasked to code something in an interview:

it [is] more to assess how I would solve the problem as opposed to the code itself.

There are many things one could do, few in a 10 minute time-frame. (And some not to be caught doing, starting with ignoring tests or maintainability, or starting to optimise prematurely.)

A Java 8 buff might come up with better than

/** Creates a <code>Map</code> from element to occurrence count. */
public static <T> Map<T, ? extends Number> histogram(Stream<T> stream) {
    return stream.collect(
        Collectors.groupingBy(Function.<T>identity(),
            Collectors.counting()));
}
…
    histogram(text.codePoints().mapToObj(i -> i));

Try that if comfortable with streams, only. (If I was the interviewer, I'd ask about a streams solution if presented a non-streams one - and vice-versa.)