dog家 完整人生系列

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

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

最后的最后，感谢面试官的善意，运气好遇到的都是比较愿意沟通的面试官，没有黑着脸就只让你写代码的那种，紧张或者懵逼了就交流两句其实对于心态调整还是很有帮助。

补充内容 (2018-7-13 13:43):
各位看官，心情好的话给赏点米呗？

补充内容 (2018-7-16 01:58):
打错了一个字。。。第二轮是ReqLogger不是Red，不要被误导，red不是关键词。。。
还有关于thread和memory的问题我在下面回复了某位盆友，大家可以去下面回复看

补充内容 (2018-7-16 02:01):
还有，地理的大牛比较多，问一句这个最后一轮的第一题矩阵，最优解应该是什么？我当场写出来的解法无比拙劣。。。面试官也说有更好的办法，但比较难想，所以最优解应该是啥？

宝儿 发表于 2018-7-16 01:56
其实很简单。。。就是多线程同时在处理user request的时候，这些request最后都是要log进disk同一个logfil ...

我在工作中有看到类似的东西, 讨论一下哈.
从我的角度的理解, 他说的share memory 很可能是针对request. 如果用一个pool来存所有的request, 从API来看. startTask(id, start_time) 这个user只给了task id, 那么在这个method里面, 我们要通过这个id来拿request的object. 类似于 m_requestsPool->GetRequest(id)这样的操作.  当user把这个request处理完了. 就要把req给release掉咯.  理论上来说, 不同的user不应该能拿到同一个req.  也就是说, 不同的thread不应该hold同一个req, 理论上来说. 如果我们需要考虑跑了太久的req的话, 我们是不是需要时不时的查看一个req跑了太久, 如果跑了太久需不需要cancel掉. 当你cancel这个req的时候, 就意味着, 我们需要有另外一个thread去访问同一个req了.  CancelActiveTask thread 拿到这个req, 完成cancel之后也要release操作.  可能就会出现 race condition, double delete req. 我们的做法是, 针对每一个req, 每一个thread拿到req的时候加一个ref, 结束的时候release ref. ref为 0 destructor做delete操作.  (很Cpp的做法哈. )
没有太多的信息, 只是个人理解. 这个说的memory ojb应该是reqest个体.

关于 synchronize, 我能够想到几个方面的处理. 我会在这个class里面维护两个obj,  Hashmap<id, starttime> workingTasks, PriorityQueue<req> FinishedTask.
一个thread startTask之后, 把这个req写进workingTasks. End()的时候remove req. 这两个操作用Write lock. 上lock大家都会, 为了multi threading.
如果为了上面讨论的, 检查是否有长时间hung的req的话, 就意味着我们要有一个monitor thread隔一会就要做一个read. 看看是不是太久了. 需要cancel. 那么这个monitor thread 不应该block其他的user. 所以用read lock, 可以解决效率问题.

然后还有一个IO的优化, 要尽量减少写进disk这种IO操作. 所以我们只有当finishedTask满了, 或者超过一点时间, 才把整个queue里面的内容写进disk. 这个write method实际上把这个queue flush到disk, 结束的时候要empty这个queue.  同样的, 因为多个user在写这个queue. 所以只需要一个write lock.

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.

感觉像是被按在地上摩擦了五次
感谢分享
期待lz的好结果

第三轮难道一个map就解决了吗？

感谢分享~未必会挂的，祝楼主好运:)

shawnchangsdu 发表于 2018-7-13 13:18
感觉像是被按在地上摩擦了五次
感谢分享
期待lz的好结果

哈哈。摩擦已经不错了。。。。。我记得有次准备了好多coding题，最后问了我一道数学题。。。。

补充内容 (2018-7-13 22:37):
感觉搂住面得还不错啊，祝好运！

lz面得cloud组吧，在sv
第二轮，一堆multi user同时使用的会造成的multithreading和share memory的问题
lz可以详细说一下吗？

我只能加5分，全给你啦。感觉楼主心态非常好，而且讲的很详细。谢谢楼主信息。

祝好运

麻烦问下楼主什么时候面的呢？听说最近google cloud招人很多，不知道是不是headcount会多些，谢谢啦！

xingwuzheng 发表于 2018-7-14 05:14
我只能加5分，全给你啦。感觉楼主心态非常好，而且讲的很详细。谢谢楼主信息。

祝好运

谢谢你！你也加油！

damonlove 发表于 2018-7-14 05:17
麻烦问下楼主什么时候面的呢？听说最近google cloud招人很多，不知道是不是headcount会多些，谢谢啦！

我上周面的～应该是的吧，但也不是我选的cloud，是hr直接安排在了sunnyvale面试，我觉得如果你想面cloud的话可以在约面试的时候跟hr讲自己对cloud感兴趣，hr都是很好说话都是尽力想帮你的那种，我觉得说一下应该没问题安排面cloud的