作假的同修们一定要低调啊 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Biology - 生物学

作假的同修们一定要低调啊

作假的同修们一定要低调啊# Biology - 生物学

m*s2011-09-13 07:09

1 楼

整个过程很折腾人：说好的上午11点，结果到11：30am没人打过来，打电话到人力资
源的联系我的人，被告知要面我的烙印还在来办公室的路上，又重约了个1：00pm，打
过来要我用google的共享文档写程序，问题是之前的电子邮件里根本没提要准备电脑，
只好回家，路上烙印有打来电话，问何时能到，因为他2：00pm还要开会。。。
问了两题，答的很糟，将题目列出和大家讨论一下：
1。给出一个柱状图，求其中最大的长方形面积.
2。给出一个数组，创建一新数组，删掉原数组的重复的数。（问了能不能用bitmap或
排序，被告知不能用很多额外的内存）
另外，记得有人发过一个博克的连接是专门收集Google面试题的，能否告诉我？现在找
不到了。

a*e2011-09-13 07:09

2 楼

第一次给妈妈办B2探亲来美国，是应该去北京？上海还是广州签？
谢谢大家。

f*g2011-09-13 07:09

3 楼

都没人给俺打分呐

t*d2011-09-13 07:09

4 楼

这期的 The Economist：
Even with all these alleged errors, the controversy might have been
relegated to an arcane debate in the scientific literature if the team at
Duke had not chosen, within a few months of the papers’ publication (and at
the time questions were being raised about the data’s quality) to launch
three clinical trials based on their work.
http://www.economist.com/node/21528593

w*12011-09-13 07:09

5 楼

mark

s*y2011-09-13 07:09

6 楼

同问。好像这几年变来变去的。
也不是很清楚了。
刚才给他们打电话，好像周末没人接的样子。
1. 现在还能跨区签证吗？
2. 有些人说可以网上预约面签时间了。如果是这样的话，是不是就不用去中信银行买
电话卡了？

i*e2011-09-13 07:09

7 楼

给我包子，我替你打

S*a2011-09-13 07:09

8 楼

第一题用一个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

i*t2011-09-13 07:09

9 楼

看看大使馆的介绍吧。这至少很多年没有签证的样子了。

【在 s****y 的大作中提到】

: 同问。好像这几年变来变去的。
: 也不是很清楚了。
: 刚才给他们打电话，好像周末没人接的样子。
: 1. 现在还能跨区签证吗？
: 2. 有些人说可以网上预约面签时间了。如果是这样的话，是不是就不用去中信银行买
: 电话卡了？

c*p2011-09-13 07:09

10 楼

排

x*32011-09-13 07:09

11 楼

merge sort不行吧，不是in place

【在 w******1 的大作中提到】

: mark

s*y2011-09-13 07:09

12 楼

是的，很多年没有签证了。
10年是可以跨区的，这个我知道。我看有人说13年不允许跨区了。
14年底，有人发帖子，又说可以跨区，但是不鼓励。
所以我就晕了。
我上大使馆和领事馆的网页都找了，没看到相关信息。
打电话，好像国内也是周末，没人工作。

【在 i******t 的大作中提到】

: 看看大使馆的介绍吧。这至少很多年没有签证的样子了。

G*p2011-09-13 07:09

13 楼

不穿新衣更帅.

v*s2011-09-13 07:09

14 楼

人家都说了不能sort

【在 w******1 的大作中提到】

: mark

k*p2011-09-13 07:09

15 楼

是否可以跨区看签证官当时的心情。有的签证官在中国工作了很多年，不管政策如何变
化，他们的脑袋里面根深蒂固不能跨区。有的签证官觉得跨区无所谓。

【在 s****y 的大作中提到】

: 是的，很多年没有签证了。
: 10年是可以跨区的，这个我知道。我看有人说13年不允许跨区了。
: 14年底，有人发帖子，又说可以跨区，但是不鼓励。
: 所以我就晕了。
: 我上大使馆和领事馆的网页都找了，没看到相关信息。
: 打电话，好像国内也是周末，没人工作。

