logo
Redian新闻
>未名空间
>Biology - 生物学
>
请问谁有分离小鼠肝cell membrane的protocol吗？
avatar
请问谁有分离小鼠肝cell membrane的protocol吗？# Biology - 生物学
b*n
1 楼
1. You have a class that supports to input sample records and to compute the
average of the samples. The class has two members: total and count. How
would you make the class thread-safe? If 99% of the time average() is called
, how to optimize for that?
2. Talk about your recent interesting project/bug.
3. You have 100 files, each containing 10G sorted integers. How to merge all
integers into one sorted file?
4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
m*o
2 楼
想测growth hormone binding,谢谢！
avatar
g*y
3 楼
赞！Bless.
avatar
m*o
4 楼
再问一声
avatar
h*d
5 楼
祝福
avatar
a*2
6 楼
bless，这个是什么 level的题吗？
8. 遍历 n*second max 复杂度该是多少啊？
12. bitset还是list啊？
谁来讲讲
avatar
g*y
7 楼
13题是数学题，很久不做这种，现场还真不知道能不能不出错搞出来
1/k > p >= 1/(k+1) 时，该发k份邀请。
avatar
b*v
8 楼
第13题我的想法是这样的，不知道对不对
P(exactly one accept) = N*p*(1-p)^{N-1}
logP = logN + log(p/(1-p)) + Nlog(1-p)
d(logP)/dN = 0 ==> N = 1/log(1/(1-p))

【在 g**********y 的大作中提到】
: 13题是数学题，很久不做这种，现场还真不知道能不能不出错搞出来
: 1/k > p >= 1/(k+1) 时，该发k份邀请。
avatar
g*y
9 楼
前面的推导对，后面我不sure：你怎么证明最大值一定出现在微分为0的地方而且解唯一？我的微积分是忘干净了。
我是直接推算的，f(N) = N*p*(1-p)^(N-1)
f(N+1) - f(N) = (1-p)^(N-1) * [(N+1)*p*(1-p) - N*p]
sgn[f(N+1) - f(N)] = sgn[(N+1)*p*(1-p) - N*p]
= sgn[p(1-(N+1)*p] = sgn[1-(N+1)*p]
递归可以证明：
p = 1~1/2, N=1最好
p = 1/2~1/3, N=2最好
p = 1/3~1/4, N=3最好
。。。

【在 b******v 的大作中提到】
: 第13题我的想法是这样的，不知道对不对
: P(exactly one accept) = N*p*(1-p)^{N-1}
: logP = logN + log(p/(1-p)) + Nlog(1-p)
: d(logP)/dN = 0 ==> N = 1/log(1/(1-p))
avatar
m*t
10 楼
两种方法应该都对。
最大值出现在导数为0的地方，很容易证明。
当N < 1/log(1/(1-p)) 时，P的导数大于0，说明P单调递增；
当N > 1/log(1/(1-p)) 时，P的导数小于0，说明P单调递减；
所以N = 1/log(1/(1-p))时，P取最大值。

唯一？我的微积分是忘干净了。

【在 g**********y 的大作中提到】
: 前面的推导对，后面我不sure：你怎么证明最大值一定出现在微分为0的地方而且解唯一？我的微积分是忘干净了。
: 我是直接推算的，f(N) = N*p*(1-p)^(N-1)
: f(N+1) - f(N) = (1-p)^(N-1) * [(N+1)*p*(1-p) - N*p]
: sgn[f(N+1) - f(N)] = sgn[(N+1)*p*(1-p) - N*p]
: = sgn[p(1-(N+1)*p] = sgn[1-(N+1)*p]
: 递归可以证明：
: p = 1~1/2, N=1最好
: p = 1/2~1/3, N=2最好
: p = 1/3~1/4, N=3最好
: 。。。
avatar
g*y
11 楼
第8题，O(n)
public int hold(int[] a) {
Stack stack = new Stack();
int level = 0;
int total = 0;
for (int i=0; iwhile (!stack.isEmpty()) {
Bar prev = stack.peek();
if (prev.height <= a[i]) {
total += (i - prev.x - 1) * (prev.height - level);
level = prev.height;
stack.pop();
}
else {
break;
}
}

if (stack.isEmpty()) level = 0;
stack.push(new Bar(i, a[i]));
}
return total;
}

class Bar {
int x;
int height;
public Bar(int x, int height) {
this.x = x;
this.height = height;
}
}
avatar
b*n
12 楼
13 题数学题
不要用连续函数思考， 要用离散
用log那种做法不是非常严谨
加入N是最大可能性， 那么 f(N+1)
avatar
b*n
13 楼
不清楚啊， 应该就是一般的developer吧。。。。
不是很senior的职位吧
LD面试回来直说， google还是不错的， 问得问题还是很有水平的。。。。。

【在 a**********2 的大作中提到】
: bless，这个是什么 level的题吗？
: 8. 遍历 n*second max 复杂度该是多少啊？
: 12. bitset还是list啊？
: 谁来讲讲
avatar
b*n
14 楼
LD面试回来后， 给偶做， 提示了不能用连续函数来思考， 要用离散， 偶大概前前后
后做了30分钟搞定， 现场LD也没有完全作对。。。。。

【在 g**********y 的大作中提到】
: 13题是数学题，很久不做这种，现场还真不知道能不能不出错搞出来
: 1/k > p >= 1/(k+1) 时，该发k份邀请。
avatar
y*m
15 楼
为啥不是 1/p 的取整?
e.g. p=0.3
0.3*3+0.1=1 应该发4份？

【在 b*****n 的大作中提到】
: 13 题数学题
: 不要用连续函数思考， 要用离散
: 用log那种做法不是非常严谨
: 加入N是最大可能性， 那么 f(N+1)
avatar
b*n
16 楼
是取整 啊。。。。
1/P down to 1/P+1 取整

【在 y***m 的大作中提到】
: 为啥不是 1/p 的取整?
: e.g. p=0.3
: 0.3*3+0.1=1 应该发4份？
avatar
o*y
17 楼
赞很详细的面经！
bless!
avatar
d*d
18 楼
c++ version
int water(int * a, int n){
stack > mystack;
int water = 0;
for(int i = 0; iwhile(!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]));
}
return water;
}

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
l*e
19 楼
记得好像有一道题大致意思是：
给出一个矩阵，每个元素表示那个方格的高度，然后求下雨后能装多少水。
例如：
2,2,2
2,1,2
2,2,2
返回1。
有什么好方法吗？

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
g*y
20 楼
考古一下吧，那是个经典题，用flood fill做的。

【在 l*****e 的大作中提到】
: 记得好像有一道题大致意思是：
: 给出一个矩阵，每个元素表示那个方格的高度，然后求下雨后能装多少水。
: 例如：
: 2,2,2
: 2,1,2
: 2,2,2
: 返回1。
: 有什么好方法吗？
avatar
X*i
21 楼
Bless.
avatar
c*r
22 楼
程序我看懂了，可是题我没有读懂
能用白话文给我讲一遍，这题什么意思吗？

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
h*m
23 楼
bless.

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
P*c
24 楼
Lots of multi-threading.

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
n*y
25 楼
13: Negative Binomial Distribution! Google it.
avatar
a*u
26 楼
不确定自己是否理解题意。对这个程序有点疑问，如果给的数组中第一个数是最大的，
那么程序的返回值total是0？

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
P*c
27 楼
ms有问题，每次for结尾都push进stack，而且prev.x是在pop之前用， total+的似乎永远
是0。

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
b*y
28 楼
big bless
avatar
P*c
29 楼
这个应该是对的。

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
P*c
30 楼
1，5，7，9，10，12没人讨论吗？感觉是复习multithread的好题目。

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
z*1
31 楼
Bless !!

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
g*i
32 楼
同求多线程题目的思路

【在 P**********c 的大作中提到】
: 1，5，7，9，10，12没人讨论吗？感觉是复习multithread的好题目。
:
: the
: called
: all
: 890
avatar
g*i
33 楼
是不是应该加个判断保证top>bottom?

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
g*y
34 楼
我写的那个有错，dinohound那个是对的，而且简洁。

