1.Given Operations {z_min: v1, z_max: v2, min_range: , max_range:, random_drop: , grid:}, and a list of 3d points, output result after applying each filter in order
2. 设计定位服务。假设在backend的storage里面也已经有好几万个image，和它们的特征向量，这些image是知道它们的位置的。车第一次到街上，照相机照出一张照片，假设已经能从这个照片里提出一个特征向量，怎么最快从backend storage里找到最接近的image，从而知道你的位置。特征向量是0/1的，表示某个特征在这张图里出现或不出现。
First define similarity. Then how to query efficiently. How to fast query diff between two bit vector? (use bitwise xor).
Then follow up, each bit should has different weight, how to optimize? Use weight like a tf-idf.
3. Design and code a memcache. 奇葩的问题，开始以为是design distributed cache或者distributed database，但是interviewer说假设database已经实现好了，在distributed system里也很好。现在有db.put,db.get,cache.put,cache.get四个方法，在client端要实现put和get接口，你想怎么调用这4个方法实现这2个接口，能把key-value既存到db里也存到cache里。How to handle concurrency? (I answered add lock in cache first). (other possible solutions include add it to db, add it to cache, then get from cache, if not consistent, then delete the cache). Suppose there is a magical value LOCK. put(key, LOCK) means lock the key. Follow up, given putif function, get(key) -> value, cas, putif(key, value, cas) -> newcas. How
to implement the spin lock system.
4.Coding, group points within distance k together, output each group. For each point, do bfs and Use union find. But can do without using union find. Add an edge between two points during bfs. After all points are done, do dfs and the graph.
5. Design netflix. How does upload flow look like. How to store video. How to notify user when upload is complete. How to improve stream speed(use cdn, how does cdn work, why cdn has the video). How to suggest most k popular videos during last day. What about during rolling last 24 hours.
补充：
第一题dict里z_min: v就是保留所有z坐标大于等于v的点。random_drop: p 是对每个点以p的概率保留。grid: v 是把空间分成边长为v的立方体，所有落在同个立方体里的点只保留随便一个