c*p2011-09-13 07:09

16 楼

穿毛衣羽绒服还咋打球？马马虎虎给你5分

w*l2011-09-13 07:09

17 楼

我觉得第二题既然不能sort,也不让用bitmap，那么简单的方法是将原始数组的数放到
一个set中，然后遍历这个set，就可以自动删除重复元素了....望高手赐教

w*e2011-09-13 07:09

18 楼

一般是去广州签的,而且广州还离湖南比较近!

【在 a********e 的大作中提到】

: 第一次给妈妈办B2探亲来美国，是应该去北京？上海还是广州签？
: 谢谢大家。

f*g2011-09-13 07:09

19 楼

才5分？不是寒碜俺么

【在 c***p 的大作中提到】

: 穿毛衣羽绒服还咋打球？马马虎虎给你5分

B*t2011-09-13 07:09

20 楼

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面试题的，能否告诉我？现在找
: 不到了。

t*g2011-09-13 07:09

21 楼

够帅，给你10分

r*u2011-09-13 07:09

22 楼

这个三哥在玩你，1题有半天能code出来就不错了。

【在 m******s 的大作中提到】

c*p2011-09-13 07:09

23 楼

你太善良了！！

【在 t**********g 的大作中提到】

: 够帅，给你10分

r*o2011-09-13 07:09

24 楼

柱子的宽度都是一样的吧，
另外，为啥这题可以用来解找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)

g*o2011-09-13 07:09

25 楼

帮你凑个整吧，也打个5分

【在 c***p 的大作中提到】

: 穿毛衣羽绒服还咋打球？马马虎虎给你5分

u*s2011-09-13 07:09

26 楼

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出来就不错了。

c*p2011-09-13 07:09

27 楼

好人真多啊！

【在 g*********o 的大作中提到】

: 帮你凑个整吧，也打个5分

z*j2011-09-13 07:09

28 楼

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;
}

t*g2011-09-13 07:09

29 楼

呵呵，除了穿内衣的，一般我都给打10分。

【在 c***p 的大作中提到】

: 你太善良了！！

c*n2011-09-13 07:09

30 楼

the second question can be solved using sort since it is required that no
extra memory can be used

y*82011-09-13 07:09

31 楼

不对吧，早打过10分了。
听说打分有包子？

【在 f******g 的大作中提到】

: 都没人给俺打分呐

l*z2011-09-13 07:09

32 楼

Mark

i*e2011-09-13 07:09

33 楼

你们不识货了吧？那是电蚊拍

I*s2011-09-13 07:09

34 楼

第一题的完整代码如下.
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 =

m*02011-09-13 07:09

35 楼

打了10分.

b*r2011-09-13 07:09

36 楼

先做预处理，对每个点算出H[i] 然后把每一行当做底，把这个Histogram当做
subproblem来解行不
行

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

: 柱子的宽度都是一样的吧，
: 另外，为啥这题可以用来解找0/1矩阵中的都是1的最大子矩阵这个问题呢？

c*p2011-09-13 07:09

37 楼

大冬天的拿电蚊拍，你是在侮辱龙大的智商么？
自罚5个包子
排！

【在 i*******e 的大作中提到】

: 你们不识货了吧？那是电蚊拍

r*o2011-09-13 07:09

38 楼

你是说用DP吗?

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

: 先做预处理，对每个点算出H[i] 然后把每一行当做底，把这个Histogram当做
: subproblem来解行不
: 行

f*g2011-09-13 07:09

39 楼

谢谢打分。
谁给俺打了1分，气愤。。。

【在 m******0 的大作中提到】

: 打了10分.

b*n2011-09-13 07:09

40 楼

http://www.mitbbs.com/article0/JobHunting/31569935_0.html

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

: 你是说用DP吗?

T*42011-09-13 07:09

41 楼

把你的61见鬼数变成了62，你该高兴才是

【在 f******g 的大作中提到】

