## Adobe Interview Question for Computer Scientists

• 1
of 1 vote

Country: India
Interview Type: In-Person

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

Here is the efficient version, Time : O(n). Also similar approach as we do regularly find height of a tree In regular tree, we assume when hit null it's a leaf. But, in this case leaf is Circular DLL. So, if my cur node's left's right is pointing to cur node then it's a leaf.

``````public int height(BinaryTreeNode<Integer> root) {
if (null == root) {
return 0;
}
if (isLeaf(root)) {
return 1;
}
return 1 + Math.max(height(root.left), height(root.right));
}

private boolean isLeaf(BinaryTreeNode<Integer> root) {
BinaryTreeNode<Integer> left = root.left;
if (null == left)
return false;
return left.right == root;
}``````

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

The basic solution can be achieved by the below steps ::
1) Find atleast one leaf node
2) Loop thru doing binary search all the leaf nodes as they are all in DLL which will return the level of the node.
3) Find the maximum of the return value which will be the height of the tree

Step 1:: In at max O(n)
Step 2:: No of Leaf nodes*binary search --- O(nlogn)
Step 3 :: No of Leaf Nodes

So order of the above operation is O(nlogn) in worst case
Aerage will be O(logn^2)
Best case will be O(n)

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

Perform BFS traversal and keep track of the level with an int var incrementing it as each level + 1 for each next level until you reach leafs (no children), for each leaf in List of nodes of level check:

``````if (node-> left != null && node->left->right != null && node->left->right.equals(node)) {
return level;
}``````

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

``````class Solution {

class Node{
Node right;
Node left;
Object value;
}

public static void main(String[] args) {

new Solution().run();
}

void run(){

Node a= new Node();
Node b= new Node(); a.left=b;
Node c = new Node(); a.right=c;

Node d = new Node(); b.left = d;
Node e = new Node(); b.right = e;
Node f = new Node(); c.left = f;
Node g = new Node(); c.right = g;

d.right = e; e.left = d;
e.right = f; f.left = e;
f.right = g; g.left = f;
g.right = d; d.left = g;

System.out.println( "Tree Height: "+treeHeight( a ));

}

int treeHeight( Node root ){

Map< Node, Integer > valueMap = new  HashMap<>();

Node currentNode = root;
int depth = 1;
while ( !valueMap.containsKey( currentNode ) ){

valueMap.put( currentNode, depth );
depth++;
currentNode = currentNode.left;

}

return valueMap.get( currentNode );
}

}``````

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

Step 1 can be done by tortise heir algorithm. Rest of the steps are evident i guess

``````FindLeaf()
{
node *temp1=root;
node *temp2=root;
while(temp1!=temp2)
{
temp1=movenext(temp1);
temp2=movenext(temp2);
temp2=movenext(temp2);
}

node *leftnode=temp1;
}

node *movenext(node *temp)
{
if(temp->left!=NULL)
temp=temp->left;
else
temp=temp->right;
return temp;
}``````

Step2 --> Max of Iterate thru DLL and binary search for the height.

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

``````public void TreeHeight(node root, int height)
{
if(root==null)
{
return null;
}

if(goDown(root,Math.pow(2,height)))
{
TreeHeight(root.left,height+1);
}else{
System.out.println("the height of the tree is: "+height);
}
}

public boolean goDown(node currNode,int circel)
{
node slow = currNode;
node fast = currNode;

for(int i=0;i<=circel;i++)
{
slow = slow.left;
fast = fast.left.left;
}

// if this level is leaf level the fast and slow nods
//should be the same one
if(slow==fast)
{
return false;
} else{
return true;
}
}``````

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

``````public void TreeHeight(node root, int height)
{
if(root==null)
{
return null;
}

if(goDown(root,Math.pow(2,height)))
{
TreeHeight(root.left,height+1);
}else{
System.out.println("the height of the tree is: "+height);
}
}

public boolean goDown(node currNode,int circel)
{
node slow = currNode;
node fast = currNode;

for(int i=0;i<=circel;i++)
{
slow = slow.left;
fast = fast.left.left;
}

// if this level is leaf level the fast and slow nods
//should be the same one
if(slow==fast)
{
return false;
} else{
return true;
}
}``````

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

``````public void TreeHeight(node root, int height)
{
if(root==null)
{
return null;
}

if(goDown(root,Math.pow(2,height)))
{
TreeHeight(root.left,height+1);
}else{
System.out.println("the height of the tree is: "+height);
}
}

public boolean goDown(node currNode,int circel)
{
node slow = currNode;
node fast = currNode;

for(int i=0;i<=circel;i++)
{
slow = slow.left;
fast = fast.left.left;
}

// if this level is leaf level the fast and slow nods
//should be the same one
if(slow==fast)
{
return false;
} else{
return true;
}``````

}

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

The basic idea is walk every left node until it reach the end.

``````#include <stdio.h>
#include <stdlib.h>

#define null   0

using namespace std;

typedef struct s_node
{
private:
int      m_val;
s_node*  m_left_node;
s_node*  m_right_node;

public:
s_node(int val)
{
m_val       = val;
m_left_node = null;
m_right_node= null;
}

void add_left_node(s_node* node)
{
m_left_node = node;
}

void add_right_node(s_node* node)
{
m_right_node = node;
}

s_node* get_left_node()
{
return m_left_node;
}

s_node* get_right_node()
{
return m_right_node;
}

int get_val()
{
return m_val;
}

~s_node()
{
if(m_left_node)
{
m_left_node = null;
}

if(m_right_node)
{
m_right_node = null;
}
}
}SNODE;

int main(int argc, char** argv)
{
//the following is examples of this test.
SNODE *root    = new SNODE(1);
SNODE *two     = new SNODE(2);
SNODE *three   = new SNODE(3);
SNODE *four    = new SNODE(4);
SNODE *five    = new SNODE(5);
SNODE *six     = new SNODE(6);

//build relationship
root->add_left_node(two);
root->add_right_node(three);
two->add_left_node(four);
two->add_right_node(five);
three->add_left_node(six);
four->add_left_node(six);
four->add_right_node(five);
five->add_right_node(six);
six->add_right_node(four);

SNODE* walk = root;
int height  = 0;

while(walk)
{
walk = walk->get_left_node();
height++;
}

height--;

printf("height = %d\n", height);

delete root;
delete two;
delete three;
delete four;
delete five;
delete six;
return 0;
}``````

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