share avoderm的哭胖...# pets - 心有所宠
g*i
1 楼
先谢谢了
1. 算POLYNOMIAL，比如5x^4+6x^3-7x^2-8=?
原文说思路是减少乘法变成x^2(x(5x+6)-7)-8, 然后找数据结构存数字和运算符.
我的问题是什么数据结构呢?是否要存prefix notation?
2.给你三个烤箱，每个烤箱可以同时烤两片面包，需要的时间分别是3分钟，4分钟和3
分钟。但第三个烤箱有一个slot出了点问题，每次只能烤面包的一面。所以这个烤箱三
分钟后只能算烤好一片半面包，你需要把那半片翻个面，在同一个slot里再烤一次才算
一片完整的。现在给你这三个烤箱，问烤好21片面包最少需要多少时间？如果是2100片
呢？如果是任意给定的N片，要求O(1)时间内给出最少需要的时间。
我的思路:12分钟正好20片没浪费,1-19事先算好存在array里.对吗?
3. read n lines of random numbers(space as delimiter) from a file, lines
with same numbers are treated as duplicated lines, regardless of the order.
check and print non-duplicate lines. performance time analysis.
我的思路:对每行排序然后用很多质数相乘算hash?
4. Given a 3x3 square:
1 2 3
4 5 6
7 8 9
You are allowed to do circular shift on any row, and circular shift on any
column, as many times as you please. Question: can you switch position of 1
and 2 with the allowed circular shifts?
5.两个玩家， 一堆石头，假设多于100块, 两人依次拿， 最后拿光者赢， 规则是
1. 第一个人不能一次拿光所有的
2. 第一次拿了之后， 每人每次最多只能拿对方前一次拿的数目的两倍
求先拿者必胜策略, 如果有的话
这是精华区里有的
http://www.mitbbs.com/bbsann2/life.faq/JobHunting/16/M.12843212
答案是先拿到fib的人必输,先拿非fib的人可以让后拿的人先拿fib,这怎么证明呢?
6. The gmail page loads very slow. any suggestion for improvement?
7.任务分配，假设有N个任务，每个任务需要W_i工作量，M个人，每人每天能做工作量w
_i，如何安排工作，使得所有工作能最快完成。这个问题其实更像一个开放性问题，因
为一个合理的贪心策略，最后的结果跟最优结是很接近的(大致上，最多只差一天)。
8.有n个房间，小偷每天偷一间，偷的规律简单说就是随机行走，如果今天偷了第i间屋
子，明天有一半的几率偷i-1，一半的几率偷i+1，注意如果刚好偷到了边界上，那么第
二天只有唯一的选择。如果你是警察，你只能每天选择一个房间蹲守，并且贼的手段相
当高明，偷了一个房间后，没有任何人能发觉该房间是否曾经被偷过。
板上应该讨论过,但是我找不到.网上有人说是第二间或者倒数第二间,因为前2天抓住的
概率大,但是总的概率如何呢?
9. How do you measure context switch time in OS? any ideas?
10.First greater number in an array.
Given a large array of positive integers, for an arbitrary integer A, we
want to know the first integer in the array which is greater than or equal A
. O(logn) solution required.
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80
1. 算POLYNOMIAL，比如5x^4+6x^3-7x^2-8=?
原文说思路是减少乘法变成x^2(x(5x+6)-7)-8, 然后找数据结构存数字和运算符.
我的问题是什么数据结构呢?是否要存prefix notation?
2.给你三个烤箱，每个烤箱可以同时烤两片面包，需要的时间分别是3分钟，4分钟和3
分钟。但第三个烤箱有一个slot出了点问题，每次只能烤面包的一面。所以这个烤箱三
分钟后只能算烤好一片半面包，你需要把那半片翻个面，在同一个slot里再烤一次才算
一片完整的。现在给你这三个烤箱，问烤好21片面包最少需要多少时间？如果是2100片
呢？如果是任意给定的N片，要求O(1)时间内给出最少需要的时间。
我的思路:12分钟正好20片没浪费,1-19事先算好存在array里.对吗?
3. read n lines of random numbers(space as delimiter) from a file, lines
with same numbers are treated as duplicated lines, regardless of the order.
check and print non-duplicate lines. performance time analysis.
我的思路:对每行排序然后用很多质数相乘算hash?
4. Given a 3x3 square:
1 2 3
4 5 6
7 8 9
You are allowed to do circular shift on any row, and circular shift on any
column, as many times as you please. Question: can you switch position of 1
and 2 with the allowed circular shifts?
5.两个玩家， 一堆石头，假设多于100块, 两人依次拿， 最后拿光者赢， 规则是
1. 第一个人不能一次拿光所有的
2. 第一次拿了之后， 每人每次最多只能拿对方前一次拿的数目的两倍
求先拿者必胜策略, 如果有的话
这是精华区里有的
http://www.mitbbs.com/bbsann2/life.faq/JobHunting/16/M.12843212
答案是先拿到fib的人必输,先拿非fib的人可以让后拿的人先拿fib,这怎么证明呢?
6. The gmail page loads very slow. any suggestion for improvement?
7.任务分配，假设有N个任务，每个任务需要W_i工作量，M个人，每人每天能做工作量w
_i，如何安排工作，使得所有工作能最快完成。这个问题其实更像一个开放性问题，因
为一个合理的贪心策略，最后的结果跟最优结是很接近的(大致上，最多只差一天)。
8.有n个房间，小偷每天偷一间，偷的规律简单说就是随机行走，如果今天偷了第i间屋
子，明天有一半的几率偷i-1，一半的几率偷i+1，注意如果刚好偷到了边界上，那么第
二天只有唯一的选择。如果你是警察，你只能每天选择一个房间蹲守，并且贼的手段相
当高明，偷了一个房间后，没有任何人能发觉该房间是否曾经被偷过。
板上应该讨论过,但是我找不到.网上有人说是第二间或者倒数第二间,因为前2天抓住的
概率大,但是总的概率如何呢?
9. How do you measure context switch time in OS? any ideas?
10.First greater number in an array.
Given a large array of positive integers, for an arbitrary integer A, we
want to know the first integer in the array which is greater than or equal A
. O(logn) solution required.
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80
