w********l
发帖数: 154 | 1 在本版潜水了很久，今天拿到Offer了，回报一下，反正没有签过保密协议：）
不记得所有的题了，尽量罗列吧：
电面：
thread是系统实现还是程序实现的
static
程序运行时，内存是怎么样的？stack, heap....
有无限长的一列数，每次读入1个，始终保持至今最大的10个数，怎么实现？heap。
onsite:
实现Hashtable, 要具有expand功能
int (*a)[10]; a++; a指向哪里？指向原来位置+10个int
一组2维坐标的点。找出一组edge，使得所有点都能相连，并且minimize sum(length(
edge)).
int sqrt(int n)，返回平方根。注意返回的只需要整数部分。不要求效率。只要code
尽可能简洁。（linear search)
其他问题：
why bloomberg? why not bank IT? why not quant? Describe one project....
应该就从了。不想再找了。有一起的朋友站内联系：） |
s****s
发帖数: 345 | 2 how much is the offer?
【在 w********l 的大作中提到】
: 在本版潜水了很久，今天拿到Offer了，回报一下，反正没有签过保密协议：）
: 不记得所有的题了，尽量罗列吧：
: 电面：
: thread是系统实现还是程序实现的
: static
: 程序运行时，内存是怎么样的？stack, heap....
: 有无限长的一列数，每次读入1个，始终保持至今最大的10个数，怎么实现？heap。
: onsite:
: 实现Hashtable, 要具有expand功能
: int (*a)[10]; a++; a指向哪里？指向原来位置+10个int
|
s*******t
发帖数: 248 | 3 一组二维的点的题，是minimum spanning tree? 还是我题理解错了？
【在 w********l 的大作中提到】
: 在本版潜水了很久，今天拿到Offer了，回报一下，反正没有签过保密协议：）
: 不记得所有的题了，尽量罗列吧：
: 电面：
: thread是系统实现还是程序实现的
: static
: 程序运行时，内存是怎么样的？stack, heap....
: 有无限长的一列数，每次读入1个，始终保持至今最大的10个数，怎么实现？heap。
: onsite:
: 实现Hashtable, 要具有expand功能
: int (*a)[10]; a++; a指向哪里？指向原来位置+10个int
|
e*****u
发帖数: 337 | |
d*********g
发帖数: 59 | 5 实现Hashtable, 要具有expand功能
这题是要coding吗？写出全部hashtable的代码？ |
X*********n
发帖数: 570 | 6 什么叫有expand功能? 是取模吗?
【在 d*********g 的大作中提到】
: 实现Hashtable, 要具有expand功能
: 这题是要coding吗？写出全部hashtable的代码？
|
l*******o
发帖数: 791 | |
w********l
发帖数: 154 | 8 面的是SDE，entry level.
hashTable需要几乎完整地写出来。expand就是dynamic hash table |
|
d*********g
发帖数: 59 | 9 有无限长的一列数，每次读入1个，始终保持至今最大的10个数，怎么实现？heap
请问这个是heap sort吗？ |
r*******e
发帖数: 7583 | 10 维持一个10个元素的min-heap（注意不是max-heap）
每新到一个元素，与heap顶端元素比较，如果小于，直接丢弃
如果大于，讲heap顶端元素抛弃，将该元素加入heap
【在 d*********g 的大作中提到】
: 有无限长的一列数，每次读入1个，始终保持至今最大的10个数，怎么实现？heap
: 请问这个是heap sort吗？
|
|
|
d*********g
发帖数: 59 | 11 那add完以后需要再动态调节吗，如果比下面的node大是不是要一级级向下递归？
【在 r*******e 的大作中提到】
: 维持一个10个元素的min-heap（注意不是max-heap）
: 每新到一个元素，与heap顶端元素比较，如果小于，直接丢弃
: 如果大于，讲heap顶端元素抛弃，将该元素加入heap
|
d*********g
发帖数: 59 | 12 还是要先比较top的，然后如果大就换掉，然后再和child比较如果大交换
这样调整顺序以后每次top上都是最小的 |
r*******e
发帖数: 7583 | 13 当然需要。你说的这个就是Heapify，Heap的基本操作啊
【在 d*********g 的大作中提到】
: 那add完以后需要再动态调节吗，如果比下面的node大是不是要一级级向下递归？
|
l*******o
发帖数: 791 | 14 一组二维点的那个题目，是不是就是最短路径问题？ |
d*********g
发帖数: 59 | 15 哦，那这个操作是O(logN)吧？
【在 r*******e 的大作中提到】
: 当然需要。你说的这个就是Heapify，Heap的基本操作啊
|
l*******o
发帖数: 791 | 16 10个最大数可不可以用个大小为10的数组，然后遇到一个数就去和这个数组里的每个元
素去比较，把最小的换成这个数。这个办法的主要是在每次遇到一个数都要扫描一遍。
但是用heap的办法，我觉得如果输入的数为依次递增的话，那么heap要不停的调整。
不知道我 的方法可行么 |
r*******e
发帖数: 7583 | 17 是的，算法书都讲了的 ;)
【在 d*********g 的大作中提到】
: 哦，那这个操作是O(logN)吧？
|
r*******e
发帖数: 7583 | 18 一个是平均情况10n次比较
一个是最坏情况 (1+2*lg(10))*n次比较
【在 l*******o 的大作中提到】
: 10个最大数可不可以用个大小为10的数组，然后遇到一个数就去和这个数组里的每个元
: 素去比较，把最小的换成这个数。这个办法的主要是在每次遇到一个数都要扫描一遍。
: 但是用heap的办法，我觉得如果输入的数为依次递增的话，那么heap要不停的调整。
: 不知道我 的方法可行么
|
l*******o
发帖数: 791 | 19 我觉得应该给面试官一个可行解，当他需要better的时候再给他个最优解。
【在 r*******e 的大作中提到】
: 一个是平均情况10n次比较
: 一个是最坏情况 (1+2*lg(10))*n次比较
|
a********1
发帖数: 750 | 20 自己能写对的还是一步写出来
不确定最优解的时候先说说其他思路
【在 l*******o 的大作中提到】
: 我觉得应该给面试官一个可行解，当他需要better的时候再给他个最优解。
|
|
|
w*******a
发帖数: 2409 | |
b*******s
发帖数: 5216 | 22
heap调整比你线性的快
【在 l*******o 的大作中提到】
: 10个最大数可不可以用个大小为10的数组，然后遇到一个数就去和这个数组里的每个元
: 素去比较，把最小的换成这个数。这个办法的主要是在每次遇到一个数都要扫描一遍。
: 但是用heap的办法，我觉得如果输入的数为依次递增的话，那么heap要不停的调整。
: 不知道我 的方法可行么
|
b*******s
发帖数: 5216 | 23
hash table这个题目直接用stl container就行了
【在 w********l 的大作中提到】
: 面的是SDE，entry level.
: hashTable需要几乎完整地写出来。expand就是dynamic hash table
|
y*****a
发帖数: 221 | 24 二维坐标的题什么思路啊？
【在 w********l 的大作中提到】
: 在本版潜水了很久，今天拿到Offer了，回报一下，反正没有签过保密协议：）
: 不记得所有的题了，尽量罗列吧：
: 电面：
: thread是系统实现还是程序实现的
: static
: 程序运行时，内存是怎么样的？stack, heap....
: 有无限长的一列数，每次读入1个，始终保持至今最大的10个数，怎么实现？heap。
: onsite:
: 实现Hashtable, 要具有expand功能
: int (*a)[10]; a++; a指向哪里？指向原来位置+10个int
|
l*******o
发帖数: 791 | 25 嗯
【在 b*******s 的大作中提到】
:
: hash table这个题目直接用stl container就行了
|
l*******o
发帖数: 791 | 26 最短路径问题?
【在 y*****a 的大作中提到】
: 二维坐标的题什么思路啊？
|
y*****a
发帖数: 221 | 27 能给展开说说 或 给个reference吗。。非科班土人
【在 l*******o 的大作中提到】
: 最短路径问题?
|
d*********g
发帖数: 59 | 28 一组2维坐标的点。找出一组edge，使得所有点都能相连，并且minimize sum(length(
edge)).
这题是啥意思？能说清楚一点吗？谢谢！ |
z*****u
发帖数: 138 | 29 这种题目真是无聊
不过还是感谢楼主share, 赞一个 |
