Amazon Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
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;
}
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;
}
- zahidbuet106 December 05, 2013