Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
0
of 0 vote

Tried to solve it with a complex logic and it kind of worked but there were too many raise conditions and the code wasn't readable at all.
Using the Dijkstra 2 stack algorithm it is pretty elegant.

public class EvaluateMathematicalExpression {
    Map<Character, Integer> variables;

    public EvaluateMathematicalExpression(Map<Character, Integer> variables) {
        this.variables = variables;                
    }

    public static void main(String[] args){
        Map<Character, Integer> variables = new HashMap<>();
        List<String> expressions = new ArrayList<>();

        Scanner scan = new Scanner(System.in);

        System.out.println("enter number of variables:");
        int variablesNumber = scan.nextInt();
        scan.nextLine();

        System.out.println("now the variables: ");
        for(int i = 0; i<variablesNumber;i++){
            String line = scan.nextLine();
            String[] varVal = line.split("=");
            variables.put(varVal[0].charAt(0),Integer.valueOf(varVal[1]));
        }

        System.out.println("--------------");
        System.out.println("enter number of expressions:");
        int expressionsNumber = scan.nextInt();
        scan.nextLine();

        System.out.println("and the expressions: ");
        for(int i = 0; i<expressionsNumber;i++) {
            expressions.add(scan.nextLine());
        }


        EvaluateMathematicalExpression eme = new EvaluateMathematicalExpression(variables);

        for(String line : expressions){
            try{
                System.out.println("Evaluation of " + line + ": " + eme.evaluateDijkstra(line));
            } catch (Exception e){
                System.out.println("Compile error for " + line);
            }

        }

    }

    public int evaluateDijkstra(String expression){
        char[] chars = expression.toCharArray();

        Stack<Integer>    vals = new Stack<>();
        Stack<Character> ops  = new Stack<>();

        for(int i = 0; i<chars.length;i++){
            char currCh = chars[i];
            if(currCh == ' ') continue;

            if(isSign(currCh)){

                if(!ops.empty() && shouldCalcPrev(currCh, ops.peek())){
                    while(!ops.empty() && ops.peek() != null) {
                        char sign = ops.pop();
                        int right = vals.pop();
                        int left = vals.pop();
                        vals.push(calc(left, right, sign));
                    }
                    ops.push(currCh);
                } else {
                    ops.push(currCh);
                }
            } else {
                Integer val = variables.get(currCh);
                if(val == null){
                    throw new IllegalArgumentException("Unexpected character " + currCh);
                }
                vals.push(val);
            }
        }

        while(!ops.empty()){
            char sign = ops.pop();
            int right = vals.pop();
            int left  = vals.pop();
            vals.push(calc(left,right,sign));
        }

        return vals.pop();
    }

    public int calc(int left, int right, char ch){
        if(ch == '+'){
            return left + right;
        } else if(ch == '-'){
            return left - right;
        } else if(ch == '*'){
            return left * right;
        } else if(ch == '/'){
            return left / right;
        } else {
            throw new IllegalArgumentException("Compilation error, sign expected");
        }
    }

    /**
     * "*" and "/" get higher priority, if we reached to "+" and "-", we can(and should) calculate previous operations.
     * @param sign
     * @param prevSign
     * @return
     */
    public boolean shouldCalcPrev(char sign, Character prevSign){
        if(prevSign == null){
            return false;
        }
        if( (sign == '+' || sign == '-') && (prevSign == '*' || prevSign == '/')) return true;
        return false;
    }

    public boolean isSign(char ch){
        if(ch == '-' || ch == '+' || ch == '*' || ch == '/') return true;
        return false;
    }

}

- miki October 30, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dijkstra's shunting yard algorithm is needed if we have to support parentheses. this problem is a special case: an expression only has binary operators and just 2 levels of precedence. this is a simpler solution to this problem:

public class EvaluateExpression {
    private static abstract class Node {
        Node left;
        Node right;
    }
    private static class Operator extends Node {
        char op;
        Operator (char op) {
            super();
            this.op = op;
        }
    }
    private static class Operand extends Node {
        int value;
        Operand(int value) {
            super();
            this.value = value;
        }
    }

    private final Map<Character, Integer> idToValue;

    //precedence: usual (* and / higher than + and -)
    //associativity: usual (left to right)
    // assume: operands are single letters
    // assume: integer arithmatic (no floating points)
    // assume: expression contains operands, operators and spaces only.
    public EvaluateExpression(List<String> assignments) {
        this.idToValue = new HashMap<>();
        for (String assignment: assignments) {
            assignment = assignment.replaceAll(" ", "");
            String[] parts = assignment.split("=");
            char id = parts[0].charAt(0);
            int value = Integer.parseInt(parts[1]);
            idToValue.put(id, value);
        }
    }

    private static int skipSpaces(String expression, int i) {
        for (; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c != ' ') {
                break;
            }
        }

