dog家 完整人生系列

iphehe 发表于 2018-7-16 06:10
请问第一题是否有类似的lc题目呀。。。我有点懵。。。

lc 165 字数字数

vtiaocao 发表于 2018-7-16 05:56
lz的第五轮矩阵是原题吗？
**** 本内容被作者隐藏 ****

哈哈是的是的！终于找到了！我帮小伙伴找了好久原题了，谢谢！！

lc issimilartree那个题的时间复杂度为什么只算叶子节点呢？为什么不算上非叶子节点？

westcoastboy 发表于 2018-7-16 01:59
同好奇第三题。
Map ;
应该是每次遇到a = b + c，如果是a那么看看map里面有没有a的赋值expression，如 ...

能再说详细点吗？怎么感觉是如果x1 = x2,+x3了，那么check x1是不是在map的key里，在的话，循环map找到有没有那个key的表达式用到了x1，如果有的话，x1就不是无用的，那么更新x1的值到表达式里面？

landy622 发表于 2018-7-16 09:20
能再说详细点吗？怎么感觉是如果x1 = x2,+x3了，那么check x1是不是在map的key里，在的话，循环map找到有 ...

不用啊。刚开始 map里对应着 x1 -> x1 = x2 + x3, 比如说后来你遇到了 x4 = x1 + x3， 那么你知道x1是在等号右边，所以你可以把map里的x1对应的value除掉，也就是除掉 x1 = x2 + x3， 因为这时候x1被调用了。

补充内容 (2018-7-16 10:28):
同时add或者update当前map里x4的value， 如果下一个x4以后出现在等号左边，那么之前的expression就是useless了； 如果下一个x4出现在等号右边，就说明x4不是useless

很有用的信息，谢谢！恭喜！

smellycat 发表于 2018-7-16 07:32
谢谢你的回答，非常详尽。但是我有两个问题
1. 关于synchronize，您提到需要维护一个Hashmap workingTas ...

哈哈. 其实我也是小白.. 只是工作中做的部分刚好是有大量的async task. 大家一起探讨一下.

1. 我添加这个obj主要是想用于lookup. 查看有哪些正在running的task. 从rubustness的角度来说, 大量的async task因为不是sequential的, 所以有前有后很正常, hung掉了也很正常. 一定需要monitor机制来处理hung掉的task. 这就是你提到的, 如果有一个task运行了很久,但是迟迟不结束. 我的理解是, 我需要找到执行了很久的task. 然后kill掉.
对于这个hashmap, 其实我们只需要一个task id和time in running. 不一定需要start time.  key是id, value是time since start. 我们可以每100ms iterate一次. 这个时间看大概的task要跑多久来调整的啦.  每一次iteration都是把这个时间累积. 超过threshold就做cancel handle.
如果req obj里面有start time info的话, 恩. 其实这个东西可以用priority queue来处理. 每次iterate queue的时候直接计算跑了多久了.

2. 我想不出有什么办法可以直接解决这个问题. 一个task先发而后至的情况蛮常见的, 但是一旦req2先写进disk了, 你就不可避免要把disk里面的内容读出来重新排序然后在写
req1, req2. 我能想到的优化就是, 我们不要一个个写req. 把独立操作变成batch操作. 存够量(100个吧)的req之后, 做merge two sorted array.  这样只是说把IO尽量减少.   我觉得应该没有办法完全解决这个问题. 类似的SQL Server里面flush dirty page的方式也是这样的. 存够量的dirty page之后, 写成一个record. 然后flush掉. 那刚好在你flush掉之后又要写同一个page怎么办. 没办法. 多做一次IO咯.  
当然如果不限定只是一个single file formart的话. 还能做得到的优化, 就是那我把一个log file到了一定是时间range. split成两个. 那你做merge two sorted array的时候, 可以少做一点的sorting.  这个其实就是page partition的概念了.  如果你继续给每一个page做下index. = =.  恭喜你, 你得到一个mini database.

小时候可帅哝 发表于 2018-7-17 01:36
哈哈. 其实我也是小白.. 只是工作中做的部分刚好是有大量的async task. 大家一起探讨一下.

1. 我添加 ...

非常详尽，谢谢层主

smellycat 发表于 2018-7-16 07:36
lc 165 字数字数

多谢多谢~！！！

求问第一轮是要自己写sort算法？还是自己定义Comparator就好？