【在 a***u 的大作中提到】
: 不确定自己是否理解题意。对这个程序有点疑问，如果给的数组中第一个数是最大的，
: 那么程序的返回值total是0？
avatar
v*y
35 楼

It should be one invitation. the probability is: p
if you sent two invitation, the probability will be: p(1-p) < p

【在 g**********y 的大作中提到】
: 13题是数学题，很久不做这种，现场还真不知道能不能不出错搞出来
: 1/k > p >= 1/(k+1) 时，该发k份邀请。
avatar
L*s
36 楼
难度比我那时候容易多了..
avatar
t*x
37 楼
I don't think the code works. Suppose input is {9, 8, 7, 6} (descending
order), then the code only pushes the numbers into stack then return. The
water is 0.

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
d*d
38 楼
这个就该是0阿.谁都沿着斜坡流走了,呆不住.

【在 t****x 的大作中提到】
: I don't think the code works. Suppose input is {9, 8, 7, 6} (descending
: order), then the code only pushes the numbers into stack then return. The
: water is 0.
avatar
P*c
39 楼
top==bottom的时候total+0, 所以不判断也可以。不会有top
【在 g*****i 的大作中提到】
: 是不是应该加个判断保证top>bottom?
avatar
t*x
40 楼
My bad. I misunderstood the question.

【在 d*******d 的大作中提到】
: 这个就该是0阿.谁都沿着斜坡流走了,呆不住.
avatar
s*e
41 楼
讨论一下#1：
我的思路(Java)一直是用synchronized，so the idea is:
public synchronized void add(int n) {
sum += n;
count++;
}
public synchronized void average() {
return sum/count;
}
曾经有个interviewer问我不用synchronized keyword (no synchronized method or
synchronized block)怎么办？所以想听听别的思路。
avatar
g*s
42 楼
the question assumed 99% cpu are used for average. so adding a field '
average' will improve performance much. After doing that, we dont need
synchronized for average(), but dont forget to add volatile key for the
field.

