log hit:Write a program that logs hits received in the past 15 minutes.
a. 问了老题 log_hit(), get_hit_in_5_minutes(), follow up thread safety. 统计最近5分钟内一个webpage被hit了多少次，精确到秒就可以了。实现两个method: logHit和getHit。logHit就是记录一次hit，getHit就是输出最近5分钟内的所有hit总和

hit那道题。重点是如果是queue的做法的话，add的时候应该先把那些不可能的时间点都poll出去，不然内存可能会不够用。当时太紧张了没get到面试官说的是这个问题http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=230590&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

要求用两种方法做，第一种，考虑到时间可以分为非常小，这个时候就用 queue + hashmap做，这样会浪费空间；
第二种，如果俭省空间，因为这个是一道很常见的题目，所以知道如何用circle array是基本知识。 你做完circle array之后，可以提一下新建一个Class， class 有两个属性，一个为 时间，另一个 为 hit次数。这样做也挺深空间的。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=215838&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

一个server不断收到request，用single thread写两个function:log_request(timestamp){}: 用于记录request，具体data structure自己设计
get_request_last_five_minutes(){}: return过去五分钟收到request的数量
一开始把timestamp都存在queue里，get_request的时候就把超过五分钟的都pop掉，然后return size。写完了小哥说要memory不够，只够存过去五分钟的timestamp。于是我在log_request里也pop。
又写完了小哥又说memory不够.....（这个地方我没有意识到request可以同时进来，所以用了好久才get到他的点）于是就用hashtable存<timestamp, counter>，这样不会存重复的timestamp。然后get的时候就把小于五分钟的key都找出来，把counter加起来。
.小哥终于开心了。写了些test casehttp://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=207357&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

https://leetcode.com/problems/design-hit-counter/description/
地里最高频的题 LC 362, 参数是不带timestamp的，所以用了系统的System.currentTimeMillis()来获得当前时间
我忘了这个名字，所以说查一下文档，他说先假装有这个方法好了，不用查。后来最后跑测试的时候，又让我查一下了，因为要检测代码
最后测试的时候，我说要测试300秒的得sleep这么久，他说怎么能加快。我说给个参数就能自定义时间戳了，然后就改了改测试都过了就好了http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=205856&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


https://discuss.leetcode.com/topic/48758/super-easy-design-o-1-hit-o-s-gethits-no-fancy-data-structure-is-needed
1. 我觉得他本意是考不带时间参数的，就是用system时间，然而我一开始硬让他加上了。。。
2. 写完程序，要写test，在main函数里，注意写成assert(..., correct answer)
3. 问多线程同时访问，我只说了加synchronize关键字，然后效率可能变慢，然后如何改进，然而我不会java多线程别的额。。瞎说了个distributed system类的。。
4. 又开始问为啥要两个数组，能不能不用time啥的。。我也不知道点在哪，瞎说一通遂弃。。
5. 再问如果没有时间参数，用system得到时间咋办。。我硬写成了个相对时间来取模，他说直接用绝对时间取模呢？我表示相对时间对于300s更。。更。。直观，貌似绝对时间也可以？但当时大脑紧张，就坚持相对时间了。。。
6. get_hit参数变为n，表示最近的n秒的访问次数，就在程序里改成n就好了，然而我脑残多改了个参数，导致bug，最后才发现。。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=205382&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

hit counter（log hits）。
聊的很愉快，就是特别多follow up：一直hit怎么办，edge cases有哪些，怎么提高时间和空间复杂度http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=293411&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


用dequeue模拟circular buffer么

用circular array做的, 需要考虑multi_threading， 但不用考虑array的互斥
write比read多该怎么办和read比write多该怎么办?

用队列和数组两种方法做，讨论时空复杂度

当时写了两种，第一个是用的bucket，每一秒算一个bucket，然后就是维护一个滚动数组。第二个比较笨，就是来一个记一个，然后需要的时候garbage collection一下。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=141917&extra=page%3D4%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

我circular buffer的害怕写出来bug， 没敢写。先写了个navie的queue, 然后优化，改成存time, count的deque。优化， 变成size最大是300的deque. 然后就是怎么测试，举出一些例子来。然后说多线程怎么办，我说deque，enque变sychronize或者手动加锁。

