郭德纲单口相声姚家井好！ (转载) - 未名空间MITBBS历史存档

郭德纲单口相声姚家井好！ (转载)# Joke - 肚皮舞运动

T12013-12-10 08:12

1 楼

老说些我们听不明白的英语，病人这么说
ok, i don't guess i got in under the wire - can you send me an Ebay invoice
for the extra memory?
什么意思？
it买了电脑，问能不能多加内存到8g我说可以，paypal 付给我$80就可以，他这么回信
。

d*02013-12-10 08:12

2 楼

May 23面的
一共三轮
就第一轮简单问了一下resume的intern
其他的每轮就只有一个算法题
1. 给定rand1()：能够产生random数字0,1
用rand1()实现:
rand3()--> 0, 1, 2, 3
rand4()--> 0, 1, 2, 3, 4
randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
，注意edge case
2. given 一个字符串，这个字符串是一个算式，包含加减乘除，没有括号，符号和数
字之间以一个空格格开，比如：“1 + 2 * 4 / 5”，return算式的结果
3. given两个字符串，分别表示两个元素等和不等，比如：
arr1 = {“A=B”, "B=C", ...}
arr2 = {"A!=C", "F!=R", ...}
判断是否有矛盾，这个例子就有矛盾：A!=C
given提取元素的method: getID(..)，这个不用自己写：String[] sarr = getID(arr1
[0]) --> sarr {A, B}
今天问道口头offer, 正在executive committee review中，求bless！！！

l*g2013-12-10 08:12

3 楼

不把大家玩死誓不罢休

g*12013-12-10 08:12

4 楼

【以下文字转载自 Military 讨论区】
发信人: ghost1 (ghost), 信区: Military
标题: 郭德纲单口相声姚家井好！
发信站: BBS 未名空间站 (Tue Dec 10 13:12:47 2013, 美东)
https://www.youtube.com/watch?v=yx9bqLdoFdI

p*d2013-12-10 08:12

5 楼

用paypal发个要钱的信的给Y

invoice

【在 T1 的大作中提到】

: 老说些我们听不明白的英语，病人这么说
: ok, i don't guess i got in under the wire - can you send me an Ebay invoice
: for the extra memory?
: 什么意思？
: it买了电脑，问能不能多加内存到8g我说可以，paypal 付给我$80就可以，他这么回信
: 。

c*r2013-12-10 08:12

6 楼

多谢分享。
第三题没看明白，是什么意思呢？
String[] sarr = getID(arr1[0]) --> sarr {A, B}，这个方法的意思是给定数组元
素，提取该元素里面涉及到的element吗？那么两个元素是否相等需要自己提取吗？

e*12013-12-10 08:12

7 楼

你确定是美国人？
美国文盲？

invoice

【在 T1 的大作中提到】

: 老说些我们听不明白的英语，病人这么说
: ok, i don't guess i got in under the wire - can you send me an Ebay invoice
: for the extra memory?
: 什么意思？
: it买了电脑，问能不能多加内存到8g我说可以，paypal 付给我$80就可以，他这么回信
: 。

y*n2013-12-10 08:12

8 楼

第一个有什么好的解法。

N*o2013-12-10 08:12

9 楼

这个不是不认真说话，是咱不是native speaker
native speaker 一瑞德就瑞德懂
u just need to read it , hear it, not to "see it"

invoice

【在 T1 的大作中提到】

: 老说些我们听不明白的英语，病人这么说
: ok, i don't guess i got in under the wire - can you send me an Ebay invoice
: for the extra memory?
: 什么意思？
: it买了电脑，问能不能多加内存到8g我说可以，paypal 付给我$80就可以，他这么回信
: 。

d*02013-12-10 08:12

10 楼

本来最先题目是一个数组，也有提取符号的方法。不不过面试官简化了，弄成了两个数
组，第一个数组都是等的，第二个都是不等的

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

: 多谢分享。
: 第三题没看明白，是什么意思呢？
: String[] sarr = getID(arr1[0]) --> sarr {A, B}，这个方法的意思是给定数组元
: 素，提取该元素里面涉及到的element吗？那么两个元素是否相等需要自己提取吗？

