W****5 发帖数: 12 | 1 假设有两个warehouse,各自有自己的inventory system, 用如下图所示的树结构表示
。问,如果在A的inventory system中添加了一些node,如何将这些node同步更新到B的
inventory system,怎么进行优化(读取A的node的操作会是remote call,所以开销会
很大)
root
/
clothes electronics books ... ...
/
men's women's
/
... ... ...
/
Nike T-Shirt #[XXXX]
让我实现的方法的signature是 int updateInventory(ITreeNode a, ITreeNode b),
返回值是新增节点的数目。 TreeNode的结构让我自己定义,大概包括一个id,和包含
所有子节点的list(他给的是list,但是我实现的时候改成了HashMap)。
我的想法是写一个递归的方法,对B进行更新。优化的地方是在TreeNode里加一个类似
hash code的field,并且保证如果两个node的hash code一致,就说明两个子树是一致
的,这样在递归开始的时候可以先检查两个node的hash code,如果不一致,再继续更
新子节点。但是这样要求在对A做更新的时候,需要对A的hash code进行相应的更新。
(面完回来后想想,也许不需要用hash code,考虑到只有添加节点的操作,是不是只
用记下当前子树的总节点数就行了。)
中间面试官提到对A的读取是remote call,一次读取只会读取当前节点的内容,并不会
load子节点的内容,然后我说可以考虑在读取节点的时候,将所有子节点的hash code
一起load出来,这样可以减少总的remote call的次数。
后来被问到还可以怎么优化,考虑到树有可能很大,如果在树的最底部新增一个节点,
那么我的办法还是要一步步的从root节点遍历到最底部的节点,怎么进行改进。然后我
就没什么想法了。。。
(题目一开始给的挺抽象的,就给了个method signature,然后让我实现update tree
并进行优化,具体TreeNode包含什么内容,优化的concern是什么,这些都是我一步步
问出来的,面试官一开始也没说清楚,基本上我问一句他回答一句。。。)
请教一下大家,碰到这种问题还能从哪些方面入手进行优化? | A*******e 发帖数: 2419 | 2 只添加,不删除?
【在 W****5 的大作中提到】 : 假设有两个warehouse,各自有自己的inventory system, 用如下图所示的树结构表示 : 。问,如果在A的inventory system中添加了一些node,如何将这些node同步更新到B的 : inventory system,怎么进行优化(读取A的node的操作会是remote call,所以开销会 : 很大) : root : / : clothes electronics books ... ... : / : men's women's : /
| A*******e 发帖数: 2419 | 3 树结构就是db schema,更新数据时没必要同时更新schema。
【在 A*******e 的大作中提到】 : 只添加,不删除?
|
|