Google Interview Question for Software Engineer / Developers


Country: United States




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

public class BinaryExpressionTree
{
   enum Operator
   {
      add(true), subtract(false), multiply(true), divide(false);

      private boolean symmetric;

      private Operator(boolean symmetric)
      {
         this.symmetric = symmetric;
      }

      boolean compare(OperatorNode a, OperatorNode b)
      {
         if (a.left.isEqual(b.left) && a.right.isEqual(b.right))
            return true;

         if (symmetric)
         {
            return (a.left.isEqual(b.right) && a.right.isEqual(b.left));
         }
         return false;
      }
   }

   abstract class Node
   {
      abstract boolean isEqual(Node other);
   }

   class OperatorNode extends Node
   {
      Operator operator;
      Node left;
      Node right;

      @Override
      boolean isEqual(Node other)
      {
         if (!(other instanceof OperatorNode))
         {
            return false;
         }

         OperatorNode n = (OperatorNode) other;
         if (operator != n.operator)
         {
            return false;
         }
         return operator.compare(this, n);
      }
   }

   class LeafNode extends Node
   {
      String value;

      @Override
      boolean isEqual(Node other)
      {
         if (!(other instanceof LeafNode))
         {
            return false;
         }

         LeafNode n = (LeafNode) other;
         return value.equals(n.value);
      }
   }

   boolean compare(Node a, Node b)
   {
      return a.isEqual(b);
   }
}

- Anonymous March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BinaryExpressionTree
{
   enum Operator
   {
      add(true), subtract(false), multiply(true), divide(false);

      private boolean symmetric;

      private Operator(boolean symmetric)
      {
         this.symmetric = symmetric;
      }

      boolean compare(OperatorNode a, OperatorNode b)
      {
         if (a.left.isEqual(b.left) && a.right.isEqual(b.right))
            return true;

         if (symmetric)
         {
            return (a.left.isEqual(b.right) && a.right.isEqual(b.left));
         }
         return false;
      }
   }

   abstract class Node
   {
      abstract boolean isEqual(Node other);
   }

   class OperatorNode extends Node
   {
      Operator operator;
      Node left;
      Node right;

      @Override
      boolean isEqual(Node other)
      {
         if (!(other instanceof OperatorNode))
         {
            return false;
         }

         OperatorNode n = (OperatorNode) other;
         if (operator != n.operator)
         {
            return false;
         }
         return operator.compare(this, n);
      }
   }

   class LeafNode extends Node
   {
      String value;

      @Override
      boolean isEqual(Node other)
      {
         if (!(other instanceof LeafNode))
         {
            return false;
         }

         LeafNode n = (LeafNode) other;
         return value.equals(n.value);
      }
   }

   boolean compare(Node a, Node b)
   {
      return a.isEqual(b);
   }
}

- Anonymous March 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package google;

import google.ExpressionTreeEvaluation.ExpressionTreeNode.Operator;

public class ExpressionTreeEvaluation {
	public static class ExpressionTreeNode {
		static enum Operator {
			Add, Subtract, Multiply, Divide;

			public int performOperation(int operand1, int operand2) {
				switch (this) {
				case Add:
					return operand1 + operand2;
				case Subtract:
					return operand1 - operand2;
				case Multiply:
					return operand1 * operand2;
				default:
					return operand1 / operand2;
				}
			}

		}

		public Boolean isLeaf;
		public Operator valIfOperator;
		public Integer valIfInteger;

		ExpressionTreeNode left;
		ExpressionTreeNode right;

		public ExpressionTreeNode(boolean isLeaf, Operator valIfOperator, Integer valIfInteger) {
			this.isLeaf = isLeaf;
			if (isLeaf == true && valIfOperator == null && valIfInteger != null) {
				this.valIfInteger = valIfInteger;
			} else if (isLeaf == false && valIfOperator != null && valIfInteger == null) {
				this.valIfOperator = valIfOperator;
			} else {
				throw new IllegalArgumentException();
			}

			left = null;
			right = null;
		}

	}

	public static void main(String args[]) {
		ExpressionTreeNode n1 = new ExpressionTreeNode(false, Operator.Add, null);
		ExpressionTreeNode n2 = new ExpressionTreeNode(false, Operator.Divide, null);
		ExpressionTreeNode n3 = new ExpressionTreeNode(false, Operator.Add, null);
		ExpressionTreeNode n4 = new ExpressionTreeNode(true, null, 5);
		ExpressionTreeNode n5 = new ExpressionTreeNode(true, null, 5);
		ExpressionTreeNode n6 = new ExpressionTreeNode(true, null, 6);
		ExpressionTreeNode n7 = new ExpressionTreeNode(true, null, -1);

		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n2.right = n5;
		n3.right = n7;
		n3.left = n6;

		
		ExpressionTreeNode en1 = new ExpressionTreeNode(false, Operator.Add, null);
		ExpressionTreeNode en2 = new ExpressionTreeNode(true, null, 3);
		ExpressionTreeNode en3 = new ExpressionTreeNode(true, null, 3);
		
		en1.left = en2;
		en1.right = en3;
		System.out.println(evaluateExpression(n1) == evaluateExpression(en1));
	}

	private static int evaluateExpression(ExpressionTreeNode node) {
		if (node.isLeaf) {
			return node.valIfInteger;
		} else {
			int left = evaluateExpression(node.left);
			int right = evaluateExpression(node.right);
			return node.valIfOperator.performOperation(left, right);
		}
	}
}

- Dhruva.Bharadwaj April 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We have only a,b,* and + so there are no braces ("(",")"). Hence, we can convert a tree to string very simply and compare it with mathematical representation.

- seriyvolk83 April 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// This solution assumes in-order, though this question could be changed to pre-order or post-order.
// This solution also assumes that a node is a value when it is a leaf, and is an expression otherwise
// Code in C++

struct Node
{
  Node* left;
  Node* right;
  double val;
  std::string exp; // --, ++, +, -, *, /
}

bool checkTrees(Node* left, Node* right)
{
  if (left == NULL && right != NULL) return false;
  if (left != NULL && right == NULL) return false;

  return eval(left) == eval(right);
}

double eval(Node* node)
{
  if (node->left == node-> right == NULL)
    return node->val;

  if (node->left == NULL && node-> right != NULL)
    return compute(node->right, node->val);

  if (node->left != NULL && node-> right == NULL)
    return compute(node->left, node->val);  

  return compute(eval(node->left), node->exp, eval(node->right));
}

double compute(double valu, const std::string& exp)
{
  if (exp == "--") return val - 1.0;
  if (exp == "++") return val + 1.0;
  
  // ERROR - Invalid tree
  return 0.0;
}

double compute(double left, const std::string& exp, double right)
{
  if (exp == "+") return left + right;
  if (exp == "-") return left - right;
  if (exp == "*") return left * right;
  if (exp == "/") return left / right;

  // ERROR - Invalid tree
  return 0.0;
}

- Josh May 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

mathematically equivalent - the ones which evaluates to same value or the ones which are equal? a * b * (c / d) can be represented as

*
a		*
	b		/
		c		d

postfix - a b c d / * *
or
		*
	*			/
a		b	c		d

postfix -  a b * c d / *

Are these to be equivalent?

- pshaikh.world March 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

are we evaluating the expression inorder???

- Anonymous March 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Read two expressions in order, then count a's, b's, and products of each and compare.

- ak_domi March 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

do depth-first traverse, at every operator level, sort left and right node with same comparator.
Then, simply see if 2 trees are identical.

- Anonymous March 16, 2017 | 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