6
\$\begingroup\$

Yesterday in an online interview, the interviewer asked me this question:

If I give you a string, you have to return if a string is number or not. You are not allowed to use any parse function available.

This was my first online interview after a long long time, so I took way too much time in this question. I want to gather feedback about my solution and better ideas for the solution to this problem. You can ignore complex numbers for now.

public static boolean isNumber(String toTest) {
    boolean isNegativeFoundAlready = false;
    boolean isDecimalPointFoundAlready = false;
    for (int i=0; i < toTest.length(); i++) {
        if (!"0123456789-.".contains(new String(new char[]{toTest.charAt(i)}))) {
            return false;
        } else {
            if ('-' == toTest.charAt(i) && i != 0) {
                return false;
            }
            if ('-' == toTest.charAt(i) && (i == toTest.length() - 1)) {
                return false;
            }

            if ('-' == toTest.charAt(i) && isNegativeFoundAlready) {
                return false;
            }
            if ('-' == toTest.charAt(i)) {
                isNegativeFoundAlready = true;
            }
            if ('.' == toTest.charAt(i) && isDecimalPointFoundAlready) {
                return false;
            }
            if ('.' == toTest.charAt(i)) {
                isDecimalPointFoundAlready = true;
            }
            if ('.' == toTest.charAt(i) && (i == toTest.length() - 1)) {
                return false;
            }
        }
    }
    return true;
}

Test cases I ran:

    System.out.println("123 isNumber? " + isNumber("123"));
    System.out.println(".123 isNumber? " + isNumber(".123"));
    System.out.println("-.123 isNumber? " + isNumber("-.123"));
    System.out.println("-. isNumber? " + isNumber("-."));
    System.out.println(".- isNumber? " + isNumber(".-"));
    System.out.println("23.34.545 isNumber? " + isNumber("23.34.545"));
    System.out.println("- isNumber? " + isNumber("-"));
    System.out.println("-0 isNumber? " + isNumber("-0"));
    System.out.println("12$%^&*# isNumber? " + isNumber("12$%^&*#"));
\$\endgroup\$
  • 3
    \$\begingroup\$ can you clarify what a valid number is for you? Or what your test cases should return? Eg is .123 (or -0, -.123) a number? \$\endgroup\$ – tim Oct 17 '14 at 20:27
  • \$\begingroup\$ They all are valid, I too checked that with interviewer, he said its fine, consider them valid \$\endgroup\$ – daydreamer Oct 17 '14 at 20:28
  • 2
    \$\begingroup\$ What about "+123" or "1.23E45" ? \$\endgroup\$ – Martin R Oct 17 '14 at 20:40
  • \$\begingroup\$ We did not test \$\endgroup\$ – daydreamer Oct 17 '14 at 21:53
  • 1
    \$\begingroup\$ What is a 'parse' function? \$\endgroup\$ – rolfl Oct 17 '14 at 23:39
13
\$\begingroup\$

Instead of reading the output of those print statements, it's better write proper unit tests to verify your implementation:

@Test
public void testValidInteger() {
    assertTrue(isNumber("123"));
}

@Test
public void testValidStartsWithDecimal() {
    assertTrue(isNumber(".123"));
}

@Test
public void testValidNegativeStartsWithDecimal() {
    assertTrue(isNumber("-.123"));
}

@Test
public void testValidDecimal() {
    assertTrue(isNumber("1.23"));
}

@Test
public void testValidMinusZero() {
    assertTrue(isNumber("-0"));
}

Your implementation passes all these, which is good. I would add at least two more:

@Test
public void testValidEndsWithDecimal() {
    assertTrue(isNumber("123."));
}

@Test
public void testValidDecimalLooooong() {
    assertTrue(isNumber("1.2311111111111111111111111111111111111111111"));
}

The second passes but the first doesn't and maybe it should, no?

For testing cases of non-numbers:

@Test
public void testNotValid() {
    assertFalse(isNumber("-."));
    assertFalse(isNumber(".-"));
    assertFalse(isNumber("12.34.56"));
    assertFalse(isNumber("-"));
    assertFalse(isNumber("12$%^&*#"));
    assertFalse(isNumber("hello"));
    assertFalse(isNumber("   "));
    //assertFalse(isNumber(""));
}

It would be good to split these to individual cases as I did for the valid cases. I leave that for you as an exercise. I added some more cases here too, and unfortunately the one with empty string doesn't pass. I think that's a bug.

As per your implementation, it seems more complicated than it needs to be. Most importantly, I'm wondering if the interviewer would consider regular expressions as "parse function". If not, then the implementation can be simplified:

public static boolean isNumber(String toTest) {
    return toTest.matches("[+-]?(\\d*\\.?\\d+)|(\\d+\\.?\\d*)");
}

This passes all the above tests. To correct and simplify your implementation, it should not be terribly difficult to implement the logic of the regular expression.

