s*******t
发帖数: 793 | 1 公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
1. Design free and malloc.
2. Implement the color filling function of MS-paint: when you click on an
image, all the pixels connected with the same color are filled with the new
color.
3. Binary Search Tree: given a node find its inorder successor.
4. Given input series in this fomat , (e.g, <3,
5>, <1,2>, <10,1>, 代表有3个5，1个2，10个1）,implement getNext()
5. Implement Iterator for Vector of Vectors
6. Given a list of intervals, 比如 (10,20),(30,50)...,and a target interval,
比如(18,35) 找有多少overlap.
7. Input string, 比如"asdhdfgalkhjkl"，search tokens 比如'a','k','h',找出包
含所有tokens的最短substring.这个例子里最短的是"alkh". | f***g
发帖数: 214 | | x*********n
发帖数: 28013 | | h**********d
发帖数: 4313 | 4 thanks~ bless
第4题getNext()是什么意思能再讲以下吗 | s*******t
发帖数: 793 | 5 就是输出下一个元素。比如上面的data stream，第一次getNext()输出5，第二次第三
次还是5，第四次输出2。
【在 h**********d 的大作中提到】
: thanks~ bless
: 第4题getNext()是什么意思能再讲以下吗
| b******n
发帖数: 4509 | 6 MS 的题目吧
new
3,
interval,
【在 s*******t 的大作中提到】
: 公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
: 就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
: 样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
: 的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
: 1. Design free and malloc.
: 2. Implement the color filling function of MS-paint: when you click on an
: image, all the pixels connected with the same color are filled with the new
: color.
: 3. Binary Search Tree: given a node find its inorder successor.
: 4. Given input series in this fomat , (e.g, <3,
| d*******r
发帖数: 208 | 7 赞 bless.
new
3,
【在 s*******t 的大作中提到】
: 公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
: 就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
: 样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
: 的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
: 1. Design free and malloc.
: 2. Implement the color filling function of MS-paint: when you click on an
: image, all the pixels connected with the same color are filled with the new
: color.
: 3. Binary Search Tree: given a node find its inorder successor.
: 4. Given input series in this fomat , (e.g, <3,
| g**e
发帖数: 6127 | 8 第六题有比O(n)更快的方法吗？除了interval tree?但是建立树就要O(nlgn)了
new
3,
interval,
【在 s*******t 的大作中提到】
: 公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
: 就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
: 样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
: 的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
: 1. Design free and malloc.
: 2. Implement the color filling function of MS-paint: when you click on an
: image, all the pixels connected with the same color are filled with the new
: color.
: 3. Binary Search Tree: given a node find its inorder successor.
: 4. Given input series in this fomat , (e.g, <3,
| c********1
发帖数: 161 | 9 7. Input string, 比如"asdhdfgalkhjkl"，search tokens 比如'a','k','h',找出包
含所有tokens的最短substring.这个例子里最短的是"alkh".
can anyone find O(n) solution? I only have O（nlgk）solution which is still
not so satisfied with.
验证码是 NCBS（NND） | g**e
发帖数: 6127 | 10 有，往前考古
still
【在 c********1 的大作中提到】
: 7. Input string, 比如"asdhdfgalkhjkl"，search tokens 比如'a','k','h',找出包
: 含所有tokens的最短substring.这个例子里最短的是"alkh".
: can anyone find O(n) solution? I only have O（nlgk）solution which is still
: not so satisfied with.
: 验证码是 NCBS（NND）
| | | l****a
发帖数: 2361 | | i**9
发帖数: 351 | | n*******t
发帖数: 77 | | w**********u
发帖数: 172 | | c******w
发帖数: 102 | | F********d
发帖数: 108 | 16 bless
new
3,
【在 s*******t 的大作中提到】
: 公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
: 就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
: 样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
: 的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
: 1. Design free and malloc.
: 2. Implement the color filling function of MS-paint: when you click on an
: image, all the pixels connected with the same color are filled with the new
: color.
: 3. Binary Search Tree: given a node find its inorder successor.
: 4. Given input series in this fomat , (e.g, <3,
| s*******t
发帖数: 793 | 17 第一题是memory allocation/management 的问题，C语言里malloc() free()如何分配
回收内存。
第六题，记不住interviewer的原话，大意就是那样了，比如输入(10,20),(30,50)...,
target interval(18,35)， 那overlap 就是18-20 和 30-35。
【在 c******w 的大作中提到】
: 楼主能不能把第一和第六题再说完整一点？谢谢。
| a*****c
发帖数: 2086 | 18 能否给个链接，帖子数目太多了，不知道如何能快速找到，呵呵
【在 g**e 的大作中提到】
: 有，往前考古
:
: still
| m**q
发帖数: 189 | 19 谢谢分享~ 看着有不少最近见过的，尝试说一下思路，请大牛们指正。
公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
1. Design free and malloc.
=> 不太了解考官的用意, 想到的是buddy system。
开一个指针数组，对应不同大小的空闲数据块。假如内存为1G,数据块大小可以为2^4,
2^5, 2^6，...2^30，指针数组共有27项。每一项引出一个链表，链表的每一项是｛
start,end, next}。
在malloc的时候，根据大小做二分查找，找到最小的能满足需求的指针数组项，
从链表中取一项，如果链表为空，则继续找更大的指针数组项引出的链表，
直到最大数据块对应的链表。如果需要的话，对找到的数据块进行分裂，把
剩余的空闲块插入到对应大小的链表中。
在free的时候，根据数据块大小找到对应的数组项，即链表头，并插入。
如果有相邻块则合并，并从当前链表中移除，加入到下一级的链表中。
重复此过程直到所有可以合并的都已经合并。在free的时候，需要快速
查找对应大小的链表中，需要用合适的数据结构组织，可以用hash或
BST。
2. Implement the color filling function of MS-paint: when you click on
animage, all the pixels connected with the same color are filled with the
new color.
=> 用queue来做广度优先遍历。将每个pixel的没有访问过的同颜色相邻pixel
加入queue，然后逐个取出处理。
3. Binary Search Tree: given a node find its inorder successor.
=> 这个应该假定每个node有指向parent的指针吧？
Career Cup 150 上 tree and graph 那一章有原题，注意考虑各种情况。
4. Given input series in this fomat , (e.g, <3,
5>, <1,2>, <10,1>, 代表有3个5，1个2，10个1）,implement getNext()
=> 记录当前在第几项的第几次
5. Implement Iterator for Vector of Vectors
6. Given a list of intervals, 比如 (10,20),(30,50)...,and a target interval,
比如(18,35) 找有多少overlap.
=> 可以认为原来的list中没有overlap？
二分搜索，各种情况需要处理一下
7. Input string, 比如"asdhdfgalkhjkl"，search tokens 比如'a','k','h',找出包
含所有tokens的最短substring.这个例子里最短的是"alkh".
=> 一个思路是找到string里的a,k,h的位置的序列，然后在这三个序列中从头开始
遍历，找最小距离。复杂度O(n)，缺点是要额外记录三个位置序列。
更好的方法是用两个指针，也是O(n),原帖见：
http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid
8,9楼
【在 s*******t 的大作中提到】
: 公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
: 就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
: 样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
: 的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
: 1. Design free and malloc.
: 2. Implement the color filling function of MS-paint: when you click on an
: image, all the pixels connected with the same color are filled with the new
: color.
: 3. Binary Search Tree: given a node find its inorder successor.
: 4. Given input series in this fomat , (e.g, <3,
| m**q
发帖数: 189 | 20 刚刚发了，在上一篇的最后
【在 a*****c 的大作中提到】
: 能否给个链接，帖子数目太多了，不知道如何能快速找到，呵呵
| | | m**q
发帖数: 189 | 21 如果已经排序的话可以binary search，只需要overlap的个数的话复杂度O(logn),
就是要处理一下细节；如果需要直到有哪些是overlap的，复杂度为O(logn+k)，
k为overlap的range的个数。
如果没排序的话就只能O(n)了吧
【在 g**e 的大作中提到】
: 第六题有比O(n)更快的方法吗？除了interval tree?但是建立树就要O(nlgn)了
:
: new
: 3,
: interval,
| c******t
发帖数: 391 | 22 关于第7题，能不能细讲下二分查找的思路？
我是这样想的，用一个长度为[max(pair.second)-min(pair.first)]的bool array进行
标记，将各个pair覆盖的区间标记为true,最后扫描target pair区间，若有check[i]==
true，则计数+1. 复杂度为O((max-min)*k)，k为pair数。
不知道此法是否可行...
,
【在 m**q 的大作中提到】
: 谢谢分享~ 看着有不少最近见过的，尝试说一下思路，请大牛们指正。
:
: 公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
: 就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
: 样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
: 的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
: 1. Design free and malloc.
: => 不太了解考官的用意, 想到的是buddy system。
: 开一个指针数组，对应不同大小的空闲数据块。假如内存为1G,数据块大小可以为2^4,
: 2^5, 2^6，...2^30，指针数组共有27项。每一项引出一个链表，链表的每一项是｛
| c******t
发帖数: 391 | 23 关于第7题, 我是这样想的，用一个长度为[max(pair.second)-min(pair.first)]的
bool array进行标记，将各个pair覆盖的区间标记为true,最后扫描target pair区间，
若有check[i]==true，则计数+1. 复杂度为O((max-min)*k)，k为pair数。
不知道此法是否可行...
new
3,
【在 s*******t 的大作中提到】
: 公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
: 就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
: 样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
: 的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
: 1. Design free and malloc.
: 2. Implement the color filling function of MS-paint: when you click on an
: image, all the pixels connected with the same color are filled with the new
: color.
: 3. Binary Search Tree: given a node find its inorder successor.
: 4. Given input series in this fomat , (e.g, <3,
| g*********s
发帖数: 1782 | 24 这些题不容易。
第一题就是讲讲memory pool的算法吗？若干个list，每个list里的block大小相同。不
同list
的block大小不一。分配/回收时按大小？
第二题什么叫connected with the same color？是说从起点走，只能走同色相邻点，
可达到
的所有点？那用bfs吧。
第四题没看懂啥是next。
an
the new
(e.g, <3,
【在 s*******t 的大作中提到】
: 公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
: 就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
: 样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
: 的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
: 1. Design free and malloc.
: 2. Implement the color filling function of MS-paint: when you click on an
: image, all the pixels connected with the same color are filled with the new
: color.
: 3. Binary Search Tree: given a node find its inorder successor.
: 4. Given input series in this fomat , (e.g, <3,
| g*********s
发帖数: 1782 | 25 看输入的区间有啥特性吧？
【在 g**e 的大作中提到】
: 第六题有比O(n)更快的方法吗？除了interval tree?但是建立树就要O(nlgn)了
:
: new
: 3,
: interval,
|
|