題目沒有很明白說明是否會提供timestamp，所以我從系統讀時間. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
做了三種做法：基本的queue存每個timestamp, 後來提了map + queue 解決同時間多個hit, 再來寫了single circular array
最後又要求我補寫第二個
時間空間複雜度考得很細
要你比較幾個這三個作法trade-off (dropbox關鍵字)
做前兩個的時候，面試官一直繞在memory問題打轉，似乎是想把我導引到array作法，但hint實在很不明確，也不太願意寫example，當下不知道是要修正既有方法還是直接寫array
面試官態度一開始感覺也不是很欣賞，也有可能是我過程typo有點多，被他抓出來，覺得我不厲害
直到把array寫出來，才說great!http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=250217&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

b. 先是最笨的方法解决问题，然后去做优化，用chaining array做。
问了很多follow up：
1. 为什么用chaining array做，误差分析
2. 怎么做测试，unit test, correct and memory, use dummy time for memory test
3. 多线程。master slave model
4. 多线程的话 lock和unlock怎么写，modify code
5. 不用chaining array的话， 怎么做，vector 搞定，效率没有chaining array高http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=179851&extra=page%3D4%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


先用一個queue<int> 的解法 他說很好 但能不能節省space, 假設每秒鐘有好幾個million的request
就改成circular array 他很滿意 然後再問怎麼測試 這題跟leetcode不一樣 沒有給timestamp as input
所以其實很難測 她說應該要用mock 我說我不會 我希望可以改function的signature 他說好 那就好測多了 給假的timestamp 然後用assert
follow up: multithread, 其實就是在access shared data之前加個鎖而已http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=206203&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

题目是hit counter，我刷过，但是记得不太清楚最优解法的细节了，于是问了下. 鍥磋鎴戜滑@1point 3 acres
1. 一秒钟可能hit多次吗？
2. 要不要考虑多线程情况.1point3acres缃�
先说了一个naive的存time再二分查找边界的。
小哥说能不能再给力一点啊，我就边想边说了下常数存储的方法。小哥对我的解法（和演技）比较满意，然后很快就写完了。
小哥继续问怎么test，我说了几个case，不过需要sleep，小哥表示你在逗我吗，unit test你sleep 5分钟？我说那你就fake一下timestamp嘛，要么传进去，要么用mockito fake一下。小哥说OK.
小哥继续问那现在我们搞multi-threading，怎么办
我说. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
1. 加全局锁，两个方法加上synchronized
2. event queue。封装方法调用，把命令放到queue上，然后server在另一端不断地取task执行，这样解耦了consumer和producer，异步化方法调用
3. ConcurrentHashMap来代替数组，因为log是读少写多，只需要在getHit的时候加锁
4. 如果只有固定的几个admin，那就固定给一个ConcurrentHashMap，用admin ID当key，内层就可以HashMap了，因为admin们不会影响别人.1point3acres缃�
5. 在4的基础上，如果admin并不是一定要全局的数据（可以只做些sampling），那可以用ThreadLocal，完全抛弃锁。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=202199&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


 不给timestamp，要从系统里取。我写了两种方法，queue的（内存会占太大），然后又换成circular array。
最后写了testcase，但是不用run。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=224465&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


dropbox电面 老题目 hit_logger/get_logger_count， 以下是优化顺序：
vector<int>存timestamp, 占内存
queue<int>存timestamp, 一秒很多个hit太占内存
queue<pair<int, int>> 存pair<timestamp, count>, 这里忘了cpp的queue没法遍历， 所以最后没法求和， 换成了vector<pair<int, int>>
vector<pair<int, int>> circular buffer, 开300个bucket， 求余存不同的bucket
multithreading - 加lockhttp://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=231050&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

网上资料：https://nuttynanaus.wordpress.com/2014/03/09/software-engineer-interview-questions/
（http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=180309&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311）
               http://blog.gainlo.co/index.php/2016/09/12/dropbox-interview-design-hit-counter/
               http://www.mitbbs.com/article_t1/JobHunting/32549839_0_1.html



web crawl: 给一个 startiingUrl 和一个method getLinks（url），该method 返回该url 所在页面的所有 links 。要求返回这个 url 所在 domain 下的所有 url。（注意存个HashMap避免链接之间互相loop）
         follow up: 1.  BFS 和 DFS 的差别 2. 写多线程的version

实现web crawler. 用BFS, 然后问如何优化，就是多线程。

web crawler，先写dfs单线程，再多个线程一起爬，主要是加锁解锁，wait，notify。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=213058&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