\$\endgroup\$
  • 2
    \$\begingroup\$ 0xFF9900 isn't a number? \$\endgroup\$ – Funky Oct 17 '14 at 23:43
  • 1
    \$\begingroup\$ No, your RegEx isn't the smallest. "-?(\\d*\\.?\\d*)". There, I've beaten you by 20 characters. ;) \$\endgroup\$ – Hungry Blue Dev Oct 18 '14 at 7:02
  • 1
    \$\begingroup\$ @ambigram_maker Who said it's the smallest? :p Btw what you proposed doesn't work: it matches invalid strings like .. But I borrowed from your idea and improved my answer. Try to shorten it now! ;-) \$\endgroup\$ – janos Oct 18 '14 at 7:29
  • \$\begingroup\$ @TheKittyKat forty two is also a number. So is negyven ketto. Oh well... \$\endgroup\$ – janos Oct 18 '14 at 7:33
  • \$\begingroup\$ @janos Any String can be represented at a number. \$\endgroup\$ – Funky Oct 18 '14 at 7:36
8
\$\begingroup\$

Using flags in the loop usually signals the design problem. Right now you have 2 states; how many would you need to parse a float? Such problems stem from the desire to cram everything in one loop. A solution is to separate what is logically separated.

A number has sign, whole part, decimal point, fractional part in that order. Pretty much everything is optional, except that at least one of the "parts" should be present. The last condition can be rephrased as that combined length of "parts" is greater than zero. Now the algorithm boils down to 2 helper methods, parse_optional_character and parse_numerical_sequence, each returning an index of a first character it didn't recognize. In pseudocode,

boolean isNumber(String s)
{
    int start = 0;
    int digits = 0;
    int end = 0;

    start = parse_optional_character('-', s, end);

    end = parse_numerical_sequence(s, i, start);
    digits += end - start;

    start = parse_optional_character('.', s, end);

    end = parse_numerical_sequence(s, i, start);
    digits += end - start;

    return ((end == s.length()) && (digits > 0));
}
\$\endgroup\$
  • \$\begingroup\$ +1, but where does i in parse_numerical_sequence(s, i, ...)come from? \$\endgroup\$ – ComFreek Oct 18 '14 at 17:25
  • \$\begingroup\$ @ComFreek You would have to write one of course \$\endgroup\$ – vnp Oct 18 '14 at 19:37
6
\$\begingroup\$

@janos already gave you great advise about unit tests and using regex, but assuming that you cannot use them in an interview, here are some more comments:

Long variable names

I really like descriptive variable names, and yours are quite clear. But I think foundNegative and foundDecimal are just as expressive, but shorter.

Extract strings to static fields

It's always good to extract repeating constants to fields. In this case it would be especially good for the decimal point, as a lot of languages do not use ., but instead use , for numbers; so a field would make later adaption a lot easier.

Early return

You can save one level of nesting by just removing your else, it's not needed since you are returning in the if anyways.

char to string

Character.toString(toTest.charAt(i)) would be simpler than new String(new char[]{toTest.charAt(i)}) to make a char to a string.

repeated call to charAt

charAt is just a simple array access, but still, to save repeated function calls, I would save it in a local variable, as you are accessing it quite often.

Combine if statements

You have quite a lot of if statements, a lot of which could be combined. For example:

        if (currentChar == '-') {
            if (isNegativeFoundAlready || (i != 0) || (i == toTest.length() - 1)) {
                return false;
            } else {
                isNegativeFoundAlready = true;
            }
        } else if (currentChar == '.') {
            if (isDecimalPointFoundAlready || (i == toTest.length() - 1)) {
                return false;
            } else {
                isDecimalPointFoundAlready = true;
            }
        }

or:

        if (currentChar == '-'
                && (isNegativeFoundAlready
                || (i != 0)
                || (i == toTest.length() - 1))) {
            return false;
        } else if (currentChar == '-' ) {
            isNegativeFoundAlready = true;
        } else if (currentChar == '.' && (isDecimalPointFoundAlready || (i == toTest.length() - 1))) {
            return false;
        } else if (currentChar == '.') {
            isDecimalPointFoundAlready = true;
        }

Simplifiy negative check

If you add this to the top of your method:

    if (toTest.startsWith("-")) {
        toTest = toTest.substring(1, toTest.length()); // remove starting "-"
        System.out.println(toTest);
    }
    if (toTest.contains("-") || toTest.isEmpty()) {
        return false; // cannot have more "-" and empty string is not a number
    }

you would already take care of everything related to negative numbers and could remove all the - checks from the loop.

Something similar could be done for the ., but I think it looks a bit complicated:

