Two CS interview questions - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Two CS interview questions

Two CS interview questions# JobHunting - 待字闺中

c*a2015-09-16 07:09

1 楼

1. Given a method (public int Rand()) that returns any random integer in the
int range, write a wrapper method that returns a random number within a
specific range [min, max], assuming int.MinValue <= min <= max <= int.
MaxValue.
my solution was: min + (Rand() - int.MinValue) * (max - min + 1) / (int.
MaxValue - int.MinValue + 1), and use long type to account for overflow
issue. is this solution correct?
2. Given a M*N matrix where some cells are blocked and there may or may not
be a cell which contains a target object. A person starts from a random cell
on the matrix and moves to find the object. You are given the below helper
method:
bool MoveUp() // Returns true and the person moves up if the upside adjacent
cell is within the border and is not blocked. Otherwise, returns false and
the person stays in current cell.
bool MoveDown()
bool MoveLeft()
bool MoveRight()
bool PickUp() // Returns true if the current cell contains the object.
Otherwise, returns false.
Describe the algorithm and write down the full code of a method (bool
FindObject(IPerson p)) to determine whether there is a target object on the
matrix or not. Note that the method takes an interface parameter.

j*r2015-09-16 07:09

2 楼

1. return min + (rand() - min) % (max - min + 1);
2. DFS (depth first search) or BFS (breadth first search)

the
not
cell
helper

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

: 1. Given a method (public int Rand()) that returns any random integer in the
: int range, write a wrapper method that returns a random number within a
: specific range [min, max], assuming int.MinValue <= min <= max <= int.
: MaxValue.
: my solution was: min + (Rand() - int.MinValue) * (max - min + 1) / (int.
: MaxValue - int.MinValue + 1), and use long type to account for overflow
: issue. is this solution correct?
: 2. Given a M*N matrix where some cells are blocked and there may or may not
: be a cell which contains a target object. A person starts from a random cell
: on the matrix and moves to find the object. You are given the below helper

c*a2015-09-16 07:09

3 楼

is this also correct or wrong? if wrong, what are potential issues? thanks.
min + Rand() * (max - min + 1) / (int.MaxValue - int.
MinValue + 1)

j*r2015-09-16 07:09

4 楼

溢出啊，来回类型cast啊，而且逻辑也完全错误，
你代入Rand() = 0, 和Rand()= int.MinValue算一下
min + Rand() * (max - min) / (int.MaxValue - int.
MinValue + 1)

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

: is this also correct or wrong? if wrong, what are potential issues? thanks.
: min + Rand() * (max - min + 1) / (int.MaxValue - int.
: MinValue + 1)

f*y2015-09-16 07:09

5 楼

From int_min to int_max, there are 2^32 numbers.
if 2^32 is not divisible by (max- min +1), then the probability is not
uniform.

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

: 1. return min + (rand() - min) % (max - min + 1);
: 2. DFS (depth first search) or BFS (breadth first search)
:
: the
: not
: cell
: helper

j*r2015-09-16 07:09

6 楼

两个整型区间互相映射，如果两者长度不互为倍数，不可能分布率完全一样。

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

: From int_min to int_max, there are 2^32 numbers.
: if 2^32 is not divisible by (max- min +1), then the probability is not
: uniform.

c*a2015-09-16 07:09

7 楼

sorry, my solution was below. this one should be logically correct. (the
previous one had a typo.)
min + (Rand() - int.MinValue) * (max - min + 1) / (int.MaxValue - int.
MinValue + 1)

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

: 溢出啊，来回类型cast啊，而且逻辑也完全错误，
: 你代入Rand() = 0, 和Rand()= int.MinValue算一下
: min + Rand() * (max - min) / (int.MaxValue - int.
: MinValue + 1)

c*a2015-09-16 07:09

8 楼

i like your modulo idea. but your solution may also have an overflow issue,
when rand() returns int.MaxValue and min is int.MinValue.
i think this modified one should work without overflow.
return min + rand() % (max - min + 1);

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

: 两个整型区间互相映射，如果两者长度不互为倍数，不可能分布率完全一样。

T*u2015-09-16 07:09

9 楼

bingo

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

: From int_min to int_max, there are 2^32 numbers.
: if 2^32 is not divisible by (max- min +1), then the probability is not
: uniform.

f*e2015-09-16 07:09

10 楼

two cs 是哪家的。。

l*n2015-09-16 07:09

11 楼

需要想办法把(M, N)和(m, n)映射到(0, N-M)和(0, n-m)，这其中用long来处理
overflow。另外丢弃qmax*(n-m)<=x <=N-M的部分即可，以保证取模时的均匀分布。遇
到丢弃即重新拿一个随机数，最坏情况是丢弃近一半，但是5次不选中概率是1/(2^5)，
十次不中是1/(2^10)，最终期望是2次。

,

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

: i like your modulo idea. but your solution may also have an overflow issue,
: when rand() returns int.MaxValue and min is int.MinValue.
: i think this modified one should work without overflow.
: return min + rand() % (max - min + 1);