x****k
发帖数: 2932 | 1 1，最近的使用multi threading的project，what's difference between mutex and
semaphore.
2. couples of balls with different weight, split them into 2 piles, 使这两堆
球有相同的总重量。
3. STL里的set是怎么实现的？有没有更快的实现方法，hash有什么缺点。
4. 1 到100的数，每个都唯一。随机拿走一个，怎么快速发现这个拿走的数。
如果随机拿走两个，怎么快速发现这两个被去掉的数？
题目挺简单，面完后就想撞墙。 |
q*******d
发帖数: 2235 | |
s*******t
发帖数: 248 | 3 Thanks for sharing.
lz哪里没发挥好？
【在 x****k 的大作中提到】
: 1，最近的使用multi threading的project，what's difference between mutex and
: semaphore.
: 2. couples of balls with different weight, split them into 2 piles, 使这两堆
: 球有相同的总重量。
: 3. STL里的set是怎么实现的？有没有更快的实现方法，hash有什么缺点。
: 4. 1 到100的数，每个都唯一。随机拿走一个，怎么快速发现这个拿走的数。
: 如果随机拿走两个，怎么快速发现这两个被去掉的数？
: 题目挺简单，面完后就想撞墙。
|
x****k
发帖数: 2932 | 4 第一个故事没编好。
最后一个如果拿走两个数怎么办？对方最后还是提示了答案 |
x******3
发帖数: 245 | 5 用给table存下1-100每个数在不在数组里，
存一遍， 扫一遍 O(n) |
x****k
发帖数: 2932 | 6 这需要两次遍历，
对方的想法是计算
1+2+3.。。+100=5050 减去剩余数的总和，得到x + y = sth
1^2+ 2^2 + 3^2 +4^2 + 5^2 +.. 100^2,再减去剩余数字square之和，得到x^2+y^2 =
sth
然后解方程。
这道题目过去经常见到，但这次才知道真正对方想要的答案。
【在 x******3 的大作中提到】
: 用给table存下1-100每个数在不在数组里，
: 存一遍， 扫一遍 O(n)
|
g*******s
发帖数: 490 | 7 第2题是用backtracking找set of balls, where the sum of weight = overall
weight/2么？
第4题，看这里
http://www.mitbbs.com/article_t0/JobHunting/31761509.html |
i**9
发帖数: 351 | 8 头晕，找两个数要算98个平方先，弄个100的array/bitmap,走一遍不更快吗，感觉interviewer
是故意的，
你说东，他偏要给来个西嘿嘿
=
【在 x****k 的大作中提到】
: 这需要两次遍历，
: 对方的想法是计算
: 1+2+3.。。+100=5050 减去剩余数的总和，得到x + y = sth
: 1^2+ 2^2 + 3^2 +4^2 + 5^2 +.. 100^2,再减去剩余数字square之和，得到x^2+y^2 =
: sth
: 然后解方程。
: 这道题目过去经常见到，但这次才知道真正对方想要的答案。
|
g*******s
发帖数: 490 | 9 那样需要size of 100的bitmap，对方考虑是memory的问题，但是算平方很明显的问题
就是有可能会overflow。
interviewer
【在 i**9 的大作中提到】
: 头晕，找两个数要算98个平方先，弄个100的array/bitmap,走一遍不更快吗，感觉interviewer
: 是故意的，
: 你说东，他偏要给来个西嘿嘿
:
: =
|
P********l
发帖数: 452 | |
x****k
发帖数: 2932 | 11 第2题我给对方报了个DP的解法，但不知道对方怎么想的。
设f(x)是总重量为x时若干球的集合。
问题变为求f(weight/2),设第i个球的重量为wi, 则
f(n) = f(n - w1) + 球1 || f(n - w2) + 球2 || ... || f(n - wn) + 球n
然后迭代下去。可能无解。
【在 g*******s 的大作中提到】
: 第2题是用backtracking找set of balls, where the sum of weight = overall
: weight/2么？
: 第4题，看这里
: http://www.mitbbs.com/article_t0/JobHunting/31761509.html
|
