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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用给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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这需要两次遍历, : 对方的想法是计算 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 头晕,找两个数要算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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第2题是用backtracking找set of balls, where the sum of weight = overall : weight/2么? : 第4题,看这里 : http://www.mitbbs.com/article_t0/JobHunting/31761509.html
|