dog家 完整人生系列

wtcupup 发表于 2018-7-13 15:56
第三轮难道一个map就解决了吗？

啊？为啥是map，不应该是dp嘛～小学奥数题走格子，只不过这个走的方向不太一样

宝儿 发表于 2018-7-16 01:59
啊？为啥是map，不应该是dp嘛～小学奥数题走格子，只不过这个走的方向不太一样

哈哈 我说的是那道方程题

wtcupup 发表于 2018-7-16 02:40
哈哈 我说的是那道方程题

哦哦哈哈我写了两个第三轮。。。对就是一个map，机智！时间复杂度是n

感谢楼主分享！

宝儿 发表于 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.

宝儿 发表于 2018-7-16 01:42
我上周面的～应该是的吧，但也不是我选的cloud，是hr直接安排在了sunnyvale面试，我觉得如果你想面cloud ...

多谢楼主了，楼主一定可以的！！！

lz的第五轮矩阵是原题吗？

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

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

最优解一言难尽，discuss有说啊。

PS 题目是真的难 看着都累

请问第一题是否有类似的lc题目呀。。。我有点懵。。。

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

谢谢详细回复！
开始想错了方向，没有理解multithreads的考点。一般来说不同user的log内容都要附加上一个UUID之类的标识符，这样可以track不同user的log。特别是在multiple services架构里面，这样比较容易track不同user的log。这种log方法不对timeline有严格妖气。
这个问题是问不同user写一个log，按照同一个时间顺序写入。

对于shared mem我觉得19楼说的也很好

小时候可帅哝 发表于 2018-7-16 04:44
我在工作中有看到类似的东西, 讨论一下哈.
从我的角度的理解, 他说的share memory 很可能是针对request ...

谢谢你的回答，非常详尽。但是我有两个问题
1. 关于synchronize，您提到需要维护一个Hashmap<id, starttime> workingTasks，请问加这个obj的好处在哪里呢？在我看来PriorityQueue<req>就足够了，每个req执行完毕之后就直接写PriorityQueue<req> FinisheTask就可以了。
2. 关于flush PriorityQueue<req> FinisheTask里面的内容到disk。例如现在有两个req，分别为req1和req2，req1的starttime要先于req2，在某个时刻req2运行完毕但是req1任然在运行，在req1运行完毕之前，系统开始flush FinisheTask里面的内容，这会导致req2的log先写到disk，req1的log会后写到task。有没有什么办法处理这种情况呢？
谢谢层主，我是system design小白，所以问题会比较多。。。

补充内容 (2018-7-16 07:34):
纠正笔误，第五行有个task，其实应该是disk。。。