Pocketgems Interview Question for Software Engineer / Developers


Team: Backend
Country: United States
Interview Type: Phone Interview




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

1. Convert infix expression to postfix expression.
a ? (b ? c : d) : e => abcd?e?
time: O(N), space: O(N)

2. Evaluate postfix expression on stack.
time: O(N), space: O(N)

1.

String infixToPostfix(String expr){

        StringBuilder res = new StringBuilder();
        Deque<Character> ops = new ArrayDeque<>();

        for( int i = 0;  i < expr.length(); i++ ){
            char ch = expr.charAt(i);

            if( ch == '?' || ch == '(' ){
                ops.add(ch);
            }
            else if( ch == ')' ){

                notEmpty(ops, "Incorrect expression passed: " + expr);
                char opCh = ops.poll();

                while( opCh != '(' ){
                    res.append(opCh);
                    notEmpty(ops, "Incorrect expression passed: " + expr);
                    opCh = ops.poll();
                }
            }
            else if( Character.isAlphabetic(ch) ){
                res.append(ch);
            }
        }

        while( ! ops.isEmpty() ){
            res.append(ops.poll());
        }

        return res.toString();
    }

2.

static Node createNodeFromPostfixExpression(String postfixExp){

            Deque<Node> evalStack = new ArrayDeque<>();


            for( int i =0; i < postfixExp.length(); i++ ){
                char ch = postfixExp.charAt(i);
                if( ch == '?' ) {

                    hasEnoughElements(evalStack, 3, "Incorrect postfix expression: '" + postfixExp + "'");
                    Node falseCond = evalStack.pop();
                    Node trueCond = evalStack.pop();
                    Node cond  = evalStack.pop();

                    cond.falseCondition = falseCond;
                    cond.trueCondition = trueCond;

                    evalStack.push(cond);
                }
                else {
                    evalStack.push(new Node(ch));
                }
            }

            return evalStack.pop();
        }

- m@}{ July 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question is to print / convert the input expression into provided tree structure, not to evaluate the expression

- understand August 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is to use recursive method, under one level when the left child or the right child of the root is a (...) parenthesis expression, then this method is called again recursively. Then, at the same level after the left child(noticed: this case does not happen to right child),
I go through the parenthesis expression represented by the left child. When will I stop? Well, I use a stack to store every '(' left parenthesis I encountered, and if I met a ')' parenthesis, I pop an element and until stack is empty. Where is the place where the right child of the current level been placed.
The code is like:

public static TreeNode generate(int start, String str) {
		if (str == null || start > str.length() - 1) return null;
		
		int pointer = start;
		TreeNode root = new TreeNode(str.charAt(pointer));
		pointer += 2;
		if (str.charAt(pointer) == '(') {
			root.left = generate(pointer + 1, str);
			Stack<Character> stack = new Stack<Character>();
			stack.push('(');
			while (!stack.isEmpty()) {
				char temp = str.charAt(++pointer);
				if (temp == '(') {
					stack.push(temp);
				} else if (temp == ')') {
					stack.pop();
				} else {
					// do nothing
				}
			}
			// now pointer points to ')'
		} else {
			root.left = new TreeNode(str.charAt(pointer));
		}
		
		pointer += 2;
		if (str.charAt(pointer) == '(') {
			root.right = generate(pointer + 1, str);
			Stack<Character> stack = new Stack<Character>();
			stack.push('(');
			while (!stack.isEmpty()) {
				char temp = str.charAt(++pointer);
				if (temp == '(') {
					stack.push(temp);
				} else if (temp == ')') {
					stack.pop();
				} else {
					// do nothing
				}
			}
			// now pointer points to ')'
		} else {
			root.right = new TreeNode(str.charAt(pointer));
		}
		
		return root;
	}

The runtime is tricky, at the first glance, it is easy to say it is O(n^2). But thinking more, I would say it is closed to O(nlogn). Anyone have a better idea?

- yijiema1991 January 13, 2015 | 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