JP Morgan Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

typedef struct tree{
    int data;
    struct tree *left;
    struct tree *right;
}TREE;

TREE *root;
int max(int a, int b) {
    return a > b ? a : b;
}

int depth(TREE *root){
    if(root == NULL)
        return 1;
    
    return 1 + max(depth(root->left), depth(root->right));
}

//Worked Well..

int isBalanced(TREE *root) {
        if(root == NULL)
            return 1;
    
        if(abs(depth(root->left) - depth(root->right)) > 1)
            return 0;
    
        return isBalanced(root->left) && isBalanced(root->right);
}

- Jagadeesha Toohima March 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node {
Node left;
Node right;
int data;
public Node(int data){
this.data = data;
left = null;
right = null;
}
}

- Aswini De March 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean isBalance=true;

int isBalanceTree(Node n){
if(n==null) return 0;
int hl=isBalance(n.left);
int hr=isBalance(n.right);
if(Math.mod(hl,hr)>1 && isBalance)
isBalance=false;
return 1+Max(hl,hr);
}

- shailendra verma March 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef struct tree{
int data;
struct tree *left;
struct tree *right;
}TREE;

TREE *root;

int max(int a, int b) {
return a > b ? a : b;
}

int depth(TREE *root){
if(root == NULL)
return 1;

return 1 + max(depth(root->left), depth(root->right));
}

int isBalanced(TREE *root) {
if(root == NULL)
return 1;

if(abs(depth(root->left) - depth(root->right)) > 1)
return 0;

return isBalanced(root->left) && isBalanced(root->right);
}

- Jagadeesha Hiremath March 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean checkBinaryTreeIsBalanced(BSTNode root){

if(computeAndCheckHeight(root) == -1)
return false;
else
return true;
}

public static int computeAndCheckHeight(BSTNode root){
if(root == null)
return 0;
int leftSubTreeHeight = computeAndCheckHeight(root.leftNode);
if(leftSubTreeHeight == -1)
return -1;

int rightSubTreeHeight = computeAndCheckHeight(root.rightNode);
if(rightSubTreeHeight == -1)
return -1;

int heightDifference = Math.abs(leftSubTreeHeight - rightSubTreeHeight);
if(heightDifference > 1)
return -1;
else
return Math.max(leftSubTreeHeight, rightSubTreeHeight) + 1;
}

Time complexity : o(n)

- Abhimanyu April 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean checkBinaryTreeIsBalanced(BSTNode root){

	     if(computeAndCheckHeight(root) == -1)
	          return false;
	     else
	          return true;
	 }

	public static int computeAndCheckHeight(BSTNode root){
	     if(root == null)
	          return 0;
	     int leftSubTreeHeight = computeAndCheckHeight(root.leftNode);
	     if(leftSubTreeHeight == -1)
	          return -1;  

	     int rightSubTreeHeight = computeAndCheckHeight(root.rightNode);
	     if(rightSubTreeHeight == -1)
	          return -1;

	     int heightDifference = Math.abs(leftSubTreeHeight - rightSubTreeHeight);
	     if(heightDifference > 1)
	          return -1;
	     else
	          return Math.max(leftSubTreeHeight, rightSubTreeHeight) + 1;
	 }

- Anonymous April 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean checkBinaryTreeIsBalanced(BSTNode root){

	     if(computeAndCheckHeight(root) == -1)
	          return false;
	     else
	          return true;
	 }

	public static int computeAndCheckHeight(BSTNode root){
	     if(root == null)
	          return 0;
	     int leftSubTreeHeight = computeAndCheckHeight(root.leftNode);
	     if(leftSubTreeHeight == -1)
	          return -1;  

	     int rightSubTreeHeight = computeAndCheckHeight(root.rightNode);
	     if(rightSubTreeHeight == -1)
	          return -1;

	     int heightDifference = Math.abs(leftSubTreeHeight - rightSubTreeHeight);
	     if(heightDifference > 1)
	          return -1;
	     else
	          return Math.max(leftSubTreeHeight, rightSubTreeHeight) + 1;
	 }

time complexity : o(n)

- Abhimanyu April 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I made a few assumptions regarding the definition and scope of the question:
1. I assume Balanced tree is referring to Height-balanced tree.
2. I take the following definition of Height balanced trees: A binary tree is height-balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
NOTE the part regarding inner nodes only.

struct node
{
  int data;
  node* left;
  node* right;
};

int checkBalance(node* root) {
  // base case
  if(node == NULL) return 0;

  int leftHeight = checkBalance(node->left);
  int rightHeight = checkBalance(node->right);

  // propogate error
  if(leftHeight == -1 || rightHeight == -1)
    return -1;

  // give error on non-balance
  if(abs(leftHeight - rightHeight) > 1)
    return -1;

  return max(leftHeight, rightHeight) + 1;
}

bool isHeightBalanced(node* root) {
  if(checkBalance(root) == -1)
    return false;
  return true;
}

If either of the left or right subtrees is unbalanced, the entire tree becomes unbalanced. Hence the propogation of error through the entire depth of the recursive stack.

- quirk April 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bool isTreeBalanced(Node root){
	if( !root.Left && !root.Right ){
		Return true;
}

if( !root.Left || !root.Right){
	if(getDepth(root.Left) > 1 || getDepth(root.Left) >1){
		Return false;
}else{
	Return true;
}
}

isTreeBalanced(root.Left == false){
Return false;
}

isTreeBalanced(root.Right == false){
Return false;
}

Return True;
}

Int getDepth(Node root){
	if( !root.Left && !root.Right){
		Return 0;
}
Else{
	Int rightDepth = getDepth(root.Right);
	Int leftDepth = getDepth(root.Left);

	if(rightDepth > rightDepth){
		Return rightDepth;
}else{
	Return leftDepth;
}
}
}

- shayan.nafisi May 08, 2016 | 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