d*02013-12-10 08:12

11 楼

2^k*rand1() + 2^k-1*rand1() + ... + 2^2*rand1() + 2*rand1() + rand1()
while 循环，如果上面式子得到的值少于等于n就return

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

: 第一个有什么好的解法。

y*n2013-12-10 08:12

12 楼

能稍微解释一下吗，这些题不太容易想

m*s2013-12-10 08:12

13 楼

Bless

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

: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case

j*42013-12-10 08:12

14 楼

想问题三题的思路是什么呢

j*42013-12-10 08:12

15 楼

第三题的思路是不是先的建无向图，然后，根据第二个集合，traverse验证?

d*e2013-12-10 08:12

16 楼

请问这个是根据什么而得出来的式子？
谢谢！

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

:
: 2^k*rand1() + 2^k-1*rand1() + ... + 2^2*rand1() + 2*rand1() + rand1()
: while 循环，如果上面式子得到的值少于等于n就return

j*32013-12-10 08:12

17 楼

is LZ new grad?

S*12013-12-10 08:12

18 楼

//11:55 第3题不是图，是disjoint set
boolean isRight(String[] ss1, String[] ss2) {
if (ss1 == null || ss2 == null)
return false;

Map indexMap = new HashMap();
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
if (!indexMap.containsKey(c1))
indexMap.put(c1, indexMap.size());
if (!indexMap.containsKey(c2))
indexMap.put(c2, indexMap.size());
}

int[] set = new int[indexMap.size()];
for (int i = 0; i < set.length; i++)
set[i] = -1;

for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
union(set, indexMap.get(c1), indexMap.get(c2));
}

for (String s : ss2) {
char c1 = s.charAt(0);
char c2 = s.charAt(3);
if (indexMap.containsKey(c1) && indexMap.containsKey(c2)) {
int p1 = findParent(set, indexMap.get(c1));
int p2 = findParent(set, indexMap.get(c2));

if (p1 == p2)
return false;
}
}

return true;
}
void union(int[] set, int i, int j) {
int p1 = findParent(set, i);
int p2 = findParent(set, j);

if (set[p1] < set[p2])
set[p2] = p1;
else
set[p1] = p2;
}
int findParent(int[] set, int i) {
if (set[i] < 0)
return i;

int p = findParent(set[i]);
set[i] = p;

return p;
}

S*12013-12-10 08:12

19 楼

第一题reject sampling,
binary search
suppose sample space is power of 2, if more, reject and select again
If negative, set offset and restore

l*a2013-12-10 08:12

20 楼

不根据什么呀
简单是就是生成如下序列(这个例子是rand5())
0000
0001
0010
0011
0100
0101
.....
每个digit调用一次rand1()
如果生成的序列超过n，就排除
剩下的这些按照概率来说出现的频率一样

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

: 请问这个是根据什么而得出来的式子？
: 谢谢！

d*02013-12-10 08:12

21 楼

是的 new grad

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

: is LZ new grad?

d*02013-12-10 08:12

22 楼

谢谢！就你bless我，大家都看题去了。。嘿嘿

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

: Bless

y*n2013-12-10 08:12

23 楼

不好意思，一看题就忽略主题了，bless。

d*02013-12-10 08:12

24 楼

哈哈，谢谢~

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

: 不好意思，一看题就忽略主题了，bless。

j*42013-12-10 08:12

25 楼

-------------------------
第一次见这种类型题，学习了，非常感谢。

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

