m**********4
发帖数: 774 | 1 Today I had my third-round interview with this company. Got some pretty
tough questions (from my standard). I won't regret that I failed this one,
because some questions are really beyond my ability.
1. n boxes, k balls, expected number of empty boxes.
2. an array with 0's and 1's, find in O(n) time and O(1) space the longest
sequence with equal number of 1's and 0's.
can do it with O(n) time and O(n) space. How to do O(1) space.
3. Suppose you have a four digit code. each one takes 0~9.
Now suppose that you have a very stupid code machine. you can enter any
length of coed into it:
if you enter 123456
it considers you entered three code:
1234
2345
3456
What is the smallest length of string I need to enter to guarantee that I
find out your code? How would you write such a string? |
Y***e
发帖数: 1030 | 2 1 N * (n-1/n)^k ?
【在 m**********4 的大作中提到】
: Today I had my third-round interview with this company. Got some pretty
: tough questions (from my standard). I won't regret that I failed this one,
: because some questions are really beyond my ability.
: 1. n boxes, k balls, expected number of empty boxes.
: 2. an array with 0's and 1's, find in O(n) time and O(1) space the longest
: sequence with equal number of 1's and 0's.
: can do it with O(n) time and O(n) space. How to do O(1) space.
: 3. Suppose you have a four digit code. each one takes 0~9.
: Now suppose that you have a very stupid code machine. you can enter any
: length of coed into it:
|
c*****a
发帖数: 95 | 3 1.同楼上，每个盒子是空的的概率是((n-1)/n)^k,然后times盒子数
第三题看不懂。。。 |
J**********g
发帖数: 213 | 4 it's an on-site one? and which company is it? thanks. |
f********y
发帖数: 278 | 5 每个盒子空的概率不是互相独立的。
这个问题可以用recurrence equation 去解。
假定f(n,k)为空盒的概率，求出它和f(n-1,k)和f(n,k-1)的关系。
【在 c*****a 的大作中提到】
: 1.同楼上，每个盒子是空的的概率是((n-1)/n)^k,然后times盒子数
: 第三题看不懂。。。
|
f********y
发帖数: 278 | 6 LZ，这是phone interview还是on-site？
我觉得如果是phone interview还是蛮难的。
【在 m**********4 的大作中提到】
: Today I had my third-round interview with this company. Got some pretty
: tough questions (from my standard). I won't regret that I failed this one,
: because some questions are really beyond my ability.
: 1. n boxes, k balls, expected number of empty boxes.
: 2. an array with 0's and 1's, find in O(n) time and O(1) space the longest
: sequence with equal number of 1's and 0's.
: can do it with O(n) time and O(n) space. How to do O(1) space.
: 3. Suppose you have a four digit code. each one takes 0~9.
: Now suppose that you have a very stupid code machine. you can enter any
: length of coed into it:
|
G********d
发帖数: 10250 | 7 楼上的答案是对的
用容斥原理的变形
【在 f********y 的大作中提到】
: 每个盒子空的概率不是互相独立的。
: 这个问题可以用recurrence equation 去解。
: 假定f(n,k)为空盒的概率，求出它和f(n-1,k)和f(n,k-1)的关系。
|
B******5
发帖数: 4676 | 8 expectation不受独立影响吧
【在 f********y 的大作中提到】
: 每个盒子空的概率不是互相独立的。
: 这个问题可以用recurrence equation 去解。
: 假定f(n,k)为空盒的概率，求出它和f(n-1,k)和f(n,k-1)的关系。
|
d****m
发帖数: 119 | 9 1. let a=(n-1)/n, result a^(k-1)*(1-n)+n |
t*****j
发帖数: 1105 | 10 是不独立的，但是二楼和三楼的做法和答案还是正确的。
【在 f********y 的大作中提到】
: 每个盒子空的概率不是互相独立的。
: 这个问题可以用recurrence equation 去解。
: 假定f(n,k)为空盒的概率，求出它和f(n-1,k)和f(n,k-1)的关系。
|
|
|
z****g
发帖数: 1978 | 11 1. should be easy, even with the most clear way that calculating P(empty = n
) is not hard. pickup empty box first then distribute k balls into the rest
and not allowing empty.
2. I can do it in time O(n) and space O(1) if it is a list, but if strictly
a array. I don't know.
3. don't understand either. |
m**********4
发帖数: 774 | 12 how to do it in a list?
n
rest
strictly
【在 z****g 的大作中提到】
: 1. should be easy, even with the most clear way that calculating P(empty = n
: ) is not hard. pickup empty box first then distribute k balls into the rest
: and not allowing empty.
: 2. I can do it in time O(n) and space O(1) if it is a list, but if strictly
: a array. I don't know.
: 3. don't understand either.
|
z****g
发帖数: 1978 | 13 one variable is not enough to record since it depends on begin position
say
100111110010011111
123423453456 |
c**********e
发帖数: 2007 | 14 co-ask. A O(n) space approach is easy to find.
If the array a[i] is integer or double, I can find an O(1) space approach by
stealing space of a[i]. How to do it? If a[i]=1, I would let a[i]=n+k to
store a positive integer k. If a[i]=0, I would let a[i]=k to store a
positive integer k. So a[i] essentially stores 2 numbers, 0/1 and k.
Technically it is O(1) space, but do not know if this satisfies the
interviewer.
But if array a[i] is boolean, the approach does not work.
【在 m**********4 的大作中提到】
: how to do it in a list?
:
: n
: rest
: strictly
|
n****e
发帖数: 629 | 15 恩 我也发现错了 //blush
【在 z****g 的大作中提到】
: one variable is not enough to record since it depends on begin position
: say
: 100111110010011111
:
: 123423453456
|
G********d
发帖数: 10250 | |
z****g
发帖数: 1978 | 17 The idea is to scan the data in a stack way, since the order of 1s and
0s in a chunk that has equal 0s and 1s does not matter so that you can
split a 1 and 0 at the same time and keep the property of the old list
unchanged.
say
|
100111110010011111 =>
xxxxxxxxxxxxxxxxxx
| |
xxxx111xx010011111 =>
1001xxx10xxxxxxxxx
|
xxxx11xxxx10010011 =>
1001xx1100xxxxxxxx
| |
xxxx11xxxxxxxx0011 =>
1001xx11001001xxxx
| |
xxxx1xxxxxxxxxx011 =>
1001x1110010010xxx
|
xxxxxxxxxxxxxxxx11 =>
1001111100100100xx
In this way it only scan the list once and the trick of list is that you
can split a list and does not use extra space. |
n****e
发帖数: 629 | 18 修正一下做法。。。
还是从abcd->bcd(a+1)
这样所有的数都可以形成若干个互斥的环
现在把每个环并起来。具体如下：
假设一个环:
abcd->.....->(d-1)abc
然后必然存在eabc, e!=d-1, 不在环内。(otherwise it'll contain all the numbers
.)
然后把这个环插到eabc存在的那个环里就可以了。eabc->abcd->...->(d-1)abc->abc(e
+1)->... |
z****g
发帖数: 1978 | 19 Sorry about the layout, please align the first line and second line
【在 z****g 的大作中提到】
: The idea is to scan the data in a stack way, since the order of 1s and
: 0s in a chunk that has equal 0s and 1s does not matter so that you can
: split a 1 and 0 at the same time and keep the property of the old list
: unchanged.
: say
: |
: 100111110010011111 =>
: xxxxxxxxxxxxxxxxxx
: | |
: xxxx111xx010011111 =>
|
c*m
发帖数: 1114 | 20 这个不全面，实际有两种情况，取决于放球这一sampling的mechanism.
如果球有区别，每个盒子是空的概率是((n-1)/n)^k，总空盒子数expectation是((n-1)
/n)^k*n。
如果球没有区别，同时认为sampling是一口气放下k个球（即不考虑放球的顺序），k个
球分布到n个盒子有C(n+k-1,k)种放法，某一个盒子为空时，k个球分布到剩下n-1个盒子
有C(n+k-2,k)种放法。这样某个盒子为空的几率是(n-1)/(n+k-1).总空盒子数的expect
ation是n(n-1)/（n+k-1).第二种情况概率里面叫unordered with replacement. 这个问
题的答案取决于sampling的mechanism.
【在 c*****a 的大作中提到】
: 1.同楼上，每个盒子是空的的概率是((n-1)/n)^k,然后times盒子数
: 第三题看不懂。。。
|
