w****x
发帖数: 2483 | 1 倒排索引, 要先做预处理.
然后用一个map, map的pair是<文件号, 出现几个词>
1. 遍历一便句子的每一个不重复的词, 把这个词对应的文件号key的value加1.
2. 便利map, 找出频率>=p的文件 |
|
z**********g
发帖数: 209 | 2 A period of time where users login and logout, given a sets of login and
logout time pairs (number N), write a function that can show the number of
users (max Number K) online at any given time.
请问这题怎么做？ 方向应该是要减少每次query的时间，因为预处理的时间要 NlogN应
该是无法减少的。
数据结构要用interval tree， 每次query就是KlogN，这也不快呀。有没有什么更好的
方法。 |
|
L***Q
发帖数: 508 | 3 我估计这题的意思是给定一个login/logout 时间的set，每次给你一个time，你的
function返回那个time在线人数。
那么每次function都去scan一遍效率就挺低了。应该是有个预处理，然后给一个time，
能很快返回在线人数，不需要去scan原来的set。
我瞎猜的哈
online |
|
w****x
发帖数: 2483 | 4
预处理因该就是, 还是先按时间端点排序, 遍历一遍时间小段, 记录时间小段的在线人
数, 就是根据开始点-结束点算, 对于给定时间点做binary search定位到时间小段并返
回在线人数 |
|
w****x
发帖数: 2483 | 5
1. 任何一个时间段(login time & logout time)都是由两个端点(login logout)组成,
首先不分端点是login还是logout对所有端点排序. 然后遍历整个数轴, 对每个端点和
端点之间的小段, 记录其在线人数(当前的login端点数 - 当前logout端点数), 这步是
算预处理, O(n)
2. 因为用户login, logout都是按时间顺序的, 所以可以很轻松的动态维护这个数轴.
3. 当需要查询一个时间点用户数的时候, 用binary search找出这个时间点坐落于哪个
时间小段, 这个时间小段对应的在线用户数就是答案(logn) |
|
g*********e
发帖数: 14401 | 6
可以优化一下。比如统计表明一个固定长的word里面所有char中第i个为x的概率最大，
则首先猜这个字母。若不正确，则猜概率第二大的char&position。
不过这样预处理比较麻烦 |
|
b*****c
发帖数: 1103 | 7 给定10万点，再给query set，怎样预处理能使每次query复杂度降低？
近似算法也行，点的坐标都是正整数，
kd树也太慢了，fortune's algorithm代码太长，比赛时连打字不够时间啊 |
|
b*****c
发帖数: 1103 | 8 sqrt(n)是每次query的，n*lg(n)是预处理的，主要还是query太慢 |
|
r*****d
发帖数: 1924 | 9 【 以下文字转载自 WashingtonDC 讨论区 】
发信人: Westridge (西岭), 信区: WashingtonDC
标 题: Java开发人员知识点（更新）
发信站: BBS 未名空间站 (Wed Apr 18 00:03:19 2012, 美东)
Java开发人员知识点
1.听说过James Gosling，SUN和Oracle公司。知道网上下载Java的地址，在哪讨论Java
。练习过Java在Windows下的安装和配置。知道Java应用系统中常见的几种license和JCP。了
解bytecode和Java在不同系统下可以轻松移植的原理。
2.懂得基本的Java编程和行命令格式。了解面向对象的编程思路。
几个基本点：Java基本语法和控制结构，命名和代码风格，结构化，对象封装，继承，
抽象，多态，接口，异常处理，堆空间，栈空间，垃圾回收器，static，this，
synchronized，annotations，JUnit，JDBC，JSP/servlet
Java Core APIs: java.lang，java.util，java.io，java.a... 阅读全帖 |
|
t*****j
发帖数: 1105 | 10 先预处理，把所有头字母和尾字母相同的的单词，只取最长单词，其他去掉。
这样最多总共有26×26种可能性。然后图论算最长环路。 |
|
p********s
发帖数: 37 | 11 呵呵我猜是对的。。
其实觉得也不用求和，楼上思路本质就是预处理把所有负数往左merge。因为如果a[i+1
]是负数的话选了a[i]肯定要再选a[i+1]，所以直接看成一个整体就行了。于是转化为
一串正数，求起来就直接了。 |
|
p*****2
发帖数: 21240 | 12
probability
这个可以动态选择吧。
每到一个数就算一下概率然后看选择。不过是O(n)。
如果预处理一下，可以log(n)吧。 |
|
h****b
发帖数: 48 | 13 背景和经历：
国内名校混混，硕士混到之后又辗转混入微软中国，懵懂干了几年的测试，决心出国。
雷蒙德的卧佛拿了两个（办公室组和手机组），无奈国内极品老板不放人还给穿小鞋，
所以又去面了亚麻和狗狗，都是测试的位子，最后选了亚麻。
技术相关的面试总共经历了包括微软内的两个组各五轮，狗狗电话一轮国内三轮柯克兰
三轮，亚麻电话两轮西雅图四轮，小计二十三轮。因为签过恩地诶，所以题目要么不写
出处，要么细节做点变化，大家见谅。
关于准备：
简历里的闪光点要有针对性的挖掘。比如我用在微软内的简历里大吹特吹自己找八哥的
数据和一些特别经典的八哥；投给狗狗和亚麻的简历就强调自己写的自动化框架解决了
多大的问题。亚麻没找人内推，招聘官特意告诉我说我的简历和这个坑太匹配了。
对于要面试的组稍微做些功课也很重要。作为测试经理，对于一个用过自己产品，甚至
能提出一些主见的候选人自然是很喜欢的。在和办公室组聊的时候，我刚好之前把一些
私人表格从狗狗文档换到了微软的天盘，做了一些对比，老板听得很开心。。。
编程题的复习我是通读了150，编程珠玑和何海涛一百题，然后再浏览本版精华区，最
后几天去找点新题做做保持临场状态... 阅读全帖 |
|
l****p
发帖数: 397 | 14 这题是用kd tree预处理吗？还记得是150哪一章的题吗？我好像不记得150有这题 |
|
s********0
发帖数: 34 | 15 O(n^3) 这样可行不～
预处理: O(N^2)
x[i][j]: (i,j) 在ith row左边的连续black
y[i][j]: (i,j) 在jth col上边的连续black
for i:
for j:
for (int d = min(x[i][j], y[i][j]); d >= 1; d--)
if (x[i][j-d+1] >= d && y[i-d+1][j] >= d) {
ans = max(ans, d);
break;
}
return ans; |
|
p********s
发帖数: 37 | 16 还是没考虑成熟，哎面完了人就懒下来了，bz大牛将就看下
如前所述如果把正方形预处理成左上和右下两部分，并根据对角线dp，那么对于每条对
角线(左上-右下方向）问题可以转化为一维情况。即
如果可能的左上角(x0,y0)可以往右往下延伸到(x0+a,y0)和(x0,y0+a)，且如果
可能的右下角(x0+i,y0+i)可以往左往下延伸到(x0+i-b,y0+i)和(x0+i,y0+i-b)
则构成正方形，否则不行。一维表示就是
用集合{(ai,bi)}表示所有(<=n)条起点为ai，终点为bi的直线，对应于上面的左上角（
ai是y0的值，bi是y0+a)
用{cj,dj}表示所有条起点为cj，终点为dj的直线，对应上面的右下角(dj是y0+i,cj是
y0+i-b)
要求的是：对于每个(ai,bi）有集合{(cj',dj')}满足cj'<=ai，bi>=dj'（才能构成正
方形），求集合中最大的dj'-ai（对于每个ai相当于求最大的dj')
-----问题描述后开始糊涂的分割线------
一开始显然{ai,bi}是按ai自然排好序的，a[i+1]=a[i]+1
而{cj,dj}是按dj... 阅读全帖 |
|
d**********x
发帖数: 4083 | 17 RMQ, O(nlogn)预处理，O(1)查询区间最大最小值
只是我对那个二分查找存疑 |
|
a*******y
发帖数: 1040 | 18 top queries 做个trie 当然也包括了你query的预处理找出expending query，然后再
去找common prefix的 |
|
g*****e
发帖数: 282 | 19 方便展开讲讲么？我想过分别对炮弹高度和地形高度分别预处理，但是分别会丢掉先后
炮弹顺序信息和地形相对位置信息。时间复杂度还是降不到O(M+N)。多谢了 |
|
w****x
发帖数: 2483 | 20
面试官当时很轻描淡写的提了一下“可能有预处理加快效率”，但是说自己看着办，当
时马上想到trie了 |
|
|
b***m
发帖数: 5987 | 22 我以前行业里最常需要用到的是路径搜索，包括实时动态搜索和预处理搜索。 |
|
w****x
发帖数: 2483 | 23
为什么/*abcddfa 不合法呢??
这个情况需要考虑进去, 编译器作预处理的时候不能假定用户输入的都是合法程序啊 |
|
w***o
发帖数: 109 | 24 我觉得应该问面试官以下几个问题before coding
1. except 是sorted吗？
2. except是［1..n]吗？
3. except 是每次都一样的吗？如果一样，可以做预处理 |
|
w***o
发帖数: 109 | 25 我觉得应该问面试官以下几个问题before coding
1. except 是sorted吗？
2. except是［1..n]吗？
3. except 是每次都一样的吗？如果一样，可以做预处理 |
|
g*****e
发帖数: 282 | 26 "还有一个问题是如何快速给出任何两个人的粉丝交集"
预处理，上hashtable（O(N))，或者把每个id的粉丝按id排序，然后bs？大家讨论下吧
=) |
|
g*****e
发帖数: 282 | 27 "还有一个问题是如何快速给出任何两个人的粉丝交集"
预处理，上hashtable（O(N))，或者把每个id的粉丝按id排序，然后bs？大家讨论下吧
=) |
|
p*****e
发帖数: 1611 | 28 来自主题: JobHunting版 - G/F面经 多串模式匹配做好的方法可能是suffix array+LCP
预处理O(m)，然后每个query的复杂度是O(n+lgm) |
|
b***m
发帖数: 5987 | 29
不是吧，写出code跟最优code差距还是很大的吧。我在原来游戏公司的时候，用A*算法
对所有关卡的地图数据做预处理，最大的512x512的地图，用当时配置的机器运行需要2
个小时（没办法，当时机器太慢了）。后来CTO嫌太慢，人家熬了一个通宵对算法做了
优化，结果同样的地图在同样的机器上运行，只要10分钟。简直羞愤得我要死啊……差
距太大了。人家现在在硅谷某中型软件公司做CTO。:-( |
|
w***o
发帖数: 109 | 30 因为字典已经给定，就不需要对字典做预处理，可以假设为HashMap，在字典里找词应
该是O（1）吧。我觉得这题的重点是要找所有valid的10个字符的排列。 |
|
g*****e
发帖数: 282 | 31 我总感觉可以怎么预处理一下，减少重复计算 =) |
|
h****n
发帖数: 1093 | 32 4) 从一个文件中找到给定的用户使用的API。文件格式如下：
user1 API1
user2 API3
user1 API2
这个题要问清楚这个操作是一次调用还是多次调用吧。
一次调用的话，就遍历一下
要是多次调用的话，预处理做个hash表效率会高很多 |
|
f*********d
发帖数: 140 | 33 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
包子！
===============================================
Oct.19th ，东部时间1:30， 一面，印度a3
1，为什么基于比较的排序问题复杂度下界是O(nlogn)
回答出来了，他表示赞同
2，分析下面递归算法的复杂度
Alg(array, size)
split -> A1, A2, A3.... O(n)
Alg(A1, size/3)
Alg(A2, size/3)
这个题目是硬伤，他push我快快快，我一紧张，递归函数没有写好， 写出来之后
说用主定理，再一紧张把 a 和 b搞反了。。。
F(n) = a * F(1/b n) + O(n)
总的来说这题做错了
3， 大数据的平方 X^2 X很长 不能用int long 之内的表示
一开始就反应时Divide and Conque， 他表示赞同， 但是我始终没有到NlogN, 只
到了N... 阅读全帖 |
|
j*****y
发帖数: 1071 | 34 一面的第三题一般是可以做到 n^(log3) 吧？
比如 算 A * A where A is n digits number
A = B * 10^(n / 2) + C
A * A = B * B * 10^n + 2 * B*C * 10(n / 2) + C * C
need to compute B * B, B * C and C * C
So we compute three items below:
(B+C) * (B+ C) = B*B + 2*B*C + C*C
B*B
C*C
from which we can get 2*B*C = (B+C) * (B + C) - B*B - C*C
let the time for A^2 is T(n)
so we have T(n) = 3 T(n/2) + O(n)
and T(n) = O(n^(log3)
这里假设两个 n digits number的求和需要 O(n)的时间
补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
包子！
=======================... 阅读全帖 |
|
s****t
发帖数: 467 | 35 刚回来，题目不难，可是遇到了很郁闷的情况。顺便问下大家遇到dev #5这种人怎么应
对比较好？
电面：
给个带有括号的字符串，判断所有的括号是否相配。扩展到几种不同的括号同时出现。
onsite：
1. manager:
给一个字符串，输出一个文件，里面每一行是一个出现的字符，后面跟着它出现的次数
。要根据出现次数降序排列。
2. senior manager:
behavior questions and past projects.
3. dev:
1）二维平面上给一堆点，再给出一个点作为目标。求离目标点最近的k个点。
2）设计A家网站上那个“买个这个东东的客人也买了下面这些东东”的feature，问了
如何scale。
4. BR:
1）给一个字典，当输入一个单词时要求返回字典里所有它的anagram。条件是可以无限
的预处理，只要输入时返回的速度最优就行。
2）elevator design: min wait time, max throughput, scale for different types
of buildings.
面到这感觉都还好，结果下面郁闷了。
5. d... 阅读全帖 |
|
d******i
发帖数: 76 | 36 周四电面，之后马上安排周一onsite，准备的不是很好，sigh~ 题目不是很难。
1.数学题
四位数字 _ _ _ _ ，要求填写这四位数，满足每位数字都是unique，而且前两位 + 后
两位的和为100， 比如 2 4 7 6， 问有多少种组合。
2. 编程题，两个string数组，比如A = {“abc”， “mn”}， B = {“pa"， “d”}
返回一个string为两个数组中string的交叉组合直到其中一个数组的string已经耗尽，
上例中string = ”apbacd“
3. Or两个四叉树
树的节点，有两种情况--没有child，有四个children，每个节点的值为T or F，要求
or两个四叉树，如果一个节点和另一个节点中所有children OR的结果相同，那么合并
为一个节点。
4. external sort，这个没答好...
5. 设计题，如何设计youbube的recommendation。
6. 动态找到median number，150题上的
7. 用sorted array，创建BST
8， 一个图像的二维矩阵，给两个坐标，返回这两个坐... 阅读全帖 |
|
l*******b
发帖数: 2586 | 37 嗯，看起来和预处理一维数组求出任何两个指标间和差不多。
S(ab, cd) = S_ab + S_cd - S_ad - S_bc
... ad cd
... ab bd
00 ... .. |
|
f*****7
发帖数: 92 | 38 你应该问面试官：是一次查询还是多次查询？
如果一次，就用CLRS上快排衍伸出的selection algorithm。如果partition算法可以确
保对半分，或者从概率角度出发，那就是O(N)时间，没有更快的。
如果多次，就先用最好的排序算法，排序预处理，之后每次的查询都是O(1)，如果次数
足够多，可以compensate排序的代价。
总之，第一个是学院派，第二个的工程的思维
你要让对方知道”做事情的方法，比算法本身更重要“ |
|
t****a
发帖数: 1212 | 39 第三题很有趣，偶来给个clojure的解
基本思路是
1. 对T做预处理，构建graph，同时，记录每个字符a-z所出现的位置
2. 由于S长度<100，数量却很大(100M)，意味着有很多重复，使用memoize function会
大大减少计算量
下面的程序在1/1000大小的S数据集上运行需要1.7秒。观察了一下时间和数据集大小趋
势，在完整数据集上几分钟内也可以产生结果
(def alphabet (map char (range (int \a) (inc (int \z)))))
(def T (vec (take 10000000 (repeatedly #(rand-nth alphabet)))))
(def S (take 100000 (repeatedly (fn [] (take (inc (int (* (rand) 100))) (
repeatedly #(rand-nth alphabet)))))))
(def T-ix (group-by #(T %) (range (count T))))
(def T-map (let [pairs (dist... 阅读全帖 |
|
t****a
发帖数: 1212 | 40 第三题很有趣，偶来给个clojure的解
基本思路是
1. 对T做预处理，构建graph，同时，记录每个字符a-z所出现的位置
2. 由于S长度<100，数量却很大(100M)，意味着有很多重复，使用memoize function会
大大减少计算量
下面的程序在1/1000大小的S数据集上运行需要1.7秒。观察了一下时间和数据集大小趋
势，在完整数据集上几分钟内也可以产生结果
(def alphabet (map char (range (int \a) (inc (int \z)))))
(def T (vec (take 10000000 (repeatedly #(rand-nth alphabet)))))
(def S (take 100000 (repeatedly (fn [] (take (inc (int (* (rand) 100))) (
repeatedly #(rand-nth alphabet)))))))
(def T-ix (group-by #(T %) (range (count T))))
(def T-map (let [pairs (dist... 阅读全帖 |
|
w**********2
发帖数: 20 | 41 http://www.mitbbs.com/article_t/JobHunting/32134627.html
large scale 方面
我google 的看了 mapreduce, gfs, bigTable, Spanner, chubby. google 的东西不太
好懂，而且没有源码可以参考。我觉得除了MapReduce 和 GFS 外，其他的过一遍就差
不多了。
facebook 的看了 cassandra, 这个有源码可以看，但是好像 很多地方和paper上面已
经不一样了。
yahoo 的看了 zookeeper，
Amazon 的看了 Dynamo， 我感觉这个最好，paper 比较好懂
所有的paper都是讲large scale 设计中的几个重要问题，
route(consistent hashing 还是B+ tree 类似的lookup table),
consistency, replica 的策略，
failure detection 和应对，
如果做预处理提高读取效率，
master election 策略，
nodes communication ... 阅读全帖 |
|
e****e
发帖数: 418 | 42 一电：
１。给定一个数组，求次大值。
２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
的元素类型不是整数型，可能是String, double, Date...，如何处理？
二电：
１。给一个文件，从中找电话号码。
２。什么是哈希表？解决冲突的方法？
３。分层打印二叉数。
４。二维坐标里n个点，求离原点坐标最近的k个点。
５。面向对象的设计题：停车场。
面对面一：
１。问简历
２。给定一个长度为n整数型数组，看是否满足以下条件，相临数字之差的绝对值，刚
好可以组成 1,2,...,n-1。
例子：2 5 4 6 --> 1, 2, 3 成立。
2 5 4 7 --> 1, 3, 3 不成立。
1 2 3 4 --> 1, 1, 1 不成立。
引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。
面二：
１。问简历
２。求次方，底是个浮点型，指数是整型。
３。面向对象的设计题：从数据模型的角度设计购物网站。主要有哪些类，类里主要有
哪些域，如何... 阅读全帖 |
|
e****e
发帖数: 418 | 43
是。
根据不同的类型，写不同的comparator，再把comparator 传进那个最初的算法（最初
的算法是针对数组元素是整数型。）
1. grep + regular expression
2. list或者open address
3. 我用了一个list, 两个list也能解决。
4. 我是用的heap, quick select更好。
：onsite1：
：2. 线性扫一遍
： followup：排序后线性扫一遍？
同意。排序后线性扫一遍还是n平方的时间复杂度。这个followup问题我没有回答出来
，至今也不知到有小于n平方的解法。
：onsite2：
：2. 二分
：3. 不清楚数据模型的角度是啥
是。data model.
：onsite4：
：2. 线性比较一下
followup：排序一下？这个不清楚
是线性比较，我的思路：有两种情况是没有overlap, 有四种情况是overlap,所以只用
看是没有overlap，再取反就行了。
followup, 预处理：按照区间数组里所有的点之间《分段》，计算每段上所重合
interval的个数。当给定区间来... 阅读全帖 |
|
|
|
d**********x
发帖数: 4083 | 46 其实这玩意在找nearest neighbor的时候，复杂度和heap是一样的,O(KlogN).
加上建树还要更费时O(nlogn)，但是因为预处理成了kd-tree的形式，它还有很多其他
的用途，比如查询在任意一个矩形内的点集，大概是O(sqrt(n))，查询任意点开始的一
个半径范围内的点集。。。
这东西偏应用了，再具体的优化什么的要问搞图像的。。。 |
|
l*****a
发帖数: 14598 | 47 仔细看
其实挺简单的
就是找一个头一段==后一段
而且预处理的程序跟实际程序流程基本一样 |
|
m******s
发帖数: 165 | 48 来自主题: JobHunting版 - G 家面经 真要虐出翔了。。。
1:
边同时遍历两个树边建一个新的，最后有可能要再遍历一次，比如：
I1 =
01
10
I2 =
10
01
则I1 intersect I2 =
00
00
即I1 intersect I2 = 0
2A:
O(n)，由于array可以随机存取所以很好写。。。
2B:
好像前面有说，根据两个人的位置dp，greedy不太对
3A:
c++ stl lower_bound
3B:
应该不用上template吧orz，意思意思行了
4A:
trie (prefix tree)，根据用户输入习惯或者是流行搜索词进行缓存
4B:
range minimum query，做法很多，在线算法评判的标准有这么几个：
空间复杂度 预处理时间复杂度 每次查询时间复杂度
可以搜索一下各种算法的不同
另外还可以扩展到多线程/多台机器
的。 |
|
E*****D
发帖数: 3 | 49 刚收到信说还要一轮电面。是不是因为第一轮表现不够好所以还要在电面一下？
附第一轮面经（班上有人面过的题目）：
给一个大文件每一行是：
parentId:childId
parentId 和 childId 都是string.
1. 定义自己的数据结构，写一个函数预处理数据。
2. 写一个函数能够快速判断两个给定的id有没有关系，即有没有共同祖先。 |
|
Y**Y
发帖数: 66 | 50 那这就是个DAG了
从两个节点同时做BFS，看有没有overlap. 最坏的是两个没关系的。
要快一些的话， 预处理，每个节点存他最早的祖先们 （sorted), 也就是DAG的
starting nodes, zero in-degree。 对所给的两个nodes, 取两个sorted lists的交集
。
null. |
|
