m******s
发帖数: 204 | 1 整个过程很折腾人： 说好的上午11点，结果到11：30am没人打过来，打电话到人力资
源的联系我的人，被告知要面我的烙印还在来办公室的路上，又重约了个1：00pm，打
过来要我用google的共享文档写程序，问题是之前的电子邮件里根本没提要准备电脑，
只好回家，路上烙印有打来电话，问何时能到，因为他2：00pm还要开会。。。
问了两题，答的很糟，将题目列出和大家讨论一下：
1。 给出一个柱状图，求其中最大的长方形面积.
2。 给出一个数组，创建一新数组，删掉原数组的重复的数。（问了能不能用bitmap或
排序，被告知不能用很多额外的内存）
另外，记得有人发过一个博克的连接是专门收集Google面试题的，能否告诉我？现在找
不到了。 |
w******1
发帖数: 520 | |
S******a
发帖数: 862 | 3 第一题用一个stack可以做到O(n)
n是柱子的个数，柱子的高度可以是float，宽度彼此可以不相等。
此题可用来解名题：0/1矩阵中都是1的sub矩阵
idea：
设H[i]为柱i高度。
设X[i]为高度为H[i]包含柱i的最大长方形。
设start[i]为X[i]水平方向的起始，end[i]为结束。
维持一个柱高度H单调递增stack
从左到右，对每个柱i
if (H[i] > top)
push柱i到stack
start[i] = 柱i的left
else if （H[i] < top）
一直pop，直到此H[i] > 新的top，push柱i到stack
start[i] = 最后pop出的柱的left
所有此次pop出的柱j的end[j] = 柱i的left
else if(H[i] == top)
啥也不干
有了所有start[i]和end[i]，就可以得到X[i]，然后得到原题的解。
【在 w******1 的大作中提到】
: mark
|
x******3
发帖数: 245 | 4 merge sort不行吧， 不是in place
【在 w******1 的大作中提到】
: mark
|
v****s
发帖数: 1112 | 5 人家都说了不能sort
【在 w******1 的大作中提到】
: mark
|
w****l
发帖数: 88 | 6 我觉得第二题既然不能sort,也不让用bitmap， 那么简单的方法是将原始数组的数放到
一个set中，然后遍历这个set，就可以自动删除重复元素了....望高手赐教 |
B*****t
发帖数: 335 | 7 for 2, min or max heap might be the answer.
what's the time complexity requirement?
【在 m******s 的大作中提到】
: 整个过程很折腾人： 说好的上午11点，结果到11：30am没人打过来，打电话到人力资
: 源的联系我的人，被告知要面我的烙印还在来办公室的路上，又重约了个1：00pm，打
: 过来要我用google的共享文档写程序，问题是之前的电子邮件里根本没提要准备电脑，
: 只好回家，路上烙印有打来电话，问何时能到，因为他2：00pm还要开会。。。
: 问了两题，答的很糟，将题目列出和大家讨论一下：
: 1。 给出一个柱状图，求其中最大的长方形面积.
: 2。 给出一个数组，创建一新数组，删掉原数组的重复的数。（问了能不能用bitmap或
: 排序，被告知不能用很多额外的内存）
: 另外，记得有人发过一个博克的连接是专门收集Google面试题的，能否告诉我？现在找
: 不到了。
|
r**u
发帖数: 1567 | 8 这个三哥在玩你，1题有半天能code出来就不错了。
【在 m******s 的大作中提到】
: 整个过程很折腾人： 说好的上午11点，结果到11：30am没人打过来，打电话到人力资
: 源的联系我的人，被告知要面我的烙印还在来办公室的路上，又重约了个1：00pm，打
: 过来要我用google的共享文档写程序，问题是之前的电子邮件里根本没提要准备电脑，
: 只好回家，路上烙印有打来电话，问何时能到，因为他2：00pm还要开会。。。
: 问了两题，答的很糟，将题目列出和大家讨论一下：
: 1。 给出一个柱状图，求其中最大的长方形面积.
: 2。 给出一个数组，创建一新数组，删掉原数组的重复的数。（问了能不能用bitmap或
: 排序，被告知不能用很多额外的内存）
: 另外，记得有人发过一个博克的连接是专门收集Google面试题的，能否告诉我？现在找
: 不到了。
|
r****o
发帖数: 1950 | 9 柱子的宽度都是一样的吧，
另外，为啥这题可以用来解找0/1矩阵中的都是1的最大子矩阵这个问题呢？
【在 S******a 的大作中提到】
: 第一题用一个stack可以做到O(n)
: n是柱子的个数，柱子的高度可以是float，宽度彼此可以不相等。
: 此题可用来解名题：0/1矩阵中都是1的sub矩阵
: idea：
: 设H[i]为柱i高度。
: 设X[i]为高度为H[i]包含柱i的最大长方形。
: 设start[i]为X[i]水平方向的起始，end[i]为结束。
: 维持一个柱高度H单调递增stack
: 从左到右，对每个柱i
: if (H[i] > top)
|
u**s
发帖数: 50 | 10 This question is a little bit too hard to program as an interview question.
However, there are quite a few people can code it in 45 mins.
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
【在 r**u 的大作中提到】
: 这个三哥在玩你，1题有半天能code出来就不错了。
|
|
|
z*j
发帖数: 42 | 11 just some naive code:
int left, right;
int rectArea;
for(int i = 0; i < size; i++)
{
//for each Histo[i] as the lowest rect, we find left and right >=
Histo[i]
//check left
for(left = i; left >=0; left--)
{
if(Histo[left] < Histo[i])
break;
}
left++;
//check right
for(right = i; right < size; right++)
{
if(Histo[right] < Histo[i])
break;
}
|
c*******n
发帖数: 112 | 12 the second question can be solved using sort since it is required that no
extra memory can be used |
l****z
发帖数: 9 | |
I**********s
发帖数: 441 | 14 第一题的完整代码如下.
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
Problem H, solution 4. O(n).
版主给个包子吧.
#include
#include
using namespace std;
void getMax(int hist[], stack * s, int right, int & max) {
int i = s->top();
int height = hist[i];
s->pop();
int left = (s->size() > 0) ? s->top() : -1;
int area = height * (right - left);
if (area > max) max = area;
}
void doHist(int hist[], int len) {
stack * s = new stack;
int i, top_v, max = |
b****r
发帖数: 1272 | 15 先做预处理，对每个点算出H[i] 然后把每一行当做底，把这个Histogram当做
subproblem来解行不
行
【在 r****o 的大作中提到】
: 柱子的宽度都是一样的吧，
: 另外，为啥这题可以用来解找0/1矩阵中的都是1的最大子矩阵这个问题呢？
|
r****o
发帖数: 1950 | 16 你是说用DP吗?
【在 b****r 的大作中提到】
: 先做预处理，对每个点算出H[i] 然后把每一行当做底，把这个Histogram当做
: subproblem来解行不
: 行
|
b******n
发帖数: 823 | |
l*********y
发帖数: 142 | 18 有人会第二题吗？
【在 m******s 的大作中提到】
: 整个过程很折腾人： 说好的上午11点，结果到11：30am没人打过来，打电话到人力资
: 源的联系我的人，被告知要面我的烙印还在来办公室的路上，又重约了个1：00pm，打
: 过来要我用google的共享文档写程序，问题是之前的电子邮件里根本没提要准备电脑，
: 只好回家，路上烙印有打来电话，问何时能到，因为他2：00pm还要开会。。。
: 问了两题，答的很糟，将题目列出和大家讨论一下：
: 1。 给出一个柱状图，求其中最大的长方形面积.
: 2。 给出一个数组，创建一新数组，删掉原数组的重复的数。（问了能不能用bitmap或
: 排序，被告知不能用很多额外的内存）
: 另外，记得有人发过一个博克的连接是专门收集Google面试题的，能否告诉我？现在找
: 不到了。
|
g*******y
发帖数: 1930 | 19 45分钟？太多了吧，我觉得10分钟之内比较靠谱。不过我是说算法想到的情况，至于在
没见过答案的情况下
独立想算法要多久的时间，这个就靠灵感+技巧经验了
【在 u**s 的大作中提到】
: This question is a little bit too hard to program as an interview question.
: However, there are quite a few people can code it in 45 mins.
: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
|
m*****g
发帖数: 226 | 20 第二题，不能sort, 不能用内存（包括bitmap)
那就是不能遍历然后预处理
那就(n2)硬来？ |
|
|
l******4
发帖数: 207 | 21 我被问到一个相反的问题, 把直方图想象成一个容器,凹下去的部分(den)可以装水, 问
最大的den 是装多少水.
这个怎么做啊
【在 z*j 的大作中提到】
: just some naive code:
: int left, right;
: int rectArea;
: for(int i = 0; i < size; i++)
: {
: //for each Histo[i] as the lowest rect, we find left and right >=
: Histo[i]
: //check left
: for(left = i; left >=0; left--)
: {
|
x****r
发帖数: 99 | 22 这个code有点问题，如果是5, 5, 5, 10, 5那么会返回30，但是应该是25
应该是getmax里面写错了
【在 I**********s 的大作中提到】
: 第一题的完整代码如下.
: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
: Problem H, solution 4. O(n).
: 版主给个包子吧.
: #include
: #include
: using namespace std;
: void getMax(int hist[], stack * s, int right, int & max) {
: int i = s->top();
: int height = hist[i];
|
b********w
发帖数: 110 | 23 我没有验证，不过当遇到当前的柱，并且不能满足递增条件时候，就pop原来进栈的
柱，这个复杂度还能保证bounded by O(n)么？ |
I**********s
发帖数: 441 | 24 好吧, 试试这个 (可以有元素是0):
#include
#include
using namespace std;
int DEBUG = 0;
void getMax(int hist[], stack * s, int newHeight, int right, int & max,
int & start) {
int height, left = 0, area;
while (s->size() > 0 && hist[s->top()] > newHeight) {
height = hist[s->top()];
s->pop();
left = (s->size() > 0) ? s->top() : start;
while (s->size() > 0 && hist[s->top()] == height) {
s->pop();
left = (s->size() > 0) ? s->top() : start;
}
area = h
【在 x****r 的大作中提到】
: 这个code有点问题，如果是5, 5, 5, 10, 5那么会返回30，但是应该是25
: 应该是getmax里面写错了
|
M******k
发帖数: 51 | 25 难道不是每次计算最大值的时候不是都需要遍历整个stack吗？这样就不是O(n)了。并
且因为要遍历这个stack，用stack就不是很合适了。我什么地方理解的不对？
【在 S******a 的大作中提到】
: 第一题用一个stack可以做到O(n)
: n是柱子的个数，柱子的高度可以是float，宽度彼此可以不相等。
: 此题可用来解名题：0/1矩阵中都是1的sub矩阵
: idea：
: 设H[i]为柱i高度。
: 设X[i]为高度为H[i]包含柱i的最大长方形。
: 设start[i]为X[i]水平方向的起始，end[i]为结束。
: 维持一个柱高度H单调递增stack
: 从左到右，对每个柱i
: if (H[i] > top)
|