follow up有exit条件 就是allocate的thread个数等于完成的thread个数 相当于每个node就增加一个threadhttp://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=192607&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

web crawler。 我很快就写出来了，他问怎么优化速度，我说用多线程。他问你觉得程序里最慢的地方是哪儿，为什么用多线程就可以提高速度，我不知道。。最后他说是从父url得到一系列url，然后让我把从父url生成list url的代码写出来，我不会写。。他给我写出来了，第一步是dowload url得到一个string就是url对应的content，第二步就是parse之类的。然后他问我慢的在哪里，我说是download。他问我为什么download慢，如果网速一定的，为什么多线程下载多个文件就可以快？我一脸蒙蔽。。他给我提示说比如服务器很远，原来是latency。。 然后我写了个多线程版本的，结果还有问题= =http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=216747&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

写一个单机爬虫，先单线程，再多线程。Java如何停止不好写啊，如果同时满足两个条件保证他们在一个transaction里完成是需要额外work的。这里也被逮到了。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=214333&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

我当时说的是用Master/Workers， Master 端维护每个worker的状态 --》 空闲/执行。 当worker 发现queue 为空的时候，就转换状态为pending。 如果拿到数据并且正在处理的时候，就设置为Active。 Master 结束的条件就是，queue里没有数据，并且每个worker的状态都是pending。 如果同时满足两条，就结束所有的workers。 然后，面试官说，那你开始写代码吧。。。。于是我就用很伪的代码写了。。。 估计就挂在这一轮。希望大家能引以为鉴，顺利通过。。。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=212612&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


这里有代码：http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=277537&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

allocate id : 给一个数N，生成N个id， 用户可以调用allocate（）来分配一个id, 用完后调用release()释放id， 这样别的用户可以用。
一开始给了基于bit的解法，但allocate的复杂度是O(N), 要求改进，并提示memory不是问题。
最后的方法是基于hash的。所有的id生成后放到hash table里，然后从里面取http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=194896&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

问了个分配id的问题，范围从1-n，写两个函数allocate和release。第二轮之前lz上了个厕所，然而不幸迷路，最终让前台MM带回，结果面试只有50min。lz和面试官讨论了一下，写了个N位bit的方法，写完还剩15min，白人让优化，但是说时间来不及了，你就说想法，然后就想到了用线段树的方法，讨论了下时间空间复杂度，期间让算了下内存占用，然后问问题结束。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=182956&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


