c**y
发帖数: 73 | 1 小公司，有点research性质的。面了6,7个人吧，问了很多关于之前的research
projects，不具有代表性。就把记得的算法题汇报一下吧。很多也没要求写code。
1. 给定一个sorted array，如何查找所有pair，他们的和等去一个给定sum。
要求给一个不用hash table的方法
给了一个用binary search加速查找过程的方法。
2. 如何用一个1G内存sort一个10G的文件，假设硬盘空间足够大。
刚开始给了一个pair-wise sort，后经讨论improve成K-way sort。相比K-way sort，
pair-wise sort要求更多的硬盘访问次数。
后来讨论一下如果硬盘空间有限，例如只有10.5G，如何做K-way sort。
3. 给定一个有向图，如何判定是不是bipartite，只讨论的算法，没有要求写code
这里是Wiki上定义http://en.wikipedia.org/wiki/Bipartite_graph
4. 如何判定一个binary search tree
5. 给定一个array和一个sum，如何找到所有个pair和triple它们的和。不确定是不是
leetcode上的two-sum和tree-sum的原题。
two-sum
开始给了一个O(n^2)的brutal force的方法。
后要求优化到O(n log n)，给了一个基于binary search的方法（和第一题一样）。
后要求优化到O(n)，给了一个基于HashTable的方法。
后要求优化到O(1)，即对于给定任何一个sum，从constant时间返回所有pair。这里可
以preprocess。就事先用brutal force的方法，对于所有pair的和，建立一个hash
table。
three-sum
开始给了一个O(n^3)的brutal force的方法。
后要求优化到O(n^2 log n)
后要求优化到O(n^2)
思路和two-sum差不多，基本都是用hash table来加速查找。
6. 给定一组判定语句，定义一个数据结构来进行快速查找。
例如给定判定条件如下
A==5 && B==1 && Z==20
Y==20 && Z==3 && C==6
D==4 && B==2 && M==30
只讨论了算法，没有要求写code。
给了用tier来建立一个快速查找表。 |
r*********n
发帖数: 4553 | |
r**h
发帖数: 1288 | 3 bless!
我现在觉得这种偏向于原创性research的小公司也蛮不错的
【在 c**y 的大作中提到】
: 小公司，有点research性质的。面了6,7个人吧，问了很多关于之前的research
: projects，不具有代表性。就把记得的算法题汇报一下吧。很多也没要求写code。
: 1. 给定一个sorted array，如何查找所有pair，他们的和等去一个给定sum。
: 要求给一个不用hash table的方法
: 给了一个用binary search加速查找过程的方法。
: 2. 如何用一个1G内存sort一个10G的文件，假设硬盘空间足够大。
: 刚开始给了一个pair-wise sort，后经讨论improve成K-way sort。相比K-way sort，
: pair-wise sort要求更多的硬盘访问次数。
: 后来讨论一下如果硬盘空间有限，例如只有10.5G，如何做K-way sort。
: 3. 给定一个有向图，如何判定是不是bipartite，只讨论的算法，没有要求写code
|
h********g
发帖数: 496 | 4 最后一题什么意思？
【在 r*********n 的大作中提到】
: 祝LZ好运
: 最后那题也可以用hash来做吧
|
c**y
发帖数: 73 | 5 多谢多谢！
如何用Hash呢？
【在 r*********n 的大作中提到】
: 祝LZ好运
: 最后那题也可以用hash来做吧
|
g**G
发帖数: 767 | 6 没看懂最后一题，是
(... && .. && ..)
|| (... && .. && ..)
|| (... && .. && ..)
这样么？
【在 c**y 的大作中提到】
: 小公司，有点research性质的。面了6,7个人吧，问了很多关于之前的research
: projects，不具有代表性。就把记得的算法题汇报一下吧。很多也没要求写code。
: 1. 给定一个sorted array，如何查找所有pair，他们的和等去一个给定sum。
: 要求给一个不用hash table的方法
: 给了一个用binary search加速查找过程的方法。
: 2. 如何用一个1G内存sort一个10G的文件，假设硬盘空间足够大。
: 刚开始给了一个pair-wise sort，后经讨论improve成K-way sort。相比K-way sort，
: pair-wise sort要求更多的硬盘访问次数。
: 后来讨论一下如果硬盘空间有限，例如只有10.5G，如何做K-way sort。
: 3. 给定一个有向图，如何判定是不是bipartite，只讨论的算法，没有要求写code
|
r*********n
发帖数: 4553 | 7 我猜是这个意思：
输入是一组数int arr[26], 然后实现函数
bool fun(int arr[])
比如第一个条件 arr[0]==5&&arr[1]==1&&arr[25]==20 (A==5 && B==1 && Z==20)
如果输入的arr满足这个条件，fun就要返回true，否则false
用hash来做的话就是如果([ arr[0], arr[1], arr[25] ])的hash值如果不等于（[5,1,
20]）的hash值，就直接返回false，如果相等，就再进一步一个一个判定。如果
predicate很复杂，而且大多数输入都判定为false的情况下，这么做应该会比一个一个
判定要快些。
也不知道这个题是不是这个意思，从感觉有点奇怪。
【在 h********g 的大作中提到】
: 最后一题什么意思？
|
e*****n
发帖数: 316 | |
c**y
发帖数: 73 | 9 多谢指正，应该是这个意思。
原题记不清了，应该下面两种使用方式对数据结构的要求差不多吧。
if ((... && .. && ..)
|| (... && .. && ..)
|| (... && .. && ..)) {
// do something
}
OR
if (... && .. && ..) {
...
} else if (... && .. && ..) {
...
} else if (... && .. && ..) {
...
}
【在 g**G 的大作中提到】
: 没看懂最后一题，是
: (... && .. && ..)
: || (... && .. && ..)
: || (... && .. && ..)
: 这样么？
|
Q****s
发帖数: 1301 | 10 答的还不错吧,
来offer了吗?
【在 c**y 的大作中提到】
: 多谢指正，应该是这个意思。
: 原题记不清了，应该下面两种使用方式对数据结构的要求差不多吧。
: if ((... && .. && ..)
: || (... && .. && ..)
: || (... && .. && ..)) {
: // do something
: }
: OR
: if (... && .. && ..) {
: ...
|
c**y
发帖数: 73 | 11 就是这个意思，check给定一个int arr[26]是不是满足所有给定的条件之一。
1,
【在 r*********n 的大作中提到】
: 我猜是这个意思：
: 输入是一组数int arr[26], 然后实现函数
: bool fun(int arr[])
: 比如第一个条件 arr[0]==5&&arr[1]==1&&arr[25]==20 (A==5 && B==1 && Z==20)
: 如果输入的arr满足这个条件，fun就要返回true，否则false
: 用hash来做的话就是如果([ arr[0], arr[1], arr[25] ])的hash值如果不等于（[5,1,
: 20]）的hash值，就直接返回false，如果相等，就再进一步一个一个判定。如果
: predicate很复杂，而且大多数输入都判定为false的情况下，这么做应该会比一个一个
: 判定要快些。
: 也不知道这个题是不是这个意思，从感觉有点奇怪。
|
