google面试题回馈 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>BrainTeaser - 大脑工作室

google面试题回馈

google面试题回馈# BrainTeaser - 大脑工作室

B*r2007-05-06 07:05

1 楼

zz
这是我遇到的google面试题目,希望后来者好运.
1.求直方图的最大内接矩形,假设每个细条的宽度为1.这个题很hot,两个人来问.我没想
出什么好的算法.
2.NxN行列有序的矩阵查找一个数.以前有人遇到过.O(N)的时间复杂度
3.给定一篇文章,求包含所有单词的最短摘要.O(N)的时间复杂度
4.将MxN的矩阵转秩,要求O(1)的空间复杂度.参考群论中cyclic group,group
generator
5.开放式问题,怎么避免重复抓取网页
6.开放式问题,有些网站每天只允许有限次访问,怎么抓取网页使得索引尽量全面和新鲜
7.写一个singleton pattern的例子
8.vector vs. arraylist, growth strategy & complexity
9.在C++文件中只declare class A, 但不以任何方式define class A, 是做什么用
10.virtual function
11.讨论html vs. xhtml vs. xml
12.描述在浏览器中敲入一个网址后所发生的事情.dns,cache等

v*s2007-05-06 07:05

2 楼

1。求直方图的最大内接矩形,假设每个细条的宽度为1
写了个算法，不知道对不对：
假设直方图为数组A=(a1,a2,。。。,an),ai代表第i个column的高度
################算法基于以下两个推论###################
#1最大的内接矩形，一定和直方图某一个column的上沿重合#
#2根据木桶原理，内接矩形的高度等于其包括的column中最低的#
MaxRectIndx = 0;
MaxRectArea = 0;
for i = 1:length(A)

。IndxLeft = i;
。IndxRight = i;
。while IndxLeft >= 1
。。if A(IndxLeft)>=A(i)
。。。IndxLeft = IndxLeft-1;
。。else
。。。break;
。。end
。end
。while IndxRight <= length(A)
。。if A(IndxRight)>=A(i)
。。。IndxRight = IndxRight+1;
。。else
。。。break;
。。end
。end

。temp

【在 B*********r 的大作中提到】

: zz
: 这是我遇到的google面试题目,希望后来者好运.
: 1.求直方图的最大内接矩形,假设每个细条的宽度为1.这个题很hot,两个人来问.我没想
: 出什么好的算法.
: 2.NxN行列有序的矩阵查找一个数.以前有人遇到过.O(N)的时间复杂度
: 3.给定一篇文章,求包含所有单词的最短摘要.O(N)的时间复杂度
: 4.将MxN的矩阵转秩,要求O(1)的空间复杂度.参考群论中cyclic group,group
: generator
: 5.开放式问题,怎么避免重复抓取网页
: 6.开放式问题,有些网站每天只允许有限次访问,怎么抓取网页使得索引尽量全面和新鲜