给你一个max_id的值，然后写两个function分别是allocate_id和deallocate_id。.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
allocate_id每次call的时候要返回一个没有被allocate过的available id。如果从1到max_id所有id都被占用了那要做error handling。
deallocate_id(int id)要release被allocate过的这个id，让这个id重新变得available。如果pass in的ID没有被allocate过要做error handling
先说了用queue存deallocate下来的id的办法，又说了用boolean array存每个ID是否被占用的方法，后来第二个方法又进化成用bit array存......这个时候，bitarray的方法 allocate是O(n), deallocate是O(1)。他space complexity问的很详细，要算多少个byte。 然后这个时候面试官说内存是没法比bit array更小了，但可以牺牲一点内存来让allocate更快。然后提示啊提示，讨论啊讨论，最后一秒我终于领会了他的方法....用tree来表示，root node的left child是一个bit，如果是1的话说明整个array的左半部分有available ID，0表示没有。right child表示右半边有没有available ID。这样一层层partition下去，最后bottom level就是代表整个0-max_id有没有被占用的bit array。这样allocate就是O(n)，内存是原来bit array linear search方法的两倍。没有见识的我表示好厉害！！没见过！！（好像在地里看到有人提过一句这个题用树做，但没看懂）不过那个时候已经没时间具体写这个方法的码了...要跪。-http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=213126&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311 本帖下面有解释线段树时间的图！


 id allocation/deallocation 先實作了queue的做法, 然後是bit array, 問是否有time/space complexity在兩個之間的方法。最後作了binary tree (each node stores whether there's any available ids in its subtrees) 有寫完，面試官很滿意http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=273407&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


allocate and release id in the range of [0, N], allocate和relase都要是o(1)
follow up 1: id分配完了怎么办，多次release 同一个id怎么办。
follow up 2: 如何减小内存花销，allocate的复杂度可以是o(n) -->使用bitmap
follow up 3: 如何在内存和效率上实现一个折衷，使用比bitmap多一些的内存，但是搜索接近o(1).
最后一个问题在提示下回答了，想法就是把bitmap分成不同部分，对每一个部分记录是否有id被分配过。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=185183&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


实现一个分配id的类，id可以是0~MAX_ID-1中的一个值，分配出去的id必须唯一，类里面还有个回收id的函数，总而言之就是实现这个类的两个函数allocate和dellocate，数组结构自己设计。我说了两个方案，一个用queue，一个用bool数组。他让我先讨论用queue的情况，写了代码，用queue很直接，然后他让改进时间和空间，方案就是用一个自增的整数，表示还没被分配的id，初始化为0，再有一个队列，每当dellocate时，就将这个回收的id放到一个队列里。每当allocate时，先判断这个队列里有没有id，有的话拿出来返回，没有就拿那个整数，并另其+=1，这样的话构造函数的复杂度就变成O(1)了，同时空间也省了很多。接着让讨论bool数组的情况，这个方法比较糟糕，初始化O(n),allocateO(n),唯一好处就是空间比queue省一点。然后他让改进，想了一会无果，他提示有没有办法可以让allocate更快呢，快32倍，快64倍。然后我就说用bit，每次我可以扫32位（int），然后如果这个int大于0的话，就说明这里面有一个id可用，然后就可以用常数级的方法找出这个id。他说还有没有更快的，比如存储一些临时信息？我就基于前面的方法和这个hint想到了用线段树，这样的话，初始化O(n),allocateO(logn),dellocateO(logn)，然后他让我写了代码，假设线段树已经建好了，要我实现allocate函数，pls note that 在实现的过程中，我假设一个数节点存着区间开始和结束点，可用id数量，左孩子和右孩子指针。写完后他让我优化空间，我说不需要开始和结束点，因为可以通过计算算出来。让我再优化，我说可用id数量可以换成一个bool值。让我再优化，让我省去两个指针，我说或许我可以用堆的数组实现方式来做，但是这不一定是一颗满二叉树，他说那假设maxid是2^n吧，我说那可以了，我只用一个数组就好了，a的左右孩子分别为a[2i+1],a[2i+2]。然后最终方案就变成了只需要2*MAX_ID-1个bit的空间来实现。总结一下就是用queue耗空间省时间，数组耗时间省空间。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=182850&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

duplicate file:

    1. 有些file 没有 permission 去访问, 会有 exception. 2. 递归可能导致 stack overflow, 所以应该用 iterator

    先码了一个把所有文件找出来的，小哥说可以。然后开始和小哥讨论怎么找出重复文件。我说MD5，然后又说有很小概率会碰撞，然后又说不然就上sha256或者sha512吧，又说实在不行就只能全文件对比了。结果小哥竟然说，sha512就行了你就当sha512不会碰撞就好了，然后就直接自定义了一个sha512函数用最简单的办法做了。然后又跟小哥说可以先看看size。小哥表示这样就可以了。接着小哥出了另一个follow up，说如果文件夹下面有类似于快捷方式的东西怎么办，快捷方式可以指向一个快捷方式，也可以指向一个文件夹，也可以指向一个文件。然后我一想这就相当于图里面有了环么，然后就弄了表记录已经访问过的位置就好了。小哥表示不错。问问题环节问了小哥dropbox自己怎么解决dup file问题的，小哥说他们也就是用sha512http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=209423&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

用dfs或bfs获得全部files in a directory..存到一个地方。。然后根据file metadata来分类..尽可能的让metadata来剔除一些unique的files或者content类似但是不是相同的。。然后hash剩下来的每个file..会得到的value来当hash map的key...hash map的value就是file path name..
再优化的话。instead of hashing a file, just compare first n bytes in a file. since hashing a large file may take a very long time. http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=143783&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

为什么选MD5
问我消耗内存最多的是什么地方（就是MD5那，需要优化一点一点hash），还可能出现什么问题？（比如在读的时候刚好有人在写文件）。什么情况到时outOfMemory之类的http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=275930&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

文件很大怎么处理?. from: 1point3acres.com/bbs
- 有很多很大的文件, 如何加快filter的速度?
- 用MD5会有什么问题, 有没有一个哈希算法是可以保证不会出现false positive的(我是不知道, 但小哥好像提到了SHR)
- 目录很深会出现什么问题?. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
- 如果有softlink会有什么问题, 如何解决?. Waral 鍗氬鏈夋洿澶氭枃绔�,
- 时间复杂度?http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=296976&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


白人小哥 经典题duplicated files 不跑代码 提供一些API比如判断是不是文件夹， 拼接路径， 说需要什么API自己写也行 全程自由发挥空间很大用python写的 先说最粗暴就比较内容 实现的是先比较文件大小 然后大小一样的再用MD5 哈希
follow up:
1. time complexity 怎么优化 md5的API加一个limit参数 每次生成文件一部分内容的hash 要写实现
2. 用了三个字典 分别比较size 部分hash 整个文件hash 他说这部分代码看起来很相似 能不能抽象出来 写lambda表达式 需要实现
3. 如果死循环了为什么 怎么办 soft link 说删除link 不行 用hashset visited把树的问题转换成图的问题 需要实现http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=299461&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


1) 如何确定文件类型？遍历目录文件时候，如何确定这是个regular文件，是一个符号链接，是一个特殊的设备文件，还是目录？这是在遍历时候的一个必要步骤。不同的语言和操作系统下可能有不同的方法。如果能够谈到linux下文件系统下有多种文件类型，Linux提供了多种API，比如is_regular_file(), is_block_file等保证确定文件类型，应该是加分项。. more info on 1point3acres.com
(2) 如何确定两个文件相同？所有文件对每个文件跟其它文件逐个byte比较是一个很直接了当的办法。但这样非常不高效。改进的办法应该是对文件产生指纹，比如用MD5，或者SHA256等hash算法来产生指纹。这样在指纹库里面进行匹配查找就容易多了。
(3) 但MD5等hash算法依然存在着冲突的可能性，也就是说，两个文件可能有同样的MD5值。怎么解决这个问题？MD5值相同的情况下，再对两个文件进行逐个byte比较。
(4) 都是大文件怎么优化这个重复文件检测？重复文件意味着两个大文件的每一个块都是相同的。可以将文件进行切块，对每个块生成MD5，这样大文件的比较就是比较每个文件的MD5列表。只有两个MD5列表完全一致，才说明两个文件完全相同。但在比较过程中，只要遇到不同的MD5，就可以跳出检测，节省时间。
(5) 如果文件数量非常多怎么办？这个考虑两点优化：第一点要对MD5指纹库查询并行化，首先是单机内多线程的查询，文件规模巨大的情况下，就是多机分布式查询。这个涉及到system design方面了。第二点是考虑文件自身的特性。文件大小相同才有可能是重复文件。所以在查询时，首先找到系统中其他相同大小的文件，然后只跟这些个文件的MD5列表对比，这样就缩小了查询范围。另外，对于一些小文件，是否可以有特殊的处理。比如空文件。比如文件特别小，那是否可以不产生MD5，直接进行byte比较。这个是开放性的提问，只要保证回答合理就行。
(6) 如果目录里面有soft symbol link怎么办？这个是要考虑是否出现死循环的情况。所以如果提到了第一个问题的解答，在这里就可以表明如果是symbol link就直接跳过。
(7) 如果目录很深怎么办？这个需要考虑，用来存储文件路径名的字符数组是否有溢出的可能性。
(8) 如果重复文件查询过程中死机了怎么办？第一点可以考虑checkpointing，定期保存进度。这样重新启动查询的时候，不需要从零开始。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=298344&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


