Amazon Interview Question SDE-2s
Country: India
Interview Type: Written Test
import random as rd
class node:
def __init__(self, data):
self.data = data
self.l = None
self.r = None
self.n = None
self.next = None
class tree:
def __init__(self):
self.root = None
def get_root(self):
return self.root
def add_node(self, node):
if (self.root == None):
self.root = node
else:
self.__add_node(self.root, node)
def __add_node(self, root, node):
if (node.data < root.data):
if (root.l != None):
self.__add_node(root.l, node)
else:
root.l = node
else:
if (root.r != None):
self.__add_node(root.r, node)
else:
root.r = node
def height(node):
if node == None:
return 0
else:
return 1 + max(height(node.l), height(node.r))
def get_max(node):
if node == None:
return 0
if node.l == None and node.r == None:
return 1
left = height(node.l)
right = height(node.r)
return max(get_max(node.l), max(get_max(node.r), 1 + left + right))
i = tree()
r = input("enter the number")
print("adding data to the tree")
for j in range(0, int(r)):
number = rd.randint(0, 100)
print(number)
i.add_node(node(number))
print("max", get_max(i.get_root()))
When you are standing at a node, this node has both left and right children, update the maximum value, and return the greater result from left and right node to its parent. If the node has only one child, return the value from that child. If it doesn't have children which indicates that's a leaf node, return itself.
int getLargestPathSize(TreeNode* root){
int sum = INT_MIN;
maxSum(root, sum);
return sum;
}
int maxSum(TreeNode* root, int & sum){
if(root == NULL) return 0;
int left = maxSum(root->left, sum);
int right = maxSum(root->right, sum);
if(root->left && root->right){
sum = max(sum, left + right + root->value);
return max(left, right) + root->value;
}
return (root->left ? left : right) + root->value;
}
suggestion:
idea: in a tree, there is only one path from the root to a leaf.
use BFS to get the maximum number of edges in a path from the root to any leaf. => O(n) time
now from all the leaves (degree 1) obtain the two longest (longest and 2nd longest, both may have same length) leaves in the tree. => O(n)
sum their distances to get the result => O(1)
Overall: Linear time
"sum their distances to get the result".. that distance is from the root. They may have a common ancestor before the root.
my solution is generally similar to the one siva.sai.2020 proposed. the ides is following:
1. either the longest path exists in left or right subtree, or the path includes the root
2. get the size of longest path of both left and right (recursive case)
3. if the path includes the root, then the size of longest path is calculated by the depth of left subtree plus the depth of right subtree plus 1
Here is my implementation with a testing function:
struct _node {
int key;
struct _node *left;
struct _node *right;
};
typedef struct _node Node;
class Solution {
public:
int getLargestPath(Node *root)
{
int depth = 0;
if (root == nullptr) return 0;
return getLargestPath(root, depth);
}
private:
int getLargestPath(Node *root, int& depth)
{
if (root == 0) { depth = 0; return 0; }
int dp_l = 0, dp_r = 0;
int left = getLargestPath(root->left, dp_l);
int right = getLargestPath(root->right, dp_r);
depth = max(dp_l, dp_r) + 1;
// either the longest path exists in left/right subtree
// or the one includes this root, but get the longest
return max(max(left, right), dp_l + dp_r + 1);
}
};
class Testing {
public:
// random generate subtree with:
// 0 - no child; 1 - left child;
// 2 - right child; 3 - both
static Node *genBinaryTree(int& len, int& depth, int limit)
{
Node *root = new Node;
root->key = 0;
root->left = nullptr;
root->right = nullptr;
if (limit < 1) { len = 0; depth = 0; return root; }
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(0, 3);
int guard = dis(gen);
int left = 0, right = 0;
int d_l = 0, d_r = 0;
root->key = guard; // just for record
if (guard & 1)
root->left = genBinaryTree(left, d_l, limit-1);
if (guard & 2)
root->right = genBinaryTree(right, d_r, limit-1);
len = max(max(left, right), d_l + d_r + 1);
depth = max(d_l, d_r) + 1;
return root;
}
};
int main(int argc, char** argv)
{
Solution s;
int gd_len = 0, gd_depth = 0;
Node *root = Testing::genBinaryTree(gd_len, gd_depth, 100);
int path = s.getLargestPath(root);
if (path == gd_len) cout << "Correct!" << endl;
cout << "Largest Path: " << path << endl;
return 0;
}
class Node{
public Node right;
public Node left;
}
public class LongestPath {
private static int longestPath=0;
public int height(Node root){
if (root == null){
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
longestPath = Math.max(longestPath, leftHeight+rightHeight+1);
return Math.max(leftHeight,rightHeight) + 1;
}
}
- siva.sai.2020 November 29, 2015struct treeNode { int key; treeNode *left, *right; treeNode(int val) :key(val), left(NULL), right(NULL) {} }; int treeDiameter(treeNode *root, int &maxHeight) { if (root == NULL) return -1; else if (root->left == NULL && root->right == NULL) return 0; int leftHeight = 0, rightHeight = 0, leftDiameter = 0, rightDiameter = 0, diameter = 0; if (root->left) { leftDiameter = treeDiameter(root->left, leftHeight); diameter += leftHeight + 1; } if (root->right) { rightDiameter = treeDiameter(root->right, rightHeight); diameter += rightHeight+ 1; } maxHeight = max(leftHeight, rightHeight) + 1; return max(diameter, max(leftDiameter, rightDiameter)); } int main() { /* 10 5 15 4 7 11 16 6 9 */ treeNode *root = new treeNode(10); root->left = new treeNode(5); root->right = new treeNode(15); root->left->left = new treeNode(4); root->left->right = new treeNode(7); root->left->right->left = new treeNode(6); root->left->right->right = new treeNode(9); root->right->left = new treeNode(11); root->right->right = new treeNode(16); int height = 0; cout << "diameter = " << treeDiameter(root, height) << endl; getchar(); }