Doordash店面

店面老题，求加米

At DoorDash, menus are updated daily even hourly to keep them up-to-date. Each menu can be regarded as a tree. When the merchant sends us the latest menu, can we calculate
how many nodes have changed/added/deleted?

Assume each Node structure is as below:

class Node {
        String key;
   

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

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

)
      /    |   \           \
e(5)   d(4)   f(6)       g(7)


There are a total of 5 changed nodes. Node f is a newly-added node. c(3) and old g(7) are deactivated and h(8) and g(7) are newly added nodes

1. int diff(Node old, Node cur) {
   
2.    if (old == null && cur == null) {
   
3.       return 0;
   
4.    } else if (old == null) {
   
5.       return count(cur);
   
6.    } else if (cur == null) {
   
7.       return count(old);
   
8.    }
   
9.       int num = 0;
   
10.       if (!old.key.equals(cur.key)) {
    
11.         return count(old) + count(cur);
    
12.       } else if (old.value != cur.value)
    
13.         num = 1;
    
14.       }
    
15.       HashMap<String, Node> curKids = new HashMap<>();
    
16.       for (Node n : cur.children) {
    
17.          curKids.put(n.key, n);
    
18.       }
    
19.       for (Node n : old.children) {
    
20.          if (curKids.containsKey(n.key)) {
    
21.             num += diff(n, curKids.get(n.key));
    
22.             curKids.remove(n.key);
    
23.          } else {
    
24.             num += count(n);
    
25.          }
    
26.       }
    
27.          for (Node n : curKids.values()) {
    
28.             num += count(n);
    
29.          }
    
30.          return num;      
    
31. }
    
32. 
    
33. int count(Node node) {
    
34.   if (node == null) {
    
35.     return 0;
    
36.   }
    
37.   int num = 1;
    
38.   for (Node n : node.children) {
    
39.     num += count(n);
    
40.   }
    
41.   return num;
    
42. }

复制代码

求问这题应该怎么做

匿名者 发表于 2021-9-30 05:03
求问这题应该怎么做

每层list根据key排序的话可以深搜求解。以原树为起点，消失和新加的下面全是改动，相同的node比较value，然后继续同理递归。