4
\$\begingroup\$

I have solved the problem "Substitute" at Topcoder.

A simple, easy to remember system for encoding integer amounts can be very useful. For example, dealers at flea markets put the information about an item on a card that they let potential buyers see. They find it advantageous to encode the amount they originally paid for the item on the card. A good system is to use a substitution code, in which each digit is encoded by a letter. An easy to remember 10-letter word or phrase, the key, is chosen. Every '1' in the value is replaced by the first letter of the key, every '2' is replaced by the second letter of the key, and so on. Every '0' is replaced by the last letter of the key. Letters that do not appear in the key can be inserted anywhere without affecting the value represented by the code.. This helps to make the resulting code much harder to break (without knowing the key). Create a class Substitute that contains the method getValue that is given the Strings key and code as input and that returns the decoded value.

I started studying Big O notation and I think the complexity of my program is \$O(n^2)\$. How can I make my program more efficient and clean? Can I make it \$O(n)\$?

     public class Substitute {

    public int getValue(String key, String code) {
        String s = "";
        for (int i = 0; i < code.length(); i++) {
            for (int j = 0; j < key.length(); j++) {
                int x = key.indexOf(code.charAt(i)) + 1;
                if (code.charAt(i) == key.charAt(j)) {
                    if (x >= 10) {
                        x = 0;
                    }
                    s = s + x;
                }
            }
        }
        return Integer.parseInt(s);
    }
}
\$\endgroup\$
6
\$\begingroup\$

Analysis

You've picked an interesting problem about which to ask about Big-O complexity. The problem is, you're being sloppy about what you call "n". This function has two inputs: a key of length 10 and a code of variable length. Let's say that m is the length of key (which is 10) and n is the length of code.

The outer i loop executes n times. For each of those, outer loops, the inner j loop executes m times. For each inner loop, key.indexOf() — an O(m) operation — is called; then we might do s = s + x — an O(n) operation. Finally, Integer.parseInt(s) is an operation that I would expect to be O(n).

The complexity, therefore, is O(nm (m + n) + n). If we consider m to be constant, that simplifies to O(n2).

However, the "silliest" part of the code is s = s + x. That O(n) operation could be O(1) if you had used a StringBuilder instead of repeated string concatenation. With a StringBuilder, your function would become O(n).

Perspective

It's important to keep a sense of perspective, though. Big-O complexity is useful for getting a feel for how well an algorithm scales to handle large input. For example, it can help you estimate whether an algorithm that analyzes a million DNA bases will finish in seconds or hours.

On the other hand, Big-O analysis is nearly useless for predicting the performance of "small" problems like this one. The challenge states that n is at most 9 — and in any case, a result larger than 9 digits would overflow an int. It is very possible that an algorithm that Big-O analysis predicts will scale well could actually perform worse than a simpler algorithm that in theory should scale poorly. For example, the time it takes to initialize an "efficient" data structure could exceed the time it takes to do a naïve String.indexOf() search.

Suggested solution

Building a string and then parsing it as an integer is inefficient. Why not just compute the integer as you go?

public int getValue(String key, String code) {
    int value = 0;
    for (int i = 0; i < code.length(); i++) {
        int pos = 1 + key.indexOf(code.charAt(i));
        if (pos == 10) {
            value *= 10;
        } else if (pos > 0) {
            value = 10 * value + pos;
        }
    }
    return value;
}
\$\endgroup\$
  • \$\begingroup\$ Note that @mdfst13 and I have picked opposite conventions for labeling m and n. \$\endgroup\$ – 200_success Jun 12 '16 at 14:38
3
\$\begingroup\$

Your program is something like \$O(m \cdot n^2)\$ where \$m\$ is the length of the code and \$n\$ is the length of the key. This is because the indexOf method is itself \$O(n)\$. However, it's possible to solve this in \$O(m+n)\$ time complexity.

class Substitute {

    private static final int ALPHABET_SIZE = 26;
    private static final int BASE = 10;

    public static int getValue(String key, String code) {
        Integer[] alphabetIndexes = new Integer[ALPHABET_SIZE];
        for (int i = 0; i < key.length(); i++) {
            // the 0 character is last rather than first
            // so use the ternary operator to differentiate
            alphabetIndexes[key.charAt(i) - 'A'] = (i + 1 < BASE) ? i + 1 : 0;
        }

        int result = 0;
        for (char c : code.toCharArray()) {
            Integer digit = alphabetIndexes[c - 'A'];
            if (digit != null) {
                result *= BASE;
                result += digit;
            }
        }

        return result;
    }

}

This works by first building an array holding the indexes in the key of each letter. This can be done in time complexity \$O(n)\$ because we have to look at each character in the key only once.

Next we scan the code and convert each character into numeric digits. Note that the original code converted numeric digits into characters to build a string and then used the built-in functionality to convert the string into an integer. This version saves both building the string and parsing it at the expense of building the integer directly. This has \$O(m)\$ time complexity.

TopCoder design flaws

TopCoder sticks you with a bunch of design decisions that they made. These certainly aren't your fault, but I don't want to leave the impression that they make for good code.

First, there's the name getValue. By convention, getFoo methods in Java return this.foo (i.e. this.value in this case). They don't decode a string. A much better name for this would be decode.

Second, it's silly to rebuild alphabetIndexes each time we call the method. Much better would be to build it once and then reuse it each time we decode a message.

Third, why build keys with the 0 character at the end rather than the beginning? Either way needs to be documented, but putting the 0 at the beginning makes for simpler code. Unless there is some compelling reason to put it at the end, why not do the simple thing?

Here's how I would actually write it if we were able to change the requirements:

class Substitute {

    private static final int ALPHABET_SIZE = 26;
    private static final int BASE = 10;

    private final Integer[] alphabetIndexes = new Integer[ALPHABET_SIZE];

    public Substitute(String key) {
        for (int i = 0; i < key.length(); i++) {
            alphabetIndexes[key.charAt(i) - 'A'] = i;
        }
    }

    public int decode(String code) {
        int result = 0;
        for (char c : code.toCharArray()) {
            Integer digit = alphabetIndexes[c - 'A'];
            if (digit != null) {
                result *= BASE;
                result += digit;
            }
        }

        return result;
    }

    public String encode(int value) {
        StringBuilder code = new StringBuilder();

        while (value > 0) {
            code.append(key.charAt(value % BASE));
            value /= BASE;
        }

        return code.reverse().toString();
    }

}
\$\endgroup\$
  • \$\begingroup\$ Wouldn't ALPHABET_SIZE be better defined to be 'Z' - 'A' + 1? \$\endgroup\$ – Jaime Jun 11 '16 at 18:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.