由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问10个老题
相关主题
问一个search in rotated array的问题问一个算法题
请问有最近G家的Quantitative Analyst的面经吗hashtable在c++里怎么实现?
求教一道老题顶风发个amazon电面面经
二叉树如何判断一个节点是不是在另外两个节点的path上。。。。好像是个老题了。。求解?Caeercup150 原题:Find a line passes most points
问个老题,find the next larger in BSTan interview question
关于内存分配器的题。 谢谢。CS interview question
one alg from amazon百思不得其解的一道题目
请教一道题Google店面刚结束
相关话题的讨论汇总
话题: lines话题: numbers话题: line话题: array话题: 烤箱
进入JobHunting版参与讨论
1 (共1页)
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
: 求出来哪个大就是哪个,完全不是编程题啊。

1 (共1页)
进入JobHunting版参与讨论
相关主题
Google店面刚结束问个老题,find the next larger in BST
问一道题,老题不过找不到答案关于内存分配器的题。 谢谢。
MS 电面面经,攒人品one alg from amazon
两道2009算法题请教一道题
问一个search in rotated array的问题问一个算法题
请问有最近G家的Quantitative Analyst的面经吗hashtable在c++里怎么实现?
求教一道老题顶风发个amazon电面面经
二叉树如何判断一个节点是不是在另外两个节点的path上。。。。好像是个老题了。。求解?Caeercup150 原题:Find a line passes most points
相关话题的讨论汇总
话题: lines话题: numbers话题: line话题: array话题: 烤箱