【在 s*******e 的大作中提到】
: 讨论一下#1：
: 我的思路(Java)一直是用synchronized，so the idea is:
: public synchronized void add(int n) {
: sum += n;
: count++;
: }
: public synchronized void average() {
: return sum/count;
: }
: 曾经有个interviewer问我不用synchronized keyword (no synchronized method or
avatar
s*e
43 楼
#4 我的思路是recursion:
int reverseN = reverse(n, 0);
public static int reverse(int n, int sum) {
if (n == 0) return sum;
sum = sum*10 + n%10;
return reverse(n/10, sum);
}
还有别的什么想法？
avatar
g*s
44 楼
try to avoid tail-recursion.

【在 s*******e 的大作中提到】
: #4 我的思路是recursion:
: int reverseN = reverse(n, 0);
: public static int reverse(int n, int sum) {
: if (n == 0) return sum;
: sum = sum*10 + n%10;
: return reverse(n/10, sum);
: }
: 还有别的什么想法？
avatar
r*n
45 楼
How about using readWriteLock, readLock in average(), writeLock in add()...

【在 s*******e 的大作中提到】
: 讨论一下#1：
: 我的思路(Java)一直是用synchronized，so the idea is:
: public synchronized void add(int n) {
: sum += n;
: count++;
: }
: public synchronized void average() {
: return sum/count;
: }
: 曾经有个interviewer问我不用synchronized keyword (no synchronized method or
avatar
g*y
46 楼
public int reverse(int n) {
return n>=0? reversePositive(n) : -reversePositive(-n);
}

private int reversePositive(int n) {
return Integer.parseInt(new StringBuilder("" + n).reverse().toString());
}

【在 s*******e 的大作中提到】
: #4 我的思路是recursion:
: int reverseN = reverse(n, 0);
: public static int reverse(int n, int sum) {
: if (n == 0) return sum;
: sum = sum*10 + n%10;
: return reverse(n/10, sum);
: }
: 还有别的什么想法？
avatar
a*2
47 楼
int reverseInteger(int val)
{
int result =0 ;
while(val)
{
result *=10;
result += val%10;
val /= 10;
}
return result;
}

【在 s*******e 的大作中提到】
: #4 我的思路是recursion:
: int reverseN = reverse(n, 0);
: public static int reverse(int n, int sum) {
: if (n == 0) return sum;
: sum = sum*10 + n%10;
: return reverse(n/10, sum);
: }
: 还有别的什么想法？
avatar
n*y
48 楼
13: last night I did not have time to go to detail. Here are some quick
thoughts on this problem for after work entertaining.
1-----
This is very close to negative binormial distribution (see http://en.wikipedia.org/wiki/Negative_binomial_distribution). According to wiki, let r be number of failure (use wiki term, which means accept invitation here), then the mode for nbd should be at floor(pr/(1-p)). (p is probability of sucess, same as in wiki)
Now noticing
p(NB(r, p) = k) = p (r-1 failures in k + r-1 trials) * p (failure). After
some index switch, we can see that p(r failure with N = k+r trials) reach
maximum at N = floor(r/1-p).
Now, we are assuming accept is failure, using the p as same meaning in prob
13 and r=1, we can see that the probabilty reaches the maximum at floor(1/P)
, here P is the probability mentioned in 13.
2----
berktov mentioned that the N should be a number neighboring -1/ln(1-p). This
answer is also correct. It is not hard to see:
0 < (1/p) + 1/ln(1-p) < 1.
3----
LZ mentioned solving f(N+1)But I am not impressed....
avatar
s*e
49 楼
can you elaborate with some (pseudo-)code?

【在 r*******n 的大作中提到】
: How about using readWriteLock, readLock in average(), writeLock in add()...
avatar
s*e
50 楼
you are right. I didn't try to address the optimization part.
is there a general approach in place of synchronized method or block?

【在 g***s 的大作中提到】
: the question assumed 99% cpu are used for average. so adding a field '
: average' will improve performance much. After doing that, we dont need
: synchronized for average(), but dont forget to add volatile key for the
: field.
avatar
g*s
51 楼
因为只有<1%的时间在add上面，所以用synchronized/lock/cas差别不大,用
synchronized反而简单易懂。

【在 s*******e 的大作中提到】
: you are right. I didn't try to address the optimization part.
: is there a general approach in place of synchronized method or block?
avatar
s*e
52 楼
this is what i'm looking for.

【在 a**********2 的大作中提到】
: int reverseInteger(int val)
: {
: int result =0 ;
: while(val)
: {
: result *=10;
: result += val%10;
: val /= 10;
: }
: return result;
avatar
C*U
53 楼
要学多久才能回答上这些问题啊
刚准备开始学cs

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
b*1
54 楼
第八题怎么是５？
从３到１０　(０　ｂａｓｅｄ).
我用的是O(N3), 慢但应该正确呀...
import java.util.*;
public class Water {
int test(int arr[]) {
int N = arr.length;
int max = 0;
for (int i = 0; i < N - 2; i++) {
for (int j = i + 2; j < N; j++) {
int min = Math.min(arr[i], arr[j]);
int sum =0;
for (int k = i + 1; k < j; k++) {
int v = min - arr[k];
if (v > 0) {
sum += v;
}
}
if (sum > max) {
max = sum;
System.out.println(i + " -> " + j);
}
}
}
return max;
}

public static void main(String args[]) {
System.out.println(new Water().test(new int[]{0,1,0,2,1,0,1,3,2,1,2,
1}));
}
}
avatar
h*i
55 楼
tail-recursion是好事吧，编译器可以优化。

【在 g***s 的大作中提到】
: try to avoid tail-recursion.
avatar
g*s
56 楼
编译器可以优化是指它不好，在编译的时候来避免掉。不是所有编译器都能做这个优化
的。

【在 h***i 的大作中提到】
: tail-recursion是好事吧，编译器可以优化。
avatar
P*c
57 楼
第9题是放一个timer再放一个static的counter吗？
第12题的意思是说这个class是个integer, 可以无穷大，还是说这个class有无穷多个
integer?
add (int) 是说加进一个integer到这个set, 还是这个integer和BigInt相加？

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
b*n
58 楼
LD看大家讨论这么激烈， 让我在第一楼加上了自战解说。。。。
让讨论来的更加激烈吧。。。。。。
avatar
P*c
59 楼
第12题vector能存多少数是有上限的吧，毕竟它的size()返回值其实是
unsigned int. 存成vector的好处是什么呢？

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
c*t
60 楼
I feel that it is just an easy application of expectation.

prob
P)

【在 n***y 的大作中提到】
: 13: last night I did not have time to go to detail. Here are some quick
: thoughts on this problem for after work entertaining.
: 1-----
: This is very close to negative binormial distribution (see http://en.wikipedia.org/wiki/Negative_binomial_distribution). According to wiki, let r be number of failure (use wiki term, which means accept invitation here), then the mode for nbd should be at floor(pr/(1-p)). (p is probability of sucess, same as in wiki)
: Now noticing
: p(NB(r, p) = k) = p (r-1 failures in k + r-1 trials) * p (failure). After
: some index switch, we can see that p(r failure with N = k+r trials) reach
: maximum at N = floor(r/1-p).
: Now, we are assuming accept is failure, using the p as same meaning in prob
: 13 and r=1, we can see that the probabilty reaches the maximum at floor(1/P)
avatar
s*y
61 楼
为什么不用linklist的?

【在 P**********c 的大作中提到】
: 第12题vector能存多少数是有上限的吧，毕竟它的size()返回值其实是
: unsigned int. 存成vector的好处是什么呢？
:
: the
: called
: all
: 890
avatar
P*c
62 楼
linked list idea不错。怎么实现add(int)呢。要先把int转换成linked list, 然后
recursive的进位吗？

【在 s*****y 的大作中提到】
: 为什么不用linklist的?
avatar
P*c
63 楼
第9题用queue存time stamp, multithreading的情况下是每次update queue的时候都
lock吗？

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
k*n
64 楼
第四题不考虑负数？
avatar
P*c
65 楼
考虑吧，例子里就有-890 -98，这个记录一个flag就可以了，不难实现。

【在 k*******n 的大作中提到】
: 第四题不考虑负数？
avatar
h*8
66 楼
mark
avatar
k*n
67 楼
是的，只是这么多天没人提，我也只是提醒下大家表忘了。这题没难度，是不是面试的
题目不仅答对还要最优？？？我一直是那种只要能编译通过从来不考虑complexity的人
...以后得加强这方面训练了。

【在 P**********c 的大作中提到】
: 考虑吧，例子里就有-890 -98，这个记录一个flag就可以了，不难实现。
avatar
k*n
68 楼
这个算法是神马意思，谁给解释一下？

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
g*i
69 楼
我觉得应该要lock吧

【在 P**********c 的大作中提到】
: 第9题用queue存time stamp, multithreading的情况下是每次update queue的时候都
: lock吗？
:
: the
: called
: all
: 890
avatar
m*q
70 楼
Good work.
I just coded a version using O(1) extra space, the down side
is it's not as clean (sigh) and I wasn't able to code it bug free
in my first try. The below code works for the specified input.
int water2(int a[], int n)
{
int i=0, prev=INT_MIN, sum=0;
int prev_high, new_high, prev_index;

while (i=prev) {
prev=a[i]; i++;
}
if (i==n)
return 0;

prev_high=prev, prev_index=i-1;

while (iint tmp=0;
while(iint diff = prev_high-a[i];
tmp += diff;
prev=a[i]; i++;
}
if (i==n)
return sum;
while (i=prev) {
if (a[i] < prev_high) {
int diff = prev_high - a[i];
tmp += diff;
}
prev=a[i]; i++;
}
new_high=prev;
if (new_high < prev_high) {
tmp -= (prev_high-new_high) * (i-1-prev_index);
}

prev_high=new_high; prev_index=i-1;
sum += tmp;

}

return sum;
}

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
m*q
71 楼
The code looks pretty neat. Draw the picture on a paper
it should be more clear.

【在 k****n 的大作中提到】
: 这个算法是神马意思，谁给解释一下？
avatar
t*r
72 楼
谢谢LZ分享
慢慢学习
avatar
i*e
73 楼
反例：
[5,4,1,2]
Your code returns -1.

【在 m**q 的大作中提到】
: Good work.
: I just coded a version using O(1) extra space, the down side
: is it's not as clean (sigh) and I wasn't able to code it bug free
: in my first try. The below code works for the specified input.
: int water2(int a[], int n)
: {
: int i=0, prev=INT_MIN, sum=0;
: int prev_high, new_high, prev_index;
:
: while (i=prev) {
avatar
i*e
74 楼
除了以上的反例之外，你的代码还不能处理比较复杂的情况：
例如：
【5 5 1 7 1 1 5 2 7 6】
你忽略了上面 左7 与 右7 在上边能装上 8 的状况。
你的代码返回的是 15，而正确的答案应该是 23.
利用 stack 的思路是 O(n) time 和 O(n) space，O(n) space 的状况就是一个严格递
减的数组。
不知道有没有 O(n) time 和 O(1) space 的解，直觉告诉我没有。
用 stack 的代码如下：
typedef pair PI;
int waterShed(int A[], int n) {
int total = 0;
stack s;
for (int i = 0; i < n; i++) {
int prevHeight = A[i];
while (!s.empty()) {
total += (min(s.top().first, A[i]) - prevHeight) * (i - s.top().second - 1);
prevHeight = s.top().first;
if (s.top().first > A[i]) break;
s.pop();
}
s.push(PI(A[i], i));
}
return total;
}
avatar
i*e
75 楼
Try this input:
[4, 2, 3]

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
g*y
76 楼
我的那个代码有错。LZ给的答案就是O(n)复杂度，O(1)空间的。
public int hold(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; iif (a[i] > left) {
left = a[i];
}
else {
total += left - a[i];
}
}
int right = a[N-1];
for (int i=N-2; i>h; i--) {
if (a[i] > right) {
right = a[i];
}
else {
total += right - a[i];
}
}
return total;
}

【在 i**********e 的大作中提到】
: Try this input:
: [4, 2, 3]
avatar
s*y
77 楼
好牛的方法，简单得来不容易code错。

【在 g**********y 的大作中提到】
: 我的那个代码有错。LZ给的答案就是O(n)复杂度，O(1)空间的。
: public int hold(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];
avatar
m*q
78 楼
嗯，我的代码是错的，把问题考虑的太简单了。

【在 i**********e 的大作中提到】
: 除了以上的反例之外，你的代码还不能处理比较复杂的情况：
: 例如：
: 【5 5 1 7 1 1 5 2 7 6】
: 你忽略了上面 左7 与 右7 在上边能装上 8 的状况。
: 你的代码返回的是 15，而正确的答案应该是 23.
: 利用 stack 的思路是 O(n) time 和 O(n) space，O(n) space 的状况就是一个严格递
: 减的数组。
: 不知道有没有 O(n) time 和 O(1) space 的解，直觉告诉我没有。
: 用 stack 的代码如下：
: typedef pair PI;
avatar
d*n
79 楼
第八题， 贴个时间O(n)，空间O(1)的，试了前面提到的所有test case。貌似全都正确
。整个数组只需扫描一遍。
int floodFill(int B[], int n)
{
int w = 0;
int i = 0, j = n;
int maxL = 0, maxR = 0;
while(i{
while(B[i]<=max(maxL, maxR) && i{
if(B[i]>maxL)
maxL = B[i];
else
w +=maxL - B[i];
i++;
}
if(i==j) break;
maxL = B[i];//found new high
while(B[--j]{
if(B[j]>maxR)
maxR = B[j];
else
w += maxR - B[j];
}
if(i==j) break;
maxR = B[j];//may be higher than maxL
i++;
}
return w;
}
avatar
n*n
80 楼
在想这题的时候 觉得它的思路跟largest rectangle under histogram的stack解法很
像。只是现在是栈顶元素比当前元素小的时候，弹出栈顶元素；之前histogram那题是
栈顶元素比当前元素大的时候，弹出。
原先那道histogram的题参考这个
http://wansishuang.appspot.com/?p=3002

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
s*f
81 楼
//4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -
890
//--> -98.
int ReverseDigits (int n){
int ret = 0;
while (n){
ret = ret * 10 + n % 10;
n /= 10;
}
return ret;
}
avatar
s*f
82 楼
楼主以前做trading systme吗？ 这么多多线程。
avatar
s*f
83 楼
//8. Given a non-negative integer array representing an elevation map
whereas
//the width of each bar is 1, compute how much water it can contain after
//raining. For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6. What is
//the complexity of your solution?
// 1 time scan; O(1) space
int HoldWater(int a[], int len){
int i = 0;
int j = len - 1;
int sum;
int ibig = INT_MIN;
int jbig = INT_MIN;
while (i <= j){
if (ibig < jbig){
if (ibig < a[i]){
ibig = a[i];
}else{
sum += ibig - a[i];
}
++i;
}else{
if (jbig < a[j]){
jbig = a[j];
}else{
sum += jbig - a[j];
}
--j;
}
}
return sum;
}
avatar
m*k
84 楼
can you try [3, 0, 1] ?

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
m*k
85 楼
can you try [ 5, 0, 3, 4]?

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
e*s
86 楼
Bless, MARK下慢慢看
avatar
l*s
87 楼
Google jobs:
http://jobguiding.com/it-jobs/it-companies/google.html

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
e*s
88 楼
不用FLAG，负数求出来的余数也是负数吧

【在 P**********c 的大作中提到】
: 考虑吧，例子里就有-890 -98，这个记录一个flag就可以了，不难实现。
avatar
c*j
89 楼
13. 我从2，3 推到n，maximize: np(1-p)^{n-1}
求导。。。。
对不对？
avatar
d*u
90 楼
能不能用白话文解释一下，多谢。

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
d*u
91 楼
白话文应该是： 下坡时把数进堆栈 （这样堆栈中最上元素是最小的，保存一个下坡序列），上坡时：如果
有底的话（堆栈中至少有两个元素），找出底，flood（累加，顶减底乘长度）。
知道过完为止。

【在 d*******u 的大作中提到】
: 能不能用白话文解释一下，多谢。
avatar
d*u
92 楼
//白话文应该是： 下坡时把数进堆栈 （这样堆栈中最上元素是最小的，保存一个下坡
序列），上坡时：如果
//有底的话（堆栈中至少有两个元素），找出底，flood（累加，顶减底乘长度）。
//知道过完为止。
int water(int * a, int n){
stack > mystack;
int water = 0;
for(int i = 0; iwhile(!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])); //下坡，进堆栈。
//上坡无底的话，是什么都不做的，因为上次进堆栈的元素直接出堆栈了，只是查
了一下底（至少两元素在堆栈）。
}
return water;
』

序列），上坡时：如果

【在 d*******u 的大作中提到】
: 白话文应该是： 下坡时把数进堆栈 （这样堆栈中最上元素是最小的，保存一个下坡序列），上坡时：如果
: 有底的话（堆栈中至少有两个元素），找出底，flood（累加，顶减底乘长度）。
: 知道过完为止。
avatar
d*u
93 楼
有没有人说一说如果是二维数组的， flood fill怎么做呀？

【在 d*******u 的大作中提到】
: //白话文应该是： 下坡时把数进堆栈 （这样堆栈中最上元素是最小的，保存一个下坡
: 序列），上坡时：如果
: //有底的话（堆栈中至少有两个元素），找出底，flood（累加，顶减底乘长度）。
: //知道过完为止。
: 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; //底
avatar
c*8
94 楼
many thanks

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
avatar
b*n
95 楼
1. You have a class that supports to input sample records and to compute the
average of the samples. The class has two members: total and count. How
would you make the class thread-safe? If 99% of the time average() is called
, how to optimize for that?
2. Talk about your recent interesting project/bug.
3. You have 100 files, each containing 10G sorted integers. How to merge all
integers into one sorted file?
4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
--> -98.
5. Discuss design challenges of a distributed web crawler running on
commercial PCs. How to utilize network bandwidth of those PCs efficiently?
6. How to test if an API is thread-safe or not?
7. How to convert a single threaded application to multiple threaded?
8. Given a non-negative integer array representing an elevation map whereas
the width of each bar is 1, compute how much water it can contain after
raining. For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6. What is
the complexity of your solution?
9. You have an API and you want to wrap it up such that it cannot be called
more than N times a second. How to do this in a multiple-threaded
environment?
10. Design a system to provide suggestions to the search box. How would you
update such a system with new search data when it is running?
11. Introduce your research.
12. Design a BigInt class to represent unlimited size of integers. Implement
a member function add(int).
13. You have two movie tickets and want to invite a friend to watch movie
together. You can invite several friends simultaneously. Each one of them
independently has probability p to accept your invitation. How many friends
should you invite to maximize the probability that exactly one friend
accepts your invitation?
谨以此感谢版上提供经验的各位前辈并顺求祝福！
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
自战解说：
1. For the 1st part of the question, I answered that read-write mutex is a possible solution and to design a good solution we'd like to know the usage pattern. Thus the 2nd part of the question and I answered that the member to input sample records can update a new member average, so that average() just needs to read and no lock is needed.
2. ...
3. I proposed two solutions: n-way merge and counting sort. Then I was asked to decide which one is better and I said counting sort, because it is easier to paralellize and uses less memory. Then I was asked to implement it but I ran out of time for the details. As a hindsight, I should make sure of these in implementation: what's the range of possible input? Any known distribution? Will my program be 32-bit or 64-bit? Is the count of some number possible to overflow? Can INT_MIN be counted correctly?
4. I came up with a recursion solution at first and changed it to an iterative version per requested. Hindsight: not all input integer can be reversed correctly and the valid input is not a simple continuous range.
5. I have little knowledge about web crawler so I asked a lot of questions. I suggested to utilize the geography information of target websites to dispatch the work load and to pool connection/job at each PC. This did not seem to be the interviewer's expectation as he told me hints about how to resolve DNS to IP addresses efficiently, how to deal with slow web sites, etc.
6. I told him thread-safety should be part of the API's interface and I cannot tell without source code. I just googled and it seems that there's no solution to this problem?
7. I told him that I would first decide if multi-thread is appropriate for the application. And then discussed the strategy of converting thread-unsafe APIs to services. Lots of detailed discussion on this problem about design choices.
8. My idea is to find the global maximum element in the array first, and then look from beginning to the global maximum, identify a "lake" after each current maximum and accumulate the water volume, and then look from the end to the global maximum in symmetry. Time complexity is O(n). Space complexity is O(1).
9. I started with a naive solution using sleep() and figured out the real requirement at that time. Then I talked about using a semaphore and to set up timer/callback to update semaphore. That's not the best solution either and the interviewer hint me to use a queue to record time stamps of the N most recent calls. I should be able to find this solution without hint.
10. A very complicated problem. We discussed browser-side/server-side work, trie (prefix tree) at letter level or word level, client side pre-fetching, how to store/build server-side data structure using lots of commercial PCs, possible data compression schemes, an estimate about how many PCs will I use according to my design, and more stuff I do not remember. For the question about how to update the system with new search trend data, I suggested to process the data offline using another set of PCs and switch live/offline set periodically. I felt quite satisfied about myself on this question.
11. ...
12. I first said that I can use a string to store each digit of the BigInt and realized that it is a dumb design when he asked me to implement it. Then I changed to use vector and a sign bit to store the BigInt. There were continuous questions on my implementation of BigInt::add(int). I am not very satisfied about my solution to this problem as I did not support adding a negative int in the time given.
13. I told him immediately that the answer is floor(1/p). But then he asked me why? I said that I remember this is binomial distribution and wrote down the formula f=n*p*(1-p)^(n-1). The interviewer still asked why and showed me that df/dn=0 does not result in n=1/p. At that time I was puzzled but still insisted that my memory should be correct. I was not able to get the correct deduction in time. So I emailed HR the solution that night and hope he would forward my solution to the interviewer per my request.
心得：本以为会被问到比较难的算法题，比如DP, string matching, suffix tree, graph algo, operations on binary tree啥的。或者OO概念，design pattern之类的设计问题。不过实战都是非常质朴而实际的问题，并没有单纯为了增加难度而出的题。白板编程一定要好好练习，听到问题后第一件事是澄清问题、确认几个测试用例、设法限制输入(assert)、明确边界条件，同时最快时间考虑出一个基本解决方案，然后再考虑优化。即使运气好碰到做过的题，也务必按照顺序给出分析思考解决优化的全过程。白板编程要注意程序篇幅的控制，根据内容多少选择恰当的字体大小；如有可能，程序中可以使用辅助函数并多半不用实现之；遇到程序分支先实现错误处理、特殊情况等短分支，再实现主体算法分支，以便控制篇幅及避免遗忘。
总体看来，G家面官准备的技术问题都颇靠谱。完全没有behavior question这一点也甚合我意。唯一不爽的是好几个面官都时间耗尽，没有机会问他们问题；倒也有几个面官比较体贴，技术问题前让我先问问题，不过他们似乎对我的问题都无准备，回答并不能使我满意。
avatar
g*y
96 楼
赞！Bless.
avatar
h*d
97 楼
祝福
avatar
a*2
98 楼
bless，这个是什么 level的题吗？
8. 遍历 n*second max 复杂度该是多少啊？
12. bitset还是list啊？
谁来讲讲
avatar
g*y
99 楼
13题是数学题，很久不做这种，现场还真不知道能不能不出错搞出来
1/k > p >= 1/(k+1) 时，该发k份邀请。
avatar
b*v
100 楼
第13题我的想法是这样的，不知道对不对
P(exactly one accept) = N*p*(1-p)^{N-1}
logP = logN + log(p/(1-p)) + Nlog(1-p)
d(logP)/dN = 0 ==> N = 1/log(1/(1-p))

【在 g**********y 的大作中提到】
: 13题是数学题，很久不做这种，现场还真不知道能不能不出错搞出来
: 1/k > p >= 1/(k+1) 时，该发k份邀请。
avatar
g*y
101 楼
前面的推导对，后面我不sure：你怎么证明最大值一定出现在微分为0的地方而且解唯一？我的微积分是忘干净了。
我是直接推算的，f(N) = N*p*(1-p)^(N-1)
f(N+1) - f(N) = (1-p)^(N-1) * [(N+1)*p*(1-p) - N*p]
sgn[f(N+1) - f(N)] = sgn[(N+1)*p*(1-p) - N*p]
= sgn[p(1-(N+1)*p] = sgn[1-(N+1)*p]
递归可以证明：
p = 1~1/2, N=1最好
p = 1/2~1/3, N=2最好
p = 1/3~1/4, N=3最好
。。。

【在 b******v 的大作中提到】
: 第13题我的想法是这样的，不知道对不对
: P(exactly one accept) = N*p*(1-p)^{N-1}
: logP = logN + log(p/(1-p)) + Nlog(1-p)
: d(logP)/dN = 0 ==> N = 1/log(1/(1-p))
avatar
m*t
102 楼
两种方法应该都对。
最大值出现在导数为0的地方，很容易证明。
当N < 1/log(1/(1-p)) 时，P的导数大于0，说明P单调递增；
当N > 1/log(1/(1-p)) 时，P的导数小于0，说明P单调递减；
所以N = 1/log(1/(1-p))时，P取最大值。

唯一？我的微积分是忘干净了。

【在 g**********y 的大作中提到】
: 前面的推导对，后面我不sure：你怎么证明最大值一定出现在微分为0的地方而且解唯一？我的微积分是忘干净了。
: 我是直接推算的，f(N) = N*p*(1-p)^(N-1)
: f(N+1) - f(N) = (1-p)^(N-1) * [(N+1)*p*(1-p) - N*p]
: sgn[f(N+1) - f(N)] = sgn[(N+1)*p*(1-p) - N*p]
: = sgn[p(1-(N+1)*p] = sgn[1-(N+1)*p]
: 递归可以证明：
: p = 1~1/2, N=1最好
: p = 1/2~1/3, N=2最好
: p = 1/3~1/4, N=3最好
: 。。。
avatar
g*y
103 楼
第8题，O(n)
public int hold(int[] a) {
Stack stack = new Stack();
int level = 0;
int total = 0;
for (int i=0; iwhile (!stack.isEmpty()) {
Bar prev = stack.peek();
if (prev.height <= a[i]) {
total += (i - prev.x - 1) * (prev.height - level);
level = prev.height;
stack.pop();
}
else {
break;
}
}

if (stack.isEmpty()) level = 0;
stack.push(new Bar(i, a[i]));
}
return total;
}

class Bar {
int x;
int height;
public Bar(int x, int height) {
this.x = x;
this.height = height;
}
}
avatar
b*n
104 楼
13 题数学题
不要用连续函数思考， 要用离散
用log那种做法不是非常严谨
加入N是最大可能性， 那么 f(N+1)
avatar
b*n
105 楼
不清楚啊， 应该就是一般的developer吧。。。。
不是很senior的职位吧
LD面试回来直说， google还是不错的， 问得问题还是很有水平的。。。。。

【在 a**********2 的大作中提到】
: bless，这个是什么 level的题吗？
: 8. 遍历 n*second max 复杂度该是多少啊？
: 12. bitset还是list啊？
: 谁来讲讲
avatar
b*n
106 楼
LD面试回来后， 给偶做， 提示了不能用连续函数来思考， 要用离散， 偶大概前前后
后做了30分钟搞定， 现场LD也没有完全作对。。。。。

【在 g**********y 的大作中提到】
: 13题是数学题，很久不做这种，现场还真不知道能不能不出错搞出来
: 1/k > p >= 1/(k+1) 时，该发k份邀请。
avatar
y*m
107 楼
为啥不是 1/p 的取整?
e.g. p=0.3
0.3*3+0.1=1 应该发4份？

【在 b*****n 的大作中提到】
: 13 题数学题
: 不要用连续函数思考， 要用离散
: 用log那种做法不是非常严谨
: 加入N是最大可能性， 那么 f(N+1)
avatar
b*n
108 楼
是取整 啊。。。。
1/P down to 1/P+1 取整

【在 y***m 的大作中提到】
: 为啥不是 1/p 的取整?
: e.g. p=0.3
: 0.3*3+0.1=1 应该发4份？
avatar
o*y
109 楼
赞很详细的面经！
bless!
avatar
d*d
110 楼
c++ version
int water(int * a, int n){
stack > mystack;
int water = 0;
for(int i = 0; iwhile(!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]));
}
return water;
}

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
l*e
111 楼
记得好像有一道题大致意思是：
给出一个矩阵，每个元素表示那个方格的高度，然后求下雨后能装多少水。
例如：
2,2,2
2,1,2
2,2,2
返回1。
有什么好方法吗？

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
g*y
112 楼
考古一下吧，那是个经典题，用flood fill做的。

【在 l*****e 的大作中提到】
: 记得好像有一道题大致意思是：
: 给出一个矩阵，每个元素表示那个方格的高度，然后求下雨后能装多少水。
: 例如：
: 2,2,2
: 2,1,2
: 2,2,2
: 返回1。
: 有什么好方法吗？
avatar
X*i
113 楼
Bless.
avatar
c*r
114 楼
程序我看懂了，可是题我没有读懂
能用白话文给我讲一遍，这题什么意思吗？

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
h*m
115 楼
bless.

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
: --> -98.
: 5. Discuss design challenges of a distributed web crawler running on
avatar
P*c
116 楼
Lots of multi-threading.

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
: --> -98.
: 5. Discuss design challenges of a distributed web crawler running on
avatar
n*y
117 楼
13: Negative Binomial Distribution! Google it.
avatar
a*u
118 楼
不确定自己是否理解题意。对这个程序有点疑问，如果给的数组中第一个数是最大的，
那么程序的返回值total是0？

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
P*c
119 楼
ms有问题，每次for结尾都push进stack，而且prev.x是在pop之前用， total+的似乎永远
是0。

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
b*y
120 楼
big bless
avatar
P*c
121 楼
这个应该是对的。

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
P*c
122 楼
1，5，7，9，10，12没人讨论吗？感觉是复习multithread的好题目。

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
: --> -98.
: 5. Discuss design challenges of a distributed web crawler running on
avatar
z*1
123 楼
Bless !!

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
: --> -98.
: 5. Discuss design challenges of a distributed web crawler running on
avatar
g*i
124 楼
同求多线程题目的思路

【在 P**********c 的大作中提到】
: 1，5，7，9，10，12没人讨论吗？感觉是复习multithread的好题目。
:
: the
: called
: all
: 890
avatar
g*i
125 楼
是不是应该加个判断保证top>bottom?

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
g*y
126 楼
我写的那个有错，dinohound那个是对的，而且简洁。

【在 a***u 的大作中提到】
: 不确定自己是否理解题意。对这个程序有点疑问，如果给的数组中第一个数是最大的，
: 那么程序的返回值total是0？
avatar
v*y
127 楼

It should be one invitation. the probability is: p
if you sent two invitation, the probability will be: p(1-p) < p

【在 g**********y 的大作中提到】
: 13题是数学题，很久不做这种，现场还真不知道能不能不出错搞出来
: 1/k > p >= 1/(k+1) 时，该发k份邀请。
avatar
L*s
128 楼
难度比我那时候容易多了..
avatar
t*x
129 楼
I don't think the code works. Suppose input is {9, 8, 7, 6} (descending
order), then the code only pushes the numbers into stack then return. The
water is 0.

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
d*d
130 楼
这个就该是0阿.谁都沿着斜坡流走了,呆不住.

【在 t****x 的大作中提到】
: I don't think the code works. Suppose input is {9, 8, 7, 6} (descending
: order), then the code only pushes the numbers into stack then return. The
: water is 0.
avatar
P*c
131 楼
top==bottom的时候total+0, 所以不判断也可以。不会有top
【在 g*****i 的大作中提到】
: 是不是应该加个判断保证top>bottom?
avatar
t*x
132 楼
My bad. I misunderstood the question.

【在 d*******d 的大作中提到】
: 这个就该是0阿.谁都沿着斜坡流走了,呆不住.
avatar
s*e
133 楼
讨论一下#1：
我的思路(Java)一直是用synchronized，so the idea is:
public synchronized void add(int n) {
sum += n;
count++;
}
public synchronized void average() {
return sum/count;
}
曾经有个interviewer问我不用synchronized keyword (no synchronized method or
synchronized block)怎么办？所以想听听别的思路。
avatar
g*s
134 楼
the question assumed 99% cpu are used for average. so adding a field '
average' will improve performance much. After doing that, we dont need
synchronized for average(), but dont forget to add volatile key for the
field.

【在 s*******e 的大作中提到】
: 讨论一下#1：
: 我的思路(Java)一直是用synchronized，so the idea is:
: public synchronized void add(int n) {
: sum += n;
: count++;
: }
: public synchronized void average() {
: return sum/count;
: }
: 曾经有个interviewer问我不用synchronized keyword (no synchronized method or
avatar
s*e
135 楼
#4 我的思路是recursion:
int reverseN = reverse(n, 0);
public static int reverse(int n, int sum) {
if (n == 0) return sum;
sum = sum*10 + n%10;
return reverse(n/10, sum);
}
还有别的什么想法？
avatar
g*s
136 楼
try to avoid tail-recursion.

【在 s*******e 的大作中提到】
: #4 我的思路是recursion:
: int reverseN = reverse(n, 0);
: public static int reverse(int n, int sum) {
: if (n == 0) return sum;
: sum = sum*10 + n%10;
: return reverse(n/10, sum);
: }
: 还有别的什么想法？
avatar
r*n
137 楼
How about using readWriteLock, readLock in average(), writeLock in add()...

【在 s*******e 的大作中提到】
: 讨论一下#1：
: 我的思路(Java)一直是用synchronized，so the idea is:
: public synchronized void add(int n) {
: sum += n;
: count++;
: }
: public synchronized void average() {
: return sum/count;
: }
: 曾经有个interviewer问我不用synchronized keyword (no synchronized method or
avatar
g*y
138 楼
public int reverse(int n) {
return n>=0? reversePositive(n) : -reversePositive(-n);
}

private int reversePositive(int n) {
return Integer.parseInt(new StringBuilder("" + n).reverse().toString());
}

【在 s*******e 的大作中提到】
: #4 我的思路是recursion:
: int reverseN = reverse(n, 0);
: public static int reverse(int n, int sum) {
: if (n == 0) return sum;
: sum = sum*10 + n%10;
: return reverse(n/10, sum);
: }
: 还有别的什么想法？
avatar
a*2
139 楼
int reverseInteger(int val)
{
int result =0 ;
while(val)
{
result *=10;
result += val%10;
val /= 10;
}
return result;
}

【在 s*******e 的大作中提到】
: #4 我的思路是recursion:
: int reverseN = reverse(n, 0);
: public static int reverse(int n, int sum) {
: if (n == 0) return sum;
: sum = sum*10 + n%10;
: return reverse(n/10, sum);
: }
: 还有别的什么想法？
avatar
n*y
140 楼
13: last night I did not have time to go to detail. Here are some quick
thoughts on this problem for after work entertaining.
1-----
This is very close to negative binormial distribution (see http://en.wikipedia.org/wiki/Negative_binomial_distribution). According to wiki, let r be number of failure (use wiki term, which means accept invitation here), then the mode for nbd should be at floor(pr/(1-p)). (p is probability of sucess, same as in wiki)
Now noticing
p(NB(r, p) = k) = p (r-1 failures in k + r-1 trials) * p (failure). After
some index switch, we can see that p(r failure with N = k+r trials) reach
maximum at N = floor(r/1-p).
Now, we are assuming accept is failure, using the p as same meaning in prob
13 and r=1, we can see that the probabilty reaches the maximum at floor(1/P)
, here P is the probability mentioned in 13.
2----
berktov mentioned that the N should be a number neighboring -1/ln(1-p). This
answer is also correct. It is not hard to see:
0 < (1/p) + 1/ln(1-p) < 1.
3----
LZ mentioned solving f(N+1)But I am not impressed....
avatar
s*e
141 楼
can you elaborate with some (pseudo-)code?

【在 r*******n 的大作中提到】
: How about using readWriteLock, readLock in average(), writeLock in add()...
avatar
s*e
142 楼
you are right. I didn't try to address the optimization part.
is there a general approach in place of synchronized method or block?

【在 g***s 的大作中提到】
: the question assumed 99% cpu are used for average. so adding a field '
: average' will improve performance much. After doing that, we dont need
: synchronized for average(), but dont forget to add volatile key for the
: field.
avatar
g*s
143 楼
因为只有<1%的时间在add上面，所以用synchronized/lock/cas差别不大,用
synchronized反而简单易懂。

【在 s*******e 的大作中提到】
: you are right. I didn't try to address the optimization part.
: is there a general approach in place of synchronized method or block?
avatar
s*e
144 楼
this is what i'm looking for.

【在 a**********2 的大作中提到】
: int reverseInteger(int val)
: {
: int result =0 ;
: while(val)
: {
: result *=10;
: result += val%10;
: val /= 10;
: }
: return result;
avatar
C*U
145 楼
要学多久才能回答上这些问题啊
刚准备开始学cs

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
: --> -98.
: 5. Discuss design challenges of a distributed web crawler running on
avatar
b*1
146 楼
第八题怎么是５？
从３到１０　(０　ｂａｓｅｄ).
我用的是O(N3), 慢但应该正确呀...
import java.util.*;
public class Water {
int test(int arr[]) {
int N = arr.length;
int max = 0;
for (int i = 0; i < N - 2; i++) {
for (int j = i + 2; j < N; j++) {
int min = Math.min(arr[i], arr[j]);
int sum =0;
for (int k = i + 1; k < j; k++) {
int v = min - arr[k];
if (v > 0) {
sum += v;
}
}
if (sum > max) {
max = sum;
System.out.println(i + " -> " + j);
}
}
}
return max;
}

public static void main(String args[]) {
System.out.println(new Water().test(new int[]{0,1,0,2,1,0,1,3,2,1,2,
1}));
}
}
avatar
h*i
147 楼
tail-recursion是好事吧，编译器可以优化。

【在 g***s 的大作中提到】
: try to avoid tail-recursion.
avatar
g*s
148 楼
编译器可以优化是指它不好，在编译的时候来避免掉。不是所有编译器都能做这个优化
的。

【在 h***i 的大作中提到】
: tail-recursion是好事吧，编译器可以优化。
avatar
P*c
149 楼
第9题是放一个timer再放一个static的counter吗？
第12题的意思是说这个class是个integer, 可以无穷大，还是说这个class有无穷多个
integer?
add (int) 是说加进一个integer到这个set, 还是这个integer和BigInt相加？

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
: --> -98.
: 5. Discuss design challenges of a distributed web crawler running on
avatar
b*n
150 楼
LD看大家讨论这么激烈， 让我在第一楼加上了自战解说。。。。
让讨论来的更加激烈吧。。。。。。
avatar
P*c
151 楼
第12题vector能存多少数是有上限的吧，毕竟它的size()返回值其实是
unsigned int. 存成vector的好处是什么呢？

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
: --> -98.
: 5. Discuss design challenges of a distributed web crawler running on
avatar
c*t
152 楼
I feel that it is just an easy application of expectation.

prob
P)

【在 n***y 的大作中提到】
: 13: last night I did not have time to go to detail. Here are some quick
: thoughts on this problem for after work entertaining.
: 1-----
: This is very close to negative binormial distribution (see http://en.wikipedia.org/wiki/Negative_binomial_distribution). According to wiki, let r be number of failure (use wiki term, which means accept invitation here), then the mode for nbd should be at floor(pr/(1-p)). (p is probability of sucess, same as in wiki)
: Now noticing
: p(NB(r, p) = k) = p (r-1 failures in k + r-1 trials) * p (failure). After
: some index switch, we can see that p(r failure with N = k+r trials) reach
: maximum at N = floor(r/1-p).
: Now, we are assuming accept is failure, using the p as same meaning in prob
: 13 and r=1, we can see that the probabilty reaches the maximum at floor(1/P)
avatar
s*y
153 楼
为什么不用linklist的?

【在 P**********c 的大作中提到】
: 第12题vector能存多少数是有上限的吧，毕竟它的size()返回值其实是
: unsigned int. 存成vector的好处是什么呢？
:
: the
: called
: all
: 890
avatar
P*c
154 楼
linked list idea不错。怎么实现add(int)呢。要先把int转换成linked list, 然后
recursive的进位吗？

【在 s*****y 的大作中提到】
: 为什么不用linklist的?
avatar
P*c
155 楼
第9题用queue存time stamp, multithreading的情况下是每次update queue的时候都
lock吗？

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
: --> -98.
: 5. Discuss design challenges of a distributed web crawler running on
avatar
k*n
156 楼
第四题不考虑负数？
avatar
P*c
157 楼
考虑吧，例子里就有-890 -98，这个记录一个flag就可以了，不难实现。

【在 k*******n 的大作中提到】
: 第四题不考虑负数？
avatar
h*8
158 楼
mark
avatar
k*n
159 楼
是的，只是这么多天没人提，我也只是提醒下大家表忘了。这题没难度，是不是面试的
题目不仅答对还要最优？？？我一直是那种只要能编译通过从来不考虑complexity的人
...以后得加强这方面训练了。

【在 P**********c 的大作中提到】
: 考虑吧，例子里就有-890 -98，这个记录一个flag就可以了，不难实现。
avatar
k*n
160 楼
这个算法是神马意思，谁给解释一下？

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
g*i
161 楼
我觉得应该要lock吧

【在 P**********c 的大作中提到】
: 第9题用queue存time stamp, multithreading的情况下是每次update queue的时候都
: lock吗？
:
: the
: called
: all
: 890
avatar
m*q
162 楼
Good work.
I just coded a version using O(1) extra space, the down side
is it's not as clean (sigh) and I wasn't able to code it bug free
in my first try. The below code works for the specified input.
int water2(int a[], int n)
{
int i=0, prev=INT_MIN, sum=0;
int prev_high, new_high, prev_index;

while (i=prev) {
prev=a[i]; i++;
}
if (i==n)
return 0;

prev_high=prev, prev_index=i-1;

while (iint tmp=0;
while(iint diff = prev_high-a[i];
tmp += diff;
prev=a[i]; i++;
}
if (i==n)
return sum;
while (i=prev) {
if (a[i] < prev_high) {
int diff = prev_high - a[i];
tmp += diff;
}
prev=a[i]; i++;
}
new_high=prev;
if (new_high < prev_high) {
tmp -= (prev_high-new_high) * (i-1-prev_index);
}

prev_high=new_high; prev_index=i-1;
sum += tmp;

}

return sum;
}

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
m*q
163 楼
The code looks pretty neat. Draw the picture on a paper
it should be more clear.

【在 k****n 的大作中提到】
: 这个算法是神马意思，谁给解释一下？
avatar
t*r
164 楼
谢谢LZ分享
慢慢学习
avatar
i*e
165 楼
反例：
[5,4,1,2]
Your code returns -1.

【在 m**q 的大作中提到】
: Good work.
: I just coded a version using O(1) extra space, the down side
: is it's not as clean (sigh) and I wasn't able to code it bug free
: in my first try. The below code works for the specified input.
: int water2(int a[], int n)
: {
: int i=0, prev=INT_MIN, sum=0;
: int prev_high, new_high, prev_index;
:
: while (i=prev) {
avatar
i*e
166 楼
除了以上的反例之外，你的代码还不能处理比较复杂的情况：
例如：
【5 5 1 7 1 1 5 2 7 6】
你忽略了上面 左7 与 右7 在上边能装上 8 的状况。
你的代码返回的是 15，而正确的答案应该是 23.
利用 stack 的思路是 O(n) time 和 O(n) space，O(n) space 的状况就是一个严格递
减的数组。
不知道有没有 O(n) time 和 O(1) space 的解，直觉告诉我没有。
用 stack 的代码如下：
typedef pair PI;
int waterShed(int A[], int n) {
int total = 0;
stack s;
for (int i = 0; i < n; i++) {
int prevHeight = A[i];
while (!s.empty()) {
total += (min(s.top().first, A[i]) - prevHeight) * (i - s.top().second - 1);
prevHeight = s.top().first;
if (s.top().first > A[i]) break;
s.pop();
}
s.push(PI(A[i], i));
}
return total;
}
avatar
i*e
167 楼
Try this input:
[4, 2, 3]

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
g*y
168 楼
我的那个代码有错。LZ给的答案就是O(n)复杂度，O(1)空间的。
public int hold(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; iif (a[i] > left) {
left = a[i];
}
else {
total += left - a[i];
}
}
int right = a[N-1];
for (int i=N-2; i>h; i--) {
if (a[i] > right) {
right = a[i];
}
else {
total += right - a[i];
}
}
return total;
}

【在 i**********e 的大作中提到】
: Try this input:
: [4, 2, 3]
avatar
s*y
169 楼
好牛的方法，简单得来不容易code错。

【在 g**********y 的大作中提到】
: 我的那个代码有错。LZ给的答案就是O(n)复杂度，O(1)空间的。
: public int hold(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];
avatar
m*q
170 楼
嗯，我的代码是错的，把问题考虑的太简单了。

【在 i**********e 的大作中提到】
: 除了以上的反例之外，你的代码还不能处理比较复杂的情况：
: 例如：
: 【5 5 1 7 1 1 5 2 7 6】
: 你忽略了上面 左7 与 右7 在上边能装上 8 的状况。
: 你的代码返回的是 15，而正确的答案应该是 23.
: 利用 stack 的思路是 O(n) time 和 O(n) space，O(n) space 的状况就是一个严格递
: 减的数组。
: 不知道有没有 O(n) time 和 O(1) space 的解，直觉告诉我没有。
: 用 stack 的代码如下：
: typedef pair PI;
avatar
d*n
171 楼
第八题， 贴个时间O(n)，空间O(1)的，试了前面提到的所有test case。貌似全都正确
。整个数组只需扫描一遍。
int floodFill(int B[], int n)
{
int w = 0;
int i = 0, j = n;
int maxL = 0, maxR = 0;
while(i{
while(B[i]<=max(maxL, maxR) && i{
if(B[i]>maxL)
maxL = B[i];
else
w +=maxL - B[i];
i++;
}
if(i==j) break;
maxL = B[i];//found new high
while(B[--j]{
if(B[j]>maxR)
maxR = B[j];
else
w += maxR - B[j];
}
if(i==j) break;
maxR = B[j];//may be higher than maxL
i++;
}
return w;
}
avatar
n*n
172 楼
在想这题的时候 觉得它的思路跟largest rectangle under histogram的stack解法很
像。只是现在是栈顶元素比当前元素小的时候，弹出栈顶元素；之前histogram那题是
栈顶元素比当前元素大的时候，弹出。
原先那道histogram的题参考这个
http://wansishuang.appspot.com/?p=3002

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
s*f
173 楼
//4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -
890
//--> -98.
int ReverseDigits (int n){
int ret = 0;
while (n){
ret = ret * 10 + n % 10;
n /= 10;
}
return ret;
}
avatar
s*f
174 楼
楼主以前做trading systme吗？ 这么多多线程。
avatar
s*f
175 楼
//8. Given a non-negative integer array representing an elevation map
whereas
//the width of each bar is 1, compute how much water it can contain after
//raining. For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6. What is
//the complexity of your solution?
// 1 time scan; O(1) space
int HoldWater(int a[], int len){
int i = 0;
int j = len - 1;
int sum;
int ibig = INT_MIN;
int jbig = INT_MIN;
while (i <= j){
if (ibig < jbig){
if (ibig < a[i]){
ibig = a[i];
}else{
sum += ibig - a[i];
}
++i;
}else{
if (jbig < a[j]){
jbig = a[j];
}else{
sum += jbig - a[j];
}
--j;
}
}
return sum;
}
avatar
m*k
176 楼
can you try [3, 0, 1] ?

【在 g**********y 的大作中提到】
: 第8题，O(n)
: public int hold(int[] a) {
: Stack stack = new Stack();
: int level = 0;
: int total = 0;
: for (int i=0; i: while (!stack.isEmpty()) {
: Bar prev = stack.peek();
: if (prev.height <= a[i]) {
: total += (i - prev.x - 1) * (prev.height - level);
avatar
e*s
177 楼
Bless, MARK下慢慢看
avatar
l*s
178 楼
Google jobs:
http://jobguiding.com/it-jobs/it-companies/google.html

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
: --> -98.
: 5. Discuss design challenges of a distributed web crawler running on
avatar
e*s
179 楼
不用FLAG，负数求出来的余数也是负数吧

【在 P**********c 的大作中提到】
: 考虑吧，例子里就有-890 -98，这个记录一个flag就可以了，不难实现。
avatar
c*j
180 楼
13. 我从2，3 推到n，maximize: np(1-p)^{n-1}
求导。。。。
对不对？
avatar
d*u
181 楼
能不能用白话文解释一下，多谢。

【在 d*******d 的大作中提到】
: c++ version
: 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;
avatar
d*u
182 楼
白话文应该是： 下坡时把数进堆栈 （这样堆栈中最上元素是最小的，保存一个下坡序列），上坡时：如果
有底的话（堆栈中至少有两个元素），找出底，flood（累加，顶减底乘长度）。
知道过完为止。

【在 d*******u 的大作中提到】
: 能不能用白话文解释一下，多谢。
avatar
d*u
183 楼
//白话文应该是： 下坡时把数进堆栈 （这样堆栈中最上元素是最小的，保存一个下坡
序列），上坡时：如果
//有底的话（堆栈中至少有两个元素），找出底，flood（累加，顶减底乘长度）。
//知道过完为止。
int water(int * a, int n){
stack > mystack;
int water = 0;
for(int i = 0; iwhile(!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])); //下坡，进堆栈。
//上坡无底的话，是什么都不做的，因为上次进堆栈的元素直接出堆栈了，只是查
了一下底（至少两元素在堆栈）。
}
return water;
』

序列），上坡时：如果

【在 d*******u 的大作中提到】
: 白话文应该是： 下坡时把数进堆栈 （这样堆栈中最上元素是最小的，保存一个下坡序列），上坡时：如果
: 有底的话（堆栈中至少有两个元素），找出底，flood（累加，顶减底乘长度）。
: 知道过完为止。
avatar
d*u
184 楼
有没有人说一说如果是二维数组的， flood fill怎么做呀？

【在 d*******u 的大作中提到】
: //白话文应该是： 下坡时把数进堆栈 （这样堆栈中最上元素是最小的，保存一个下坡
: 序列），上坡时：如果
: //有底的话（堆栈中至少有两个元素），找出底，flood（累加，顶减底乘长度）。
: //知道过完为止。
: 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; //底
avatar
c*8
185 楼
many thanks

the
called
all
890

【在 b*****n 的大作中提到】
: 1. You have a class that supports to input sample records and to compute the
: average of the samples. The class has two members: total and count. How
: would you make the class thread-safe? If 99% of the time average() is called
: , how to optimize for that?
: 2. Talk about your recent interesting project/bug.
: 3. You have 100 files, each containing 10G sorted integers. How to merge all
: integers into one sorted file?
: 4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
: --> -98.
: 5. Discuss design challenges of a distributed web crawler running on
avatar
d*d
186 楼
用求导数算出来的，是n=-1/ln(1-p),
p小于１时 ln(1-p) 的近似值就是 -p。
（在p＝０处泰勒展开，保留一次项。）
所以近似以后就是1/p了。

唯一？我的微积分是忘干净了。

【在 g**********y 的大作中提到】
: 前面的推导对，后面我不sure：你怎么证明最大值一定出现在微分为0的地方而且解唯一？我的微积分是忘干净了。
: 我是直接推算的，f(N) = N*p*(1-p)^(N-1)
: f(N+1) - f(N) = (1-p)^(N-1) * [(N+1)*p*(1-p) - N*p]
: sgn[f(N+1) - f(N)] = sgn[(N+1)*p*(1-p) - N*p]
: = sgn[p(1-(N+1)*p] = sgn[1-(N+1)*p]
: 递归可以证明：
: p = 1~1/2, N=1最好
: p = 1/2~1/3, N=2最好
: p = 1/3~1/4, N=3最好
: 。。。
相关阅读
ELISA新手问题这年头，做6－7年博士后都成寻常事了青霉素在中国的历史今天细胞年会Amy Wagers做报告，看上去很美问问大家写一份12页的grant大概要多少时间会议的travel award能自己留着吗Paper help丙酮蛋白沉淀求助!问个技术问题2个包子求篇paper（1984年的Endocrinology）关于很多学校不给办H1Bmicroarray问题MGH是不是相当于瑞金医院在国内的地位呀？封面故事：Ardi——颠覆人类进化论gene cloning的问题有人用过Arcturus kit吗？Top 10 Everything of 2010《时代》杂志评出2010年十大求助Re: zt: 天涯相亲 (转载)二號染色體融合有多確定？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。