public static boolean isNumber(String toTest) {
    if (toTest.startsWith("-")) {
        toTest = toTest.substring(1, toTest.length()); // remove starting "-"
    }
    if (toTest.contains("-") || toTest.isEmpty()) {
        return false; // cannot have more "-" and empty string is not a number
    }

    String[] parts = toTest.split(".");
    if (parts.length == 0) {
        if (toTest.startsWith(".")) { // special case for ".123"
            toTest = toTest.substring(1, toTest.length());
        }
        if (toTest.isEmpty()) {
            return false;
        }
        return isSimpleNumber(toTest);
    } else if (parts.length == 2) {
        return isSimpleNumber(parts[0]) && isSimpleNumber(parts[1]);
    } else {
        return false; // more than one "."
    }
}

private static boolean isSimpleNumber(String number) {
    for (int i = 0; i < number.length(); i++) {
        if (!"0123456789".contains(Character.toString(number.charAt(i)))) {
            return false;
        }
    }
    return true;
}
\$\endgroup\$
5
\$\begingroup\$

As evidenced by the comments, we don't think that you have posted a question that clearly specifies what should and shouldn't be considered a valid number. In addition to Scientific Notation, I'd ask whether "六萬七千" or "MDXVI" counts as a number. How about a European-style "," as a decimal point? How about thousands separators? How about an explicit leading positive sign? Can there be a space between the negative sign and the digits? What about gratuitous leading/trailing whitespace? In an interview, you should engage your interviewer in the same way to seek clarification. (Poke hard enough, and you might even get your interviewer to do part of the work for you!)

I'd also like to know what is considered a parse function. new BigDecimal(toTest) seems like it should be off-limits, but can you use a regular expression matcher? That could reduce the function down to one line.

By inspection, your function is incorrect: an empty string would cause the entire for-loop to be skipped, and isNumber("") would return true.

if (!"0123456789-.".contains(new String(new char[]{toTest.charAt(i)}))) is rather monstrous. A typical way to test that is

if ("0123456789-.".indexOf(toTest.charAt(i)) < 0)

Inside the for-loop, you seem to be obsessed with testing for the negative sign and decimal point. I'd pull those special cases out of the loop.

Keeping to the spirit of a brute-force approach, I'd write something like this:

public static boolean isNumber(String toTest) {
    if (toTest == null || toTest.isEmpty()) {
        return false;
    }

    int dots = 0, digits = 0;
    for (int i = toTest.startsWith("-") ? 1 : 0; i < toTest.length(); i++) {
        switch (toTest.charAt(i)) {
          case '0': case '1': case '2': case '3': case '4':
          case '5': case '6': case '7': case '8': case '9':
            digits++;
            break;
          case '.':
            dots++;
            break;
          default:
            return false;    // Illegal character
        }
    }
    return dots <= 1 && digits > 0;
}

It's not the most efficient solution, but it is short and easy to understand. Those are good attributes to aim for in a stressful interviewing situation.

\$\endgroup\$
  • 1
    \$\begingroup\$ your solution is missing a lot of the corner cases mentioned in the question (eg ., .., -, -.). You could add a flag to the loop checking if there is at least one character between 0 and 9 present to catch these. \$\endgroup\$ – tim Oct 18 '14 at 8:31
  • 1
    \$\begingroup\$ @tim Unfortunately, checking for the presence of at least one digit leads to quite a different approach! \$\endgroup\$ – 200_success Oct 18 '14 at 8:48
3
\$\begingroup\$

Considering the ASCII-value of a character, you could make use of the simple fact, that in order to convert a character to an integer, you could subtract '0':

'0'-'0'=0; '1'-'0'=1 ... and so on.

Every result of that subtraction has to be greater/equals 0 and less than 10. While parsing, there are some additional corner-cases:

  1. a - at the beginning is allowed (so we could skip it)
  2. exactly one decimal point should be allowed anywhere after the -
  3. any occurring - or a second point lead to a shortcut to false

I came up with this:

private static boolean isNumber(String string) {
    int i = 0;
    boolean decimalpoint = false;
    boolean anyNumber = false;
    if (string == null || string.isEmpty()) return false;
    if (string.charAt(i) == '-') i++;
    for (; i < string.length(); i++) {
        if (string.charAt(i) == '.') {
            if (decimalpoint) return false;
            decimalpoint = true;
        } else if (string.charAt(i) - '0' > 9 || string.charAt(i) - '0' < 0) {
            return false;
        } else {
            anyNumber = true;
        }
    }
    return anyNumber;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Unfortunately, the code you show as an example here has some issues: It parses ., -., -, and the empty string ("") as numbers. Typically, i++ should be used rather than i+=1. decimalpoint should probably be a boolean. You use inconsistant spacing after your if's (if( dec...). Your check in the loop for if there is an extra - sign is useless, because the between 0 and 9 check would catch - signs. result is never set except when it is created: you should either set result = false; instead of return false;, or eliminate result and just return true;`. \$\endgroup\$ – g.rocket Oct 18 '14 at 2:12

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.