p*****a
发帖数: 147 | 1 来自主题: JobHunting版 - G家一道题 这题正解是什么？
- 树结构，O(lgn), how to build tree? 怎么用二分加速？
- 矢量乘法？
- scan all polys, find the min poly that contains the given poly. O(n), easy
to understand and divide to multiple machines.
原题见：http://www.mitbbs.com/article_t/JobHunting/31828487.html
10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，
要么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求
出最小的包含它的多边形。已知有现成的函数可以判断两个多边形是否相互包含，
iscontained(poly p1, poly p2)。
如何加速？如果在多机的情况下呢？
=> 可以用树结构表示包含的关系。
可以用二分搜索做加速。
多机的话可以range一个机器处理一个... 阅读全帖 |
|
k****n
发帖数: 369 | 2 我估计意思是不能用hashmap，不能用extra memory，所以只能Inplace sort其中一个
那么应该sort哪一个。
假设长度分别是m，n，m>>n。
如果sort短的，时间是O(nlogn)+O(mlogn) = O((m+n) logn)
如果sort长的，时间是O(mlogm)+O(nlogm) = O((m+n) logm)
所以应该sort短的。
但是实际也有可能是这样
sort短的，时间是anlogn + bmlogn = (an + bm) logn
sort长的，时间是amlogm + bnlogm = (am + bn) logm
a和b分别是排序和二分查找的常数系数
因为 m >> n，所以带n的可以忽略，那么就是b * logn * m vs a * logm * m
所以当查找的常数项b和排序的常数项a满足 b logn > a logm的时候
排序长的可能比较快。
不过这一般不会发生。。。除非二分查找写成shit...
（刚才写错了，不过结论是一样的） |
|
H*****1
发帖数: 4815 | 3 是log k
第一个array里二分作为pilot在第二个array里二分查找
如果m > k; n > k，只用搜索a[0:k-1] 和 b[0:k-1] |
|
H*****1
发帖数: 4815 | 4 是log k
第一个array里二分作为pilot在第二个array里二分查找
如果m > k; n > k，只用搜索a[0:k-1] 和 b[0:k-1] |
|
S**I
发帖数: 15689 | 5 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人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... 阅读全帖 |
|
S**I
发帖数: 15689 | 6 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人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... 阅读全帖 |
|
g***j
发帖数: 1275 | 7 各位大侠，我在写程序的时候，特别是二分程序的时候，经常不知道边界什么时候减1
，什么时候加1，什么时候就用求出来的mid
比如如下的code，我开始就搞错了，把第一个merge_sort的重点弄的mid-1，第二个弄
的mid，然后merge里面写的mid-1，发现不work，调试了才知道错了。
理论上来说，这个边界的起始应该不是问题啊，为什么差一个就不work呢
请问，在处理类似，先求mid，然后二分的时候，有什么诀窍呢？
int merge_sort(int array[], int start, int end){
if(start < end) {
int mid = (start + end)/2;
merge_sort(array, start, mid); // shound't be mid -1 !!!!
merge_sort(array, mid+1, end);
merge(array, start, mid, end);
}
... 阅读全帖 |
|
Q**a
发帖数: 406 | 8 说一下我的想法，请指正
lz的方法是可行的，唯一的问题是cost estimation比较困难，很难说比原始方法更优
我倾向于认为lz的方法更慢一点，模糊的感觉如下，欢迎按编号批驳
1. 二分查找隐含的假设是“所查找的元素在有序表中的位置服从均匀分布“
2. 而类似的合理假设是在本题的矩阵中所查找的目标元素可能的位置同样服从均匀分布
3. 在绘制阶梯的过程中，移除部分行列后目标元素的投影不再服从均匀分布
4. 使用二分查找的效率逐渐降低
另外在lz的启发下我想到这个办法，可能会稍微好一点：在绘制阶梯的过程中第i步走2
^i |
|
Q**a
发帖数: 406 | 9 说一下我的想法，请指正
lz的方法是可行的，唯一的问题是cost estimation比较困难，很难说比原始方法更优
我倾向于认为lz的方法更慢一点，模糊的感觉如下，欢迎按编号批驳
1. 二分查找隐含的假设是“所查找的元素在有序表中的位置服从均匀分布“
2. 而类似的合理假设是在本题的矩阵中所查找的目标元素可能的位置同样服从均匀分布
3. 在绘制阶梯的过程中，移除部分行列后目标元素的投影不再服从均匀分布
4. 使用二分查找的效率逐渐降低
另外在lz的启发下我想到这个办法，可能会稍微好一点：在绘制阶梯的过程中第i步走2
^i |
|
C***U
发帖数: 2406 | 10 楼主说的二分发和你发的二分发不是同一个。。。
要么就是我理解错楼主的意思了。。。。 |
|
p********n
发帖数: 20 | 11 直接这样是不对的吧...
貌似应该是先二分找到lower bound；然后在lower bound到n的范围内，再二分找到最
大的以prefix为前缀的串... |
|
G******i
发帖数: 5226 | 12 ☆─────────────────────────────────────☆
lanmao (懒猫) 于 (Sat Jul 9 11:29:24 2011, 美东) 提到:
（坑已经够大了，只管挖不管填不道德，俺自个合集了。）
看了芙蓉的减肥照片和凤姐的励志围脖，也想来跟个励志潮流。满版上都是google
amazon facebook，搞得不是编程熟手不会脑筋急转弯就没好工作似的。 俺来贴个BSO
的Java面经吧，来鼓励一下正在奋斗着的童鞋们。认识俺的都不要说啊，俺那么低调~~~
个人背景：人工智能方向的，学校算top 50吧，9月答辩，读了整整八年的老博士马上
就要新鲜出炉啦！
先低调的说一下amazon经历。amazon给俺发信三四次，要求俺去面试，没理。HR打电话
过来说为啥不理，俺说你们招聘职位太entry level，没兴趣。HR说那给你找个高层次
点的职位。过两天打电话来，说有个高级程序员的活，能不能给我们的hiring manager
一个向你展示我们项目产品的机会。俺心想，说得好听，还不是又要问那种脑筋急转弯
问题，反正答不出，没必要耽误时间。于是很彪... 阅读全帖 |
|
f***n
发帖数: 117 | 13 这个m和n不等的时候对角线是怎么找的？
另外，如果从矩阵的最边上（横和竖）二分似乎也可行，也比较简单。
比如
1 2 4 5
3 8 10 19
4 9 12 20
要找10的话，
从1 3 4 9 12 20中二分找，到9和12 之间的时候，就可以把9左边和上面的全扔掉了，
就掉下
4 5
10 19
然后继续在这个小矩阵边上找。
复杂度是log(m+n) + log(m-1+n-1)+ .. + log(m-n)
不知道这个逼近应该是啥，数学忘光了。。 |
|
f***n
发帖数: 117 | 14 · 大体背景
⁃ CS fresh phd，东部某top50工科小学校，方向是超算环境下的存储优
化，在应用层作业，通信环境主要是MPI，跟工业界流行的分布式关系不算太大。
⁃ phd期间在fb实习过一个学期，在ibm research实习过两个月，在某国
家实验室实习过几个暑假。
⁃ 因为个人原因，主要申了东北部的职位，基本都在boston nyc。
· 技术积累和准备
⁃ 我自己很懒，也没有很强的毅力，我觉得复习很痛苦。我看过
programming interview exposed，这本书比较简单；看过150题的基础知识部分，题看
了20道左右，随机挑的，认真写过5道题左右；leetcode的题看了估计也有20道左右，
写过一个数字转换的题，写了两小时才pass，corner case太多了。之后就有了心理阴
影，很少写题，这也是我的硬伤之一。幸运的是，我面的很多职位偏系统和后台，并不
是每个公司都让白板编程。
⁃ 另外，我2010年初投... 阅读全帖 |
|
h********6
发帖数: 285 | 15 可以先二分找到peak位置，O(logN)
然后在peak两边分别二分，O(logK) + O (log(N-K)) |
|
w***g
发帖数: 5958 | 16 【 以下文字转载自 Programming 讨论区 】
发信人: wdong (cybra), 信区: Programming
标 题: 算法导论重点
发信站: BBS 未名空间站 (Mon Oct 15 17:15:36 2012, 美东)
上次在CS版答应给划重点的，发到这儿算了。我手上是第二版。我觉得转行的没有基础
的看完下面这些(约300页，全书1/3的样子）在算法上基本上能达到科班出身水平。可
以按书本身的顺序看，也可以按下面给出的顺序看。
A. 基本概念
1-3 pp.1-61
B. 基本程序设计方法
穷举法 看眼八皇后问题的接法和产生全排列的方法
贪心法 16.1-16.3 pp.370-393
23.1-23.2 pp.561-580
动态规划 15.1-15.4 pp.323-356
分治法(divide and conquer) 本书没有专门的章节讲这个，需要自己随便上网搜搜。
结合下面章节看
选中位数 9.1-9.3 183-189
快速排序和二分查找
回溯(recursion) 这个是具体的实现方法，可以和... 阅读全帖 |
|
h****n
发帖数: 1093 | 17 二分的复杂度也是O（n×m）吧
两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
复杂度还是O（N×M）啊
你怎么个二分的 |
|
y***m
发帖数: 7027 | 18 这样可否:
二分递归思路, 假设都是正整数, 数组 a[n]
f 函数三比一, g 函数二分递归
bool f(a1,a2,a3)
{
return a2
}
int g(a[1..n])
{
if n 偶:
if n >= 4
{
m=n/2
if f(a[m-1],a[m],a[m+1])
return a[m];
else if f(a[m],a[m+1],a[m+2])
return a[m=1];
else
{
int rst = g(a[1...m/2]);
if(rst>0)
return rst;
else
return g(a[m/2...n]);
}
}
else
return -1;
////////////////... 阅读全帖 |
|
f*********d
发帖数: 140 | 19 刚才面完
三哥, 以为又会搞我的...总共38分钟,问了如下问题，感觉他是想整我来着, 结果貌似
未遂:)
前戏: 自我介绍
高潮:
1. 荷兰国旗问题, 给算法, 分析实例, 都完整的给他走了一遍 rrggbbgrbg
2. 一个建筑物，楼层有无限， 有无限多的鸡蛋，仍最少次数找出最高的那层扔下去鸡
蛋不会挂
搞了一会， 最后用类似二分的思想， 1 2 4 8 16.... 先找到区间， 再二分查找
， 我说不知道是不是最优的， 他说可以了， move on吧
3. priority inversion
不知道inversion 什么意思， 查了一下， 就瞎猜的是降低进程优先级的， 承认了
自己不懂这个概念
4. volatile
问他是不是c里面的概念， 他说是的， 然后我balabala
5. static
问他是不是c里面的概念， 他说是的， 然后我balabala
然后说在c++里面，他说够了， 就不说了。。。move on
6. mutex and semaphore
7. 什么是multi-threading
8. 让我解释recursio... 阅读全帖 |
|
t*****l
发帖数: 241 | 20 先二分选定一行，再在行里二分？这个方法是不对的 |
|
c****p
发帖数: 6474 | 21 快排吧。。。
快排和二分查找没专门写过练过的基本没人能一次写对。二分从发明到被认为完全正确
也经过了好长时间。 |
|
k*****m
发帖数: 14 | 22 来自主题: JobHunting版 - G 家面经 最后一题是不是可以用segment Tree，假设二分，每个节点保存index range和在这个
区间的最小值。然后子节点就是二分父节点的range，分别保存在这个range内的最小值
，一次类推。
这样就是log(N)的复杂度得到最小值。
不知道有没有更好的解法。
求第二题的解法呀。 |
|
k*****m
发帖数: 14 | 23 来自主题: JobHunting版 - G 家面经 最后一题是不是可以用segment Tree，假设二分，每个节点保存index range和在这个
区间的最小值。然后子节点就是二分父节点的range，分别保存在这个range内的最小值
，一次类推。
这样就是log(N)的复杂度得到最小值。
不知道有没有更好的解法。
求第二题的解法呀。 |
|
m******s
发帖数: 165 | 24 假设是m*n的表（m<=n）
朴素走对角线：最差O(n+m)
二分：最差O(m*log(2n/m))
即m==n时最差的情况下二分也是linear |
|
m******s
发帖数: 165 | 25 二分的最差复杂度是（省略全部big-O）：
T(1,n) = logn
T(m,1) = logm
T(m,n) = max_j{T(m/2,j) + T(m/2,n-j)} + logn
要费一点力气，最终可以搞出来
T(m,n) = mlog(2n/m)
需要注意到二分运气不好是要搜两边的。。。 |
|
r*******e
发帖数: 7583 | 26 只能想到nlogn的笨办法
把A,B,C都排序
然后遍历A中的元素a
对于每一个a，在B里找小于a的最大元素b'(二分查找logn)
再在C里找小于b'的最大元素c'（二分logn）
记录distance = a-b + b-c + a-c = 2(a-c)
由于A,B,C排列有六种可能，重复六遍上述过程，复杂度不变。。
them |
|
a*******3
发帖数: 27 | 27 对N个数组中的最大元素开始做二分，找到一个最小的m，是的N个数组中恰好有>=k个数
小于等于m，那么m就是所求。
每次求N个数组中多少个元素小于等于m，nlogn，最多二分32或者64次（取决于数据是
32位还是64位），这样看的话是nlogn的，只不过常数有点大
如果不认为这个实常数，那么就是nlog(n)log(max_value-min_value)
klogn的问题是，k可能很大，如果k~n^2/2，那复杂度就高上去了 |
|
c********t
发帖数: 5706 | 28 ~然后再在b[j .. j+2^x]里做二分找到刚好大于a[i]的数
应该是b[j+2^(x-1), j+2^x]里做二分吧。
这里的x取什么值最好，那很难说了，感觉和a[i] b[j]value相关，与j,m大小也相关。
甚至先x=10,找到 b[j+10^(x-1), j+10^x]，再在这个区间 x=5来缩小范围也可以吧。
太复杂了。
i] |
|
b****g
发帖数: 192 | 29 如果三人互为朋友，那就说明无法二分partition，就回答否就可以了。
要是能二分partition，就回答是。
这题是不是就递归或者iterative搜索，见到一个点染一个色，其实就黑白两色间隔着
染，万一发现一个点被染成两种颜色了，就返回否。 |
|
l*n
发帖数: 529 | 30 挖个坟。
你这个结论是错的，二分查找要求必须是ArrayList，但是如果是ArrayList的话，
merge区域before/after区段的拷贝还是要O(n)(新建ArrayList作为返回值)；而如果完
全使用原ArrayList，因为ArrayList没有public的区段删除方法，每次remove(i)的时
候都是O(n)。只有LinkedList处理after区段是O(1)，但是before区段还是O(n)，而且
二分就不存在了。综上，还是线性处理+新建ArrayList吧。 |
|
f*********d
发帖数: 140 | 31 wow, 这是实在是精巧~多谢指点了！
二分会用，翻转的也会用，合在一起就傻眼了，
顿时发现，二分也不会用，翻转也还没掌握~ |
|
f****e
发帖数: 34 | 32 这题挺多方法的，hash，利用快排对后缀下标排序+二分，或者直接后缀数组+二分等。 |
|
l****o
发帖数: 315 | 33 用ArrayList， 插入时二分查找logN, insertion average O(1), worst O(n). Find
也用二分LogN. |
|
l****o
发帖数: 315 | 34 用ArrayList， 插入时二分查找logN, insertion average O(1), worst O(n). Find
也用二分LogN. |
|
b******p
发帖数: 49 | 35
这题我完全没做出来
面试官没让我写code，我就和他说了，建一个hash table，或是建一个bloom filter之类
他说这些不行，又补充说：
blacklist是一个链表，所以二分查找的代价和数组的二分查找不一样
他说要“incremental”的解法
也就是将整个blacklist读入，再建hash table的方法通通不行
他说，譬如blacklist里面有几百万个数怎么办？几百万个数就是~400MB，超过了CPU的
缓存的大小。如果建hash table，性能会损失非常大。所以，我说的方法全都错误，不
是他想要的。估计是因此被拒了。
后来才知道这个是CareerCup 12.3这道题目。
没做过，真该面壁思过去… |
|
x****g
发帖数: 1512 | 36 有点晕.
如果做过a(i+1)-a(i)就已经是O(N)了.
再二分意义何在?
直接二分不行吗? |
|
g*****g
发帖数: 212 | 37 来自主题: JobHunting版 - 新鲜G面经 如果每一行二分,每一列二分找边界
nlogm + mlogn
不过
看来大牛还有更优解 |
|
z**a
发帖数: 69 | 38 已跪，回想我的这次onsite经历，那就是一个joke啊，浪费了我的时间，也浪费了面试
官的时间。还浪费了我一天PTO飞过去。
第一轮，关键词，无厘头。开始先各自寒暄了几句，天真的我没有想到后来的尴尬。第
一个问题是：“如果有一个大文件，只有小写的（关键）的a-z（关键），那么怎么压
缩这个文件呢？”我是最近看大数据的东西看得有点太投入了，上来就说把文件分段，
hash每段，有个server专门存内容，bla，bla…，他问，那怎么恢复呢，我说每个文件
最后表现为一串hash key，恢复的时候按hash key找到存放的位置就行了。他没说啥，
我意识到这不是他想要答案，不过我最后才意识到这其实都不是想要问的问题。。。为
了引导我，他举了个例子说比如：abcd…z重复了一百遍。这你怎么存呢？当时我有点
懵了，我说：”这不就是存个abcd…z，然后存个100不就得了？”，他又问还有“怎么
恢复“，我老实点的说：”有多少遍，恢复的时候写多少被“. 他接着说：”abcd…z
100遍不是连续的呢？“我以为他说的是先50遍在这，后50遍在那，虽然我现在感觉有
点地方不对劲了，也只有硬着头皮说，... 阅读全帖 |
|
r*******k
发帖数: 1423 | 39 好像可以进一步优化，类似LIS优化成O(NlgN)
之前的所有record的upper bound是排序了的。
用i+1个record的lower bound去upper bound里二分查找，可以找到不想交的最大index
，然后低于这个index的就不用比了。高于这个index的，由于相交了，也不用比了。
这需要另外一个数组X记录低于i的最大值。因为M[i]是以i结尾的最大值，并不是小于
等于i的最大值。
不过这么看，M都没有记录的必要了。。。
因为高于i的那些record，也就是和i+1有交集的，也有可能是最大值。
所以M[i+1]可以通过二分查找迅速算出，但X[i+1]必须用M[i+1]和X[i]比较之后算出 |
|
z**a
发帖数: 69 | 40 两轮店面。第一轮看面试官的名字，应该是以前在本版被抱怨的很多回的华裔面试官。
不过个人感觉真人却不像很多人抱怨的那样糟糕，其实我觉得他还挺不错的。面试题只
有一道，怎么查找一个数组中缺省的那一个整数，是的，不难找到方法。他会不停改变
条件，然后我给出不同的方法。最后一点是数据很大，而且数组不可变，如何找。给我
的提示用二分，不过到最后我都没做出来。其实在编程珠玑上有类似的题，可惜我没看
过。。。出乎意料，我最后拿到了二面。二面的题目也不难，数独valid，实现vector
类。当天拿到了Onsite。
Onsite签了NDA所以不透题了，其实也没什么必要透题，题目真心不难，可以说是在
leetcode平均水平，甚至以下，什么树啊，图啊，dp啊根本没有，链表都没。不过面试
官会追问很多细节的地方，比如代码的效率和改进，数据的overflow，进程空间等基础
概念，一个二分查找搞了我40分钟。三轮coding，我觉得我死在第三轮了，题目没听清
。。。写到最后才知道会错意了，当场就要崩溃。第四轮是design，我觉得不难，面试
官引导的很好，我也算是把自己能说得上的都表达出来了。最后看起来面... 阅读全帖 |
|
z**a
发帖数: 69 | 41 两轮店面。第一轮看面试官的名字，应该是以前在本版被抱怨的很多回的华裔面试官。
不过个人感觉真人却不像很多人抱怨的那样糟糕，其实我觉得他还挺不错的。面试题只
有一道，怎么查找一个数组中缺省的那一个整数，是的，不难找到方法。他会不停改变
条件，然后我给出不同的方法。最后一点是数据很大，而且数组不可变，如何找。给我
的提示用二分，不过到最后我都没做出来。其实在编程珠玑上有类似的题，可惜我没看
过。。。出乎意料，我最后拿到了二面。二面的题目也不难，数独valid，实现vector
类。当天拿到了Onsite。
Onsite签了NDA所以不透题了，其实也没什么必要透题，题目真心不难，可以说是在
leetcode平均水平，甚至以下，什么树啊，图啊，dp啊根本没有，链表都没。不过面试
官会追问很多细节的地方，比如代码的效率和改进，数据的overflow，进程空间等基础
概念，一个二分查找搞了我40分钟。三轮coding，我觉得我死在第三轮了，题目没听清
。。。写到最后才知道会错意了，当场就要崩溃。第四轮是design，我觉得不难，面试
官引导的很好，我也算是把自己能说得上的都表达出来了。最后看起来面... 阅读全帖 |
|
c********6
发帖数: 33 | 42 那用什么存放数呢？
如果要支持插入的话就得是链表或动态数组
链表没法二分查找吧，寻找时o(n)
动态数组到时可是二分，但是插入得o(n) |
|
d*******s
发帖数: 695 | 43 这个似乎不行，但二分也许是个好思路
假设有个(6, 15) (7, 14) (7.5, 12） (8, 13)
对(7.5, 12)来说，一二分，就会把(6,15)给漏掉。 |
|
a********5
发帖数: 1631 | 44 这种题标准解法（未必是最优）应该是扫描线+二分。说标准意思是可以写出模板来，
类似的题一套就行了。
但是问题是真的45分钟可以搞定？我大二时候做类似的merge矩形的题，扫描线+二分，
光写码就写了快俩小时。。后面DEBUG什么的，POJ还出各种奇奇怪怪的问题，弄了两天
才过。。 |
|
c********5
发帖数: 26 | 45 我用的二分查找，这个跟majority number不太一样，这道题是有序数组，不太需要用
voting的算法
这里是在n/4 2n/4 3n/4的位置做二分查找，如果存在popular number的话，一定在这
几个位置会出现
希望不要这么崩吧，一点错误都不能犯 |
|
h*******e
发帖数: 1377 | 46 先两个二分找到两个peak 然后用3段做二分找val? |
|
|
|
r*******g
发帖数: 1335 | 49 这个二分什么意思？一维数组又没有排序，即使只有0/1，即使有一段是连续1，如何找
到1？没法二分吧 |
|
l******s
发帖数: 3045 | 50 感觉还是二分，不过是以矩形四边一个框的形式二分而不是每个边的形式。每个边的查
法的劣势在于会有过多的在另一向量上的浪费查询。四边一起查的方式虽然在理论上计
算time complexity是(m+n)*ln(m +n)但实际上因为此方法的剪枝优势，实际会少很多。 |
|