        return i;
    }

    public int parseExpression(String expression) {
        //represent the expression as a list of operands and operators
        Node head = null;
        Node tail = null;
        boolean expectOperand = true;
        for (int i = skipSpaces(expression, 0); i < expression.length(); i++, i = skipSpaces(expression, i)) {
            char c = expression.charAt(i);
            if (expectOperand) {
                if (!idToValue.containsKey(c)) {
                    throw new IllegalArgumentException();
                }
                int value = idToValue.get(c);
                Node operand = new Operand(value);
                if (head == null) {
                    head = operand;
                    tail = operand;
                } else {
                    operand.left = tail;
                    tail.right = operand;
                    tail = operand;
                }
                expectOperand = false;
            } else {
                if ((c != '+') && (c != '-') && (c != '*') && (c != '/')) {
                    throw new IllegalArgumentException();
                }
                Node operator = new Operator(c);
                operator.left = tail;
                tail.right = operator;
                tail = operator;
                expectOperand = true;
            }
        }

        if (expectOperand) {
            throw new IllegalArgumentException("compilation error");
        }

        //evaluate all * and /
        Set<Character> operatorsToEvaluate = new HashSet<>();
        operatorsToEvaluate.add('/');
        operatorsToEvaluate.add('*');
        head = evaluateLeftToRight(head, operatorsToEvaluate);

        //evaluate all + and -
        operatorsToEvaluate.remove('/');
        operatorsToEvaluate.remove('*');
        operatorsToEvaluate.add('+');
        operatorsToEvaluate.add('-');
        head = evaluateLeftToRight(head, operatorsToEvaluate);

        return ((Operand)head).value;
    }

    private int evaluate(Operator operator) {
        int operand1 = ((Operand)operator.left).value;
        int operand2 = ((Operand)operator.right).value;
        char op = operator.op;
        int value;
        switch(op) {
            case '+': value = operand1 + operand2; break;
            case '-': value = operand1 - operand2; break;
            case '*': value = operand1 * operand2; break;
            case '/': value = operand1 / operand2; break;
            default:
                throw new IllegalArgumentException();
        }

        return value;
    }

    private Node evaluateLeftToRight(Node head, Set<Character> operatorsToEvaluate) {
        for (Node node = head; node != null; node = node.right) {
            if (!(node instanceof Operator)) {
                continue;
            }
            Operator operator = (Operator)node;
            if (!operatorsToEvaluate.contains(operator.op)) {
                continue;
            }
            int value = evaluate(operator);
            Operand operand = new Operand(value);
            operand.left = operator.left.left;
            operand.right = operator.right.right;
            if (operator.left.left != null) {
                operator.left.left.right = operand;
            } else {
                head = operand;
            }
            if (operator.right.right != null) {
                operator.right.right.left = operand;
            }
            node = operand;
        }

        return head;
    }

    private static void test(EvaluateExpression evaluator, String expression, int expected) {
        int actual = evaluator.parseExpression(expression);
        assert (actual == expected);
    }

    private static void negativeTest(EvaluateExpression evaluator, String expression) {
        try {
            evaluator.parseExpression(expression);
        } catch (IllegalArgumentException e) {
            return; //success
        }

        assert (false); //fail
    }

    private static void test() {
        List<String> assignments = Arrays.asList("a = 3", "b=8", " c =5", "d = 6 ");
        EvaluateExpression evaluator = new EvaluateExpression(assignments);

        test(evaluator, "a + b + c", 16);
        test(evaluator, "a + b - c", 6);
        test(evaluator, "b - a * c", -7);
        test(evaluator, "d / a + c - b", -1);
        test(evaluator, "a + b * c - d", 37);
        test(evaluator, "a*b*c - d", 114);
        test(evaluator, "b", 8);
        test(evaluator, "b + b", 16);
        test(evaluator, "b / b", 1);
        test(evaluator, "b / b / b", 0);
        test(evaluator, "b / a / b", 0);
        test(evaluator, "b / a + d", 8);
        test(evaluator, "c-a", 2);
        test(evaluator, "c-a ", 2);
        test(evaluator, "c- a ", 2);
        test(evaluator, "c -a ", 2);
        test(evaluator, " c-a", 2);
        test(evaluator, " c -   a", 2);

        negativeTest(evaluator, "");
        negativeTest(evaluator, " ");
        negativeTest(evaluator, " x ");
        negativeTest(evaluator, "a + * b");
        negativeTest(evaluator, "a + x");
        negativeTest(evaluator, "a + b * c /");
        negativeTest(evaluator, "-a + b * c");

        EvaluateExpression evaluator2 = new EvaluateExpression(Arrays.asList("a=1", "b=2", "c=2"));
        test(evaluator2, "a*b + a*c + b*c", 8);
        test(evaluator2, "a*c - b/c + c*c", 5);

        EvaluateExpression evaluator3 = new EvaluateExpression(Arrays.asList("g=2", "p=3", "t=1", "w=2"));
        test(evaluator3, "g + p*t - w*p", -1);
        test(evaluator3, "t - g + t - w", -2);
        negativeTest(evaluator3, "e + t*t -m");
    }

    public static void main(String[] args) {
        test();
    }

- Soubhik December 14, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More