: //11:55 第3题不是图，是disjoint set
: boolean isRight(String[] ss1, String[] ss2) {
: if (ss1 == null || ss2 == null)
: return false;
:
: Map indexMap = new HashMap();
: for (String s : ss1) {
: char c1 = s.charAt(0);
: char c2 = s.charAt(2);
: if (!indexMap.containsKey(c1))

d*e2013-12-10 08:12

26 楼

难道你说的序列不算根据啊？这个理解比较简单。
不过话说回来，我到现在还是不明白那题，就是跟这题类似的，好像是rand3生成rand5
还是7的，说如果大过某数就去除，然后再继续得到某个范围为止。
打个比方，可以得到1~25，但expect得到1～21，所以如果产生的数是22～25，就去掉
，再继续找到1～21为止。这时问题我的问题就来了。
如果说一个随机函数是均匀分布的可以得到1~25,那是说不管我运行多少次，得到的数
都是1～25.那希望以此函数产生均匀分布的函数得到1~21，也就是说原随机函数不管运
行多少次，那根据某个公式得到的数也都是1～21，但如果去除某些结果，这还是算随
机分布吗？
我不是学数学的，高数概率也学得不好，所以没好好去证明，但就是想不明白。

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

: 不根据什么呀
: 简单是就是生成如下序列(这个例子是rand5())
: 0000
: 0001
: 0010
: 0011
: 0100
: 0101
: .....
: 每个digit调用一次rand1()

R*d2013-12-10 08:12

27 楼

祝福

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

: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case

c*s2013-12-10 08:12

28 楼

Bless!

May 23面的一共三轮就第一轮简单问了一下resume的intern其他的每轮就只有一个算法
题1. 给定rand1()：能够产生random数字0,1

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

:
: 哈哈，谢谢~

w*c2013-12-10 08:12

29 楼

big bless

D*72013-12-10 08:12

30 楼

bless，问题不大，yahoo最近招不到人

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

: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case

d*02013-12-10 08:12

31 楼

May 23面的
一共三轮
就第一轮简单问了一下resume的intern
其他的每轮就只有一个算法题
1. 给定rand1()：能够产生random数字0,1
用rand1()实现:
rand3()--> 0, 1, 2, 3
rand4()--> 0, 1, 2, 3, 4
randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
，注意edge case
2. given 一个字符串，这个字符串是一个算式，包含加减乘除，没有括号，符号和数
字之间以一个空格格开，比如：“1 + 2 * 4 / 5”，return算式的结果
3. given两个字符串，分别表示两个元素等和不等，比如：
arr1 = {“A=B”, "B=C", ...}
arr2 = {"A!=C", "F!=R", ...}
判断是否有矛盾，这个例子就有矛盾：A!=C
given提取元素的method: getID(..)，这个不用自己写：String[] sarr = getID(arr1
[0]) --> sarr {A, B}
今天问道口头offer, 正在executive committee review中，求bless！！！
-----------
收到正式offer！谢谢大家的祝福！

c*r2013-12-10 08:12

32 楼

多谢分享。
第三题没看明白，是什么意思呢？
String[] sarr = getID(arr1[0]) --> sarr {A, B}，这个方法的意思是给定数组元
素，提取该元素里面涉及到的element吗？那么两个元素是否相等需要自己提取吗？

y*n2013-12-10 08:12

33 楼

第一个有什么好的解法。

d*02013-12-10 08:12

34 楼

本来最先题目是一个数组，也有提取符号的方法。不不过面试官简化了，弄成了两个数
组，第一个数组都是等的，第二个都是不等的

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

: 多谢分享。
: 第三题没看明白，是什么意思呢？
: String[] sarr = getID(arr1[0]) --> sarr {A, B}，这个方法的意思是给定数组元
: 素，提取该元素里面涉及到的element吗？那么两个元素是否相等需要自己提取吗？

d*02013-12-10 08:12

35 楼

2^k*rand1() + 2^k-1*rand1() + ... + 2^2*rand1() + 2*rand1() + rand1()
while 循环，如果上面式子得到的值少于等于n就return

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

: 第一个有什么好的解法。

y*n2013-12-10 08:12

36 楼

能稍微解释一下吗，这些题不太容易想

m*s2013-12-10 08:12

37 楼

Bless

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

: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case

j*42013-12-10 08:12

38 楼

想问题三题的思路是什么呢

j*42013-12-10 08:12

39 楼

第三题的思路是不是先的建无向图，然后，根据第二个集合，traverse验证?

d*e2013-12-10 08:12

40 楼

请问这个是根据什么而得出来的式子？
谢谢！

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

:
: 2^k*rand1() + 2^k-1*rand1() + ... + 2^2*rand1() + 2*rand1() + rand1()
: while 循环，如果上面式子得到的值少于等于n就return

j*32013-12-10 08:12

41 楼

is LZ new grad?

S*12013-12-10 08:12

42 楼

//11:55 第3题不是图，是disjoint set
boolean isRight(String[] ss1, String[] ss2) {
if (ss1 == null || ss2 == null)
return false;

Map indexMap = new HashMap();
for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
if (!indexMap.containsKey(c1))
indexMap.put(c1, indexMap.size());
if (!indexMap.containsKey(c2))
indexMap.put(c2, indexMap.size());
}

int[] set = new int[indexMap.size()];
for (int i = 0; i < set.length; i++)
set[i] = -1;

for (String s : ss1) {
char c1 = s.charAt(0);
char c2 = s.charAt(2);
union(set, indexMap.get(c1), indexMap.get(c2));
}

for (String s : ss2) {
char c1 = s.charAt(0);
char c2 = s.charAt(3);
if (indexMap.containsKey(c1) && indexMap.containsKey(c2)) {
int p1 = findParent(set, indexMap.get(c1));
int p2 = findParent(set, indexMap.get(c2));

if (p1 == p2)
return false;
}
}

return true;
}
void union(int[] set, int i, int j) {
int p1 = findParent(set, i);
int p2 = findParent(set, j);

if (set[p1] < set[p2])
set[p2] = p1;
else
set[p1] = p2;
}
int findParent(int[] set, int i) {
if (set[i] < 0)
return i;

int p = findParent(set[i]);
set[i] = p;

return p;
}

S*12013-12-10 08:12

43 楼

第一题reject sampling,
binary search
suppose sample space is power of 2, if more, reject and select again
If negative, set offset and restore

l*a2013-12-10 08:12

44 楼

不根据什么呀
简单是就是生成如下序列(这个例子是rand5())
0000
0001
0010
0011
0100
0101
.....
每个digit调用一次rand1()
如果生成的序列超过n，就排除
剩下的这些按照概率来说出现的频率一样

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

: 请问这个是根据什么而得出来的式子？
: 谢谢！

d*02013-12-10 08:12

45 楼

是的 new grad

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

: is LZ new grad?

d*02013-12-10 08:12

46 楼

谢谢！就你bless我，大家都看题去了。。嘿嘿

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

: Bless

y*n2013-12-10 08:12

47 楼

不好意思，一看题就忽略主题了，bless。

d*02013-12-10 08:12

48 楼

哈哈，谢谢~

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

: 不好意思，一看题就忽略主题了，bless。

j*42013-12-10 08:12

49 楼

-------------------------
第一次见这种类型题，学习了，非常感谢。

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

: //11:55 第3题不是图，是disjoint set
: boolean isRight(String[] ss1, String[] ss2) {
: if (ss1 == null || ss2 == null)
: return false;
:
: Map indexMap = new HashMap();
: for (String s : ss1) {
: char c1 = s.charAt(0);
: char c2 = s.charAt(2);
: if (!indexMap.containsKey(c1))

d*e2013-12-10 08:12

50 楼

难道你说的序列不算根据啊？这个理解比较简单。
不过话说回来，我到现在还是不明白那题，就是跟这题类似的，好像是rand3生成rand5
还是7的，说如果大过某数就去除，然后再继续得到某个范围为止。
打个比方，可以得到1~25，但expect得到1～21，所以如果产生的数是22～25，就去掉
，再继续找到1～21为止。这时问题我的问题就来了。
如果说一个随机函数是均匀分布的可以得到1~25,那是说不管我运行多少次，得到的数
都是1～25.那希望以此函数产生均匀分布的函数得到1~21，也就是说原随机函数不管运
行多少次，那根据某个公式得到的数也都是1～21，但如果去除某些结果，这还是算随
机分布吗？
我不是学数学的，高数概率也学得不好，所以没好好去证明，但就是想不明白。

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

: 不根据什么呀
: 简单是就是生成如下序列(这个例子是rand5())
: 0000
: 0001
: 0010
: 0011
: 0100
: 0101
: .....
: 每个digit调用一次rand1()

R*d2013-12-10 08:12

51 楼

祝福

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

: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case

c*s2013-12-10 08:12

52 楼

Bless!

May 23面的一共三轮就第一轮简单问了一下resume的intern其他的每轮就只有一个算法
题1. 给定rand1()：能够产生random数字0,1

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

:
: 哈哈，谢谢~

w*c2013-12-10 08:12

53 楼

big bless

D*72013-12-10 08:12

54 楼

bless，问题不大，yahoo最近招不到人

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

: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case

c*12013-12-10 08:12

55 楼

我面试的时候面了这个我用union find做的那人说有o（n)的解法，面试官没跟我说正
确解法。但是一起面的人用了你这个解法面试官表示满意，我之前没看懂你这个解法，
现在觉得你这个做法也是O(n^2)把？

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

: //11:55 第3题不是图，是disjoint set
: boolean isRight(String[] ss1, String[] ss2) {
: if (ss1 == null || ss2 == null)
: return false;
:
: Map indexMap = new HashMap();
: for (String s : ss1) {
: char c1 = s.charAt(0);
: char c2 = s.charAt(2);
: if (!indexMap.containsKey(c1))

I*s2013-12-10 08:12

56 楼

第一题应该也可以这样吧: n == 0 ? 0 : ((rand1() * INT_MAX) % n).
第三题可以用union find.

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

: May 23面的
: 一共三轮
: 就第一轮简单问了一下resume的intern
: 其他的每轮就只有一个算法题
: 1. 给定rand1()：能够产生random数字0,1
: 用rand1()实现:
: rand3()--> 0, 1, 2, 3
: rand4()--> 0, 1, 2, 3, 4
: randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
: ，注意edge case

z*y2013-12-10 08:12

57 楼

祝福lz！
1.相当于每次产生一个bit，运行k次，保证2^k >= n，如果超过n就重新运算，否则就
返回；
2.可以用一个stack吧，碰到*/操作立马计算，完了以后再处理一下剩下的+ -；
3.用hash table吧。如果对象都只是一个字符，那么char table[256]即可。遍历相等
的串，把相等的元素设置成同样的值。然后遍历不等的串，取值出来比较即可。

f*c2013-12-10 08:12

58 楼

能具体说说第三个怎么做吗如果用hashmap?

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

: 祝福lz！
: 1.相当于每次产生一个bit，运行k次，保证2^k >= n，如果超过n就重新运算，否则就
: 返回；
: 2.可以用一个stack吧，碰到*/操作立马计算，完了以后再处理一下剩下的+ -；
: 3.用hash table吧。如果对象都只是一个字符，那么char table[256]即可。遍历相等
: 的串，把相等的元素设置成同样的值。然后遍历不等的串，取值出来比较即可。

f*c2013-12-10 08:12

59 楼

感觉这个算法有bug,加入输入：
A=B,C=D,B=D
A!=C
按这个算法返回true啊

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

: 我面试的时候面了这个我用union find做的那人说有o（n)的解法，面试官没跟我说正
: 确解法。但是一起面的人用了你这个解法面试官表示满意，我之前没看懂你这个解法，
: 现在觉得你这个做法也是O(n^2)把？

d*m2013-12-10 08:12

60 楼

bless

c*12013-12-10 08:12

61 楼

我也觉得，这个问题感觉是个标准的union find 怎么会有O（n）的解法（我面试的时
候说只有26个字母所以是26n 也可以是 lg26 n）那人马上说如果有很多别的item ，不
知道是不是面试官想错了

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

: 感觉这个算法有bug,加入输入：
: A=B,C=D,B=D
: A!=C
: 按这个算法返回true啊

t*d2013-12-10 08:12

62 楼

这个帖子不是很老的么？怎么冒上来了

f*c2013-12-10 08:12

63 楼

不知你面的时候怎么做的？有没有和别人讨论得到O(n)的解啊？

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

:
: 我也觉得，这个问题感觉是个标准的union find 怎么会有O（n）的解法（我面试的时
: 候说只有26个字母所以是26n 也可以是 lg26 n）那人马上说如果有很多别的item ，不
: 知道是不是面试官想错了

u*l2013-12-10 08:12

64 楼

恭喜一下楼主。
以后有机会找楼主要个推荐