c***p
发帖数: 221 | 1 1. 给定内存开始地址和大小， 实现 m a l l o c 和 f r e e
只能用给定的内存，没有额外的空间。
讨论了半天，其实他想要的是knuth 的第一卷里面Dynamic Storage Allocation
2. 实现 h a s h t a b l e
3. 序列化一个BST, 放到文件中，然后基于文件做key search.
node中不仅有key 还有 data
|
p*****2
发帖数: 21240 | 2
哪个组呀？电面还是onsite?
【在 c***p 的大作中提到】
: 1. 给定内存开始地址和大小， 实现 m a l l o c 和 f r e e
: 只能用给定的内存，没有额外的空间。
: 讨论了半天，其实他想要的是knuth 的第一卷里面Dynamic Storage Allocation
: 2. 实现 h a s h t a b l e
: 3. 序列化一个BST, 放到文件中，然后基于文件做key search.
: node中不仅有key 还有 data
:
|
c***p
发帖数: 221 | 3 onsite. 面试官说是general面试。不针对组。
感觉对coding要求比较高。要简洁，清晰。
【在 p*****2 的大作中提到】
:
: 哪个组呀？电面还是onsite?
|
p*****2
发帖数: 21240 | 4
第一题没看过书咋办呢？只能胡侃了。第三题有什么好办法吗？
【在 c***p 的大作中提到】
: onsite. 面试官说是general面试。不针对组。
: 感觉对coding要求比较高。要简洁，清晰。
|
c***p
发帖数: 221 | 5 第一题我一开始用链表表示已分配和未分配的内存块。他不满意。强调只能用给定的内
存范围做。
主要方法就是：在分配一块内存的时候，用开始的几个字节表示这个块的大小和是否是
空闲块。(knuth 的书里叫 TAG)。这样回收的时候，就可以知道内存的大小了，如果后
面紧挨着的内存块如果也是空闲块就能合并了。
注意：TAG size的是和整个内存块大小相关的。
优化：相邻空闲块的合并可以delay到分配的时候做。不必在free的时候做。
第三题，我一开始做错了方向。到后来才意识到，已经来不及了。
我的方法是：
对于每个node，在文件中记录下key, 左儿子的offset, 右儿子的offset, 数据块的大
小，以及数据。
BFS遍历BST,依次把node信息append到文件上去。儿子的offset要在遍历的过程中填到
父节点的记录上去。
【在 p*****2 的大作中提到】
:
: 第一题没看过书咋办呢？只能胡侃了。第三题有什么好办法吗？
|
p*****2
发帖数: 21240 | 6
第一题我也有这些思路。刚才去想碎片整理了。好像不用考虑这个。
第三题这个思路不错。好久不用文件了。忘记文件可以跳跃读取？
希望你很快拿到offer。
【在 c***p 的大作中提到】
: 第一题我一开始用链表表示已分配和未分配的内存块。他不满意。强调只能用给定的内
: 存范围做。
: 主要方法就是：在分配一块内存的时候，用开始的几个字节表示这个块的大小和是否是
: 空闲块。(knuth 的书里叫 TAG)。这样回收的时候，就可以知道内存的大小了，如果后
: 面紧挨着的内存块如果也是空闲块就能合并了。
: 注意：TAG size的是和整个内存块大小相关的。
: 优化：相邻空闲块的合并可以delay到分配的时候做。不必在free的时候做。
: 第三题，我一开始做错了方向。到后来才意识到，已经来不及了。
: 我的方法是：
: 对于每个node，在文件中记录下key, 左儿子的offset, 右儿子的offset, 数据块的大
|
f****0
发帖数: 151 | 7 第一题的话可以看一下这个
http://gee.cs.oswego.edu/dl/html/malloc.html
我只看了里面的那张图，大概看懂。。
第三题的话我会把node分成非数据和数据两部分吧，非数据部分同时还包含有指向数据
部分的offset和size，这样的话非数据部分的长度就是固定的，便于搜索。 |
c***p
发帖数: 221 | 8 第一题不必考虑碎片。
面试过程感觉到，他们不仅要求算法想的快，代码质量也要高。代码写的难看他们似乎
也不满意。
每道题大概给你20-30分钟。从问题到coding结束。所以，同学们有空一定要多练
coding。算法想出来了，但是没coding好很吃亏。
【在 p*****2 的大作中提到】
:
: 第一题我也有这些思路。刚才去想碎片整理了。好像不用考虑这个。
: 第三题这个思路不错。好久不用文件了。忘记文件可以跳跃读取？
: 希望你很快拿到offer。
|
c***p
发帖数: 221 | 9
细节也要注意，比如字节对齐等。其中的陷阱不少。小心对待
我也提到了这个方法。但是计算offset的时候写错了:-(
【在 f****0 的大作中提到】
: 第一题的话可以看一下这个
: http://gee.cs.oswego.edu/dl/html/malloc.html
: 我只看了里面的那张图，大概看懂。。
: 第三题的话我会把node分成非数据和数据两部分吧，非数据部分同时还包含有指向数据
: 部分的offset和size，这样的话非数据部分的长度就是固定的，便于搜索。
|
f****0
发帖数: 151 | 10
嗯。。真写起来很容易错。。
【在 c***p 的大作中提到】
:
: 细节也要注意，比如字节对齐等。其中的陷阱不少。小心对待
: 我也提到了这个方法。但是计算offset的时候写错了:-(
|
|
|
p*****2
发帖数: 21240 | 11
20－30分钟写出来也不容易呀。微软啥时候要求这么高了？
【在 c***p 的大作中提到】
: 第一题不必考虑碎片。
: 面试过程感觉到，他们不仅要求算法想的快，代码质量也要高。代码写的难看他们似乎
: 也不满意。
: 每道题大概给你20-30分钟。从问题到coding结束。所以，同学们有空一定要多练
: coding。算法想出来了，但是没coding好很吃亏。
|
c***p
发帖数: 221 | 12 面试一个人也就是45分钟。开始10分钟聊简历，背景介绍之类的。最后5分钟他回答问
题。所以剩下也就30分钟给的时间做题用。
【在 p*****2 的大作中提到】
:
: 20－30分钟写出来也不容易呀。微软啥时候要求这么高了？
|
p*****2
发帖数: 21240 | 13
微软的面试是60分钟吧？
【在 c***p 的大作中提到】
: 面试一个人也就是45分钟。开始10分钟聊简历，背景介绍之类的。最后5分钟他回答问
: 题。所以剩下也就30分钟给的时间做题用。
|
c***p
发帖数: 221 | 14 原则是60分钟。不过他们都争取45分钟结束。这是一个面试官和我说的。果然，今天的
4个面试官都是45分钟结束。
【在 p*****2 的大作中提到】
:
: 微软的面试是60分钟吧？
|
h********6
发帖数: 285 | |
p*****2
发帖数: 21240 | 16
靠。是不是说明你表现太好了？
【在 c***p 的大作中提到】
: 原则是60分钟。不过他们都争取45分钟结束。这是一个面试官和我说的。果然，今天的
: 4个面试官都是45分钟结束。
|
w****x
发帖数: 2483 | 17 啊!! 文件访问一般都是sequential的吧.
seek(n)操作硬盘的访问是O(1)还是O(n)啊, 底层不懂哎 |
l*****a
发帖数: 14598 | 18 BST的序列化没这么麻烦吧
你去看看那个leetcode. no need for offset...
一行一项，key在开头，直接挨行查，不可以吗？
【在 c***p 的大作中提到】
: 原则是60分钟。不过他们都争取45分钟结束。这是一个面试官和我说的。果然，今天的
: 4个面试官都是45分钟结束。
|
c***p
发帖数: 221 | 19 因为NODE中有Binary Data，所以不能用换行符来分割记录。
【在 l*****a 的大作中提到】
: BST的序列化没这么麻烦吧
: 你去看看那个leetcode. no need for offset...
: 一行一项，key在开头，直接挨行查，不可以吗？
|
c***p
发帖数: 221 | 20 不是Fresh.不过工作经验不到两年。估计是被按照fresh来面的。
【在 h********6 的大作中提到】
: lz是fresh grad吗？
|
|
|
p*****2
发帖数: 21240 | 21
我印象中一直是sequential。不过硬盘读写肯定能跳跃。file的话如果cache了应该也
可以跳跃提高性能。最好有大牛来confirm一下。
【在 w****x 的大作中提到】
: 啊!! 文件访问一般都是sequential的吧.
: seek(n)操作硬盘的访问是O(1)还是O(n)啊, 底层不懂哎
|
b********e
发帖数: 386 | 22 早说过，M,A的面试题不比LGF容易
【在 c***p 的大作中提到】
: 1. 给定内存开始地址和大小， 实现 m a l l o c 和 f r e e
: 只能用给定的内存，没有额外的空间。
: 讨论了半天，其实他想要的是knuth 的第一卷里面Dynamic Storage Allocation
: 2. 实现 h a s h t a b l e
: 3. 序列化一个BST, 放到文件中，然后基于文件做key search.
: node中不仅有key 还有 data
:
|
w****x
发帖数: 2483 | |
w****x
发帖数: 2483 | 24
leetcode假设每个节点都是int, 这里每个节点的大小可能都不一样, 而且最主要的是
这题不光序列化, 还用用BST的性质查找在硬盘上(不能全部load到内存)查找, 要不存
储个前序遍历就可以了.我第一眼看到这题就想file到底能不能random access或random
access真像内存一样可以是O(1)???
【在 l*****a 的大作中提到】
: BST的序列化没这么麻烦吧
: 你去看看那个leetcode. no need for offset...
: 一行一项，key在开头，直接挨行查，不可以吗？
|
c***p
发帖数: 221 | 25 是的。这种面试题都不是那种YES/NO问题。
面试官要看你如果解决问题以及熟练程度。
【在 w****x 的大作中提到】
: 这种面试题很开放啊, 代码都很抽象
|
w****x
发帖数: 2483 | 26
第一题有要你写代码吗??
【在 c***p 的大作中提到】
: 是的。这种面试题都不是那种YES/NO问题。
: 面试官要看你如果解决问题以及熟练程度。
|
p*****2
发帖数: 21240 | 27
random
是呀。你做下research吧。回来share一下。我的感觉是file是有cache的，所以random
访问效率可能提升。
【在 w****x 的大作中提到】
:
: 第一题有要你写代码吗??
|
w****x
发帖数: 2483 | 28
random
http://stackoverflow.com/questions/2438953/how-is-fseek-impleme
这里有讨论, 看的不大懂
【在 p*****2 的大作中提到】
:
: random
: 是呀。你做下research吧。回来share一下。我的感觉是file是有cache的，所以random
: 访问效率可能提升。
|
c***p
发帖数: 221 | 29 要写代码。数据结构中的每一项都要说清楚，类型，大小。 仅仅有个概念或者算法是
不够的。
考的蛮深的。
【在 w****x 的大作中提到】
:
: random
: http://stackoverflow.com/questions/2438953/how-is-fseek-impleme
: 这里有讨论, 看的不大懂
|
p*****2
发帖数: 21240 | 30
很苛刻呀。
【在 c***p 的大作中提到】
: 要写代码。数据结构中的每一项都要说清楚，类型，大小。 仅仅有个概念或者算法是
: 不够的。
: 考的蛮深的。
|
|
|
w****x
发帖数: 2483 | 31
这种数据结构都是嵌在分配内存里的, 挺抽象的, 怎么没什么标准的能写出可执行代码
的题.
【在 c***p 的大作中提到】
: 要写代码。数据结构中的每一项都要说清楚，类型，大小。 仅仅有个概念或者算法是
: 不够的。
: 考的蛮深的。
|
c***p
发帖数: 221 | 32 考的挺细的。
比如：对于每个内存块，TAG要多少个BIT.你要根据总共可用的内存大小，以及要表示
是否是free的来确定TAG要用的BIT。
而且，他给你的内存块的开始地址不是00,而是0A. 估计还有字节对齐的问题。
反正我感觉里面的东西很多。恐怕还有的东西我还没有意识到。
考官是个很senior的。有三十年的经验。
【在 p*****2 的大作中提到】
:
: 很苛刻呀。
|
w****x
发帖数: 2483 | 33
TAG用多少bit??TAG是变长的吗?? 用个integer不行吗, 有必要个把bit的省吗.
【在 c***p 的大作中提到】
: 考的挺细的。
: 比如：对于每个内存块，TAG要多少个BIT.你要根据总共可用的内存大小，以及要表示
: 是否是free的来确定TAG要用的BIT。
: 而且，他给你的内存块的开始地址不是00,而是0A. 估计还有字节对齐的问题。
: 反正我感觉里面的东西很多。恐怕还有的东西我还没有意识到。
: 考官是个很senior的。有三十年的经验。
|
t******e
发帖数: 98 | 34 MS一直都是按组招人，general面试难道是新政策么？lz见了几个人,只有三道题么？ |
t******e
发帖数: 98 | |
c***p
发帖数: 221 | 36 integer可以。但是面试官希望尽量节省bit.所以要找到最少的bit.
【在 w****x 的大作中提到】
:
: TAG用多少bit??TAG是变长的吗?? 用个integer不行吗, 有必要个把bit的省吗.
|
n****n
发帖数: 117 | 37 感觉这个面试官有些刁难
【在 c***p 的大作中提到】
: integer可以。但是面试官希望尽量节省bit.所以要找到最少的bit.
|
w****x
发帖数: 2483 | 38
memory 一alignment省的那个把bit有啥用, 那读取的时候怎么知道bit要多长呢, 再拿
个byte来记,有没有搞错啊.
【在 n****n 的大作中提到】
: 感觉这个面试官有些刁难
|
c***p
发帖数: 221 | 39 当我问面试官他们的组是做什么的，他们是这样说的：他们面试是为公司面试的。因此
也就没有介绍什么他们的背景。
我见了4个人。有一个人的题目比较简单，翻转string 中的 word. 所以没有列出来。
【在 t******e 的大作中提到】
: MS一直都是按组招人，general面试难道是新政策么？lz见了几个人,只有三道题么？
|
c***p
发帖数: 221 | 40 他要求的是：需要多少，分配多少。和他讨论过buddy algorithm，因为有可能有浪费，
所以不行。
这题和面试官讨论了很久，提出了多个方案都被否决了，才知道他要的是哪个算法。后来写CODE都
没什么时间了。
【在 t******e 的大作中提到】
: 第一题用buddy algorithm啊。
|
|
|
q******1
发帖数: 310 | |
