h**6
发帖数: 4160 | 1 如果可以预处理那就简单了，求出一个优先增长子序列就可以了，如原题，是2, 10,
80。
优先增长子序列是我自己起的名字，方法是把下一个比子序列中最后一个元素更大的元
素加入序列中，遍历原数组所得到的子序列。
于是乎：
第一个大于等于0~2的是2，
第一个大于等于3~10的是10，
第一个大于等于11~80的是80，
第一个大于等于81的没有。 |
|
d**e
发帖数: 6098 | 2 所以要先预处理find the lengths of all paths?
time |
|
f***g
发帖数: 214 | 3 先预处理下那串字符串，存在一个int[26]，记录每个字母出现的次数。如果有大小写
或者其他字符，最多也就int[256].
然后对于那个list of candidate words, 一个一个的试，每一个单词就从计数数组中
减去那个单词相应的字符。例如，单词是hi,则int['h']--, int['i']--.
如果计数数组为空，输出结果，否则递归试下一个单词。
这样可以列出所有可能性。 |
|
h***n
发帖数: 276 | 4 我是假设每个节点知道他所有孩子的数目的信息，你可以把这步看成预处理，不把复杂
度计算在内，就像binary search之前已经assume array is sorted，这样才能达到楼主
说的O(logn），否则是O(n）
另外，知道父节点信息的话，并不能使得复杂度降为O(n）
numb |
|
n****t
发帖数: 241 | 5 楼主说的那个，也需要预处理（一样的复杂度）。。。 |
|
k*n
发帖数: 150 | 6 第一题两两比较，可以每一对数少一次比较
找subset这个我不确定有没有比greedy更好的办法
不加预处理应该没有吧 |
|
j*******r
发帖数: 20 | 7 RMQ可以做到O(n)时间预处理，然后O(1)时间回答一个query。。。
Query |
|
l*****g
发帖数: 685 | 8 sieve of eratosthenes的空间确实是个问题。因此，如果记得住Sieve of Atkin方法
的人当然最好用Sieve of Atkin来做。
如果只记得sieve of eratosthenes的话， 我觉得可以给原算法稍微做点预处理，以减
少空间要求。
譬如把100之内的prime number先存到一个数组a里，反正数目也不大
a = {2, 3, 5, 7, ..., 97}
接下去是3种情况
1） 如果n小于100， 直接从a里搜索
2） 如果n大于100，loop i from 100-->n, 给i apply a里的所有prime numbers，如
果i最后还能漏下来，那就放到一个list b
b = { 101, 103, ...}
这一轮下来，剩下来的数字估计减少了十几倍。（没具体算过到底减少到多少，大致估
计是：1/2 * 2/3 * 4/5 * 6/7 *....*96/97, 不过这是不确切的)
3) 接下来再对b里的数字做正常的sieve of eratosthenes筛法, 当然用不着从2开始了
，可以直接从101开始。
最后的结果是a... 阅读全帖 |
|
i******s
发帖数: 301 | 9 没那么麻烦，就是事先预处理矩阵任意一点和左上角点构成矩形的sum, 有M * N个，然
后任意矩形的sum都可以用4个左上角矩形表示，比如要求矩形(a, b)， (c, d)的面积,
(a, b)表示矩阵左上角坐标，(c, d)表示右下角, 那么S = sum((0, 0), (c, d)) -
sum ((0, 0), (c, b)) - sum((0, 0), (a, d)) + sum((0, 0), (a, b)), O(1)时间 |
|
d*******l
发帖数: 338 | 10 又想了想，上面的做法大概还是可以的，和你说的差不多。任何一个被1包围的0矩阵肯
定是局部最大的0矩阵，也就是说在上面那种做法中，在对每一行运用直方图方法的时
候，会被作为一个局部的最大值去更新整体的最大值。这个问题中，我想只要判断一下
，只对那些被1包围的0矩阵，才去更新整体最大值，就能得到结果。
不过你没说一个很关键的地方就是怎么在常数时间判断一个0矩阵是否被1包围，你说只
是检查两侧我觉得还是不够的，你这样存在的固然能找出来，却有可能将实际不是的给
误算上。比如你的例子如果改成这样：
1 0 1 0 1
2 0 0 0 0
0 0 1 1 0
1 0 2 2 0
0 0 3 3 0
0 0 1 0 0
那你的方法可能就会把那部分算上，其实并不应该算。
不过这个方法应该还是能行的通的，可以利用0-1矩阵的特点。先预处理得到矩阵每个
点与左上角确定的矩形的面积a[i][j]，所谓面积就是所有值的累加。这个是n^2时间内
能完成的。然后通过一些简单的加减就能在常数时间内得到任何一个子矩阵的面积。假
如我们现在有一个全0矩阵，知道它右下角和左上角的位置，只需要判断比它大一圈的
那个矩阵面积... 阅读全帖 |
|
d*******l
发帖数: 338 | 11 你这个是求最大子矩阵的方法，这样确实没错，但0-1矩阵的最大全1矩阵确实是O(n^2)
的，对每一行用一次直方图方法即可，而每行的值可以在一次O(n^2)的预处理中全部得到
共O |
|
r*******g
发帖数: 1335 | 12 请教
第三题不清楚bit vector在这里的作用，难道不是直接把url放hashtable就行了？bit
vector作用是？
第五题不清楚如果用每次只能读4K的函数实现读取任意字节。
第八题，分布式LRU如何实现?
10，write code to find all the possible combinations of chars in a given
string
这个题是不是要找出所有形成单词的combination？感觉需要像programming pearl一样
对字典做预处理，否则的话难道test每个combination？
谢谢了 |
|
r*******g
发帖数: 1335 | 13 请教
第三题不清楚bit vector在这里的作用，难道不是直接把url放hashtable就行了？bit
vector作用是？
第五题不清楚如果用每次只能读4K的函数实现读取任意字节。
第八题，分布式LRU如何实现?
10，write code to find all the possible combinations of chars in a given
string
这个题是不是要找出所有形成单词的combination？感觉需要像programming pearl一样
对字典做预处理，否则的话难道test每个combination？
谢谢了 |
|
g**u
发帖数: 583 | 14
面试完了就想到其实我们需要的是一个从 infix expression-->postfix expression的
预处理，但是等到自己想到这一步的时候，这个时候就需要合适的数据结构来实现这种
转变，binary tree就可以了，但是那时候时间快没了... |
|
d*******l
发帖数: 338 | 15 想到如下方法：
1. 按区间起点排序
2. 离散化，总共不超过2n个端点，重新编号为0 - 2n-1
3. 遍历所有区间，对每个区间，计算(start, end)区间中起点的个数，累加到结果中
4. 单独计算起点重合的情况
离散化之后，可以用O(n)空间记录起点的分布，如果用O(n)预处理一下sum[i]，第三步
只需要O(1)时间。并且能处理区间端点不是整数的情况。只有第一步是O(nlogn)的，其
他都是O(n)。这样有什么bug吗？ |
|
w*****3
发帖数: 101 | 16 来自主题: JobHunting版 - 问个编程题 这个可以预处理一下么，
在去掉1的数组里找sum - 1 和sum，
最后比较dp[sum - 1] + 1 和 dp[sum]的大小 |
|
w*****p
发帖数: 215 | 17 我能坐到n^3. 通过一个n^2的预处理，可以做到 issquare() 在循环里面 O(1).
举个例子。0是白，1是黑。
10011
01110
01010
01111
做两个矩阵： 一个是对于每一个元素（i，j），同一行从它开始的最大连续1的个数。
同理，做一个矩阵，对于同列连续的1的个数。这两矩阵就n^2做到。
比如 行的矩阵 xcell，
10021
03210
01010
04321
和列的矩阵 ycell
10041
03030
02020
01011
给定任意个点(x,y)，和size k， 就可以判断 这个square是不是都是黑边的。
比如 (2,2,3), 只要看4个值，xcell[2,2]>=k, ycell[2,2]>=k, xcell[2+k,2]>=k and
ycell[2,2+k]>=k, 这里的 k=3.因为 成立，所以issquare 是成立的。
但是不管是dp还是非 dp，我都只能做到 n cube。 |
|
l*****e
发帖数: 1374 | 18 来自主题: JobHunting版 - 一道G家题 如果可以对N个数预处理，将其简单的存放至hashtable中，以后每次查询都可以在O(1)完成，即
M >> N的条件猜测是interviewer不想让人使用bit operation. |
|
g**********y
发帖数: 14569 | 19 Assumption: 你说的rectangle, 不是square, 那么比大小的话，只能比面积。
1. 把字典做成Trie
2. 预处理Matrix, 从上往下，从左往右，对位置(i, j), 如果水平向有长度k的单词，
把{i, j} 放进 SetY[k]; 如果纵向有长度k的单词，把{i, j} 放进 SetX[k].
3. 从大到小处理SetY[k], k最长好象是19，存在横向长度为k的word rectangle必要条
件：
- SetY[k]里包含(i, j), (i, j+1), ... (i, j+l)
For (t=l; t>0; t--) 扫描SetX[t], 看是否包含(I, j), (I+1, j), … (i+k, j). 如
果是，找到一word rectangle, 跟当前最大值比较，保存最大。然后退出循环。
SetY的元素，因为有序，处理一个后即可扔掉。
这个是地毯式搜索。 |
|
s****j
发帖数: 67 | 20 平面最近点对那题，提供一种方法供参考，该方法看似复杂度o(n^2)，但实际使用中几
乎是o(n)（不算nlgn排序的预处理）。主要是利用了三角形两边之差小于第三边的性质
，大大减枝。另外该方法实现简单，比传统o(nlgn)的实现简单很多也直观很多。
代码如下：
#include
#include
#include
#include
#include
using namespace std;
const int maxn=100005;
const double eps=1e-8;
struct Point
{
double x,y,dis;
} p[maxn];
int n;
bool cmpp(const Point &p1,const Point &p2)
{
return p1.dis
}
void solve()
{
sort(p,p+n,cmpp);
double ans=1e18,now;
int i,j;
for (i=0;i阅读全帖 |
|
|
s*********e
发帖数: 197 | 22 因为对C最熟悉，当时就选了C。感觉考的比较细，有些题目比较偏，比如有些预处理的
问题有些措手不及。而且时间比较紧，每道题限时3分钟好像。好在代码类的题目都比
较简短，所以当时我开了一个终端在旁边，感觉有唯一答案但来不及想的就先把代码敲
上去编译运行一下再说。对于选项感觉答案不唯一或者有陷阱的，再细细看过。估计也
是侥幸通过吧。这么晚了再也看不下去书了，明天回来发面经！ |
|
j********x
发帖数: 2330 | 23 finbonaci number，是前三个数的和而不是两个；写代码；改进；logn算法
range sum query，array，给[i,j]算区间内元素和，给出不同的space/time
complexity组合，在提示下给出一个n^1/2 space/time complexity的算法
同上，现在的数组是2维，给出一个O(n^2) time/space complexity的预处理方法，然
后是一个O(1)的query
最后一个设计题，一个目录下面有别的目录和source file，要把所有的source file的
一个name替换，考regular expression，然后修改的时候要备份所有文件
然后问了他两个问题
本来是定的一个中国人，临时换了印度人，不过这个印度人挺正常，没感觉针对我 |
|
d*******l
发帖数: 338 | 24 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
的满足条件的窗口。
对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
这样总的时间复杂度可以达到nlogn。空间复杂度O(n)。 |
|
d*******l
发帖数: 338 | 25 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
的满足条件的窗口。
对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
这样总的时间复杂度可以达到nlogn。空间复杂度O(n)。 |
|
w****x
发帖数: 2483 | 26 搞错了, 是给定一个星球, 求距离它最近的k个, 又没有什么预处理可以处理一次, 以
后很快能得到解答的方法??? |
|
w****x
发帖数: 2483 | 27 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
后一次查询只需要O(n)时间复杂度 |
|
w****x
发帖数: 2483 | 28 图的遍历怎么会是O(n^2)???
图可以用邻接表表示, 不一定非要用矩阵...
一次O(n^2)的预处理， 剩下每次查询都是O(n)的最坏复杂度， 从同一节点开始遍历的
查询， 实际问题远远没到O(n)的程度 |
|
w****x
发帖数: 2483 | 29 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
后一次查询只需要O(n)时间复杂度 |
|
w****x
发帖数: 2483 | 30 图的遍历怎么会是O(n^2)???
图可以用邻接表表示, 不一定非要用矩阵...
一次O(n^2)的预处理， 剩下每次查询都是O(n)的最坏复杂度， 从同一节点开始遍历的
查询， 实际问题远远没到O(n)的程度 |
|
b*******y
发帖数: 232 | 31 恩，以前看到过，不过这个算法真的是O(n)的么？
如果预处理的potential starting point的个数跟n可比呢？ |
|
S**I
发帖数: 15689 | 32 ☆─────────────────────────────────────☆
recursive (递归) 于 (Mon Apr 11 10:56:49 2011, 美东) 提到:
大半夜收到HR的thank you note。不用管什么NDA了
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the out... 阅读全帖 |
|
c*****e
发帖数: 737 | 33 that's easy, 就是INT_MAX个map到n-k个。
先预处理一下，找出所有不在list里的数，放入一个array.
然后选array[rand() % array.size() - 1]。 |
|
c*****e
发帖数: 737 | 34 that's easy, 就是INT_MAX个map到n-k个。
先预处理一下，找出所有不在list里的数，放入一个array.
然后选array[rand() % array.size() - 1]。 |
|
|
f*****i
发帖数: 56 | 36 上周一onsite,左等右等，本来要move on了，结果中午在洗手间玩游戏时接到了offer
电话。
回报本版，报面经，同时求意见，恳请大家帮助。
面经：
电面1轮（因为之前面过）：
1.基本数据结构及其操作的时间空间复杂度，不同数据结构对比，如array, linked
list, tree, queue, stack, hashtable, heap，etc.
2.实现queue用array还是linked list，优缺点对比。
3.给一个folder里面有上千个文件，要求返回包括电话号码的文件。（grep+regex)
4.linkedlist有无环 （fast/slow runner）
5.非负整数数组，除了一个值出现奇数次之外，其余都是偶数次，返回出现奇数次的数
（异或）
Onsite(4轮技术+1轮午饭+senior recruiter）
1.两个字符串，求出unique characters，即只出现在一个string中的char
（array[26]，用0-3标记）
2.manager午饭，聊组里情况+我现在的工作项目
3.warm-up question:给个tr... 阅读全帖 |
|
w****o
发帖数: 2260 | 37 fairyli,
你的这个问题到底指的是什么？
是不是可以简单的理解为给一个string,给一个dictionay,从字典里找这个string的所
有的anagram？
这个字典dictionary是以什么数据结构形式给你的？还是你自己随便用你认为合适的数
据结构存的？
这个字典是以map的形式给你的吗？还是以DAG给你的？有没有排序号？如果搜索一个单
词的话，时间的复杂度是多少？
还是不用管字典具体是如何实现的，他们已经提供了一个接口可以查找一个单词而已？
谢谢！
"给个猜词小游戏的app，显示一个合法string的anagram，要求用户一分钟内给答案，
返回对错，time out之后返回所有的正确答案。dictionary作为list，已知。
（预处理dictionary,用hashtable存，key是string排序后的结果，每个slot用bst存
，时间为logk）eg:给atme，正确答案包括team, mate, meat, tame
"
offer |
|
g**********r
发帖数: 27 | 38 最后那个可以用空间四叉树搞应该， 预处理好后，可以log(n)的查询
看你的面试间隔都好长啊，是twitter的处理速度很慢吗？ |
|
l****p
发帖数: 397 | 39 怎么预处理比较好呢？用breadth-first search的复杂度能达到O(4^n)，如果最近结点
很远的话，那也是很耗时的。
Twitter基本得面试完一周后才有结果，然后schedule下一次再拖它一周 |
|
|
g**********r
发帖数: 27 | 41 最后那个可以用空间四叉树搞应该， 预处理好后，可以log(n)的查询
看你的面试间隔都好长啊，是twitter的处理速度很慢吗？ |
|
l****p
发帖数: 397 | 42 怎么预处理比较好呢？用breadth-first search的复杂度能达到O(4^n)，如果最近结点
很远的话，那也是很耗时的。
Twitter基本得面试完一周后才有结果，然后schedule下一次再拖它一周 |
|
|
O******i
发帖数: 269 | 44 第一题要是没想到要先用排序作预处理，就会像我那样悲剧了。 |
|
r******r
发帖数: 700 | 45 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
r******r
发帖数: 700 | 46 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
|
t****t
发帖数: 6806 | 48 如果不能预处理, 这个就可以了. 但是考虑到面试题一般不会这么简单, 还是问清楚比
较好. |
|
y****n
发帖数: 743 | 49 只是就题论题，如果能预处理还要平衡“时间和空间”和“空间换时间”的问题。
因为原题要求时间空间都优化。 |
|
r**m
发帖数: 1825 | 50 Nod, 应该先问一下这个，已知的点集合是否可以预处理。
用简单hash是不是最快。 |
|
