P********i
发帖数: 172 | 1 Phone 1:
:
What is “static” variable?
How can many instance share a resource
What is deadlock, how to prevent it?
Compare whether two strings s1, s2 are equal, inside a huge set of string.
Normal way is to compare each character one by one, but it is O( n ) time
complexity. What type of short circuit can u think?
One short circuit is to use the length, since s1.len <> s2. len , then
return false. Anything else you can think of in the similar way?
My answers:
Hashtable? No, need extra space
Binary search? No, worst case is O(n)
1) # of unique chars
2) Bit vector for each
I did not know KMP and Robin Karp at that time, i guess it is the desirable
solution for the interview :(
Given a perfect random generator Random(n) which can generate number between
[0,1], write a program to generate a random pair of (x, y) within a circle
of radius 1, and with (0,0) center with uniform distribution inside the
circle. What is the expect probability of values fall into the circle? |
r****k
发帖数: 173 | 2 Bless个。
Compare whether two strings s1, s2 are equal, inside a huge set of string.
Normal way is to compare each character one by one, but it is O( n ) time
complexity. What type of short circuit can u think?
这道题是不是要用概率呢？我想的是每次取一个随机数做为下标，看着两个string在这
个位置上是否相等。如果一直相等，循环n（数组长度）次。在n次内没有找到不相等的
，就假定它们相等。我觉得找出来string不相等的概率很小，就算不相等也是很类似的
因为这个算法是在big set的 string中找相等，如果不相等的概率很高的话。效率应该
很高，可能一次两次就能，知道两个string不一样了。这样preprocess之后再进行O(n)
比较，效率会高很多吧。
等高人解答 |
t****o
发帖数: 31 | 3 Bloom filter?
★ Sent from iPhone App: iReader Mitbbs 6.8 - iPhone Lite |
n******t
发帖数: 4406 | 4 感觉google真是个和尚庙啊。。。
【在 P********i 的大作中提到】
: Phone 1:
: :
: What is “static” variable?
: How can many instance share a resource
: What is deadlock, how to prevent it?
: Compare whether two strings s1, s2 are equal, inside a huge set of string.
: Normal way is to compare each character one by one, but it is O( n ) time
: complexity. What type of short circuit can u think?
: One short circuit is to use the length, since s1.len <> s2. len , then
: return false. Anything else you can think of in the similar way?
|
g*******s
发帖数: 2963 | 5 我记得KMP好像也是O(n)吧，但是KMP优势是可以找出一个连续string是否是另一个的
substring |
s*******3
发帖数: 134 | |
P********l
发帖数: 452 | 7 http://en.wikipedia.org/wiki/BLAST#Algorithm
【在 P********i 的大作中提到】
: Phone 1:
: :
: What is “static” variable?
: How can many instance share a resource
: What is deadlock, how to prevent it?
: Compare whether two strings s1, s2 are equal, inside a huge set of string.
: Normal way is to compare each character one by one, but it is O( n ) time
: complexity. What type of short circuit can u think?
: One short circuit is to use the length, since s1.len <> s2. len , then
: return false. Anything else you can think of in the similar way?
|
P********l
发帖数: 452 | 8 生成两个随机数 (theta, r).
theta is uniform distributed
r = 1/sqrt(uniform). (<>0)
目的是让面积*密度=常数。
Given a perfect random generator Random(n) which can generate number between
[0,1], write a program to generate a random pair of (x, y) within a circle
of radius 1, and with (0,0) center with uniform distribution inside the
circle. What is the expect probability of values fall into the circle? |
c********0
发帖数: 112 | 9 Compare whether two strings s1, s2 are equal, inside a huge set of string.
啥意思啊。。。 |
n***5
发帖数: 86 | |
|
|
c*****u
发帖数: 107 | |
P********l
发帖数: 452 | 12 re
【在 c*****u 的大作中提到】
: blesssssssssssssss
|
l*****g
发帖数: 685 | 13 这个方法不大对
如果set of strings是随机排列的，那么，从index 0开始逐个比较两个string的
char, 跟你的方法（取随机的index来比较）没有本质区别
如果说这些strings是预先sort好的, 那么shortcut是从最末位开始比较两个string
n)
【在 r****k 的大作中提到】
: Bless个。
: Compare whether two strings s1, s2 are equal, inside a huge set of string.
: Normal way is to compare each character one by one, but it is O( n ) time
: complexity. What type of short circuit can u think?
: 这道题是不是要用概率呢？我想的是每次取一个随机数做为下标，看着两个string在这
: 个位置上是否相等。如果一直相等，循环n（数组长度）次。在n次内没有找到不相等的
: ，就假定它们相等。我觉得找出来string不相等的概率很小，就算不相等也是很类似的
: 因为这个算法是在big set的 string中找相等，如果不相等的概率很高的话。效率应该
: 很高，可能一次两次就能，知道两个string不一样了。这样preprocess之后再进行O(n)
: 比较，效率会高很多吧。
|
r****k
发帖数: 173 | 14
不大可能是排好序的吧。如果是排好序的，相同的字符串应该都在相邻的地方了。如果
字符串随机产生
的话，你说的方法确实和随机index一样。
但考虑到单词的前缀和后缀有很高的相似程度，长度相同的情况下，或许从中间开始找
效率会更高一
点。
不知道答案是啥
【在 l*****g 的大作中提到】
: 这个方法不大对
: 如果set of strings是随机排列的，那么，从index 0开始逐个比较两个string的
: char, 跟你的方法（取随机的index来比较）没有本质区别
: 如果说这些strings是预先sort好的, 那么shortcut是从最末位开始比较两个string
:
: n)
|
r*********n
发帖数: 234 | 15
between
r也可能uniformly distributed就好了吧？首先随便选一个角度［0, 360］，然后在此
角度上任选一点，这样所有点都是相同的概率了吧
【在 P********l 的大作中提到】
: 生成两个随机数 (theta, r).
: theta is uniform distributed
: r = 1/sqrt(uniform). (<>0)
: 目的是让面积*密度=常数。
: Given a perfect random generator Random(n) which can generate number between
: [0,1], write a program to generate a random pair of (x, y) within a circle
: of radius 1, and with (0,0) center with uniform distribution inside the
: circle. What is the expect probability of values fall into the circle?
|
t*****s
发帖数: 416 | 16 显然不是。你这样等于把一个长方形像扇子一样扭成一个圆形，点密度是里高外低
保持相同点密度的情况下，点所在同心圆上的点数应该和同心圆的周长成正比，即和点的圆心距成正
比。
所以应该想办法获得分布概率函数使得某个内同心圆上的概率与该圆半径成正比。
【在 r*********n 的大作中提到】
:
: between
: r也可能uniformly distributed就好了吧？首先随便选一个角度［0, 360］，然后在此
: 角度上任选一点，这样所有点都是相同的概率了吧
|
S*********3
发帖数: 142 | |
g**e
发帖数: 6127 | 18 dumb solution, randomly generate x & y between [0,1], if x^2+y^2<1 accept
the pair, otherwise reject and regenerate.
距成正比。
【在 t*****s 的大作中提到】
: 显然不是。你这样等于把一个长方形像扇子一样扭成一个圆形，点密度是里高外低
: 保持相同点密度的情况下，点所在同心圆上的点数应该和同心圆的周长成正比，即和点的圆心距成正
: 比。
: 所以应该想办法获得分布概率函数使得某个内同心圆上的概率与该圆半径成正比。
|
t*****s
发帖数: 416 | 19 我只不过是讨论一下他的思路怎么改进而已。
你这个算法当然是最容易想到的，效率也未必低，但是万一人家不接受这个怎么办？
【在 g**e 的大作中提到】
: dumb solution, randomly generate x & y between [0,1], if x^2+y^2<1 accept
: the pair, otherwise reject and regenerate.
:
: 距成正比。
|
d******2
发帖数: 456 | |
|
|
g**e
发帖数: 6127 | 21 I don't see any reason interviewer doesn't accept this method. If you are
talking about this method below, I don't think it's anywhere faster than the
first method:
double p = rand()*2*pi;
double r = sqrt(rand());
double x = r * sin(p);
double y = r * cos(p);
return (x,y);
accept
【在 t*****s 的大作中提到】
: 我只不过是讨论一下他的思路怎么改进而已。
: 你这个算法当然是最容易想到的，效率也未必低，但是万一人家不接受这个怎么办？
|
t*****s
发帖数: 416 | 22 我觉得r应该是
x=rand();
if ( x < 0.5 ) r = rand() < x ? x : 1-x;
else r = x;
将平均分布函数映射成它的累计分布函数。
你开方之后r的分布向原点集中，只会导致圆心附近的点密度更大。
sin(),cos()都不是什么速度很快的函数，但是人家出这个题未必只是想看看你敢不敢
把最简单的答案当作回答给出来。而且考官会不会想要你提出一个别的解法来谁也说不
准。
the
【在 g**e 的大作中提到】
: I don't see any reason interviewer doesn't accept this method. If you are
: talking about this method below, I don't think it's anywhere faster than the
: first method:
: double p = rand()*2*pi;
: double r = sqrt(rand());
: double x = r * sin(p);
: double y = r * cos(p);
: return (x,y);
:
: accept
|
g**e
发帖数: 6127 | 23
this is not uniform distribution.
why do you think it pushes toward 0? are you suggesting the value gets
smaller after sqrt? think again.
are
【在 t*****s 的大作中提到】
: 我觉得r应该是
: x=rand();
: if ( x < 0.5 ) r = rand() < x ? x : 1-x;
: else r = x;
: 将平均分布函数映射成它的累计分布函数。
: 你开方之后r的分布向原点集中，只会导致圆心附近的点密度更大。
: sin(),cos()都不是什么速度很快的函数，但是人家出这个题未必只是想看看你敢不敢
: 把最简单的答案当作回答给出来。而且考官会不会想要你提出一个别的解法来谁也说不
: 准。
:
|
c********0
发帖数: 112 | 24 double r = sqrt(rand());
为什么要 sqrt 而不是直接 r = rand()?
不明白。。。
【在 g**e 的大作中提到】
:
: this is not uniform distribution.
: why do you think it pushes toward 0? are you suggesting the value gets
: smaller after sqrt? think again.
: are
|
g**e
发帖数: 6127 | 25 x^2+y^2=r^2 < 1
【在 c********0 的大作中提到】
: double r = sqrt(rand());
: 为什么要 sqrt 而不是直接 r = rand()?
: 不明白。。。
|
c********0
发帖数: 112 | 26 这样可以吗
0-360 随机选一个角度
double p = rand()*2*pi;
0-1 随机选一个半经
double r = rand()
返回 r*sin(p) r*cos(p)
好像也是随机的吧 |
g**e
发帖数: 6127 | 27 两个坐标的平方和等于r^2，往原点集中，非均匀分布
【在 c********0 的大作中提到】
: 这样可以吗
: 0-360 随机选一个角度
: double p = rand()*2*pi;
: 0-1 随机选一个半经
: double r = rand()
: 返回 r*sin(p) r*cos(p)
: 好像也是随机的吧
|
h**********8
发帖数: 267 | |
p*********9
发帖数: 287 | |
d*******d
发帖数: 2050 | 30 最后那个dictionary啥意思啊,没看懂题.
【在 P********i 的大作中提到】
: Phone 1:
: :
: What is “static” variable?
: How can many instance share a resource
: What is deadlock, how to prevent it?
: Compare whether two strings s1, s2 are equal, inside a huge set of string.
: Normal way is to compare each character one by one, but it is O( n ) time
: complexity. What type of short circuit can u think?
: One short circuit is to use the length, since s1.len <> s2. len , then
: return false. Anything else you can think of in the similar way?
|
