Amazon Interview question SDE - 1

general
,
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)

@L_returns @aryanc403 @anon55659401 @akshay_1 @samarthtandon @hetp111 @ashokshaun @s5960r

1 Like
2

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
3

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
4

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

// your code

}

5

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]]]
:smiley:
Assuming grandparent is immediate parent of parent and parent is immediate parent of child :stuck_out_tongue:

11 Likes
6 
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…

7

this is not a dp problem…:stuck_out_tongue_closed_eyes:

1 Like
8

have you got any referral for amazon interview?

9

Ab aapko kya kahe bhai. Enjoy.

1 Like
10

:joy: lol \hspace{0mm}

11

Can anyone give me referral to Amazon interview ?

2 Likes
12

I’ll surely give you once I get the job :joy:

2 Likes
13

Bro i am also in the queue,

1 Like
14

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);
15

I’ll pop you soon. Don’t worry :slight_smile:

1 Like
16

Heap* :stuck_out_tongue: \hspace{0mm}

1 Like
17

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

18

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

2 Likes
19

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);
}
20 
/**
 * 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){
            list = new LinkedList<TreeNode>();
        }
        int sum = 0;
        for(TreeNode tn:list){
            sum+= tn.val;
        }
        if(list.size()==3){
            TreeNode node = list.poll();
            sum-=node.val;
        }
        list.add(root);
        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;
        }
    }
    private void print(LinkedList<TreeNode> list){
        System.out.println("");
        for(TreeNode tn:list){
            System.out.print(tn.val+",");
        }
    }
    
}