max photo count： 实现一个类，用户可以view一张相片（给id），然后也可以求被目前被view最多k个photos（多次调用）http://www.1point3acres.com/bbs/thread-211240-1-1.html

可以参考李特抠 二九五http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=215225&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


给出一堆log, 里面有photo id和访问时间, 还有一个iterator, 能够按照photoId 和访问时间iterate, 问如何输出top m的访问photo. 鐣欏鐢宠璁哄followup: 如何存储这些log, 来支持方便的retrieve 这些信息. http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=139110&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


照片每次被view就會call View(photo id), 給top-k view photo. 一開始假設有整個oracle, 用heap解決。延伸如果view是一個個來，寫了一個很複雜的heap + hashmap。期待的最佳解應該是bucket sorthttp://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=273407&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


给了一个Iterator遍历{PhotoId, Timestamp}这样的数据(Timestamp和这个题没关系。。。)，实现getTopM获取访问最多的PhotoId，假设数据都可以放在内存中
FollowUp：1. 如果getTopM会被调用多次，同时iterator只会获取自上次调用getTopM之后的新数据如何处理。2. 用了一个Heap加HashMap，FollowUp就把这个结构状态存在Class中每次getTopM的时候进行更新。由于Java的PriorityQueue取TopK需要不断Poll，为了维护数据最后还需要把TopK再给add回去。另外Followup每次更新Count的时候PriorityQueue没有API能够直接进行Adjust，最直接的办法是remove再add但是remove是O(N)复杂度。所以自己实现了一个Heap的adjust，不断把Node给bubble up就好了。感觉应该也可以用bucket sort，不过最好和面试官确定一下数据范围；我并没有提这个方法，大家自行判断吧。 LeetCode: https://discuss.leetcode.com/top ... olution-bucket-sort
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=294622&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


