y*****e
发帖数: 712 | 1 今天面的第二轮。。。面完很伤心很失望，下午上了一下午班后，感觉好了点，开始觉
得自己发挥的好差，题也不容易，为啥别人都能碰到常见的常规的题，我就碰不到。。
。。不够难过的时候怪运气是太容易的事了，但现在冷静下来感觉，不过是给自己找借
口罢了。发面经上来，给自己差劲的人品增值，希望将来的面试顺利。
第一轮两道题
1. first missing positive
2. 写一个file line iterator
Implement a (Java) Iterable object that iterates lines one by one from a
text file..
/** A reference to a file. */
public class TextFile implements Iterable. From 1point 3acres bbs
{
public TextFile(String fileName) { // please implement this
/** Begin reading the file, line by line. The returned Iterator.next()
will return a line. */
@Override
public Iterator iterator() { // please implement this
第二题没见过。。。但准备了不少iterator的题，算是有思路，磕磕巴巴的写完了。这
一轮就这么过了。
今天第二轮，是一个同胞和一个美国女孩面的，同胞一直没说话，除了开始你好最后再
见。。。估计还在training阶段，全程都是那个女孩面的。
第一题是twoSum, 前两天面经里刚看过，也是两种方法，optimize store efficiency
和optimize test efficiency都写了。但写4 = 2 + 2这种情况竟然被我写出了一个bug
，真是不应该，过test case也没发现，结果是面试官指出来的。。。当时就好囧，想
第二题要好好写了，没想到第二题才是悲剧的开始。。。
第二题叫canIwin, 是两个人轮流取数，取过的不能再用，把取过的数都加起来，谁先
取到目标数谁赢。
题目在这里
/* In "the 100 game," two players take turns adding, to a running
total, any integer from 1..10. The player who first causes the running
total to reach or exceed 100 wins.
What if we change the game so that players cannot re-use integers?
For example, if two players might take turns drawing from a common pool of
numbers
of 1..15 without replacement until they reach a total >= 100. This problem
is
to write a program that determines which player would win with ideal play.
Write a procedure, "Boolean canIWin(int maxChoosableInteger, int
desiredTotal)",
which returns true if the first player to move can force a win with optimal
play.
Your priority should be programmer efficiency; don't focus on minimizing
either space or time complexity.
*/
Boolean canIWin(int maxChoosableInteger, int desiredTotal) {
// Implementation here. Write yours
}
然后我就傻眼了。。。。我看明白题都花了好多时间，感觉这种博弈的题，大概是dfs
是最简单直接的。。。。也没想啥更简单的方法，时间也没多少了，马上开始写。。。
结果写出来两个bug...>_<, 然后她指出来这两个bug之后，我就觉得生无可恋了，改了
之后，她让我问问题，我也不想问了，直接就想挂电话。。。
感觉自己还是基本功不扎实，碰到没见过的题很容易慌，再有就是太容易放弃了，其实
我的思路是对的，如果肯沉下心来写对它，也许还有翻盘的机会。但看着时间一点点过
去，状态已经很浮躁了，以至于过程十分痛苦+惨烈，而且那个女面试官也不够友好，
有点凶，哎，女人何苦为难女人呢，
后来我查面经，这题今年没怎么出现过，但14年出现过两次，所以如果肯下功夫过面经
的话，也是能看到的。所以要不就很牛，当场写也没问题，要不就肯下苦功，把所有的
题都过一遍，我两头都不占，失败也是必然的吧。。。人生不如意事常89，move on吧
。希望对正在面L的人有用。 |
g****o
发帖数: 547 | 2 The player who first causes the running
total to reach or exceed 100 wins.
超过100也赢
那岂不是大家都从大取到小？ |
y*****e
发帖数: 712 | 3 应该从小的开始取，自己才有机会赢。取大的，剩下小的目标值给对方，对方就赢了。
这是愚蠢的lz唯一在面试的时候想清楚的事情。
【在 g****o 的大作中提到】
: The player who first causes the running
: total to reach or exceed 100 wins.
: 超过100也赢
: 那岂不是大家都从大取到小？
|
g****o
发帖数: 547 | 4 为啥？
题目不是超过100也算赢么？ 又不是正好100才算赢
【在 y*****e 的大作中提到】
: 应该从小的开始取，自己才有机会赢。取大的，剩下小的目标值给对方，对方就赢了。
: 这是愚蠢的lz唯一在面试的时候想清楚的事情。
|
n******n
发帖数: 12088 | 5 贪心法不行，相当于你在给对手做球。
比如已经是88，你只能取1，这样对手无论怎么拿，你都赢。
【在 g****o 的大作中提到】
: The player who first causes the running
: total to reach or exceed 100 wins.
: 超过100也赢
: 那岂不是大家都从大取到小？
|
n******n
发帖数: 12088 | 6 这个应该有必胜策略。
【在 y*****e 的大作中提到】
: 应该从小的开始取，自己才有机会赢。取大的，剩下小的目标值给对方，对方就赢了。
: 这是愚蠢的lz唯一在面试的时候想清楚的事情。
|
g****o
发帖数: 547 | 7 哦 明白了
我以为各自取数求和呢
题目意思是每个人分别取数，求总和。
【在 n******n 的大作中提到】
: 贪心法不行，相当于你在给对手做球。
: 比如已经是88，你只能取1，这样对手无论怎么拿，你都赢。
|
y*****e
发帖数: 712 | 8 可是取过的不能再取了啊，先取大的，后面只剩小数了，对方再取小数最大的，他就赢
了啊。
【在 g****o 的大作中提到】
: 为啥？
: 题目不是超过100也算赢么？ 又不是正好100才算赢
|
n******n
发帖数: 12088 | 9 第一题写太快，被看出来练过，所以来道难题？
【在 y*****e 的大作中提到】
: 今天面的第二轮。。。面完很伤心很失望，下午上了一下午班后，感觉好了点，开始觉
: 得自己发挥的好差，题也不容易，为啥别人都能碰到常见的常规的题，我就碰不到。。
: 。。不够难过的时候怪运气是太容易的事了，但现在冷静下来感觉，不过是给自己找借
: 口罢了。发面经上来，给自己差劲的人品增值，希望将来的面试顺利。
: 第一轮两道题
: 1. first missing positive
: 2. 写一个file line iterator
: Implement a (Java) Iterable object that iterates lines one by one from a
: text file..
: /** A reference to a file. */
|
n******n
发帖数: 12088 | 10 是楼主没说清楚。
【在 g****o 的大作中提到】
: 哦 明白了
: 我以为各自取数求和呢
: 题目意思是每个人分别取数，求总和。
|
|
|
j********l
发帖数: 325 | 11 第二轮第二道的确是面经里面的，careercup上面有。
【在 y*****e 的大作中提到】
: 今天面的第二轮。。。面完很伤心很失望，下午上了一下午班后，感觉好了点，开始觉
: 得自己发挥的好差，题也不容易，为啥别人都能碰到常见的常规的题，我就碰不到。。
: 。。不够难过的时候怪运气是太容易的事了，但现在冷静下来感觉，不过是给自己找借
: 口罢了。发面经上来，给自己差劲的人品增值，希望将来的面试顺利。
: 第一轮两道题
: 1. first missing positive
: 2. 写一个file line iterator
: Implement a (Java) Iterable object that iterates lines one by one from a
: text file..
: /** A reference to a file. */
|
n******n
发帖数: 12088 | 12 第一问很简单。先取的一方拿1，对方取多少，你就用11减掉，必胜。
【在 y*****e 的大作中提到】
: 可是取过的不能再取了啊，先取大的，后面只剩小数了，对方再取小数最大的，他就赢
: 了啊。
|
y*****e
发帖数: 712 | 13 目标数不是100啊，这也是一个variable来的。你看function signature，
desiredvariable是目标数
【在 n******n 的大作中提到】
: 第一问很简单。先取的一方拿1，对方取多少，你就用11减掉，必胜。
|
y*****e
发帖数: 712 | 14 有可能。。。。这题我刚做过，还在memory cache的最外面，读取数据的时候那个快啊
。。。
【在 n******n 的大作中提到】
: 第一题写太快，被看出来练过，所以来道难题？
|
n******n
发帖数: 12088 | 15 类似的思路。最小加最大，和目标求余数，然后拿那个余数，必胜。
【在 y*****e 的大作中提到】
: 目标数不是100啊，这也是一个variable来的。你看function signature，
: desiredvariable是目标数
|
d*****c
发帖数: 605 | 16 应该没出结果吧？ 别太难过，再等等看看。
【在 y*****e 的大作中提到】
: 今天面的第二轮。。。面完很伤心很失望，下午上了一下午班后，感觉好了点，开始觉
: 得自己发挥的好差，题也不容易，为啥别人都能碰到常见的常规的题，我就碰不到。。
: 。。不够难过的时候怪运气是太容易的事了，但现在冷静下来感觉，不过是给自己找借
: 口罢了。发面经上来，给自己差劲的人品增值，希望将来的面试顺利。
: 第一轮两道题
: 1. first missing positive
: 2. 写一个file line iterator
: Implement a (Java) Iterable object that iterates lines one by one from a
: text file..
: /** A reference to a file. */
|
p*****r
发帖数: 1883 | 17 不要紧张，这是模拟类的题目，套路就是模拟题的想策略的解法，第一问允许重复是热
身，这里有个必胜策略就是不要让对方剩下的数字低于10，所以你方的目标是取到89，
这个目标之前的目标是取到78，再之前就是67，56，45，34，23，12，反复重复直到第
一次抢先取1就行，第二次取10，第三次再取1（达到11的目标）。第二问说不允许重复
的策略也是类似想法但是不能猥琐的取1＋10，但还是按照每个目标来取，1，2+9，3+8
，4+7这样一对一对的取就行了。这个必胜策略只适用于100，超过100再不允许重复就
不行了。
还是那句话，leetcode瞎刷没用，要按照套路来。
【在 y*****e 的大作中提到】
: 应该从小的开始取，自己才有机会赢。取大的，剩下小的目标值给对方，对方就赢了。
: 这是愚蠢的lz唯一在面试的时候想清楚的事情。
|
n******n
发帖数: 12088 | 18 第二问是1到15，且大于等于100。
+8
【在 p*****r 的大作中提到】
: 不要紧张，这是模拟类的题目，套路就是模拟题的想策略的解法，第一问允许重复是热
: 身，这里有个必胜策略就是不要让对方剩下的数字低于10，所以你方的目标是取到89，
: 这个目标之前的目标是取到78，再之前就是67，56，45，34，23，12，反复重复直到第
: 一次抢先取1就行，第二次取10，第三次再取1（达到11的目标）。第二问说不允许重复
: 的策略也是类似想法但是不能猥琐的取1＋10，但还是按照每个目标来取，1，2+9，3+8
: ，4+7这样一对一对的取就行了。这个必胜策略只适用于100，超过100再不允许重复就
: 不行了。
: 还是那句话，leetcode瞎刷没用，要按照套路来。
|
d******a
发帖数: 238 | 19 感觉你说的是对的。你能写个程序看看吗？
热身，这里有个必胜策略就是不要让对方剩下的数字低于10，所以你方的目标是取到89
，这个目标之前的目标是取到78，再之前就是67，56，45，34，23，12，反复重复直到
第一次抢先取1就行，第二次取10，第三次再取1（达到11的目标）。第二问说不允许重
复的策略也是类似想法但是不能猥琐的取1＋10，但还是按照每个目标来取，1，2+9，3
+8，4+7这样一对一对的取就行了。这个必胜策略只适用于100，超过100再不允许重复就 |
r****7
发帖数: 2282 | 20 你的第二轮面经是我电面的面经，careercup上也有
我打算自己offer定了发所有面经回馈版面，可惜offer一直没定下来。。。
其实第二题就是lc的permutation，用dp的话能变成2^n复杂度.
【在 y*****e 的大作中提到】
: 今天面的第二轮。。。面完很伤心很失望，下午上了一下午班后，感觉好了点，开始觉
: 得自己发挥的好差，题也不容易，为啥别人都能碰到常见的常规的题，我就碰不到。。
: 。。不够难过的时候怪运气是太容易的事了，但现在冷静下来感觉，不过是给自己找借
: 口罢了。发面经上来，给自己差劲的人品增值，希望将来的面试顺利。
: 第一轮两道题
: 1. first missing positive
: 2. 写一个file line iterator
: Implement a (Java) Iterable object that iterates lines one by one from a
: text file..
: /** A reference to a file. */
|
|
|
c*******7
发帖数: 438 | 21 看了半天才看明白，原来那个和是两个player是共享的，谁的回合里把这个和加到超过
100谁赢。
一直以为是每人一个和各自算。。。 |
d******a
发帖数: 238 | 22 把第二题帖个代码看看？没看出和permutation有联系 |
n******n
发帖数: 12088 | 23 就是暴力解法，排列时求和，前奇数项超100，先手赢，前偶数项超100，后手赢。
【在 d******a 的大作中提到】
: 把第二题帖个代码看看？没看出和permutation有联系
|
y*****e
发帖数: 712 | 24 我跟你写的差不多，不过used_positions java里不能这么传，要不回到第一层所有的
都是position都被mark false了，这是她指出的两个bug之一。。。
你咋不早点发面经，你发了我肯定会看的，我看了就不会写的这么狼狈了，哎都是命啊
。。。你的面试官也是一个美国女孩吗？
【在 r****7 的大作中提到】
: 你的第二轮面经是我电面的面经，careercup上也有
: 我打算自己offer定了发所有面经回馈版面，可惜offer一直没定下来。。。
: 其实第二题就是lc的permutation，用dp的话能变成2^n复杂度.
|
r****7
发帖数: 2282 | 25 为啥会都被mark false？每一层都先set true然后递归出来set false啊，我觉得即使
java也是一样的吧。
我是一个白男面的，L家就这个interviewer觉得还不错，别的都是典型的烙印和让人无
力吐槽的老中，和啥都不懂的老美。。。觉得没啥好去的。
【在 y*****e 的大作中提到】
: 我跟你写的差不多，不过used_positions java里不能这么传，要不回到第一层所有的
: 都是position都被mark false了，这是她指出的两个bug之一。。。
: 你咋不早点发面经，你发了我肯定会看的，我看了就不会写的这么狼狈了，哎都是命啊
: 。。。你的面试官也是一个美国女孩吗？
|
s******7
发帖数: 1758 | 26 你这个就是全排列，只要其中有个排列能赢，就返回true, 只能算有赢的可能，怎么能
算有必胜的的策略，要判断必胜的话，得无论对手怎么下，你都能赢， 得有两个递归
方法交替来，其中一个是对手的必须每个都返回true, 另外一个算自己的只要一个能赢
就行。
【在 r****7 的大作中提到】
: 为啥会都被mark false？每一层都先set true然后递归出来set false啊，我觉得即使
: java也是一样的吧。
: 我是一个白男面的，L家就这个interviewer觉得还不错，别的都是典型的烙印和让人无
: 力吐槽的老中，和啥都不懂的老美。。。觉得没啥好去的。
|
n******n
发帖数: 12088 | 27 从函数名看是对的。 can I win？不是can I always win。
后者电面不合适。
【在 s******7 的大作中提到】
: 你这个就是全排列，只要其中有个排列能赢，就返回true, 只能算有赢的可能，怎么能
: 算有必胜的的策略，要判断必胜的话，得无论对手怎么下，你都能赢， 得有两个递归
: 方法交替来，其中一个是对手的必须每个都返回true, 另外一个算自己的只要一个能赢
: 就行。
|
t****o
发帖数: 94 | 28 这个呢？随便写的，没test过。
bool CanAlwaysWin(vector& num, vector& used, int target)
{
if (target <= 0) return false;
for (int i = 0; i < num.size(); i++)
{
if (used[i]) continue;
if (num[i] >= target) return true;
used[i] = true;
bool win_anyway = true;
for (int j = 0; j < num.size(); j++)
{
if (used[j]) continue;
used[j] = true;
if (!CanAlwaysWin(num, used, target - num[i] - num[j]))
win_anyway = false;
used[j] = false;
}
used[i] = false;
if (win_anyway) return true;
}
return false;
}
【在 n******n 的大作中提到】
: 从函数名看是对的。 can I win？不是can I always win。
: 后者电面不合适。
|
r****7
发帖数: 2282 | 29 我这个显然是返回的必胜啊
这个code和permutation还是有不一样的，你估计没看懂。。。要不就是你不懂后向归纳
【在 s******7 的大作中提到】
: 你这个就是全排列，只要其中有个排列能赢，就返回true, 只能算有赢的可能，怎么能
: 算有必胜的的策略，要判断必胜的话，得无论对手怎么下，你都能赢， 得有两个递归
: 方法交替来，其中一个是对手的必须每个都返回true, 另外一个算自己的只要一个能赢
: 就行。
|
n******n
发帖数: 12088 | 30 没看懂。那你这个函数的语义是什么？到底是必胜，还是有可能胜？
归纳
【在 r****7 的大作中提到】
: 我这个显然是返回的必胜啊
: 这个code和permutation还是有不一样的，你估计没看懂。。。要不就是你不懂后向归纳
|
|
|
B***i
发帖数: 724 | |
r****7
发帖数: 2282 | 32 必胜啊，对方可能胜你就算不能必胜
【在 n******n 的大作中提到】
: 没看懂。那你这个函数的语义是什么？到底是必胜，还是有可能胜？
:
: 归纳
|
n******n
发帖数: 12088 | 33 对方不必胜，你就必胜？说不通啊。
if (!can_other_win) {
return true;
}
【在 r****7 的大作中提到】
: 必胜啊，对方可能胜你就算不能必胜
|
a**y
发帖数: 335 | 34 caniWin就是小时候玩的抢三十嘛。
【在 y*****e 的大作中提到】
: 今天面的第二轮。。。面完很伤心很失望，下午上了一下午班后，感觉好了点，开始觉
: 得自己发挥的好差，题也不容易，为啥别人都能碰到常见的常规的题，我就碰不到。。
: 。。不够难过的时候怪运气是太容易的事了，但现在冷静下来感觉，不过是给自己找借
: 口罢了。发面经上来，给自己差劲的人品增值，希望将来的面试顺利。
: 第一轮两道题
: 1. first missing positive
: 2. 写一个file line iterator
: Implement a (Java) Iterable object that iterates lines one by one from a
: text file..
: /** A reference to a file. */
|
r****7
发帖数: 2282 | 35 你在歪曲我的逻辑啊
我说对方可能胜，你就不是必胜，对于这个函数就是return false，因为俩人都是最优
选项，你就是必败。
不是说对方不是必胜，你就是必胜
65533;0�2 return true;
【在 n******n 的大作中提到】
: 对方不必胜，你就必胜？说不通啊。
: if (!can_other_win) {
: return true;
: }
|
c*******e
发帖数: 373 | 36 兄弟们
对方是绝顶高手 你不能假定对方是乱走的 你要证明对方不管怎么走 你一定有选择导
向你的必胜
就是博弈树 最大最小剪枝什么的
每次到你走时 选择对你最有利的 每次对方走 选择对你最不利的 因为对方想你输啊
这是有限制的穷举
如果你的某个招法 对方下一步有个办法让你输 那你就不要再考虑对方得其他招法 因
为你的这个招法已经证明是败招
这样提前结束对此招的研究 你要换个招法
以上都是通用的博弈算法
针对此特定问题 还可以看看有哪些情形 可以直接确定赢或者输 这样可以进一步提高
效率 |
B******l
发帖数: 262 | 37 100 ％ 16 ＝ 4，第一次取4。然后每次对手取x，你就取16-x。
【在 n******n 的大作中提到】
: 第二问是1到15，且大于等于100。
:
: +8
|
s*****g
发帖数: 72 | 38 完美
【在 B******l 的大作中提到】
: 100 ％ 16 ＝ 4，第一次取4。然后每次对手取x，你就取16-x。
|
n******n
发帖数: 12088 | 39 完美个鬼。对方取12，你怎么取16-12=4？已经用掉了。
【在 s*****g 的大作中提到】
: 完美
|
n******n
发帖数: 12088 | 40 你说的是：
对方可能胜，你就不是必胜，因为两个人都是最优选项，你就是必败。
你必败，就是对方必胜。如此你不是论证了可能胜就是必胜吗？
哪里歪曲了？都是你自己的原话。
【在 r****7 的大作中提到】
: 你在歪曲我的逻辑啊
: 我说对方可能胜，你就不是必胜，对于这个函数就是return false，因为俩人都是最优
: 选项，你就是必败。
: 不是说对方不是必胜，你就是必胜
:
: 65533;0�2 return true;
|
|
|
l****e
发帖数: 276 | 41 LZ 的电面是电话还是SKYPE？
【在 y*****e 的大作中提到】
: 今天面的第二轮。。。面完很伤心很失望，下午上了一下午班后，感觉好了点，开始觉
: 得自己发挥的好差，题也不容易，为啥别人都能碰到常见的常规的题，我就碰不到。。
: 。。不够难过的时候怪运气是太容易的事了，但现在冷静下来感觉，不过是给自己找借
: 口罢了。发面经上来，给自己差劲的人品增值，希望将来的面试顺利。
: 第一轮两道题
: 1. first missing positive
: 2. 写一个file line iterator
: Implement a (Java) Iterable object that iterates lines one by one from a
: text file..
: /** A reference to a file. */
|
r****7
发帖数: 2282 | 42 。。。“对方可能胜”中“胜”的定义是必胜啊
比如你选了一个数字K之后，对方有N个选项，如果有一个选项他选了之后是必胜的，其
他N-1个选项是必败的，那你选K也是必败的，因为对方会选最优的选项。
你要看看博弈论
【在 n******n 的大作中提到】
: 你说的是：
: 对方可能胜，你就不是必胜，因为两个人都是最优选项，你就是必败。
: 你必败，就是对方必胜。如此你不是论证了可能胜就是必胜吗？
: 哪里歪曲了？都是你自己的原话。
|
n******n
发帖数: 12088 | 43 那就是说要么先手必胜，要么后手必胜，因为不必胜就是必败？
【在 r****7 的大作中提到】
: 。。。“对方可能胜”中“胜”的定义是必胜啊
: 比如你选了一个数字K之后，对方有N个选项，如果有一个选项他选了之后是必胜的，其
: 他N-1个选项是必败的，那你选K也是必败的，因为对方会选最优的选项。
: 你要看看博弈论
|
n******n
发帖数: 12088 | 44 OK，早说是策梅洛定理嘛。
【在 n******n 的大作中提到】
: 那就是说要么先手必胜，要么后手必胜，因为不必胜就是必败？
|
r****7
发帖数: 2282 | 45 嗯。。。函数就是让你返回这个啊。。。
【在 n******n 的大作中提到】
: 那就是说要么先手必胜，要么后手必胜，因为不必胜就是必败？
|
m******3
发帖数: 346 | 46 安慰一下楼主，能上一下你iterator那道题的code么，对这类题不熟悉！ |
s******x
发帖数: 417 | 47 放狗一搜
http://www.cnblogs.com/jxlgetter/p/4395098.html
【在 m******3 的大作中提到】
: 安慰一下楼主，能上一下你iterator那道题的code么，对这类题不熟悉！
|
b******i
发帖数: 914 | 48 好难啊，俺估计碰到也是凶多吉少，请问是哪个组呢？
求问那个file line iterator你是怎么写的？谢谢啦！
还有，有时候是这样的，我们这儿有个哥们面试，所有公司都是给的leetcode或者
lintcode原题，结果都拿到offer，可是我看网上其他面经真的是很不容易，每个公司
都不容易。
【在 y*****e 的大作中提到】
: 今天面的第二轮。。。面完很伤心很失望，下午上了一下午班后，感觉好了点，开始觉
: 得自己发挥的好差，题也不容易，为啥别人都能碰到常见的常规的题，我就碰不到。。
: 。。不够难过的时候怪运气是太容易的事了，但现在冷静下来感觉，不过是给自己找借
: 口罢了。发面经上来，给自己差劲的人品增值，希望将来的面试顺利。
: 第一轮两道题
: 1. first missing positive
: 2. 写一个file line iterator
: Implement a (Java) Iterable object that iterates lines one by one from a
: text file..
: /** A reference to a file. */
|
y*****e
发帖数: 712 | 49 大牛！！！看到你泪流满面。。把你的牛气借给我好吗，我面试面的自己一点信心都没
有了。
我面的就是application组啊，传说中最简单的那个组。
iterator我就是用一个temp string记录next line,
hasNext() return temp != null
next()的话把找个result = temp, 把temp更新到到一行，然后return result.
【在 b******i 的大作中提到】
: 好难啊，俺估计碰到也是凶多吉少，请问是哪个组呢？
: 求问那个file line iterator你是怎么写的？谢谢啦！
: 还有，有时候是这样的，我们这儿有个哥们面试，所有公司都是给的leetcode或者
: lintcode原题，结果都拿到offer，可是我看网上其他面经真的是很不容易，每个公司
: 都不容易。
|
b******i
发帖数: 914 | 50 我完全不是大牛啊。OK. 了解了，那可能跟这个差不多：
http://www.fgdsb.com/2015/01/25/peek-iterator/
【在 y*****e 的大作中提到】
: 大牛！！！看到你泪流满面。。把你的牛气借给我好吗，我面试面的自己一点信心都没
: 有了。
: 我面的就是application组啊，传说中最简单的那个组。
: iterator我就是用一个temp string记录next line,
: hasNext() return temp != null
: next()的话把找个result = temp, 把temp更新到到一行，然后return result.
|
|
|
e*******g
发帖数: 1488 | 51 第二题...我能弱弱得说一下么？这题是我当年面试我老板研究生出的题，怎么会一模
一样...我当时选得就是1-10. |
m******3
发帖数: 346 | |
S****G
发帖数: 3 | 53 关于输赢那个题目，根据版上大牛们的讨论，写了code大家可以一看，主要用了zemel
定理（也可以不用但code会比较messy）。此外，博弈树怎么做这个题，谁有相关资料
可以发来看看。
http://feisyr.blogspot.com/2015/04/zermelos-theorem-game-theory
bool canW(int val1, std::vector &available, int curSum, int & desT){
if (val1 + curSum >= desT) return true;
else{
bool theOtherWin = false;
for (int val2 = 1; val2 < available.size(); ++val2){
if (!available[val2]) continue;
available[val2] = false;
theOtherWin = theOtherWin || canW(val2, available, curSum + val1
, desT);
available[val2] = true;
if(theOtherWin) break;
}
return !theOtherWin;
}
}
bool canIWin(int maxC, int desT){
if (desT <= 0) return true;
if (maxC <= 0) return false;
std::vector available(maxC+1,true);
return !canW(0, available, 0, desT);
} |
y*****e
发帖数: 712 | 54 可以去mtv一趟了！好开心啊，从来没去过耶！！ |
a***e
发帖数: 413 | |
b******i
发帖数: 914 | 56 恭喜恭喜！
【在 y*****e 的大作中提到】
: 可以去mtv一趟了！好开心啊，从来没去过耶！！
|
b******i
发帖数: 914 | 57 请问能否贴个code？谢谢！
根据你的思路，是不是这样的（猜的）？
1. 统计所有的permutations
2. 对于每一个permutation，算一下是player1赢还是player2赢
3. 把这些permutations group by 第一个数
4. 如果有一个group里面所有的permutations都是player1赢，那就返回true
【在 r****7 的大作中提到】
: 你的第二轮面经是我电面的面经，careercup上也有
: 我打算自己offer定了发所有面经回馈版面，可惜offer一直没定下来。。。
: 其实第二题就是lc的permutation，用dp的话能变成2^n复杂度.
|
b******i
发帖数: 914 | 58 拿数字那题写了个巨复杂的code，肯定不是最简单的，也不一定对，欢迎提意见
class Solution {
public:
bool canIWin(int n, int target) {
// assume we choose from 1 to n, target is a positive integer
if(n >= target)
return true;
unordered_set used;
return first_win_helper(n, used, target);
}
bool first_win_helper(int n, unordered_set &used, int target) {
// return true if the first player will be guaranteed to win
if(used.size() == n)
return false;
for(int i = n; i >= n; i--) {
if(used.find(i) != used.end())
continue;
if(i >= target)
return true;
used.insert(i);
int next_target = target - i;
// consider the next step played by the second player, no matter
what he does, the next
// next round, first player should win
bool flag = true;
for(int j = n; j >= 1; j--) {
if(used.find(j) != used.end())
continue;
if(j >= next_target) {
flag = false;
break;
}
used.insert(j);
if(!first_win_helper(n, used, next_target - j)) {
flag = false;
break;
}
used.erase(j);
}
used.erase(i);
if(flag)
return true;
}
return false;
}
}; |
b******i
发帖数: 914 | 59 题目要求是
which returns true if the first player to move can force a win with optimal
play.
感觉是can I always win的意思
【在 n******n 的大作中提到】
: 从函数名看是对的。 can I win？不是can I always win。
: 后者电面不合适。
|
d*****c
发帖数: 605 | 60 昨天就说过啦，不要灰心的，看你答的其实没有很差的。onsite加油！
onsite
经。
【在 y*****e 的大作中提到】
: 可以去mtv一趟了！好开心啊，从来没去过耶！！
|
|
|
h****3
发帖数: 89 | |
m******3
发帖数: 346 | 62 恭喜，等你好消息和面经啊！
【在 y*****e 的大作中提到】
: 可以去mtv一趟了！好开心啊，从来没去过耶！！
|
L**B
发帖数: 54 | 63 对手取8呢
【在 B******l 的大作中提到】
: 100 ％ 16 ＝ 4，第一次取4。然后每次对手取x，你就取16-x。
|
r*g
发帖数: 186 | 64 第二题第二问 下午发了删了 朋友说是对的就又发上来了
bool canIWin(int, std::vector &v, int sum, int obj)
{
for(int i = 1; i < v.size(); ++i){
if(v[i]){
if(sum + i >= obj){
return true;
}else{
v[i] = false;
bool res = canIWin(2, v, sum + i, obj);
v[i] = true;
if(!res){
return true;
}
}
}
}
return false;
}
int main()
{
std::vector v(15 + 1, true);
if(canIWin(1, v, 0, 150)){
std::cout << "YES" << std::endl;
}
return 0;
}
onsite
经。
【在 y*****e 的大作中提到】
: 可以去mtv一趟了！好开心啊，从来没去过耶！！
|
y*****e
发帖数: 712 | 65 这题还有一个情况要考虑一下，就是maxnumber的和小于desiredNumber,比如
允许的数是1,2,3。需要的和是20这样，谁都赢不了，这种也return false。 |
v*****y
发帖数: 68 | 66 我on site的时候也遇到了这个题，我在优化上遇到了问题。
不谈优化的话，我觉得就是典型的backtracking，把每一个可能的数字都都试一下，如
果对方一定不能赢，那就我们可以赢。reg的答案就是这样的。
哪位能说说优化？当时面试的时候我想这种方法是否有重复计算？我们是否能把一些结
果cache一下？比如说maxChoosableInteger = 10， desiredTotal=10的话，如果第一
次我们取1，对方取2，和第一次我们取2，对方取1，都需要计算canWin([3..10], 7)。
所以我们是否可以以各一个set为key，boolean为value的hashmap来cache结果？
求大神们指点，谢谢。 |
m***9
发帖数: 1671 | 67 第一题，先取1，然后取11-x（x是对手取的值）
第二题，先取8，然后去16-x（x是对手取的值） |
r****7
发帖数: 2282 | 68 不错，恭喜，onsite算法题都弱到爆，设计题也就是网上那几道
不过估计最后你也会把它拒掉。
onsite
经。
【在 y*****e 的大作中提到】
: 这题还有一个情况要考虑一下，就是maxnumber的和小于desiredNumber,比如
: 允许的数是1,2,3。需要的和是20这样，谁都赢不了，这种也return false。
|
y*****e
发帖数: 712 | 69 怎么可能。。。我现在0个offer,别说linkedin这样的一流公司了，就是差些的给我
offer，我也颠颠的去啊。大牛啥时候安顿下来给俺们上上面经吧。
【在 r****7 的大作中提到】
: 不错，恭喜，onsite算法题都弱到爆，设计题也就是网上那几道
: 不过估计最后你也会把它拒掉。
:
: onsite
: 经。
|
r****7
发帖数: 2282 | 70 你搜下版上mr 谢尔顿的面经，我的设计题和他一样。算法题都是LC上的原题，我有的
说做过了他就换一个，换了还是做过的我就没好继续说了。所以我觉得算法题比重不大
，设计题我没干过类似的也不会忽悠，答得估计没啥出彩的。本来面之前就打算当练手
的，顺带yy如果愿意给个staff的话也不错，结果丫连senior都不给，当时没别的offer
我也就直接拒了。。。
【在 y*****e 的大作中提到】
: 怎么可能。。。我现在0个offer,别说linkedin这样的一流公司了，就是差些的给我
: offer，我也颠颠的去啊。大牛啥时候安顿下来给俺们上上面经吧。
|
|
|
b******i
发帖数: 914 | 71 同问linkedin有哪些设计题啊，看到有一些，但是没有什么答案
offer
【在 r****7 的大作中提到】
: 你搜下版上mr 谢尔顿的面经，我的设计题和他一样。算法题都是LC上的原题，我有的
: 说做过了他就换一个，换了还是做过的我就没好继续说了。所以我觉得算法题比重不大
: ，设计题我没干过类似的也不会忽悠，答得估计没啥出彩的。本来面之前就打算当练手
: 的，顺带yy如果愿意给个staff的话也不错，结果丫连senior都不给，当时没别的offer
: 我也就直接拒了。。。
|
r****7
发帖数: 2282 | 72 我也不知道答案。。。我觉得设计题就是用来烙印照顾烙印的。
你搜下版上的，我现在也记不清而且敲起来太慢。估计题库就那么几个题搞来搞去
【在 b******i 的大作中提到】
: 同问linkedin有哪些设计题啊，看到有一些，但是没有什么答案
:
: offer
|
n******n
发帖数: 12088 | 73 想当然。对手留着12以上不取，到88时，对手直接拿这些就赢了。
【在 m***9 的大作中提到】
: 第一题，先取1，然后取11-x（x是对手取的值）
: 第二题，先取8，然后去16-x（x是对手取的值）
|
n******n
发帖数: 12088 | 74 谢尔顿？
offer
【在 r****7 的大作中提到】
: 你搜下版上mr 谢尔顿的面经，我的设计题和他一样。算法题都是LC上的原题，我有的
: 说做过了他就换一个，换了还是做过的我就没好继续说了。所以我觉得算法题比重不大
: ，设计题我没干过类似的也不会忽悠，答得估计没啥出彩的。本来面之前就打算当练手
: 的，顺带yy如果愿意给个staff的话也不错，结果丫连senior都不给，当时没别的offer
: 我也就直接拒了。。。
|
t*********r
发帖数: 387 | |
a********5
发帖数: 1631 | 76 又瞎黑
今天我觉得 L算一流公司了！
【在 t*********r 的大作中提到】
: 祝楼主好运
: 不过L绝壁不算一流公司
|
t*********r
发帖数: 387 | 77 你这个傻逼就是个无脑黑抽筋喷
在L喷L，在G喷G
吃个老赵都要哔哔几下才买单
【在 a********5 的大作中提到】
: 又瞎黑
: 今天我觉得 L算一流公司了！
|
r*g
发帖数: 186 | 78
yes you are right,
I tried your idea and it's much faster than before.
int calcHash(std::vector &v)
{
int res = 0;
for(auto ele: v){
res = res * 2 + ele;
}
return res;
}
bool canIWin(int, int sum, std::vector &v, int obj,
std::unordered_map &cache)
{
int key = calcHash(v);
if(cache.find(key) != cache.end()){
return cache[key];
}
for(int i = 1; i < v.size(); ++i){
if(v[i]){
if(sum + i >= obj){
return cache[key] = true;
}else{
v[i] = false;
auto res = canIWin(2, sum + i, v, obj, cache
);
v[i] = true;
if(!res){
return cache[key] = true;
}
}
}
}
return cache[key] = false;
}
int main()
{
std::unordered_map cache;
std::vector v(15 + 1, true);
if(canIWin(1, 0, v, obj, cache)){
std::cout << "YES" << std::endl;
}
return 0;
}
【在 v*****y 的大作中提到】
: 我on site的时候也遇到了这个题，我在优化上遇到了问题。
: 不谈优化的话，我觉得就是典型的backtracking，把每一个可能的数字都都试一下，如
: 果对方一定不能赢，那就我们可以赢。reg的答案就是这样的。
: 哪位能说说优化？当时面试的时候我想这种方法是否有重复计算？我们是否能把一些结
: 果cache一下？比如说maxChoosableInteger = 10， desiredTotal=10的话，如果第一
: 次我们取1，对方取2，和第一次我们取2，对方取1，都需要计算canWin([3..10], 7)。
: 所以我们是否可以以各一个set为key，boolean为value的hashmap来cache结果？
: 求大神们指点，谢谢。
|
l*****o
发帖数: 214 | 79
// 我觉得4不对。不可能所有的permutations都是player1赢得，你这样找肯定找不出
true的来。因为player1要是按作死的方式玩，肯定赢不了。题目问的是有没有策略保
证赢，不管player2怎么出牌
【在 b******i 的大作中提到】
: 请问能否贴个code？谢谢！
: 根据你的思路，是不是这样的（猜的）？
: 1. 统计所有的permutations
: 2. 对于每一个permutation，算一下是player1赢还是player2赢
: 3. 把这些permutations group by 第一个数
: 4. 如果有一个group里面所有的permutations都是player1赢，那就返回true
|
S****G
发帖数: 3 | 80 唯一牛逼的解法
【在 r*g 的大作中提到】
:
: yes you are right,
: I tried your idea and it's much faster than before.
: int calcHash(std::vector &v)
: {
: int res = 0;
: for(auto ele: v){
: res = res * 2 + ele;
: }
: return res;
|
|
|
j********l
发帖数: 325 | 81 恭喜哈，一举拿下哟！
onsite
经。
【在 y*****e 的大作中提到】
: 怎么可能。。。我现在0个offer,别说linkedin这样的一流公司了，就是差些的给我
: offer，我也颠颠的去啊。大牛啥时候安顿下来给俺们上上面经吧。
|
l*****o
发帖数: 214 | 82 public class NumberPickGame {
public NumberPickGame() {}
public static boolean canIForceWin(int maxNumber, int total) {
if ((maxNumber + 1) * maxNumber /2 < total) {
return false;
}
Set numbersAvailable = new HashSet();
for (int i = 1; i <= maxNumber; i++) {
numbersAvailable.add(i);
}
int[] picks = new int[maxNumber];
boolean canWin = canFirstPlayerWin(numbersAvailable, total, 0, picks
);
Log.print(picks);
return canWin;
}
private static boolean canFirstPlayerWin(Set numbersAvailable,
int total, int turnNumber, int[] picks) {
// even turn is first player, odd turn is second player
boolean firstPlayerTurn = (turnNumber % 2 == 0);
if (firstPlayerTurn) {
// first player: among all possible picks, there is at least one
pick that guarantees win
for (Integer number: numbersAvailable) {
if (total - number <= 0) {
picks[turnNumber] = number;
return true;
}
Set numbersLeft = new HashSet(
numbersAvailable);
numbersLeft.remove(number);
picks[turnNumber] = number;
boolean secondPlayerForceWin = canFirstPlayerWin(numbersLeft
, total - number, turnNumber + 1, picks);
if (secondPlayerForceWin) {
return true;
}
}
return false;
} else {
// second player: no matter what the second player choose, the
first player always win
for (Integer number: numbersAvailable) {
if (total - number <= 0) {
picks[turnNumber] = number;
return false;
}
Set numbersLeft = new HashSet(
numbersAvailable);
numbersLeft.remove(number);
picks[turnNumber] = number;
boolean firstPlayerForceWin = canFirstPlayerWin(numbersLeft,
total - number, turnNumber + 1, picks);
if (!firstPlayerForceWin) {
return false;
}
}
return true;
}
}
/**
* @param args
*/
public static void main(String[] args) {
NumberPickGame game = new NumberPickGame();
System.out.println(game.canIForceWin(5, 12)); => true
System.out.println(game.canIForceWin(2, 1)); => true
System.out.println(game.canIForceWin(1, 1)); => true
System.out.println(game.canIForceWin(3, 3)); => true
System.out.println(game.canIForceWin(3, 4)); => false
System.out.println(game.canIForceWin(3, 5)); => true
System.out.println(game.canIForceWin(4, 10)); => false
}
} |
i*****h
发帖数: 1534 | 83 祝福下楼主，调整下心态再接再厉一定能拿到！
onsite
经。
【在 y*****e 的大作中提到】
: 怎么可能。。。我现在0个offer,别说linkedin这样的一流公司了，就是差些的给我
: offer，我也颠颠的去啊。大牛啥时候安顿下来给俺们上上面经吧。
|
