B*********r
发帖数: 267 | 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******s
发帖数: 51 | 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.开放式问题,有些网站每天只允许有限次访问,怎么抓取网页使得索引尽量全面和新鲜
|
|