有photo {photoId, timestamp}，还有iterator读取photo。实现getTopM返回review次数最多的M个photoId
这个题面经出现的次数比较少，没有准备好。。。花了很长时间才理解题意，没有时间写代码，不知能不能给过。。。. 鍥磋鎴戜滑@1point 3 acre其实timestamp／iterator什么的都是噱头。。。就是实现一个支持修改的heap 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
我的做法是用一个heap保持当前top m，还有一个hashmap<photoId, ptr_node_in_heap>，读到新的photo，通过hashmap找到对应的node，更新node，然后swim up／down。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=298525&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


token bucket：地里没找到详细的面经，也没准备。加上吃完饭实在太困反应迟钝，写的太烂.. 然后问如果有thread要求的token比较少，可以先给它token的话要怎么做.. 还有怎么加锁... 反正followup也是没写完，伤感http://www.1point3acres.com/bbs/thread-275930-1-1.html

写一个bucket对象，constructor是给一个max_capacity, 和按一个fill_rate向bucket添加tokens，然后写一个get(n_tokens)，多线程调用，token不够时block。写完后又写了一个put method。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=170828&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

TokenBucket。一个 class TokenBucket，有max_capacity，fill_rate 两个属性，要求实现 get (int n) function，thread safe。Followup，另加一个 put (int n) function.http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=207171&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

多线程tokenbucket, 实现ettoken(int n), token不够就block。 我用的pthread_cond_timedwait, 但是要注意sleep 的时间不保证是准确的， 所以需要while loop sleep http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=277537&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

token bucket，假设每x秒提供一个token，然后外面可以申请任意数量的token，如果token不够就block，要求concurrent情况下，不能有专门的thread产生token，怎样用最简单的方法实现https://www.jiuzhang.com/qa/766/


read write lock
这轮被虐得太惨了.. 而且还有有shadow。那个大哥基本就在手把手地挑问题+教我怎么写.. 最后超时了，面试官走了也没说啥= =http://www.1point3acres.com/bbs/thread-275930-1-1.html

read write lock。可以从Writer或者Reader方面来favor write，防止writer starved. 小哥刚开始很高冷，后面终于露出微笑。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=215633&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

实现 read write lock。（面试官 用的是 mutex） --> follow up, 怎么优化锁，读操作和写操作很多的时候，怎么权衡。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=212612&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

请利用conditional variable 和 lock 写一套reader lock & writer lockhttp://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=197713&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

整轮multithreading（我明明记得我填的是没有接触过multithreading啊喂）。具体题目我都不知道怎么描述，反正基本上是叫你写一个特别简单的function，但是这个funcion里面一定要调用一个特别费时间的已经有了的method。问怎么保持multithread safe，进而问怎么弄lock提高效率，接着继续加场景然后继续加conditional_variable，加完了以后继续加场景问怎么保持多线程安全。反正我感觉我所有知道的多线程知识已经被掏空了但是小哥还是意犹未尽，反正就是面到了最后一秒然后让我问问题。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=214225&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

网上有很多java的impementation，把这个好好看明白就差不多了，http://tutorials.jenkov.com/java ... ad-write-locks.html，他们最近应该是降bar了，要是能写出reentrant的就肯定没问题

 KV store transaction implementation： 就是要求实现一个in memory的map支持transaction，begin返回一个transactionID, 实现put(transacId, k, v) get(transactId, k ,v)以及commit，需要考虑多个transaction交错的情况以及abort http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=299159&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311


我下载的code：http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=234049&fromuid=208786
code合集：
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=209378&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3046%5D%5Bvalue%5D%3D25%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311