i*********e
发帖数: 9 | 1 Google(summer intern)
1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
，矩形的4个角都是1.
leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
意。不知道有没有复杂度更少的算法。
2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
目。之后把队打乱，
跟据高度和比自己高的人的数目还原原来的队列。
我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
算法。
Bloomberg:
1. 给一个数组： 6， 3， 10， 5， 16， 8， 4， 2， 1
找出这个数组的顺序。写一个程序，input是数组里的一个数，Output是从这个数开始
的整个数组。
2. 实现一个BFS算法。
3. 一个数组，里面有成对出现的数，也有单个的数，把单个的数找出来（leetcode原
题）。
4. 一个公司有好多员工，员工之间的关系储存为（employee ID, manager ID) 这样的
pair。要求写一个数据结构，储存这些员工之前的关系。
基于这样的数据结构写出：
1)查找employee的manager.
2)给一个employee和一个manager,查找这个manger是不是这个员工的直接或简介
manager(manager的manager这样的）
3)打印出一个manager手下所有的直接或者间接员工。
4）向这个数组里增加新的(employee, manager)关系。
并给出复杂度分析。
最后推荐一个算法群229623621,里面牛人很多，群里还自己做了OJ，讨论氛围很活跃。
发一些包子攒人品，期待好消息 |
j**********e
发帖数: 1034 | 2 bless!
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
i*********e
发帖数: 9 | 3 谢谢。现在还在忧伤google summer intern的host match >.<
【在 j**********e 的大作中提到】
: bless!
|
J***e
发帖数: 16 | |
c****f
发帖数: 28 | |
l*****a
发帖数: 14598 | 6 thanks for sharing
群里的OJ上线了？赶紧去看看
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
l******t
发帖数: 37 | |
G*****s
发帖数: 39 | 8 Bless!
求问google第二题O(NlogN)的算法 谢谢 |
l********y
发帖数: 1068 | |
h********5
发帖数: 114 | 10 请教一下google第二题，我的想法是按每个人手里的数字排序，然后再逐步插入，请问
你是怎么做的 |
|
|
R*******d
发帖数: 13640 | |
w****m
发帖数: 146 | |
a********j
发帖数: 708 | |
d******0
发帖数: 191 | 14 bless
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
l*****a
发帖数: 14598 | 15 1) sort
2) 对于最矮的人，你还知道前面比他高的有几个。这样你就知道了他的位置
然后找第二矮的，你还知道前面比他高的有几个。你还知道最矮的人在哪里，就因
该可以确定第2矮的位置
然后类推
【在 G*****s 的大作中提到】
: Bless!
: 求问google第二题O(NlogN)的算法 谢谢
|
i*********e
发帖数: 9 | 16 我也是这么做的
【在 h********5 的大作中提到】
: 请教一下google第二题，我的想法是按每个人手里的数字排序，然后再逐步插入，请问
: 你是怎么做的
|
i*********e
发帖数: 9 | 17 是的
【在 w****m 的大作中提到】
: G的第二题是不是身高不能重复？
|
f*********n
发帖数: 635 | |
l**********a
发帖数: 181 | |
J***o
发帖数: 553 | 20 其实关键在于确定第i个人的位置的时候，因为剩下的都是比他高的，而已经确定位置
的都是比他矮的，只要保证他前面有和原排序前面比他高的人数量相等的空位即可。如
果直接扫空位的话是O(N^2)。快一点的方法是把剩下的空位段保存在interval tree里
，这样每次找第k个空位只要O(logN)，总体的复杂度是O(NlogN)
【在 l*****a 的大作中提到】
: 1) sort
: 2) 对于最矮的人，你还知道前面比他高的有几个。这样你就知道了他的位置
: 然后找第二矮的，你还知道前面比他高的有几个。你还知道最矮的人在哪里，就因
: 该可以确定第2矮的位置
: 然后类推
|
|
|
l*****a
发帖数: 14598 | 21 需要那么复杂吗？
sort完了，一个个插入相应位置不就可以了
【在 J***o 的大作中提到】
: 其实关键在于确定第i个人的位置的时候，因为剩下的都是比他高的，而已经确定位置
: 的都是比他矮的，只要保证他前面有和原排序前面比他高的人数量相等的空位即可。如
: 果直接扫空位的话是O(N^2)。快一点的方法是把剩下的空位段保存在interval tree里
: ，这样每次找第k个空位只要O(logN)，总体的复杂度是O(NlogN)
|
l*********5
发帖数: 12 | |
k********6
发帖数: 33 | 23 按身高排序 NlogN， 然后按身高顺序问数，linear time重现元队列，所以只要NlogN。
解释：
最高的人(P0)站哪里都无所谓，因为他记得数是一定是0.
所以直接问身高第二的人(P1)，如果是0站P0前面，如果是1站P0后面。
再问身高第三的人，。。。。
这题不难，我是不是说太细了， 汗。
【在 h********5 的大作中提到】
: 请教一下google第二题，我的想法是按每个人手里的数字排序，然后再逐步插入，请问
: 你是怎么做的
|
k********6
发帖数: 33 | 24 刚看到lolhaha的方法，从最矮的开始直接定位，更节省space，赞。
NlogN。
【在 k********6 的大作中提到】
: 按身高排序 NlogN， 然后按身高顺序问数，linear time重现元队列，所以只要NlogN。
: 解释：
: 最高的人(P0)站哪里都无所谓，因为他记得数是一定是0.
: 所以直接问身高第二的人(P1)，如果是0站P0前面，如果是1站P0后面。
: 再问身高第三的人，。。。。
: 这题不难，我是不是说太细了， 汗。
|
J***o
发帖数: 553 | 25 就是sort完一个个插入啊。。。问题是你怎么得到"相应位置"，虽然表达起来很直观。
interval tree可以O(logN)。
【在 l*****a 的大作中提到】
: 需要那么复杂吗？
: sort完了，一个个插入相应位置不就可以了
|
i*******r
发帖数: 51 | 26 这是phone interview的题目还是onsite，phone interview一个小时内能把两个题的
code写完吗？
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
p*d
发帖数: 1128 | |
F******g
发帖数: 138 | 28
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
f******n
发帖数: 279 | |
n******c
发帖数: 38 | 30 说一下第一题矩阵的思路，抛砖引玉。
把矩阵的每行看成一个int
每行和其他行与，得到N^2/2个结果
设与的结果为m，则任一m如果有两个以上bit为1，则存在这个矩形。
O(1)时间判断m是否两个以上bit为1
如果m==0，则0个bit为1
如果m只有一个bit为1，则是2的n次幂，满足m&(m-1)==0
所以只要m!=0 && m&(m-1)!=0，m必有两个以上bit为1
所以整体解法复杂度是O(N^2) |
|
|
J***o
发帖数: 553 | 31 这个只有一行大小<=32的时候才能O(N^2)吧。复杂度应该是O(N^2 * N/32)，相当于降
低了常数项，整体复杂度没变。不知道有没有更优的解法。。
【在 n******c 的大作中提到】
: 说一下第一题矩阵的思路，抛砖引玉。
: 把矩阵的每行看成一个int
: 每行和其他行与，得到N^2/2个结果
: 设与的结果为m，则任一m如果有两个以上bit为1，则存在这个矩形。
: O(1)时间判断m是否两个以上bit为1
: 如果m==0，则0个bit为1
: 如果m只有一个bit为1，则是2的n次幂，满足m&(m-1)==0
: 所以只要m!=0 && m&(m-1)!=0，m必有两个以上bit为1
: 所以整体解法复杂度是O(N^2)
|
m*****k
发帖数: 731 | 32 你想说O(N^2 * （N－32）)吧？
【在 J***o 的大作中提到】
: 这个只有一行大小<=32的时候才能O(N^2)吧。复杂度应该是O(N^2 * N/32)，相当于降
: 低了常数项，整体复杂度没变。不知道有没有更优的解法。。
|
m*****k
发帖数: 731 | 33 同求楼主说的leecode上类似解法。
【在 c****f 的大作中提到】
: 求问google第一题解法
|
m*****k
发帖数: 731 | 34 记下每行为1的indexes,
和另一行的indexes
求交，结果集>1即可。还是O(N^3), :(
【在 J***o 的大作中提到】
: 这个只有一行大小<=32的时候才能O(N^2)吧。复杂度应该是O(N^2 * N/32)，相当于降
: 低了常数项，整体复杂度没变。不知道有没有更优的解法。。
|
M********t
发帖数: 5032 | 35 伊昔太仆张景顺
喜气自能成岁丰
酒开新瓮鲊开包
一等孔门为弟子
昨日嘉鱼来访我
后会未期心的的
朝来自觉承恩最
但是人家有遗爱 |
A********a
发帖数: 1846 | |
m****t
发帖数: 2329 | |
h*****k
发帖数: 420 | |
a****q
发帖数: 10636 | |
w*****2
发帖数: 3093 | |
|
|
w***a
发帖数: 341 | |
h**********2
发帖数: 1473 | 42 bless
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
w*****c
发帖数: 7276 | |
P****9
发帖数: 177 | |
s********h
发帖数: 2190 | |
w********s
发帖数: 1570 | 46 第二题不是heap sort么？
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
v******y
发帖数: 4134 | 47 小庭新扫地
手种未全成
一回终宴喜
伸屈须看蠖
包胥心独许
子夜最可怜
来朝大将稀 |
f*******r
发帖数: 976 | |
x**l
发帖数: 2337 | |
h*******l
发帖数: 923 | 50 天街雪似盐
芟庭留野菜
掘壕不到水
豁然逢光晶
但和大小包 |
|
|
d******r
发帖数: 327 | 51 Bless
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
n********r
发帖数: 300 | 52
应该可以重复吧？
貌似不影响
【在 i*********e 的大作中提到】
: 是的
|
n********r
发帖数: 300 | 53 google 第一题，可以是O(n*m)的时间的。 但需要 O(n^2)的空间，（假设n<=m) |
b*f
发帖数: 1436 | 54 bless
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
w****3
发帖数: 110 | 55 求O（n*m）的解法？
【在 n********r 的大作中提到】
: google 第一题，可以是O(n*m)的时间的。 但需要 O(n^2)的空间，（假设n<=m)
|
S********e
发帖数: 74 | 56 请问interval tree 如何使用可以详细说说吗？
谢谢！
【在 J***o 的大作中提到】
: 其实关键在于确定第i个人的位置的时候，因为剩下的都是比他高的，而已经确定位置
: 的都是比他矮的，只要保证他前面有和原排序前面比他高的人数量相等的空位即可。如
: 果直接扫空位的话是O(N^2)。快一点的方法是把剩下的空位段保存在interval tree里
: ，这样每次找第k个空位只要O(logN)，总体的复杂度是O(NlogN)
|
y******k
发帖数: 91 | 57 bless，我也申请了很多intern，都没下文 |
w****e
发帖数: 1322 | |
f*******y
发帖数: 9773 | 59 bless
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
z***d
发帖数: 1051 | |
|
|
n****o
发帖数: 41 | |
d******1
发帖数: 452 | |
s***d
发帖数: 314 | |
l*********u
发帖数: 19053 | 64 bless
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
b***e
发帖数: 1419 | 65 For G1 O(n^2):
map[][] = 0; // map[i][j] records whether line i and line j have two
positions overlapping as 1s
for (i = 0; i < n; i++) {
currentOnes = []; // currentOnes is list of all the 1s that are
discovered so far on column i.
for (j = 0; j < m; j++) {
if (A[i][j] == 1) {
for (k = 0; k < currentOnes.length; k++) {
map[currentOnes[k]][j]++;
if (map[currentOnes[k]][j] > 2) {
return true;
}
currentOnes.push(j);
}
}
}
}
return false;
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
d***y
发帖数: 8107 | |
z******h
发帖数: 22 | 67 这个不是O(n^2) 吧
★ 发自iPhone App: ChineseWeb 7.8
【在 b***e 的大作中提到】
: For G1 O(n^2):
: map[][] = 0; // map[i][j] records whether line i and line j have two
: positions overlapping as 1s
: for (i = 0; i < n; i++) {
: currentOnes = []; // currentOnes is list of all the 1s that are
: discovered so far on column i.
: for (j = 0; j < m; j++) {
: if (A[i][j] == 1) {
: for (k = 0; k < currentOnes.length; k++) {
: map[currentOnes[k]][j]++;
|
F******g
发帖数: 138 | 68 bless
【在 i*********e 的大作中提到】
: Google(summer intern)
: 1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
: ，矩形的4个角都是1.
: leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
: 意。不知道有没有复杂度更少的算法。
: 2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
: 目。之后把队打乱，
: 跟据高度和比自己高的人的数目还原原来的队列。
: 我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
: 算法。
|
b***e
发帖数: 1419 | 69 仔细看。最内层循环amortize O (1) , because every cell in map [][] will be
set at most twice.
【在 z******h 的大作中提到】
: 这个不是O(n^2) 吧
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
