Doordash Phone Screen

先上题目：
Given a binary tree with alive nodes, alive node can only be leaf nodes and marked with aterisk mask. Find the maximum path length between two alive nodes.
e.g.
           5
          /      \
     2           0
   /   \            /   \
100*  50*  14* 15*

上述例子返回

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

也需要random api，面试官提示可以用web api，比如weather什么的。感觉是一个open question。

面试官当场给了positive feedback，说我是他面试过的人中间第一个做出这道题的，所以如无意外大概能进入下一轮吧。

已经第二次phone screen就遇到tree/graph题了，跟楼主三年前第一次找工作时的状况截然不同了。如果你觉得有用，帮加一下大米吧！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

弄的复杂了，这题直接recursion解更简单

这题难道不是利扣【一二四】吗

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

hgon23 发表于 2021-9-11 00:55
思路是一样的哈；解法细节上稍微变一下，还是递归比较直接。。。

就是二叉树，以所有非l叶节点为根， ...

对的，二楼我大概写了下代码。 不知道对不对。

xiaozhuxiaozhu 发表于 2021-9-11 01:02
对的，二楼我大概写了下代码。 不知道对不对。

看着挺对的。楼主一上来也想用recursion做，但是想不明白如何判断path的两端是alive nodes。哎，做了不少tree的题了，还是对题目要求的变化无法快速适应。

1. public class MyClass {
   
2.     private static class TreeNode{
   
3.         int val;
   
4.         boolean hasMask;
   
5.         TreeNode left;
   
6.         TreeNode right;
   
7.         public TreeNode(int val, boolean hasMask) {
   
8.             this.val = val;
   
9.             this.hasMask = hasMask;
   
10.         }
    
11.     }
    
12.    
    
13.     static int maxSum = Integer.MIN_VALUE;
    
14.     private static int maxPathSum(TreeNode root) {
    
15.         if(root == null) return Integer.MIN_VALUE;
    
16.         
    
17.         
    
18.         //Find the alive node
    
19.         if(root.left == null && root.right == null && root.hasMask) {
    
20.             return root.val;
    
21.         }
    
22.         
    
23.         int rootVal = root.val;
    
24.         int leftSum = maxPathSum(root.left);
    
25.         int rightSum = maxPathSum(root.right);
    
26.         
    
27.         
    
28.         //Cur node can be root;
    
29.         if(leftSum != Integer.MIN_VALUE && rightSum != Integer.MIN_VALUE) {
    
30.             maxSum = Math.max(leftSum + rootVal + rightSum, maxSum);
    
31.         }
    
32.         
    
33.         int leftMax = leftSum == Integer.MIN_VALUE ? Integer.MIN_VALUE : leftSum + rootVal;
    
34.         int rightMax = rightSum == Integer.MIN_VALUE ? Integer.MIN_VALUE : rightSum + rootVal;
    
35.         
    
36.         
    
37.         return Math.max(leftMax, rightMax);
    
38.         
    
39.     }
    
40.    
    
41.     public static void main(String args[]) {
    
42.         TreeNode root = new TreeNode(5, false);
    
43.         TreeNode node_1 = new TreeNode(2, false);
    
44.         TreeNode node_2 = new TreeNode(0, false);
    
45.         TreeNode node_3 = new TreeNode(-100, true);
    
46.         TreeNode node_4 = new TreeNode(50, true);
    
47.         TreeNode node_5 = new TreeNode(14, true);
    
48.         TreeNode node_6 = new TreeNode(15, true);
    
49.         root.left = node_1;
    
50.         root.right = node_2;
    
51.         node_1.left = node_3;
    
52.         node_1.right = node_4;
    
53.         node_2.left = node_5;
    
54.         node_2.right = node_6;
    
55.         
    
56.         int res = maxPathSum(root);
    
57.         System.out.println("MaxSum: " + maxSum);
    
58.     }
    
59. }

复制代码

大概写了一下第一题。follow up 就是多加一些判断吧

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies