后院的石头应该怎么处理？# Living
i*a
1 楼
1 best time to sell and buy stock1
2 find k largest/smallest in n sorted list
3 lru cache
4 design etsy database schema
5 find element in rotated array
~~~~~~~~~~~~~~~~~~~~~~
都不难，可惜挂了，自己分析，可能是1 第四轮印度小哥说的优化用db polymorphism
没懂（真的不太懂这个）2自己写题慢了（可是聊天20分钟，面试官也没有要出下一题
的意思）
～～～～～～
dropbox的在线题目
就是一个矩阵，来表示n个人之间的关系，可以是朋友（用f）或者是敌人（e）, 俄且
这个关系是双向的，现在 给你一个string的关系，还有两个人的id判断这个string的
关系是合法还是非法的，string关系比如 feffeef 是可以倒回来的。
～～～～～～～～～～
马上要面L家了，想请教一下几道经典题，new grad小白，啥都不懂，请各位大牛不吝
赐教：
1library design题，design一个java library，可以insert task，每个task有个
start
time，task要在start time开始run，library要支持multi threading
我的想法是hashmap(查询)＋priority queue(以时间排序)，multi-threading用
blocking queue，如何保证task在start time run呢？
2 tree to N-ary tree, 看了好多参考，没理解，我的想法是层叙遍历，同时建树，每
满n个就建一个结点
3 design web calendar
要求可以create event, send invitation, accept/reject invitation, forward
invitation, check calendar等等
class: calendar, date, event, invitation
db schema如果用cassandra
a) calendar table: key: user id; col: date; cell: event id(这个有点不解，如
果一个用户当天有多个event呢)
b) event table: key: event id; col: date+userid为composite key； cell:
event detail
c) invitation table: key: event id; col: user id(受邀请者)因为cassandra的
col不是fix sized的
d) user_invitation table: key: user id; col: invitation id; cell: 接受不接
受，如果接受就把event也写到user的event里？
那么如何实现forward或者像google calendar那种分享calendar的功能呢？
对数据库设计实在是没有什么经验，跪求各种资料和指导
这种calendar如果流量大，应该是read heavy还是write heavy呢？如果考虑
concurrency，因为一个用户只编辑他自己的calendar是不是就不要lock了呢？
4 streaming的题目：
Design and code a system that can accept millions of events in real time
and report the number of events for the last 10 minutes (sliding window).
The system has to account for performance and concurrency.
或者
有一个stream of messgages，把最近的一些message存到Window里面，就像个sliding
window一样。要求design这个Window class。
比如，Window里面存最近5分钟的message。
addMsg（）就要添加一个mesage。
getMsg（）就return一个message。
getAvg（）计算window里所有message的val的平均值。
是不是该用spark+sliding window的方法？像这个帖子
http://www.michael-noll.com/blog/2013/01/18/implementing-real-t
具体就是用一个queue，如果expire了就踢出去，concurrency就用blocking queue，
performance考虑用distributed？（有木有什么distributed queue, 我听过一个
apache mina不知道是不是这个？）
5a restful server with 4GB,
given a request such as: http://seq=4?len=60?xxxxdata
the system will store the binary data with that sequence number.
given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.
multiple clients calling simutaneous
what data structure, concurrency, locking, etc..
这道题一直没懂。。。
6 关于iterator, find union/intersection of array using two iterator, 因为要
比较两个iterator大小再决定如何做，可是iterator只有两个Function, hasnext和
next，而且next就直接移到下一个了。是不是要写一个peek iterator比较好，就是加
一个方法getvalue（），或者还是写一个iterator wrapper像mergeksortedlist那种？
2 find k largest/smallest in n sorted list
3 lru cache
4 design etsy database schema
5 find element in rotated array
~~~~~~~~~~~~~~~~~~~~~~
都不难，可惜挂了，自己分析，可能是1 第四轮印度小哥说的优化用db polymorphism
没懂（真的不太懂这个）2自己写题慢了（可是聊天20分钟，面试官也没有要出下一题
的意思）
～～～～～～
dropbox的在线题目
就是一个矩阵，来表示n个人之间的关系，可以是朋友（用f）或者是敌人（e）, 俄且
这个关系是双向的，现在 给你一个string的关系，还有两个人的id判断这个string的
关系是合法还是非法的，string关系比如 feffeef 是可以倒回来的。
～～～～～～～～～～
马上要面L家了，想请教一下几道经典题，new grad小白，啥都不懂，请各位大牛不吝
赐教：
1library design题，design一个java library，可以insert task，每个task有个
start
time，task要在start time开始run，library要支持multi threading
我的想法是hashmap(查询)＋priority queue(以时间排序)，multi-threading用
blocking queue，如何保证task在start time run呢？
2 tree to N-ary tree, 看了好多参考，没理解，我的想法是层叙遍历，同时建树，每
满n个就建一个结点
3 design web calendar
要求可以create event, send invitation, accept/reject invitation, forward
invitation, check calendar等等
class: calendar, date, event, invitation
db schema如果用cassandra
a) calendar table: key: user id; col: date; cell: event id(这个有点不解，如
果一个用户当天有多个event呢)
b) event table: key: event id; col: date+userid为composite key； cell:
event detail
c) invitation table: key: event id; col: user id(受邀请者)因为cassandra的
col不是fix sized的
d) user_invitation table: key: user id; col: invitation id; cell: 接受不接
受，如果接受就把event也写到user的event里？
那么如何实现forward或者像google calendar那种分享calendar的功能呢？
对数据库设计实在是没有什么经验，跪求各种资料和指导
这种calendar如果流量大，应该是read heavy还是write heavy呢？如果考虑
concurrency，因为一个用户只编辑他自己的calendar是不是就不要lock了呢？
4 streaming的题目：
Design and code a system that can accept millions of events in real time
and report the number of events for the last 10 minutes (sliding window).
The system has to account for performance and concurrency.
或者
有一个stream of messgages，把最近的一些message存到Window里面，就像个sliding
window一样。要求design这个Window class。
比如，Window里面存最近5分钟的message。
addMsg（）就要添加一个mesage。
getMsg（）就return一个message。
getAvg（）计算window里所有message的val的平均值。
是不是该用spark+sliding window的方法？像这个帖子
http://www.michael-noll.com/blog/2013/01/18/implementing-real-t
具体就是用一个queue，如果expire了就踢出去，concurrency就用blocking queue，
performance考虑用distributed？（有木有什么distributed queue, 我听过一个
apache mina不知道是不是这个？）
5a restful server with 4GB,
given a request such as: http://seq=4?len=60?xxxxdata
the system will store the binary data with that sequence number.
given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.
multiple clients calling simutaneous
what data structure, concurrency, locking, etc..
这道题一直没懂。。。
6 关于iterator, find union/intersection of array using two iterator, 因为要
比较两个iterator大小再决定如何做，可是iterator只有两个Function, hasnext和
next，而且next就直接移到下一个了。是不是要写一个peek iterator比较好，就是加
一个方法getvalue（），或者还是写一个iterator wrapper像mergeksortedlist那种？
