 # Amazon Interview question SDE - 1

Recently I read some interview questions on gfg of amazon sde-1 , and this question has no solution till now , so asked here , the q. is :

Print all three nodes in a binary tree such that sum of all these three nodes is greater than given x and these three nodes must hold the relationship of grandparent-parent-child.

Expected Complexity – O(n)

1 Like

Short explanation:-

Simple dp on tree.

Tree gets rooted.

dp[i]=sum of (current-node + max(dp[children])
.
Keep comparing and checking !

dp[i] , means sum of current guy and best-child it can get.

5 Likes

I think you could also maintain the stack of your ancestors in a DFS and, whenever the number of ancestors \ge 2, sum the current node’s value plus that of the two most recent ancestors and see if this sum > x.

4 Likes

can you please give code means :
void printthreenode(Node* root){

}

Very simple solution :
Just make an array pointing to parent of every node.
Meaning,
array[k] = parent of node k
Now for each node k find sum of Val[k]+Val[array[k]] + Val[array[array[k]]] Assuming grandparent is immediate parent of parent and parent is immediate parent of child 11 Likes
void solve(Node* root, int d)
{
if(root == NULL)
return;

int x, gp, p;
x = root->val;
p = parent[x];
gp = parent[p];

if(x + p + gp > x and d >= 3)
cout << gp << ' ' << p << ' ' << x << endl;

solve(root->left, d+1);
solve(root->right, d+1);
}


Note: starting depth is 1

hope this helps…

this is not a dp problem… 1 Like

have you got any referral for amazon interview?

Ab aapko kya kahe bhai. Enjoy.

1 Like lol \hspace{0mm}

Can anyone give me referral to Amazon interview ?

2 Likes

I’ll surely give you once I get the job 2 Likes

Bro i am also in the queue,

1 Like

This could be the possible solution to this problem working in O(n) time using recursion

int co = 0;
vector<vector<int>> res;

void calc(Node* root, int n1, int n2, int c, int x) {
// cout<<root->val<<"\n";
if(root == nullptr) return;
if(c == 2 && n1 + n2 + root->val > x) {
++co;
res.pb({n1, n2, root->val});
}
if(c < 2) {
++c;
}
if(root->left != nullptr) {
calc(root->left, n2, root->val, c, x);
}
if(root->right != nullptr) {
calc(root->right, n2, root->val, c, x);
}
return;
}
calc(root, 0, 0, 0, x);

I’ll pop you soon. Don’t worry 1 Like

Heap* \hspace{0mm}

1 Like

So we have to maintain parent and grandparents pointer as well?

But hum to aapke piche h…lgva Dena kripa hogi , @l_returns u too…

2 Likes

no you can compute the parent array by first dfs traversal of a tree;

void dfs(Node* root, int p)
{
if(root == NULL)
return;

parent[root->val] = p;
dfs(root->left , root->val);
dfs(root->right, root->val);
}
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {

public static void main(String[] args){
//assuming we have root.
print(root,20);
}
private void print(TreeNode root,int x){
print(root,x,null);
}
private void print(TreeNode root,int x,LinkedList<TreeNode> list){
if(root==null){
return;
}
if(list==null){
}
int sum = 0;
for(TreeNode tn:list){
sum+= tn.val;
}
if(list.size()==3){
TreeNode node = list.poll();
sum-=node.val;
}
sum+=root.val;
if(list.size()==3&&sum>=x){
print(list);
}else{
print(root.left,x,list);
print(root.right,x,list);
}
if(list.remove(root)){
sum-=root.val;
}
}
}