s***c
发帖数: 50 | 1 刚从微软onsite回来。 当天面试了6轮，从11点直到下午6点，最后都快撑不住了。有
一个算法问题，都不太难，但有很多open design的问题有些难度。我记得的问题有几
个：
1. two arrays of strings A and B, find intersections, union, A-B and B-A.
如果array小于mem size，我的思路是: scan A array, 建立hash table; 然后scan
array B, 对每一个元素
检查是否在A 的hash table存在。在白板上code实现。
如果array 大于mem size, 导致hash table也大于mem size, 则对每个array做
external sort:
把array分割成多块，每块都小于mem size, load到memory, sort, 写回disk；然后
merge sort.
之后，顺序扫描另个array，比较每个元素是否相同。
面试官还问，如果用SSD，该如何改进。我的答案是建立index table,但这是把index
table存在SSD里。
2. 不断从一个stream里读数据，找到最大的K个数。就是用一个大小为K的min-heap就
好了。但是要求
写code 实现min-heap的插入/删除操作。
3. 一个超大文件(many TB)， have 1 GB memory. 如何设计一个cache，主要目的是
缓存最近访问过的
数据。本质上就是一个LRU list加上一个hash table。用文件的offset做key来查找
hash table以找到
访问过的数据记录。在数据记录里要包括一个refence count来标识当前active的数据。
同时要更新LRU list。当memory不够用时，要evict一些缓存的数据。
4. tow single linked-list, see if they converge。我用了career cup上典型解法
，后来在面试官提醒下才发现还有更好的方法：
traverse list 1, note down last node;
traverse list 2, note down last node;
it the two last nodes are identical, converge
(2) find converge point。这个不用多说了吧。 |
k*j
发帖数: 153 | |
a*****g
发帖数: 110 | 3 zan面经！
请问lz面的是哪个组？是SDE么？
-A.
【在 s***c 的大作中提到】
: 刚从微软onsite回来。 当天面试了6轮，从11点直到下午6点，最后都快撑不住了。有
: 一个算法问题，都不太难，但有很多open design的问题有些难度。我记得的问题有几
: 个：
: 1. two arrays of strings A and B, find intersections, union, A-B and B-A.
: 如果array小于mem size，我的思路是: scan A array, 建立hash table; 然后scan
: array B, 对每一个元素
: 检查是否在A 的hash table存在。在白板上code实现。
: 如果array 大于mem size, 导致hash table也大于mem size, 则对每个array做
: external sort:
: 把array分割成多块，每块都小于mem size, load到memory, sort, 写回disk；然后
|
g*****i
发帖数: 2162 | 4 bless
第一题ssd和普通有啥区别?不用考虑硬盘寻道时间了? 你的index table存什么呢?
第三题"在数据记录里要包括一个refence count来标识当前active的数据" 什么意思?
最后一题反正也要找出list长度,直接看最后个元素一样与否用来判断确实好. |
s***c
发帖数: 50 | 5
我面的是SDE, windows azure组
【在 a*****g 的大作中提到】
: zan面经！
: 请问lz面的是哪个组？是SDE么？
:
: -A.
|
s***c
发帖数: 50 | 6
ssd的好处在于它的random access.
cache里每项记录要有一个refcount，如果一个记录正在被使用，它的refcount>0。这
样在evict时该记录就不会被reclaim了。
【在 g*****i 的大作中提到】
: bless
: 第一题ssd和普通有啥区别?不用考虑硬盘寻道时间了? 你的index table存什么呢?
: 第三题"在数据记录里要包括一个refence count来标识当前active的数据" 什么意思?
: 最后一题反正也要找出list长度,直接看最后个元素一样与否用来判断确实好.
|
g*****i
发帖数: 2162 | 7
那你的index table其实就相当于前面的hashtable吧,不过是存在ssd里的?
LRU里自动把使用过的放到list最后了,为啥还要用ref count呢? 要删除的时候直接删
list最前的就可以了吧.
【在 s***c 的大作中提到】
:
: ssd的好处在于它的random access.
: cache里每项记录要有一个refcount，如果一个记录正在被使用，它的refcount>0。这
: 样在evict时该记录就不会被reclaim了。
|
s***c
发帖数: 50 | 8
差不多就这个意思。
新的数据插入cache时，如果out of mem,需要evict old data. 这时候需要检查
refcount，如果refcount>0，标识该数据正在被其他thread访问，不能evcit它。
【在 g*****i 的大作中提到】
:
: 那你的index table其实就相当于前面的hashtable吧,不过是存在ssd里的?
: LRU里自动把使用过的放到list最后了,为啥还要用ref count呢? 要删除的时候直接删
: list最前的就可以了吧.
|
c****p
发帖数: 6474 | 9 如果是假设LRU的话，ref count应该是用不上的。。
任何一个entry被访问的时候，立刻就将这条entry放在list的最前端，
evict的时候从list的尾端移除，而且能够保证被移除的肯定是LRU的。
ref count一般是用在dead cache block prediction的，
实现LRU用不着它。
【在 s***c 的大作中提到】
:
: 差不多就这个意思。
: 新的数据插入cache时，如果out of mem,需要evict old data. 这时候需要检查
: refcount，如果refcount>0，标识该数据正在被其他thread访问，不能evcit它。
|
g*****i
发帖数: 2162 | 10 放list 尾端删除是不是比从head删除效率高? 似乎看到过,原因又是什么呢? 难道是因
为要更新heap的head信息?
【在 c****p 的大作中提到】
: 如果是假设LRU的话，ref count应该是用不上的。。
: 任何一个entry被访问的时候，立刻就将这条entry放在list的最前端，
: evict的时候从list的尾端移除，而且能够保证被移除的肯定是LRU的。
: ref count一般是用在dead cache block prediction的，
: 实现LRU用不着它。
|
|
|
c****p
发帖数: 6474 | 11 这个应该用不到heap吧。。。
我说的这个是在SimpleScalar里面看到的。
双链表就能实现吧，专门设一个变量保存尾端entry就可以了，
hit和miss的代价都是O(1)的。
【在 g*****i 的大作中提到】
: 放list 尾端删除是不是比从head删除效率高? 似乎看到过,原因又是什么呢? 难道是因
: 为要更新heap的head信息?
|
G****2
发帖数: 37 | 12 Open Design 都问什么了，能说说么？
thanks. |
f*******t
发帖数: 7549 | 13 楼主举的例子就是Open Design吧。。。
这面经质量挺高的
【在 G****2 的大作中提到】
: Open Design 都问什么了，能说说么？
: thanks.
|
h*u
发帖数: 122 | |
l*******y
发帖数: 192 | 15 很赞的面经哦！
do you mind if i forward this information on
http://www.overseatalents.com for free?
Thanks. |
s***c
发帖数: 50 | 16 只要能帮助更多中国人，欢迎转载 :)
【在 l*******y 的大作中提到】
: 很赞的面经哦！
: do you mind if i forward this information on
: http://www.overseatalents.com for free?
: Thanks.
|
l*******y
发帖数: 192 | 17 无数赞！！
【在 s***c 的大作中提到】
: 只要能帮助更多中国人，欢迎转载 :)
|
s*******f
发帖数: 1114 | 18 //2. 不断从一个stream里读数据，找到最大的K个数。就是用一个大小为K的min-heap就
//好了。但是要求
//写code 实现min-heap的插入/删除操作。
int* GetMaxKNums(int k){
const static int gMagicNumberForStop = -1;
if (k < 1)
return NULL;
int *arr = new int[k];
fill(arr, arr + k, INT_MIN);
while (1){
int n;
cin >> n;
if (n == gMagicNumberForStop){
return arr;
}else if (n > arr[0]){
int r = 0;
for (int j = 1; j < k; j = j * 2 + 1){
if (j + 1 < k && arr[j] > arr[j + 1])
++j;
if (n > arr[j]){
arr[r] = arr[j];
r = j;
}else{
break;
}
}
arr[r] = n;
}
}
} |
e***s
发帖数: 799 | 19 求解答。
“把array分割成多块，每块都小于mem size, load到memory, sort, 写回disk；然后
merge sort.
之后，顺序扫描另个array，比较每个元素是否相同。”
merge sort的时候也只能一个一个元素从file里面读出吗？这样也会很慢吧？
扫另外一个array,然后再二分查找sort好的那个array？也是直接在file完成吗？ |
e***s
发帖数: 799 | 20 //2. 不断从一个stream里读数据，找到最大的K个数。就是用一个大小为K的min-heap就
//好了。但是要求
//写code 实现min-heap的插入/删除操作。
public static void getKMaxNumber(int k)
{
int[] min_heap;
min_heap = new int[k + 1]; //min_heap[1] is root.
for (int i = 0; i <= k; i++)
min_heap[i] = int.MinValue;
while (true)
{
int n;
n = Convert.ToInt32(Console.ReadLine());
if(n > min_heap[1])
{
min_heap[1] = n;
Heap(min_heap, 1);
}
Console.WriteLine("{0}, {1}, {2}, {3}, {4}", min_heap[1],
min_heap[2], min_heap[3], min_heap[4], min_heap[5]);
}
}
public static void Heap(int[] heap, int index)
{
int left = index << 1;
int right = (index << 1) + 1;
int minindex = index;
if (left < heap.Length && heap[left] < heap[minindex])
minindex = left;
if (right < heap.Length && heap[right] < heap[minindex])
minindex = right;
if (minindex != index)
{
int temp = heap[minindex];
heap[minindex] = heap[index];
heap[index] = temp;
Heap(heap, minindex);
}
} |
