Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
1. check whether it is a valid float number:
^\\s*[+-]?\\d+\\.?(\\d+)?([eE][+-]?\\d+)?\\s*$
^\\s*[+-]?\\.\\d+([eE][+-]?\\d+)?\\s*$
2. extract the integer part A, the decimal part B and the part after e/E C from the regular expression, then merge them together Result = (A + B/1e(length of B)) * 1eC
Not all questions have to be algorithm intensive.
For good or bad, Some interviewers are looking for
1) Whether you are handling all corner cases
2) Whether you are reducing duplication of code ( we can parse integral and decimal part by some common code )
3) Whether you are using descriptive variables names ( "decimalPart" instead of "d" )
It is a very good question to test if someone has heard about regular expressions - or even about more formal language theory!
And if yes does he/she have an idea how to write a program to process them - some knowledge of finite automata and their implementation.
Or just test if someone can use a regex library in a given environment.
Or just test if someone can really capture "float" as a specification. And how well he is handling the wrong-format cases - for testing jobs this is a brilliant question to ask!
Assuming I have no regular expression library to use:
enum States { INIT, SIGN, EXPSIGN, MANTISSA_BEFORE, MANTISSA_DEC, MANTISSA_AFTER,
EXP, EXP_BEFORE, EXP_DEC, EXP_AFTER };
public static double atof(String s) {
double mantissa = 0;
double exp = 1;
int sign = 1;
int mdcount = 0;
int expdcount = 0;
int expsign = 1;
States state = States.INIT;
for (int i=0; i<s.length(); ++i) {
char c = s.charAt(i);
switch (state) {
case INIT:
if (Character.isWhitespace(c))
continue;
if (c == '+') {
state = States.SIGN;
sign = 1;
} else if (c == '-') {
state = States.SIGN;
sign = -1;
} else if (Character.isDigit(c)) {
mantissa = Character.digit(c, 10) + (mantissa * 10);
state = States.MANTISSA_BEFORE;
} else if (c == '.') {
state = States.MANTISSA_DEC;
} else {
throw new RuntimeException();
}
break;
case SIGN:
if (Character.isDigit(c)) {
mantissa = Character.digit(c, 10) + (mantissa * 10);
state = States.MANTISSA_BEFORE;
} else if (c == '.') {
state = States.MANTISSA_DEC;
} else {
throw new RuntimeException();
}
break;
case MANTISSA_BEFORE:
if (Character.isDigit(c)) {
mantissa = Character.digit(c, 10) + (mantissa * 10);
state = States.MANTISSA_BEFORE;
} else if (c == '.') {
state = States.MANTISSA_DEC;
} else if (c == 'e') {
state = States.EXP;
exp = 0;
} else {
throw new RuntimeException();
}
break;
case MANTISSA_DEC:
if (Character.isDigit(c)) {
mantissa = (Character.digit(c, 10)*1.0 * Math.pow(10, -1 * ++mdcount)) + (mantissa);
state = States.MANTISSA_AFTER;
} else {
throw new RuntimeException();
}
break;
case MANTISSA_AFTER:
if (Character.isDigit(c)) {
mantissa = (Character.digit(c, 10)*1.0 * Math.pow(10, -1 * ++mdcount)) + (mantissa);
state = States.MANTISSA_AFTER;
} else if (c == 'e') {
state = States.EXP;
exp = 0;
} else {
throw new RuntimeException();
}
break;
case EXP:
if (Character.isDigit(c)) {
exp = Character.digit(c, 10) + (exp * 10);
state = States.EXP_BEFORE;
} else if (c == '.') {
state = States.EXP_DEC;
} else if (c == '-') {
expsign = -1;
state = States.EXPSIGN;
} else if (c == '+') {
state = States.EXPSIGN;
expsign = +1;
} else {
throw new RuntimeException();
}
break;
case EXPSIGN:
if (Character.isDigit(c)) {
exp = Character.digit(c, 10) + (exp * 10);
state = States.EXP_BEFORE;
} else if (c == '.') {
state = States.EXP_DEC;
} else {
throw new RuntimeException();
}
break;
case EXP_BEFORE:
if (Character.isDigit(c)) {
exp = Character.digit(c, 10) + (exp * 10);
state = States.EXP_BEFORE;
} else if (c == '.') {
state = States.EXP_DEC;
} else {
throw new RuntimeException();
}
break;
case EXP_DEC:
if (Character.isDigit(c)) {
exp = Character.digit(c, 10) / Math.pow(10, 1.0/expdcount++) + (exp);
state = States.EXP_AFTER;
} else {
throw new RuntimeException();
}
break;
case EXP_AFTER:
if (Character.isDigit(c)) {
exp = Character.digit(c, 10) / Math.pow(10, 1.0/expdcount++) + (exp);
state = States.EXP_AFTER;
} else {
throw new RuntimeException();
}
break;
default:
throw new RuntimeException();
}
}
return sign*Math.pow(mantissa, expsign*exp);
}
1. detect delimiter "e" and split to left and right parts
- peter tang October 14, 20122. then two parts are parsed as
* detect the starting character with "+"/"-"
* call atoi() on the right part
* detect delimiter "." on the left part and split into two sections
* use atoi() on two sections
* the 2nd section times power(10, - 2ndSection.size());
* Then combine them together including the sign.