dropbox 电面（附加资料代码包）

这周dropbox 电面的，面试过程很愉快，可惜自己不争气，准备了很多道面经题，可惜被考了道不怎么常见的has Access题，只

游客，本帖隐藏的内容需要积分高于 188 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

，基本都是面经题，就算碰到新题也不要慌。

求问楼主丢盒子的t

游客，本帖隐藏的内容需要积分高于 10 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

谢谢

byfwh 发表于 2018-10-28 01:34
求问楼主丢盒子的timeline 谢谢

内推后一天发oa，两天后完成oa，约电面，电面约的两周后

想问下楼主 folder access那题 fol

游客，本帖隐藏的内容需要积分高于 10 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

可以再优化嘛？

感谢lz分享！！！

whosays 发表于 2019-2-23 04:07
感谢lz分享！！！

加油准备～～紫薯紫薯

happycsdogs 发表于 2018-11-25 02:57
想问下楼主 folder access那题 followup 是O(mlogn) 还可以再优化嘛？

假設有m個file，你一開始要建立一個adjacency list，會花掉O(m)的時間。
然後接下來做一次BFS/DFS來收集accessible files, worst case會花掉O(m)的時間。
接下來就是所有的hasAccess(filename) query了。

如果你把accessible的set的initialization當作一個初始過程，後面不停query，amortized runtime應該是O(1)