r******d
发帖数: 308 | 1 刚刚电面结束， 觉得他们的问题非常厚道。
1．说说以前做的是什么project
2．写过template 没有， 都做了什么？
我就说写过。 如果是函数的template就用来pass in不同类型的parameter, 如果是函
数的template就用来pass in 不同类型的object. 例如STL.
3．STL 的list, array, map的insert function的时间复杂度是多少？
4．有一本书， 要找出书里面出现最多的20个单词和他们所在的书里面的页码， 他提
供一个function, 那个function 输入是单词， 每次返回那个单词的页码和下一个单词
， 可以反复call那function.
我用了一个hush table, key是单词， 然后里面存一个count, 和页码
然后再用一个size为20的binary tree， 把word 一个一个插进去找出现次数最大的
5． 有一个70楼的building, 往下扔球，看最高几楼会破。 一种是只有一个球，
第二种情况是有无数多的球， 呵呵。
一个球的就从一楼开始一层一层往上扔，如果很多球就用binary search. | s****n
发帖数: 150 | 2 楼主牛人。
请问楼主是fresh grad 还是 experienced ？
【在 r******d 的大作中提到】
: 刚刚电面结束， 觉得他们的问题非常厚道。
: 1．说说以前做的是什么project
: 2．写过template 没有， 都做了什么？
: 我就说写过。 如果是函数的template就用来pass in不同类型的parameter, 如果是函
: 数的template就用来pass in 不同类型的object. 例如STL.
: 3．STL 的list, array, map的insert function的时间复杂度是多少？
: 4．有一本书， 要找出书里面出现最多的20个单词和他们所在的书里面的页码， 他提
: 供一个function, 那个function 输入是单词， 每次返回那个单词的页码和下一个单词
: ， 可以反复call那function.
: 我用了一个hush table, key是单词， 然后里面存一个count, 和页码
| r******d
发帖数: 308 | | s*******t
发帖数: 248 | 4 Thanks for sharing.
问下Lz面的是什么职位？ 通过什么方式拿到面试机会的，网投，猎头还是内部推荐？
谢谢！
【在 r******d 的大作中提到】
: 刚刚电面结束， 觉得他们的问题非常厚道。
: 1．说说以前做的是什么project
: 2．写过template 没有， 都做了什么？
: 我就说写过。 如果是函数的template就用来pass in不同类型的parameter, 如果是函
: 数的template就用来pass in 不同类型的object. 例如STL.
: 3．STL 的list, array, map的insert function的时间复杂度是多少？
: 4．有一本书， 要找出书里面出现最多的20个单词和他们所在的书里面的页码， 他提
: 供一个function, 那个function 输入是单词， 每次返回那个单词的页码和下一个单词
: ， 可以反复call那function.
: 我用了一个hush table, key是单词， 然后里面存一个count, 和页码
| r******d
发帖数: 308 | 5 我面的职位是software engineer之类的吧，说是用c++, 但是好像也没有问什么c++的
东西。 这个职位不是我找的， 是中介找的我， 所以有点稀里糊涂的。。。。 现在都
没有看到具体的职位要求。 主要是去练习去了， 呵呵
【在 s*******t 的大作中提到】
: Thanks for sharing.
: 问下Lz面的是什么职位？ 通过什么方式拿到面试机会的，网投，猎头还是内部推荐？
: 谢谢！
| m*********g
发帖数: 646 | 6 Goldman Sachs uses their own in-house language to develop the trading tools,
so don't worry about the language.
【在 r******d 的大作中提到】
: 我面的职位是software engineer之类的吧，说是用c++, 但是好像也没有问什么c++的
: 东西。 这个职位不是我找的， 是中介找的我， 所以有点稀里糊涂的。。。。 现在都
: 没有看到具体的职位要求。 主要是去练习去了， 呵呵
| r******d
发帖数: 308 | 7 原来如此， 多谢信息， 呵呵， 不知道需要面试几轮， 网上看的都要面很多轮的样子
。。。。 | r********t
发帖数: 395 | 8 the solution to #5 is not as simple as binary search, man. | s*******r
发帖数: 47 | | s*******r
发帖数: 47 | 10 那怎解？ 没有限制用球数， 貌似平均时间O(nlgn)是最好的解法了
【在 r********t 的大作中提到】
: the solution to #5 is not as simple as binary search, man.
| r******d
发帖数: 308 | 11 用堆思路可能更加清楚把, 不插入一个节点过复杂度都是 lg(n)
http://en.wikipedia.org/wiki/Selection_algorithm
上面的连接还有o(n)的算法, 不过......看了半天没有琢磨明白, 所以面试的时候就说
了说我能够理解的方法
Data structure based solutions
Another simple method is to add each element of the list into an ordered set
data structure, such as a heap or self-balancing binary search tree, with
at most k elements. Whenever the data structure has more than k elements, we
remove the largest element, which can be done in O(log k) time. Each
insertion operation also takes O(log k) time, resulting in O(nlog k) time
overall.
It is possible to transform the list into a heap in Θ(n) time, and then
traverse the heap using a modified Breadth-first search algorithm that
places the elements in a Priority Queue (instead of the ordinary queue that
is normally used in a BFS), and terminate the scan after traversing exactly
k elements. As the queue size remains O(k) throughout the traversal, it
would require O(klog k) time to complete, leading to a time bound of O(n +
klog k) on this algorithm.
Tournament Algorithm
Another method is tournament algorithm. The idea is to conduct a knockout
minimal round tournament to decide the ranks. It first organises the games (
comparisons) between adjacent pairs and moves the winners to next round
until championship (the first best) is decided. It also constructs the
tournament tree along the way. Now the second best element must be among the
direct losers to winner and these losers can be found out by walking in the
binary tree in O(log n) time. It organises another tournament to decide the
second best among these potential elements. The third best must be one
among the losers of the second best in either of the two tournament trees.
The approach continues until we find k elements. This algorithm takes O(n +
k log n) complexity, which for any fixed k independent of n is O(n).
(sugarbear) 的大作中提到: 】 |
|
