C***U
发帖数: 2406 | 1 1 一个不知道长度的数组，让你随机取出1000个数字。只能走一边。只能常数空间。
2 有一个数组，然后你和另外一个人两头开始取数字。每次你只能取两头里面的某一个
数字。让你设计一种策略，使得你取的数字尽可能大。 |
h****n
发帖数: 1093 | 2 第一题 resevior sampling
第二题
2个的话，先取则赢
3 1
3个的话，中间那个如果比两边和大，则先取必输，否则则先取必赢
2 4 1
4 1 2
1 2 4
4个的话 分成两组，奇数位一组，偶数位一组，那组大则先取哪组，先取必赢
1 2 3 4
现在可以推出规律了，分成两组，奇数位一组，偶数位一组，看哪组和最大，最大的话
先取哪组，然后一直保持取那一组的数即可
比如
1 2 3 4 5 6
偶数位和比较大，先取6 ，对方只能取1或者5，取1你就取2，取5你就取4，保持对方取
奇数位上的就行了
话说楼主真是面霸啊。。。各大公司面试你都去了 |
t*******2
发帖数: 292 | 3 同意第三句
【在 h****n 的大作中提到】
: 第一题 resevior sampling
: 第二题
: 2个的话，先取则赢
: 3 1
: 3个的话，中间那个如果比两边和大，则先取必输，否则则先取必赢
: 2 4 1
: 4 1 2
: 1 2 4
: 4个的话 分成两组，奇数位一组，偶数位一组，那组大则先取哪组，先取必赢
: 1 2 3 4
|
C***U
发帖数: 2406 | 4 我除了google
别的都是小公司面试。。。。
版上大牛都是flag一起面的
别取笑我了
这个小公司肯定挂了
那个resevior sampling还发论文了。。。晕
那我那么几分钟咋想的到啊！
好吧。。。
【在 h****n 的大作中提到】
: 第一题 resevior sampling
: 第二题
: 2个的话，先取则赢
: 3 1
: 3个的话，中间那个如果比两边和大，则先取必输，否则则先取必赢
: 2 4 1
: 4 1 2
: 1 2 4
: 4个的话 分成两组，奇数位一组，偶数位一组，那组大则先取哪组，先取必赢
: 1 2 3 4
|
d**********x
发帖数: 4083 | 5 未必就要你答出来
当年我面ms intern的时候就面的我这个，嘿嘿。。= =
【在 C***U 的大作中提到】
: 我除了google
: 别的都是小公司面试。。。。
: 版上大牛都是flag一起面的
: 别取笑我了
: 这个小公司肯定挂了
: 那个resevior sampling还发论文了。。。晕
: 那我那么几分钟咋想的到啊！
: 好吧。。。
|
C***U
发帖数: 2406 | 6 你自己想出来了？
还是事先知道？
【在 d**********x 的大作中提到】
: 未必就要你答出来
: 当年我面ms intern的时候就面的我这个，嘿嘿。。= =
|
K*********n
发帖数: 2852 | 7 加油加油，有offer了没？
我正在面Seattle的Saas公司，最后一轮，还分成两天……
周三面四个公司，从在上8点到下午5点……
【在 C***U 的大作中提到】
: 1 一个不知道长度的数组，让你随机取出1000个数字。只能走一边。只能常数空间。
: 2 有一个数组，然后你和另外一个人两头开始取数字。每次你只能取两头里面的某一个
: 数字。让你设计一种策略，使得你取的数字尽可能大。
|
C***U
发帖数: 2406 | 8 加油！
【在 K*********n 的大作中提到】
: 加油加油，有offer了没？
: 我正在面Seattle的Saas公司，最后一轮，还分成两天……
: 周三面四个公司，从在上8点到下午5点……
|
l*****a
发帖数: 14598 | 9 what is the name of the company?
卖力？
【在 K*********n 的大作中提到】
: 加油加油，有offer了没？
: 我正在面Seattle的Saas公司，最后一轮，还分成两天……
: 周三面四个公司，从在上8点到下午5点……
|
K*********n
发帖数: 2852 | 10 concur
这公司好像名气不大？看起来是个几千人的上市公司，规模还可以。不过找得到关于他
们的东西比较少。版上没见讨论过。
另外还没给offer就说了没有relocation，in-persion interview是skype，感觉很小气
啊。
【在 l*****a 的大作中提到】
: what is the name of the company?
: 卖力？
|
|
|
d**********x
发帖数: 4083 | 11 没想出来。。。。
但是他们要我了当时。。
【在 C***U 的大作中提到】
: 你自己想出来了？
: 还是事先知道？
|
C***U
发帖数: 2406 | 12 这个不一样M家看得东西多
这些小公司一般就看你行不行
不行就知道不要你了
【在 d**********x 的大作中提到】
: 没想出来。。。。
: 但是他们要我了当时。。
|
h****n
发帖数: 1093 | 13 2个的话，先取则赢
3 1
3个的话，中间那个如果比两边和大，则先取必输，否则则先取必赢
2 4 1
4 1 2
1 2 4
4个的话 分成两组，奇数位一组，偶数位一组，那组大则先取哪组，先取必赢
1 2 3 4
现在可以推出规律了，分成两组，奇数位一组，偶数位一组，看哪组和最大，最大的话
先取哪组，然后一直保持取那一组的数即可
比如
1 2 3 4 5 6
偶数位和比较大，先取6 ，对方只能取1或者5，取1你就取2，取5你就取4，保持对方取
奇数位上的就行了 |
h****n
发帖数: 1093 | 14 牛人。。。精力充沛的很
【在 K*********n 的大作中提到】
: 加油加油，有offer了没？
: 我正在面Seattle的Saas公司，最后一轮，还分成两天……
: 周三面四个公司，从在上8点到下午5点……
|
l*****a
发帖数: 14598 | 15 标题党
以为ZGNA关门了
【在 C***U 的大作中提到】
: 1 一个不知道长度的数组，让你随机取出1000个数字。只能走一边。只能常数空间。
: 2 有一个数组，然后你和另外一个人两头开始取数字。每次你只能取两头里面的某一个
: 数字。让你设计一种策略，使得你取的数字尽可能大。
|
Q*******e
发帖数: 939 | 16 赞
【在 h****n 的大作中提到】
: 第一题 resevior sampling
: 第二题
: 2个的话，先取则赢
: 3 1
: 3个的话，中间那个如果比两边和大，则先取必输，否则则先取必赢
: 2 4 1
: 4 1 2
: 1 2 4
: 4个的话 分成两组，奇数位一组，偶数位一组，那组大则先取哪组，先取必赢
: 1 2 3 4
|
l******d
发帖数: 530 | 17 epic成了小公司？
【在 C***U 的大作中提到】
: 我除了google
: 别的都是小公司面试。。。。
: 版上大牛都是flag一起面的
: 别取笑我了
: 这个小公司肯定挂了
: 那个resevior sampling还发论文了。。。晕
: 那我那么几分钟咋想的到啊！
: 好吧。。。
|
p*****2
发帖数: 21240 | 18
如果是odd number的怎么办？
【在 h****n 的大作中提到】
: 第一题 resevior sampling
: 第二题
: 2个的话，先取则赢
: 3 1
: 3个的话，中间那个如果比两边和大，则先取必输，否则则先取必赢
: 2 4 1
: 4 1 2
: 1 2 4
: 4个的话 分成两组，奇数位一组，偶数位一组，那组大则先取哪组，先取必赢
: 1 2 3 4
|
h****n
发帖数: 1093 | 19 Good point 数量是偶数位的先取必胜策略大家都知道了
那么如果一共有总是奇数呢
考虑一下一个情况
1 2 3 4 5 6 7
任意先取一边都将转化成偶数位的情况，且这个时候对方先取，此时对方必胜
比如你取1那么 转成 2 3 4 5 6 7 不考虑1的话，对方会胜你3，先前取的是1，所以你
还输对方 2
你取7那么转成1 2 3 4 5 6 不考虑 7的话对方同样会胜你3 但是先前有7，所以你先取
还是必胜的
那么你要评估 两边最大的那个数拿出来之后，对方会胜你多少，如果最大的那个数比
对方胜你的数多的话，那么你还是可以选择先取的，否则宁愿选择对方先取
【在 p*****2 的大作中提到】
:
: 如果是odd number的怎么办？
|
p*****2
发帖数: 21240 | 20
其实这题要求的不是谁胜谁负，而是要求怎么可以取得最大值。即使你输了，你还是可
以取得你最大值的，即使你胜了，你也不能保证你取的是最大值。
这题应该是到DP题。
【在 h****n 的大作中提到】
: Good point 数量是偶数位的先取必胜策略大家都知道了
: 那么如果一共有总是奇数呢
: 考虑一下一个情况
: 1 2 3 4 5 6 7
: 任意先取一边都将转化成偶数位的情况，且这个时候对方先取，此时对方必胜
: 比如你取1那么 转成 2 3 4 5 6 7 不考虑1的话，对方会胜你3，先前取的是1，所以你
: 还输对方 2
: 你取7那么转成1 2 3 4 5 6 不考虑 7的话对方同样会胜你3 但是先前有7，所以你先取
: 还是必胜的
: 那么你要评估 两边最大的那个数拿出来之后，对方会胜你多少，如果最大的那个数比
|
|
|
h****n
发帖数: 1093 | 21 不知道题目是要求必胜策略呢还是要求求最大值，不过不管是什么，先取后取关系差别
很大 |
p*****2
发帖数: 21240 | 22
让你设计一种策略，使得你取的数字尽可能大。
【在 h****n 的大作中提到】
: 不知道题目是要求必胜策略呢还是要求求最大值，不过不管是什么，先取后取关系差别
: 很大
|
l*******b
发帖数: 2586 | 23 听一个同学讲过第二个，很有意思呀
【在 C***U 的大作中提到】
: 1 一个不知道长度的数组，让你随机取出1000个数字。只能走一边。只能常数空间。
: 2 有一个数组，然后你和另外一个人两头开始取数字。每次你只能取两头里面的某一个
: 数字。让你设计一种策略，使得你取的数字尽可能大。
|
l*******b
发帖数: 2586 | 24 反过来想吧，如果你不按那个策略，对手按那个策略，对手就比你取得大，所以一开始
你按这个策略走肯定比不按这个策略取得大。
【在 p*****2 的大作中提到】
:
: 让你设计一种策略，使得你取的数字尽可能大。
|
h****n
发帖数: 1093 | 25 那还是回到必胜策略的问题上来了
对方也是很理智的人，你要是不按照必胜策略来，你就输了，也谈不上取得最大了
【在 l*******b 的大作中提到】
: 反过来想吧，如果你不按那个策略，对手按那个策略，对手就比你取得大，所以一开始
: 你按这个策略走肯定比不按这个策略取得大。
|
C***U
发帖数: 2406 | 26 对 我的解答基本就是dp的意思。但是这个dp还是根据对手选择来变化的。
【在 p*****2 的大作中提到】
:
: 让你设计一种策略，使得你取的数字尽可能大。
|
A**u
发帖数: 2458 | 27 可惜啊...
1. 静下来，从2，3，4，5,试试，就找出规律啦
2. 动态规划问题.
找最大和Max-gain(1,n)，等价于找“比对手最多赢多少”max-diff(1,n) +
max-diff(i,j) 为
1, A[i] - max-diff(i+1,j)
2, A[j] - max=diff(i,j-1)
的两个最大值
边界--- max-diff(i,i) = A[i] only one left, and it's A's turn.
用DP...反着做，O(N^2)
大牛。。太可惜了...
【在 C***U 的大作中提到】
: 1 一个不知道长度的数组，让你随机取出1000个数字。只能走一边。只能常数空间。
: 2 有一个数组，然后你和另外一个人两头开始取数字。每次你只能取两头里面的某一个
: 数字。让你设计一种策略，使得你取的数字尽可能大。
|
p*****2
发帖数: 21240 | 28
看上边所述，greedy可以搞定，我刚才想了想，没想出反例。
【在 C***U 的大作中提到】
: 对 我的解答基本就是dp的意思。但是这个dp还是根据对手选择来变化的。
|
A**u
发帖数: 2458 | 29 你们怎么都会greedy
贪婪算法不是要证明“有效性”吗？
这玩意面试能搞定吗？
【在 p*****2 的大作中提到】
:
: 看上边所述，greedy可以搞定，我刚才想了想，没想出反例。
|
C***U
发帖数: 2406 | 30 我做了dp 但是我觉得不对
他说是对的
当然没时间讨论细节
不过还是觉得自己弱。第一题 大牛一见就会做
我完全没头绪
【在 A**u 的大作中提到】
: 可惜啊...
: 1. 静下来，从2，3，4，5,试试，就找出规律啦
: 2. 动态规划问题.
: 找最大和Max-gain(1,n)，等价于找“比对手最多赢多少”max-diff(1,n) +
: max-diff(i,j) 为
: 1, A[i] - max-diff(i+1,j)
: 2, A[j] - max=diff(i,j-1)
: 的两个最大值
: 边界--- max-diff(i,i) = A[i] only one left, and it's A's turn.
: 用DP...反着做，O(N^2)
|
|
|
k***g
发帖数: 58 | 31 第二题 DP, O(n^2)
p(i,j) = max { A[i] + min {p(i+2,j), p(i+1,j-1)},
A[j] + min {p(i,j-2), p(i+1,j-1)} } |
C***U
发帖数: 2406 | 32 这个式子就是我一开头写的
【在 k***g 的大作中提到】
: 第二题 DP, O(n^2)
: p(i,j) = max { A[i] + min {p(i+2,j), p(i+1,j-1)},
: A[j] + min {p(i,j-2), p(i+1,j-1)} }
|
C***U
发帖数: 2406 | 33 主要问题是你这个式子不够。 还要设计对应战术 所以其实每次对手选完 不是按照你
设想的走的话 要重新算一次 我当时这点没想明白
【在 k***g 的大作中提到】
: 第二题 DP, O(n^2)
: p(i,j) = max { A[i] + min {p(i+2,j), p(i+1,j-1)},
: A[j] + min {p(i,j-2), p(i+1,j-1)} }
|
p*****2
发帖数: 21240 | 34
不管对手怎么走，剩下的数字都是你以前早已经计算出来的结果。
比如
a1, a2, a3, a4, a5
不管对手取a1 还是 a5
你已经有了结果
a2, a3, a4, a5 和 a1, a2, a3, a4 了。
所以对手怎么走不影响你的DP。
【在 C***U 的大作中提到】
: 主要问题是你这个式子不够。 还要设计对应战术 所以其实每次对手选完 不是按照你
: 设想的走的话 要重新算一次 我当时这点没想明白
|
C***U
发帖数: 2406 | 35 那就要记录很多
【在 p*****2 的大作中提到】
:
: 不管对手怎么走，剩下的数字都是你以前早已经计算出来的结果。
: 比如
: a1, a2, a3, a4, a5
: 不管对手取a1 还是 a5
: 你已经有了结果
: a2, a3, a4, a5 和 a1, a2, a3, a4 了。
: 所以对手怎么走不影响你的DP。
|
r*********n
发帖数: 4553 | 36 1.
假设当前考虑第n个数， n>1000，如果n<=1000，直接选上。
从之前的1000个选出来的数里随机选一个出来，以（n-1000）/n的概率和当前数交换。
PS：一个simplified version的问题是：选一个数，要求均匀分布，one pass algo
2. 你的问题是不是 Optimal Strategy for a Game.：
Consider a row of n coins of values v(1) ... v(n), where n is even. We play
a game against an opponent by alternating turns. In each turn, a player
selects either the first or last coin from the row, removes it from the row
permanently, and receives the value of the coin. Determine the maximum
possible amount of money we can definitely win if we move first.
如果是的话，参考
http://people.csail.mit.edu/bdean/6.046/dp/
【在 C***U 的大作中提到】
: 1 一个不知道长度的数组，让你随机取出1000个数字。只能走一边。只能常数空间。
: 2 有一个数组，然后你和另外一个人两头开始取数字。每次你只能取两头里面的某一个
: 数字。让你设计一种策略，使得你取的数字尽可能大。
|
