西雅图分店，直接上题，等结果中
-
上来问了一些CS基本知识，面向对象语言基础概念。然后抛出一常见题。
设计O(1)时间insert(), delete(), random()的数据结构，要求解释为什么随机是uniform的。 -
国人大叔两题
(1) 写一个tree的iterator，支持next()和hasNext()。秒了。可能是写得太快了还有不少时间。大叔说那就再来一瓶，哦不，是再来一题
(2) 如果有库函数已经实现了这个iterator, 要你增加prev()和hasPrev()。prev最多可以回退一步。
我的做法是继承这个iterator。大叔这时候插话说为什么用继承而不是聚类，各有什么优缺点。
然后内部保留一个上一步的引用。大叔很满意。最后临走说要是最多能回退k步呢？ -
设计google map上的typeahead。比如用户开始敲数字的时候先是当成street #, 这是如果输入字母，就会当成street name。比如敲367时会typeahead 367 xxx St, …。如果接下来时367th，会马上替换成搜街道。另外还要考虑输出结果的排序。比如里用户近的排考前。瞎说了一通，不知道效果如何
-
常见的BQ
-
设计数据结构表达稀疏矩阵，实现加法运算。设计测试case.