## Amazon Interview Question for SDE1s

• 1
of 1 vote

Country: India
Interview Type: Phone Interview

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

``````int maxPath(TreeNode* root, int *height)
{
if(!root)
{
*height = 0;
return 0;
}

int lh=0, rh=0;

int ld = diameter(root->left, &lh);
int rd = diameter(root->right, &rh);

*height = 1+max(lh, rh);

return max(max(ld, rd), 1+lh+rh);
}``````

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

how you handle the case : one bend in your code?

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

There it is: ------------->

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

Approach:

max path with a bend
=
max of {
max path with a bend of right subtree,
max path with a bend of left subtree,
max path with a bend including the root
}

In the above, max path with a bend including the root is the max of {
max of {length of left only path of right subtree, max length of right path of right subtree with one bend} + 1,
max of {length of right only path of left subtree, max length of left path of left subtree with one bend} + 1
}

Following code should work:

``````private static class State {
int max = 0; // max path with bend
int lpwb = 0; // left path with bend
int rpwb = 0; // right path with bend
int lpwob = 0; // left path without bend
int rpwob = 0; // right path without bend
}

private static class Node {
Node left;
Node right;
int data;

public Node(int d) {
data = d;
left = null;
right = null;
}
}

private static int max (int i, int j) {
return i > j ? i : j;
}

private static State getState(Node root) {
State s = new State();
if (root.left == null && root.right == null) {
return s;
}
State rs = root.right == null ? null : getState(root.right);
State ls = root.left == null ? null : getState(root.left);
s.lpwob = ls == null ? 0 : ls.lpwob + 1;
s.rpwob = rs == null ? 0 : rs.rpwob + 1;
s.lpwb = ls == null ? 0 : (max(ls.lpwb, ls.rpwob) + 1);
s.rpwb = rs == null ? 0 : (max(rs.rpwb, rs.lpwob) + 1);
if (s.lpwb < 2) { // a path with bend must be of length at least 2
s.lpwb = 0;
}
if (s.rpwb < 2) {
s.rpwb = 0;
}

s.max = max(s.lpwb, max(s.rpwb, max(rs == null ? 0 : rs.max, ls == null ? 0 : ls.max)));
return s;
}``````

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

Hi, can you explain the final assigned sentence "s.max = ..." a bit more ? Thanks.

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

``````int longestPath(node *root)
{
if(! root)
return 0;

node *r1 = root->left;
int pathLen = 2;

for(int len=0; r1; r1 = r1->left, len++)
{
int tempcount = len + 1;
while(r1)
{
r1 = r1->right;
tempcount++;
}

if(tempcount > pathLen)
pathLen = tempcount;
}

r1 = root->right;

for(int len=0; r1; r1 = r1->right, len++)
{
int tempcount = len + 1;
while(r1)
{
r1 = r1->left;
tempcount++;
}

if(tempcount > pathLen)
pathLen = tempcount;
}

if(pathLen > 2)
return pathLen;
else
return 0;
}``````

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

You are assuming that the desired path must contain the root. This is not necessary.

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

If I understand correctly it means to find the diameter of binary tree. Please confirm.

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.

### 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.