g*****i
发帖数: 2162 | 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 | c****p
发帖数: 6474 | 2 第一题把系数存成数组就行了。
你这个例子：{5 6 -7 0 -8}
3
【在 g*****i 的大作中提到】
: 先谢谢了
: 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里.对吗?
| g*****i
发帖数: 2162 | 3 原来如此,谢谢回复.
【在 c****p 的大作中提到】
: 第一题把系数存成数组就行了。
: 你这个例子：{5 6 -7 0 -8}
:
: 3
| s****e
发帖数: 139 | 4 10.
Build a array A'[i] = max(A[0...i]) take O(n) to build it
Lookup for max is O(logn) (binary search) | g*****i
发帖数: 2162 | 5 o,可以预处理那这样确实可以,thanks.
【在 s****e 的大作中提到】
: 10.
: Build a array A'[i] = max(A[0...i]) take O(n) to build it
: Lookup for max is O(logn) (binary search)
| c******r
发帖数: 225 | 6 这不就是bst找succesor问题吗？
优化可以建个balance tree
【在 g*****i 的大作中提到】
: o,可以预处理那这样确实可以,thanks.
| c******r
发帖数: 225 | 7 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.
sort the n line based on the # of numbers in each line o(nlgn)
only lines that have the same # of numbers will be compared
suppose we have a set of m lines of length k
for each line in line_set:
sort numbers in each line ~ o(klgk)
then build a hashmap as a helper data structure
for all numbers in vertical order i in range[0,k-1]
hash the m numbers at pos i to the hashmap, and count the occurrence of each
number whenever collision happens
then erase those lines with count=1 from the set
for each line with count >1, compare their next number using a new hashmap
until all arrays are exhausted
at the end of the array, remove the duplicate line # from the original set
of line #s ~ o(mk)
The sub problem shows a recursive pattern, so you will need a recursion
function for divide-n-conquer | g*****i
发帖数: 2162 | 8 谢谢回复,你的方法确实减少了很多次比较
【在 c******r 的大作中提到】
: 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.
: sort the n line based on the # of numbers in each line o(nlgn)
: only lines that have the same # of numbers will be compared
: suppose we have a set of m lines of length k
: for each line in line_set:
: sort numbers in each line ~ o(klgk)
: then build a hashmap as a helper data structure
: for all numbers in vertical order i in range[0,k-1]
| g*****i
发帖数: 2162 | 9 2,4,5,7,8这5道题有人有想法吗?谢谢.
3
【在 g*****i 的大作中提到】
: 先谢谢了
: 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里.对吗?
| r*******g
发帖数: 1335 | 10 第8题难道不是求最后stationary probability vector
http://en.wikipedia.org/wiki/Stochastic_matrix
求出来哪个大就是哪个，完全不是编程题啊。
【在 g*****i 的大作中提到】
: 2,4,5,7,8这5道题有人有想法吗?谢谢.
:
: 3
| g*****i
发帖数: 2162 | 11 恩,肯定不是编程题,概率之类的,你说的我以前没听说过,让我看看,先谢谢了.
【在 r*******g 的大作中提到】
: 第8题难道不是求最后stationary probability vector
: http://en.wikipedia.org/wiki/Stochastic_matrix
: 求出来哪个大就是哪个，完全不是编程题啊。
|
|
