x*****n
发帖数: 195 | 1 水平不行，已挂。感慨自己工作也好几年了，主持设计开发的项目/feature还是太少。
感谢版上面过sumo logic的大牛的热情咨询。
感觉设计题考cache挺常见的，大家讨论一下？中国大叔主面，很nice，年轻三哥
shadoow。设计一个cache system，要pseduo code，存储结构，API等，不要求LRU等替
换策略，需要考虑concurrent的情况。要求考虑真实的使用场景，也就是这个cache
system码工们用起来很方便。我给的答案就是传统的hashtable的api，加上处理miss、
需要从硬盘或者数据库load的时候，做些处理确保不重复load。感觉让中国大叔失望了
:(
这种完全open的设计题最怕了，面试官很容易从你的解题过程中判断你的老练程度，
problem solving的思维方式，系统设计的基本原理，pro con的tradeoff，用code快速
描述的能力，等等。个人感觉挺难装出来的。
======================
别的几轮里的算法题：
1. 字典里有大量words，给一个query，如果在字典里能找到one edit distance则返回
那个word。followup是如果是k edit distance呢。不能对字典里的所有word做简单的
预处理（产生所有可能的k edit以后的词加入字典）。
2. 设计带历史记录的哈希表。对于同一个key下出现过的多个value都记录，每个value
都加个timestamp。查找时get（key， ts），输出value，其时间戳是在ts或者ts之前
最近的。
之前两轮店面都是树的题目，基本都挺简单的，一个稍微麻烦点的是任意叉树的序列化
和逆序列化。都要在codepad里跑过测试。 |
A*******e
发帖数: 2419 | 2 0.
设计一个cache system，要pseduo code，存储结构，API等，不要求LRU等替换策略，
需要考
虑concurrent的情况。要求考虑真实的使用场景，也就是这个cache system码工们用起
来很
方便。
-- 这个cache里放什么样的数据？
1. 字典里有大量words，给一个query，如果在字典里能找到one edit distance则返回
那个word。followup是如果是k edit distance呢。不能对字典里的所有word做简单的
预处理（产生所有可能的k edit以后的词加入字典）。
-- 这题有点意思。trie没法做模糊查询吧。
2. 设计带历史记录的哈希表。对于同一个key下出现过的多个value都记录，每个value
都加个timestamp。查找时get（key， ts），输出value，其时间戳是在ts或者ts之前
最近的。
-- unorder_map> hash_table; 查询用upper_bound，平均O(logk)？
之前两轮店面都是树的题目，基本都挺简单的，一个稍微麻烦点的是任意叉树的序列化
和逆序列化。都要在codepad里跑过测试。
-- 这个用特殊数值标记树的结尾？
【在 x*****n 的大作中提到】
: 水平不行，已挂。感慨自己工作也好几年了，主持设计开发的项目/feature还是太少。
: 感谢版上面过sumo logic的大牛的热情咨询。
: 感觉设计题考cache挺常见的，大家讨论一下？中国大叔主面，很nice，年轻三哥
: shadoow。设计一个cache system，要pseduo code，存储结构，API等，不要求LRU等替
: 换策略，需要考虑concurrent的情况。要求考虑真实的使用场景，也就是这个cache
: system码工们用起来很方便。我给的答案就是传统的hashtable的api，加上处理miss、
: 需要从硬盘或者数据库load的时候，做些处理确保不重复load。感觉让中国大叔失望了
: :(
: 这种完全open的设计题最怕了，面试官很容易从你的解题过程中判断你的老练程度，
: problem solving的思维方式，系统设计的基本原理，pro con的tradeoff，用code快速
|
t**r
发帖数: 3428 | 3 是设计数据库的cache吧？
这个没做过确实不好说 |
g*********e
发帖数: 14401 | 4 your cache requirement is too general to come up with any specific design,
better ask interviewer about the user cases and performance requirement. |
t**r
发帖数: 3428 | |
x*****n
发帖数: 195 | 6 跟面试官讨论下来他要一个特别general purpose的cache system，可以方便集成到任
何需要cache的系统里，所有read/write也没什么pattern，数据规模也没限制，
concurrent也是什么情况都需要讨论。我按常规做法想不断narrow down scope都被打
回来了。。。
sumo logic没给feedback，算法题我也不知道自己答得到底怎样，坐等版上大牛们了。
【在 A*******e 的大作中提到】
: 0.
: 设计一个cache system，要pseduo code，存储结构，API等，不要求LRU等替换策略，
: 需要考
: 虑concurrent的情况。要求考虑真实的使用场景，也就是这个cache system码工们用起
: 来很
: 方便。
: -- 这个cache里放什么样的数据？
: 1. 字典里有大量words，给一个query，如果在字典里能找到one edit distance则返回
: 那个word。followup是如果是k edit distance呢。不能对字典里的所有word做简单的
: 预处理（产生所有可能的k edit以后的词加入字典）。
|
s*****m
发帖数: 8094 | 7
是单机的cache还是distributed cache？
concurrent需不需要支持critical write？尤其是distributed的情况下。
【在 x*****n 的大作中提到】
: 水平不行，已挂。感慨自己工作也好几年了，主持设计开发的项目/feature还是太少。
: 感谢版上面过sumo logic的大牛的热情咨询。
: 感觉设计题考cache挺常见的，大家讨论一下？中国大叔主面，很nice，年轻三哥
: shadoow。设计一个cache system，要pseduo code，存储结构，API等，不要求LRU等替
: 换策略，需要考虑concurrent的情况。要求考虑真实的使用场景，也就是这个cache
: system码工们用起来很方便。我给的答案就是传统的hashtable的api，加上处理miss、
: 需要从硬盘或者数据库load的时候，做些处理确保不重复load。感觉让中国大叔失望了
: :(
: 这种完全open的设计题最怕了，面试官很容易从你的解题过程中判断你的老练程度，
: problem solving的思维方式，系统设计的基本原理，pro con的tradeoff，用code快速
|
b*****n
发帖数: 618 | 8 设计题比较open，不是很清楚需求到底是啥，听起来像是设计一个足够general的cache
framework。
算法题第一道不能做任何precomputation么？那样的话只能想到用trie暴力搜了。
第二道是hashmap + binary search？或者hashmap + treemap，假设所有data都在
memory里面。 |
t********5
发帖数: 522 | 9 cache这个如果换做我的话我可能会先山寨一个memcached，然后高级点再山寨一个
redis，再高级点可能要山寨cassandra，不过最后这个只知道大概没有实际用过
真让我说到这一步我还真就只能胡扯了…… |
g*****g
发帖数: 34805 | 10 我觉得山寨一个Guava Cache就可以了。
【在 t********5 的大作中提到】
: cache这个如果换做我的话我可能会先山寨一个memcached，然后高级点再山寨一个
: redis，再高级点可能要山寨cassandra，不过最后这个只知道大概没有实际用过
: 真让我说到这一步我还真就只能胡扯了……
|
t**r
发帖数: 3428 | 11 还是不够给力吧 不好用
★ 发自iPhone App: ChineseWeb 8.7
【在 g*****g 的大作中提到】
: 我觉得山寨一个Guava Cache就可以了。
|
x*****n
发帖数: 195 | 12 从单机版开始讨论，分布式的情况没怎么讨论时间就差不多来
【在 s*****m 的大作中提到】
:
: 是单机的cache还是distributed cache？
: concurrent需不需要支持critical write？尤其是distributed的情况下。
|