: 谢谢打分。
: 谁给俺打了1分，气愤。。。

l*y2011-09-13 07:09

42 楼

有人会第二题吗？

【在 m******s 的大作中提到】

l*d2011-09-13 07:09

43 楼

我来给凑个整，看我是好人吧！

【在 T*******4 的大作中提到】

: 把你的61见鬼数变成了62，你该高兴才是

g*y2011-09-13 07:09

44 楼

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

f*g2011-09-13 07:09

45 楼

今天落枕，在家歇着，
我们去打牌吧

【在 l*********d 的大作中提到】

: 我来给凑个整，看我是好人吧！

m*g2011-09-13 07:09

46 楼

第二题，不能sort, 不能用内存（包括bitmap)
那就是不能遍历然后预处理
那就(n2)硬来？

T*42011-09-13 07:09

47 楼

又要被追着打了，阔年

【在 f******g 的大作中提到】

: 今天落枕，在家歇着，
: 我们去打牌吧

l*42011-09-13 07:09

48 楼

我被问到一个相反的问题, 把直方图想象成一个容器,凹下去的部分(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--)
: {

l*d2011-09-13 07:09

49 楼

真幸福，自家开的公司？
想歇着就歇着？

【在 f******g 的大作中提到】

: 今天落枕，在家歇着，
: 我们去打牌吧

x*r2011-09-13 07:09

50 楼

这个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];

j*i2011-09-13 07:09

51 楼

帅。狠招女生喜欢

b*w2011-09-13 07:09

52 楼

我没有验证，不过当遇到当前的柱，并且不能满足递增条件时候，就pop原来进栈的
柱，这个复杂度还能保证bounded by O(n)么？

l*d2011-09-13 07:09

53 楼

拿个榔头把你捶扁，叫我去打牌，邀请你又不理我，耍我玩呢？

【在 f******g 的大作中提到】

: 今天落枕，在家歇着，
: 我们去打牌吧

I*s2011-09-13 07:09

54 楼

好吧, 试试这个 (可以有元素是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里面写错了

T*42011-09-13 07:09

55 楼

帅哥怎么把坑王也吸引来了？

【在 j****i 的大作中提到】

: 帅。狠招女生喜欢

M*k2011-09-13 07:09

56 楼

难道不是每次计算最大值的时候不是都需要遍历整个stack吗？这样就不是O(n)了。并
且因为要遍历这个stack，用stack就不是很合适了。我什么地方理解的不对？

【在 S******a 的大作中提到】

T*42011-09-13 07:09

57 楼

帅哥正抱大腿抱得欢..............

【在 l*********d 的大作中提到】

: 拿个榔头把你捶扁，叫我去打牌，邀请你又不理我，耍我玩呢？

l*d2011-09-13 07:09

58 楼

你肯定不是腰？

【在 T*******4 的大作中提到】

: 帅哥正抱大腿抱得欢..............

M*t2011-09-13 07:09

59 楼

誰把這分兒給湊整了？! 氣憤!

【在 l*********d 的大作中提到】

: 你肯定不是腰？

l*d2011-09-13 07:09

60 楼

我，赶快一头钻进大粪里！

【在 M*****t 的大作中提到】

: 誰把這分兒給湊整了？! 氣憤!

w*e2011-09-13 07:09

61 楼

if you change your name as "衣悦龙", eveyone will notice your new outwear.:)

【在 f******g 的大作中提到】

: 都没人给俺打分呐

m*62011-09-13 07:09

62 楼

刚给你补了2分，凑了个整十。。

a*12011-09-13 07:09

63 楼

+10
100了

【在 f******g 的大作中提到】

: 都没人给俺打分呐

L*12011-09-13 07:09

64 楼

我给你打了9分那，记得给我发包子

y*82011-09-13 07:09

65 楼

打十分也没有包子的，呵呵。

【在 L***1 的大作中提到】

: 我给你打了9分那，记得给我发包子

n*h2011-09-13 07:09

66 楼

打分了