c****s
发帖数: 241 | 1 I only met three persons today. It looks failed already although I think I d
id pretty well. The interview questions that I met today:
1) implement Most Recently Used cache
2) a. print trees in level by level (breadth first seach)
b. print the trees in level by level. But nodes in the odd levels are pri
nted in sequence order,
and those in even levels are printed in reverse order.
3) there is one binary search tree. Now, add one more pointer for each node
and link nodes in the same level. The |
t*********n
发帖数: 1292 | |
d**a
发帖数: 84 | 3 请问能不能把你的回答过程也写出来？分析一下原因？
d
pri
node
N
【在 c****s 的大作中提到】
: I only met three persons today. It looks failed already although I think I d
: id pretty well. The interview questions that I met today:
: 1) implement Most Recently Used cache
: 2) a. print trees in level by level (breadth first seach)
: b. print the trees in level by level. But nodes in the odd levels are pri
: nted in sequence order,
: and those in even levels are printed in reverse order.
: 3) there is one binary search tree. Now, add one more pointer for each node
: and link nodes in the same level. The
|
c****s
发帖数: 241 | 4 for windows live.
【在 t*********n 的大作中提到】
: for which position?
|
g*****u
发帖数: 298 | 5 有道理，分析原因，吸取教训是很重要的。
【在 d**a 的大作中提到】
: 请问能不能把你的回答过程也写出来？分析一下原因？
:
: d
: pri
: node
: N
|
z*******y
发帖数: 578 | 6 楼主是面SDE还是SDET？
看问题像是SDET |
g*******y
发帖数: 1930 | 7 感觉是SDE，要是SDET的话会有很多的测试问题吧
建议楼主再回头思考一下自己的面试过程：
有时候你觉得都做对了的不一定对；
对了不一定最优；
最优了说不定还有其他的方法(可以讨论tradeoff)；
算法没问题了coding不一定能写的很漂亮；
题目做的完美了，你说话的语气态度(这个才是真正的考察behavior的地方)不一定做的
好；
所以我觉得要多来跟大家讨论，才能发现自己的不足，借鉴别人的长处。
【在 z*******y 的大作中提到】
: 楼主是面SDE还是SDET？
: 看问题像是SDET
|
r**u
发帖数: 1567 | 8 什么是most recently used cache？ cache替换该是替换least recently used cache
line吧。
d
pri
node
N
【在 c****s 的大作中提到】
: I only met three persons today. It looks failed already although I think I d
: id pretty well. The interview questions that I met today:
: 1) implement Most Recently Used cache
: 2) a. print trees in level by level (breadth first seach)
: b. print the trees in level by level. But nodes in the odd levels are pri
: nted in sequence order,
: and those in even levels are printed in reverse order.
: 3) there is one binary search tree. Now, add one more pointer for each node
: and link nodes in the same level. The
|
H*X
发帖数: 281 | 9 是啊, 如果是LRU还是蛮常出现的题目, 可以用stack做 |
r**u
发帖数: 1567 | 10 怎么用stack做LRU，stack不是ordered啊。我想直接用一个array，每个entry对应一个
cache line，记录访问时间。替换的时候就check整个array，或者maintain一个
priority_queue。
【在 H*X 的大作中提到】
: 是啊, 如果是LRU还是蛮常出现的题目, 可以用stack做
|
|
|
R***r
发帖数: 120 | 11 Why not use hash table? Store each data in the hash table as a doubly linked
list node where next and previous pointers are the hash key. When reading a
node, move it to the head. Add to head and delete from tail. Timestamp is
not necessary.
【在 r**u 的大作中提到】
: 怎么用stack做LRU，stack不是ordered啊。我想直接用一个array，每个entry对应一个
: cache line，记录访问时间。替换的时候就check整个array，或者maintain一个
: priority_queue。
|
c****s
发帖数: 241 | 12 一般这种地方没做好，自己很难发觉。不像题目没有做出来，回头想一下就可以搞定。
多谢建议
【在 g*******y 的大作中提到】
: 感觉是SDE，要是SDET的话会有很多的测试问题吧
: 建议楼主再回头思考一下自己的面试过程：
: 有时候你觉得都做对了的不一定对；
: 对了不一定最优；
: 最优了说不定还有其他的方法(可以讨论tradeoff)；
: 算法没问题了coding不一定能写的很漂亮；
: 题目做的完美了，你说话的语气态度(这个才是真正的考察behavior的地方)不一定做的
: 好；
: 所以我觉得要多来跟大家讨论，才能发现自己的不足，借鉴别人的长处。
|
c****s
发帖数: 241 | 13 我当时给的就是这个解，用circular double link list + hash table.
linked
a
【在 R***r 的大作中提到】
: Why not use hash table? Store each data in the hash table as a doubly linked
: list node where next and previous pointers are the hash key. When reading a
: node, move it to the head. Add to head and delete from tail. Timestamp is
: not necessary.
|
g*****u
发帖数: 298 | 14 这个应该是正解啊。楼主是不是表达的不清楚，还是态度有问题？不过有的情况下也不
见得是你的问题。我遇到过比较笨的interviewer，自己想不清楚。
顺便再讨论一下LFU的实现吧。hash table(key:page ID, value: map iterator) +
map(key:freq, value:page id)?
一个变种是加上时间限制的LFU,比如page fault的时候先换出5分钟以上的，如果都在5
分钟之内，换出次数最少的。以前也没讨论出个所以然来。
【在 c****s 的大作中提到】
: 我当时给的就是这个解，用circular double link list + hash table.
:
: linked
: a
|
r**u
发帖数: 1567 | 15 这个，我不知道你们有没有考虑hardware level的overhead, 真正在hardware level实
现的时候，用hash恐怕overhead太大吧。
在5
【在 g*****u 的大作中提到】
: 这个应该是正解啊。楼主是不是表达的不清楚，还是态度有问题？不过有的情况下也不
: 见得是你的问题。我遇到过比较笨的interviewer，自己想不清楚。
: 顺便再讨论一下LFU的实现吧。hash table(key:page ID, value: map iterator) +
: map(key:freq, value:page id)?
: 一个变种是加上时间限制的LFU,比如page fault的时候先换出5分钟以上的，如果都在5
: 分钟之内，换出次数最少的。以前也没讨论出个所以然来。
|
B**r
发帖数: 42 | 16 记得真正的hardware是并行比较器吧，一次比较很多。
【在 r**u 的大作中提到】
: 这个，我不知道你们有没有考虑hardware level的overhead, 真正在hardware level实
: 现的时候，用hash恐怕overhead太大吧。
:
: 在5
|
m*****k
发帖数: 64 | 17 能不能具体讲一下？或者谁有链接吗？
在5
【在 g*****u 的大作中提到】
: 这个应该是正解啊。楼主是不是表达的不清楚，还是态度有问题？不过有的情况下也不
: 见得是你的问题。我遇到过比较笨的interviewer，自己想不清楚。
: 顺便再讨论一下LFU的实现吧。hash table(key:page ID, value: map iterator) +
: map(key:freq, value:page id)?
: 一个变种是加上时间限制的LFU,比如page fault的时候先换出5分钟以上的，如果都在5
: 分钟之内，换出次数最少的。以前也没讨论出个所以然来。
|
H*X
发帖数: 281 | 18 每次搜索一遍, 看看stack里有没有要找的,有的话,就挪到stack最上面, 替换的时候,
就把stack最下面的换掉,
【在 r**u 的大作中提到】
: 怎么用stack做LRU，stack不是ordered啊。我想直接用一个array，每个entry对应一个
: cache line，记录访问时间。替换的时候就check整个array，或者maintain一个
: priority_queue。
|
