五月 yelp 面经

电面：Word Ladder
ONSITE:
1. WORD COUNT
2. DFS (具体

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

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

yURL
5. RATE LIMITER

1. public static int dfs(TreeNode root){
   
2.         if (root == null)
   
3.                 return 0;
   
4.         int sum = root.val;
   
5.         int left = dfs(root.left);
   
6.         int right = dfs(root.right);
   
7.         sum += Math.max(left,right);
   
8.         return sum;
   
9.     }

复制代码

这个?

readman 发表于 2016-6-20 08:25
这个?

噢 对 我想起来一个问题 我去找下那个链接 比我帖子写的还要trick一些

readman 发表于 2016-6-20 08:25
这个?

请看看这个，有shared nodes
https://www.quora.com/How-do-I-f ... tree-like-structure

第三题MAX SUM IN BT, 有shared nodes. 请看链接 https://www.quora.com/How-do-I-f ... tree-like-structure

ninacc 发表于 2016-6-21 02:21
第三题MAX SUM IN BT, 有shared nodes. 请看链接 https://www.quora.com/How-do-I-find-the-greatest-sum-o ...

谢谢...我那个code好像也能work在这里...

下面是你link的例子..

1. public class Yelp {
   
2.     public static int maxSum(TreeNode root){
   
3.         if (root == null)
   
4.                 return 0;
   
5.         int sum = root.val;
   
6.         int left = maxSum(root.left);
   
7.         int right = maxSum(root.right);
   
8.         sum += Math.max(left,right);
   
9.         return sum;
   
10.     }
    
11. 
    
12.     public static void main(String[] args) {
    
13.         TreeNode root = new TreeNode(3);
    
14.         root.left = new TreeNode(2);
    
15.         root.right = new TreeNode(1);
    
16.         root.left.left = new TreeNode(6);
    
17.         root.left.right = new TreeNode(4);
    
18.         root.left.left.left = new TreeNode(1);
    
19.         root.left.left.right = new TreeNode(2);
    
20.         root.left.right.left = root.left.left.right;
    
21.         root.right.left = root.left.right;
    
22.         root.right.right = new TreeNode(6);
    
23.         root.right.right.right = new TreeNode(3);
    
24.         root.right.left.right = new TreeNode(9);
    
25.         root.right.right.left = root.right.left.right;
    
26.         System.out.println(maxSum(root));
    
27.     }
    
28. }
    

复制代码

补充内容 (2016-6-21 02:46):
3->1->6->9  = 19?

readman 发表于 2016-6-20 13:45
谢谢...我那个code好像也能work在这里...

下面是你link的例子..

是的是的，你写的一点没问题！我当时第一个写的就这样，后来被问到怎么可以避免重复计算shared node的sum. 可以考虑下DP?

ninacc 发表于 2016-6-21 03:26
是的是的，你写的一点没问题！我当时第一个写的就这样，后来被问到怎么可以避免重复计算shared node的sum ...

:D

这个看起来好么?妹纸

1. public static int maxSum(TreeNode root, HashMap<TreeNode, Integer> map){
   
2.         if (root == null)
   
3.             return 0;
   
4.         if (map.containsKey(root))
   
5.             return map.get(root);
   
6.         int left = maxSum(root.left,map);
   
7.         int right = maxSum(root.right,map);
   
8.         int sum = root.val;
   
9.         sum += Math.max(left,right);
   
10.         map.put(root,sum);
    
11.         return sum;
    
12.     }

复制代码

RATE LIMITER是啥呀？

ninacc 发表于 2016-6-21 03:26
是的是的，你写的一点没问题！我当时第一个写的就这样，后来被问到怎么可以避免重复计算shared node的sum ...

这个share node的树斜着可以看成一个上三角矩阵，就相当于从矩阵的左上角走，只能向右或向下走，然后直接DP就可以了吧？我觉得这样似乎可以，不知道描述清楚没