|
g*******y
发帖数: 1930 | 2 这个经典题目看来不少人都知道了，不过你面试的时候怎么present你想到这个方法的
过程？ |
|
l******h
发帖数: 405 | 3 这题我觉得有点像Max SubArray Sum问题，可以用O(n)做出来？ |
|
x****r
发帖数: 99 | 4 谢谢分享
这个题怎么那么常见啊，，看来要准备一下：/， 那天看到一个人总结这类问题的帖子
里面也提到了 |
|
|
j**l
发帖数: 2911 | 6 我觉得，做题最好先不要看别人的解答，最多看一些提示，一定要坚持自己先想，自己
先写写白板代码，实在做不出来才去看答案。这样理解才深入，印象才深刻。
我们都有印象，再tricky的数学题，直接看答案都是很快就能理解的，但这样只是让我
们记住了这个方法，要弄清想到这个方法的过程，不如自己先做一遍。即使自己的方法
不是最优，即使最终没想出来，也是有助更好更深理解思考过程，同时也锻炼自己思考
过程的。
如果自己实地想过做过，即使走了弯路或者用时过多，面试时候也容易简练present解
题思路的。
你新换的头像是你本人么？怎么感觉有赵纯阳的气质？ |
|
j**l
发帖数: 2911 | 7 有些类似，只是Max SubArray Sum有贪心的策略，一路向前走，不断更新舍弃。
这个题目用的是栈，有回溯的意味。不过每个元素最多入栈出栈一次，保证了O(n)的复
杂度。
这道题，其实更象编译原理课程中讲到的左右括号匹配，只是一个右括号，可以cancel
前面若干个左括号。 |
|
A*********r
发帖数: 564 | 8 考古出来的。。
觉得代码有问题，没有考虑到如果所有的元素都入栈了，但是堆栈还不为空的情况。。
需要在ｆｏｒ 循环后再加测试堆栈不为空的情况。。 |
|
|
z****e
发帖数: 2024 | 10 请问哪里有详细的解释？能不能给个link？
还有这个题目的难点在哪里？
我觉得如果总高度和总长度都不是很大，就线性时间O(n)不就完了？ |
|
|
z****e
发帖数: 2024 | 12 最大直方图题，
发现原来题目有限制，每一个小矩形最大高度，可以到1E9.
如果用statck什么的，内存会不够用。
觉得原来的题目，是说矩形高度大到内存放不下。
有没有link？
多谢了。 |
|
j**l
发帖数: 2911 | 13 好几个变体
1. 找最大全1方块，用DP
2. 找最大全1矩形，用直方图下的最大矩形方法
3. 找四条边全1的矩形 |
|
j**l
发帖数: 2911 | 14 结合我自己的经历还有别人的面经，最近MSFT, GOOG, AMZN等大公司的面试题似乎不再
那么难了，也就是基本上是版上反复讨论的经典中等难度题，而那些比较难的题目，比
如直方图下的最大矩形面积，最大全1子矩阵，最长递增子序列的NlgN解法，复制有
random指针的链表，几乎没有被考到。
但是就这样，offer也不容易拿到。因为对这些不难的题目，你要做的快，又要少bug，
还要能考虑到各种情况，代码要写的整洁简明健壮，还有些soft skills的考查。
每个准备面大公司的人，还是要把版上反反复复提到的中等难度以下的题目多做多写代
码多总结，这才能把握住最近时间这个题目本身难度降低的机遇。 |
|
s***i
发帖数: 10182 | 15 【 以下文字转载自 WaterWorld 讨论区 】
发信人: saadi (saadi), 信区: WaterWorld
标 题: 葛军，男，秒杀了52万江苏考生。。来做最后两题吧
发信站: BBS 未名空间站 (Wed Jun 9 04:50:17 2010, 美东)
一、填空题
1、设集合A={-1,1,3}，B={a+2,a2+4},A∩B=，则实数a=______▲________
2、设复数z满足z(2-3i)=6+4i（其中i为虚数单位），则z的模为______▲________
3、盒子中有大小相同的3只小球，1只黑球，若从中随机地摸出两只球，两只球颜色不
同的概率是_▲__
4、某棉纺厂为了了解一批棉花的质量，从中随机抽取了100根棉花纤维的长度（棉花纤
维的长度是棉花质量的重要指标），所得数据都在区间[5,40]中，其频率分布直方图如
图所示，则其抽样的100根中，有_▲___根在棉花纤维的长度小于20mm。
5、设函数f(x)=x(ex+ae-x),x∈R，是偶函数，则实数a=_______▲_________
2010年江苏高考数学试题
6、在平面直角坐标系 |
|
x**y
发帖数: 1086 | 16 一个含1 million 32位整数的文件，统计不同整数出现次数的直方图，以及算法复杂度.
要求：文件内容只能顺序读取，可以自己建临时文件进行读写，同时可打开的文件数无
限制，但是内存中只能保留3000个整数。
想不出来该怎么做，哪位能指点一下，谢谢！ |
|
z*s
发帖数: 209 | 17 这学期终于结束，今天回家。分享一下上个月的Google校园面试题。一共两个面试官，
每人问45分钟。
一、
1、1~1000的数中有一个重复的数，把这个数找出来。
2、找出Binary Search Tree树的Median number。
这两道题的要求都是提出尽量多的算法，并给出复杂度。
3、第2题我说了一个O(log n)的算法，他就让我比较几个时间复杂度：O(n)、O(n^2)、
O(log n)、O(n log n)，问哪个是最快的。是不是任何时候O(log n)都比O(n)的算法好
？他想要的答案大概是："Big O notation discards multiplicative constants on
the running time, and ignores efficiency for low input sizes, it does not
always reveal the fastest algorithm in practice or for practically-sized
data sets." http://en.wikipedia.org/wik... 阅读全帖 |
|
m******0
发帖数: 73 | 18 二、就问了一道题，直方图中找最大矩形。要求也是提出尽量多的算法，并分别给出复
杂度。我当时没有没说出来O(n)的算法，但还是过了。
O(n) 的解法是什么 |
|
n****t
发帖数: 241 | 19 第二题怎么做？
这学期终于结束，今天回家。分享一下上个月的Google校园面试题。一共两个面试官，
每人问45分钟。
一、
1、1~1000的数中有一个重复的数，把这个数找出来。
2、找出Binary Search Tree树的Median number。
这两道题的要求都是提出尽量多的算法，并给出复杂度。
3、第2题我说了一个O(log n)的算法，他就让我比较几个时间复杂度：O(n)、O(n^2)、
O(log n)、O(n log n)，问哪个是最快的。是不是任何时候O(log n)都比O(n)的算法好
？他想要的答案大概是："Big O notation discards multiplicative constants on
the running time, and ignores efficiency for low input sizes, it does not
always reveal the fastest algorithm in practice or for practically-sized
data sets." http://en.wikipedi... 阅读全帖 |
|
b**y
发帖数: 32 | 20 直方图中的最大矩阵指的是什么？有什么好的solution码？ |
|
g*******y
发帖数: 1930 | 21
有非stack的o(n)方法，我以前没看stack的solution时候想到的，不过现在没太多时间
码字。
大概的基本思路就是，考虑这个问题：现在你要做的是，寻找并记录下：对于直方图的
每一个bar，左边第一个比它更高的
bar的位置 ＋ 右边第一个比它更高的bar的位置。 |
|
j*j
发帖数: 5564 | 22 恩，这个跟直方图问题不一样
如果ai是负数，那么它参与构成的容器盛不住液体，这些数一定得过滤掉；所以我们不
妨简单化一下，假定ai都是positive的
可以用两个queue来做，q1, q2
先做1->n的loop, 根据逐次增大的ai 把（i, ai) push 到 q1
再做n->1的loop, 也根据逐次增大的ai 把 (i, ai) push 到 q2
同时从q1和q2 pop Aq11, Aq21，计算构成的rectangle面积，作为初始的最大容积max；
比较Aq11和Aq21的大小，pop小的所对应的queue, 假定pop出Aq12, 计算出Aq12和Aq21
的rectangle面积，跟max比较，大的话就替代max；
这样一直做下去，直到最后q1,q2为空 |
|
e****a
发帖数: 449 | 23 . 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非
湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针
对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司:
Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公司。 有一
点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经验
,
j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统和网络的基本知识, 还有就是
经常在
mitbbs 学习大牛们的帖子. 整理了版上一年内的 和 careercup 上的一些面经, 比较
乱, 大家
可以参考下, 基本上概括了店面的所有题，onsite的大部分题. 非常感谢版上的常驻大
牛小牛们给
我的帮助，现在牛牛们都忙着发财... 阅读全帖 |
|
l******t
发帖数: 2243 | 24 congrats!
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
. 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非
湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针
对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司:
Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公司。 有一
点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经验
,
j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统和网络的基本知识, 还有就是... 阅读全帖 |
|
g***s
发帖数: 3811 | 25 这题跟最大直方图是一个思路。
同理，用类似“发个湾区P公司的第一轮phone interview”第二题的方法也可解。 |
|
b*******8
发帖数: 37364 | 26 有人贴过O(MN)的算法，大意是对每行求直方图的最大面积O(N)，一共M行。 |
|
T*****8
发帖数: 119 | 27 看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
Google
1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
find all the paths inside the cube to the (n, n,...n)
3. Given a matrix with values of 0 and 1, for any point, if there are three
1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
recall exactly anymore). how to do it. Given a very big such matrix... 阅读全帖 |
|
T*****8
发帖数: 119 | 28 看大家都吵得不亦乐乎。作为一个深度潜水员和WSN，我就顶风而上，去年面试NYC
Google
1. 在直方图里面找Biggest Square. 没有准备这个提，答的不好
2. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,....
n) and bottom left point is (0, 0, 0.... 0), given any point in the cube,
find all the paths inside the cube to the (n, n,...n)
3. Given a matrix with values of 0 and 1, for any point, if there are three
1s around it, change its value to 1. Otherwise, mark its value to 0 (cannot
recall exactly anymore). how to do it. Given a very big such matrix... 阅读全帖 |
|
g***s
发帖数: 3811 | 29 没错。 直方图也可以用类似的方法来做，比用栈要清楚一些。
指点一下哪错了，至少我运行了几个例子倒没错/** * c[i] = A[0]*A[1]*..*A[i]
★ Sent from iPhone App: iReader Mitbbs 6.8 - iPhone Lite |
|
x******g
发帖数: 41 | 30 不能诶，不过我想了一下能不能这么解
0 1 0 1 0
0 1 1 1 1
1 1 0 0 1
0 1 0 0 1
1 1 0 0 1
1 1 1 1 1
-》每行统计连续上升的0，跟你刚才说的方法一样的话得到
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 0 0 0
如果是被1包围的，那它周围必定都是0，而且是个矩形
就变成直方图里面找个矩形，而且两侧都是0，比前面那个应该还简单一些
这么解可以么？ |
|
d*******l
发帖数: 338 | 31 又想了想，上面的做法大概还是可以的，和你说的差不多。任何一个被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矩阵，知道它右下角和左上角的位置，只需要判断比它大一圈的
那个矩阵面积... 阅读全帖 |
|
g**e
发帖数: 6127 | 32 这题跟矩阵内找max subarray sum是相同的方法。唯一的区别是你这题是找直方图最大
面积
，max sum是找array内连续subarray最大和，都是O(n)，最后的复杂度都是O(n^3) |
|
x******g
发帖数: 41 | 33 啊，难道我又弄错了？
直方图内切矩形的算法不是O(n)的吗？
那最后的复杂度不该是O(n^2)吗？ |
|
d*******l
发帖数: 338 | 34 你这个是求最大子矩阵的方法，这样确实没错，但0-1矩阵的最大全1矩阵确实是O(n^2)
的，对每一行用一次直方图方法即可，而每行的值可以在一次O(n^2)的预处理中全部得到
共O |
|
d*******d
发帖数: 2050 | 35 他这个直方图内接算法是n方,overall是n^3 |
|
t**r
发帖数: 3428 | 36 没看懂，谁给给个详细的链接或者解释？谢了
什么叫 ’求直方图的内切矩阵” |
|
s******n
发帖数: 226 | 37 你说的对 我以为和直方图面积一样的那种，遇到大的就停了 |
|
k****n
发帖数: 369 | 38 攒rp。兄弟们一起努力，共度时艰。
五轮技术加一个午饭。
第一轮主要问project。还问了怎么改进page rank算法。
这个是老本行，不过都忘差不多了。吭哧半天想起来一些，不是很爽。
最后出了一道简单coding题，就是两个dim都分别有序的
matrix，怎么查找。我先说了binary search，用master theorem估算了一下
发现是大于linear的，就说了正常的算法。然后是实现。
这个发挥一般，open questin让我准备不足。
第二轮两道比较简单的题，一个是识别一个字符串是否是一个合法的utf-8串。
因为合法utf8字符可能是变长字节的，就是1/2/3字节都有可能
先用状态机做了，看是否会跳到合法的结束，还是跳到非法状态。
写完代码经过提示才发现可以直接用一个256大小的数组判断是否合法。
弄完了之后暗骂自己，这么明显的空间换时间都没看出来。发挥太差了
第二题是设计一个数据结构存储soduku，目标是判断没有完全填好的行/列/方块
是否合法。因为有第一题地教训，我直接就往那边想了，说存三份数据，一共
才243个字节，更新的时候更新三份，方便又简洁。估计... 阅读全帖 |
|
|
r*******g
发帖数: 1335 | 40 HI
能不能详细讲讲是题目是什么，这4道没看明白，出了两个dim有序的search那道其他都
不清楚。。。
1，设计一个数据结构存储soduku，what is soduku?
2, google hint words
3, 那道底在x轴上的矩形数组求外轮廓的成题?
4, 直方图盛水最大容量
谢谢了。 |
|
x***i
发帖数: 64 | 41 原来在版里看到过code,现在找不到了。哪位好心可以再贴一下吗？ |
|
f*******t
发帖数: 7549 | 42 int water(int * a, int n) {
stack > mystack;
int water = 0;
for(int i = 0; i
while(!mystack.empty() && mystack.top().second <= a[i]) {
int bottom = mystack.top().second;
mystack.pop();
if( mystack.empty())
break;
int top = mystack.top().second < a[i]? mystack.top().second: a[i];
int length = i - mystack.top().first - 1;
water = water + (top-bottom)* length;
}
mystack.push(make_pair(i, a[i]));
}
retur... 阅读全帖 |
|
|
g**********y
发帖数: 14569 | 44 G的标准解法是：找到最高的bar, 分别算左边和右边，那个解写起来长一点，但是解释
简单，不容易错。
public int hold2(int[] a) {
int h = 0;
int N = a.length;
for (int i=1; i a[h]) h = i;
int total = 0;
int left = a[0];
for (int i=1; i
if (a[i] > left) {
left = a[i];
}
else {
total += left - a[i];
}
}
int right = a[N-1];
for (int i=N-2; i>h; i--) {
... 阅读全帖 |
|
I***A
发帖数: 6 | 45 能不能讲讲具体的题目啊？ 考古了一下，但没有找到具体的描述； 那位大虾给
讲讲，谢谢！ |
|
|
|
|
|
A**u
发帖数: 2458 | 50 大牛 能不能讲解一下
这个算法为啥是对的？ 我看不懂.
假设栈里元素为 AB. (B>A)。
读入C, C < A
那么 AB 都pop出.
难道不存在这样的可能性吗: 将来某个时候，可以以A开头，形式最大的面积? |
|
