w*********e
发帖数: 49 | 1 上点新鲜面经回馈版面
F家phone
中年亚裔，比较注重细节
3sum, 每个元素可用多次
ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
简单方法写了个recursive的
约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
L家
phone
两个老美都挺nice 一个主面一个shadow
第一题lowest common ancestor in binary tree with parent pointer
第二题find minimum distance between two words in a string array
e.g (“the”, “quick”, “brown”, “fox”, “quick”)
distance(“fox”,”the”) = 3
distance(“quick”, “fox”) = 1
onsite
1.host manager面，国人大叔，主要是些背景和behavior question
2.technical communication，亚裔小哥，讲自己的project
这里一点个人的经验是如果面试官不熟悉你的领域的话不一定要讲自己亲手做的东西，
但一定要懂细节（因为不是每个人都有拿得出手又适合展示的project），我就是讲自
己组产品的框架。重点是不要让面试官觉得你做的东西很简单没挑战性，但是也不能太
晦涩要让他能听懂。所以最好先讲大的框架不要抠细节，他如果对那个具体细节感兴趣
自己会问，然后你再和他讨论效果会比较好。最好从他感兴趣的某个点上展开体现下你
的知识深度。另外如果面试官问哪块是你做的可以适当吹牛。
3.lunch interview
陪同你吃饭的人要提供feedback所以开始以为会吃得很不自在，结果碰到超nice的国人
大哥，直接和我中文聊让我放松，最后一路聊天加饭后散步水过，非常感谢！
4. system design，两位国女面试官，经典题url shortener。
开始上网上看过的一个做法，直接被shadow面试官全盘否定。主面试官大姐人很好帮我
打圆场，重新开始设计。这里一点个人经验是有些面试官喜欢否定面试者，这样的人往
往不是大牛但自傲，这种时候哪怕你知道自己是对的也千万不要与之硬扛，否则必死无
疑。最好顺着他来拍个马屁什么的，还有一线生机。
5. coding interview one，面试官是酷酷的国人小哥和新来的印度小哥。
warm up 如果两个linked list intersect的话如何找到merge point。
follow up 有环的情况
假设给一排n个房子paint，有m种不同颜色可选，相邻房子不能同色，给定一个mxn的
cost matrix，求最小cost的染色方法。
6. coding interview two，白人小哥。
algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set choosable，target）
判断一个数组里是否存在三个数可以组成一个三角形
lc原题all permutation of array，array 可以有重复元素，结果不允许重复
G家
内部哥们强推，跳过phone
onsite
1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
片的下一个位置
e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
能得话要多少次。
吐槽下，面试官是个三哥，全程非常严肃／黑脸，我说句话就用小本子记下搞得我很紧
张。我说用java写可以吗，曰可以，刚写了两行问我add是啥意思，不知道是想考我基
础知识还是不懂java。
2. 给定一个binary search tree，返回range内所有key，key可以有重复。
版上出现了多次的把一个数拆成任意个平方和的最小拆法。
面试官是中年国人大叔，除了告诉我题目是啥就在电脑上自顾自工作，问话要问两遍才
有反应。写完说我程序有问题，查了半天查不出bug，然后指出我漏了个尖括号，跪了
。。
3. 版上出现多次的longest consecutive sequence in tree
follow up 如何加速，memory放不下怎么办。
国人小哥比较nice，但是只要我不和他主动说话绝不主动和我说话，因为前两场心情略
糟糕写完题目在白板前发呆，哥们就望着我啥也不说，尴尬。。当然也不怪他我自己比
较紧张，回家发现有很弱智的bug但小哥没提不知道怎么回事，可能放我水了
4. 设计个用bit形式表示时间（小时：分钟）的clock，
e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的
时间，
e.g. n＝0就只有0:0一种可能。
面试官是亚裔年轻mm，话不多人很cool，但是思路清晰会引导面试者，感觉碰到懂得引
导面试者或冷漠面试官对面试人表现会有很大影响，真的是看运气了。
5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。
面试官是做android前端的白人mm，非常活泼健谈，一路聊天愉快，面完就感觉她会给
强推。
之前发过了U的店面，最后签了offer，就不发onsite面筋了。
背景：phd1年多经验，非互联网养老公司
工作c/c++为主做软件性能优化比较多，为了面试专门去coursera上了java（之前有人
推荐的Princeton的算法课）和python的课，感觉多会几种语言后对水平帮助很大，准
备过程中有什么不懂就stackoverflow，
也很有帮助。之前没有任何互联网经验，唯一经验就是自己在aws上做一个小blog网站
，aws构架是scalability的经典教科书，值得学习一下
干货结束，之后是对各个公司和offer的看法，有很多主观因素，不喜勿喷。
G家
很多人觉得g家面试官总体素质很高，不过个人最近面试中的不愉快经历基本都是在g家
发生的，没有明显觉得g家面试官比别家水平高，可能是我运气不好或第一个面的太紧
张。
g家offer流程不确定性很大，快的一周内搞定，慢的要一个月也不稀奇（我自己亲身经
历没有team match还用了快一个月，中间recruiter换过一次，第一个面的g但别家
offer deadline都过了才出结果）。所以最好把g排在最早面试，但是坏处是拿g热身风
险太大，面专门的热身公司对骑驴找马的同学cost又比较高。
个人对g的看法比较neutral，觉得5年之内还是稳稳的业界老大，但是增长已经放缓，
暂时看不到第二春的迹象。坏处就是有明显的刷简历和养老公司的趋势，碰到许多ex－
googler对自由度低和没有存在感颇有微词。很多人升T5不久就走了。
g家默认发low ball offer，但是如果你有好的competing offer可以给的range比任何
一家都大，就看想不想抢你了。从我自己搜集的资料来看，T4的range大概是（括号我
自己的number做参考）
base ： 130-140K （130）
GSU：300-800 （670）
signon：0-50K （50）
基本原则就是没好的competing offer往下限看齐，否则往上限看齐，当然可以更多，
但那基本是极少数牛人，不在讨论范围内。base是HC定的，negotiate空间很小，GSU和
signon有很大空间，senior的recruiter给个几万signon完全可以自己决定。所以有
competing尽管开口要不会有问题。
g家刷题还是有些用处的，但不是决定性的。对非大牛来说g offer运气成分很大，g家
的挑人原则和别人不一样，有strong hire很重要，有个把not hire不影响大局，总体
是1 strong hire ＋ 1 not hire 》1 hire ＋ 1 hire。如果一个strong没有哪怕全是
hire也可能过不了HC。从我自己的base可以推断feedback平均分很一般，但有人力挺我
才拿到的offer，因为recruiter专门和我提到impress some interviewer，并且自己感
觉很有可能有一个面试官给了我not hire。
L家
个人对L家印象不错，recruiter很热情，感觉对面试人比狗家上心，面完后两天就告诉
过了HC可以有offer，专门找了hm和director和我约谈，感觉都不错，最后据offer的时
候很不好意思。
L家是我面过所有里面coding比重较小的，它家题库不大，career cup和论坛上把他家
题都刷熟再加leetcode过coding面一点问题都没有。L家的重头戏在design和
communication，一定要好好准备，我有认识acm大牛没拿到L offer估计就是栽在这些
上面。
L家感觉作为第一份工作非常好：entry level package高，不low ball；app track很
多职位做的事情类似full stack engineer，从mobile到后端都管，是学习的好机会；
总体氛围不错，worklife balance好。缺点是：senior拿的／refresh不如g； 烙印hm
多，干活的都是老中；在普通人群中牌子不如g硬。当然每个人感受不同，其中很多缺
点也算不上缺点。个人聊过的烙印hm感觉人还不错。最后拿的包裹：
base： 145K
RSU： 300K
signon： 50K
U家
对U家最深刻的印象是里面每个人都对公司有超乎寻常的热情。后来才知道对他家没热
情的面试就被刷了。他家很看重这个，如果有人面试中觉得你对他们公司没信心，基本
是一票否决。U家大概是近几十年争议最大的公司了，如果你去网上看新闻评论，各种
负面报道和谩骂基本是铺天盖地，看不见什么好评论，光看这些感觉这个公司分分钟要
倒闭的样子，但事实是它的business还在以惊人的速度增长，鲜明对比下的问题值得深
思。网上有很大的一部分负面评论和customer service有关，它家只有邮件没有电话客
服让很多人很抓狂，另外负面宣传让很多没怎么用过uber的民众觉得它就是个黑车公司
，根本不知道它后面的mission。还有一个很有意思的是我生活中认识的用过uber的人
基本都说好，没见过一个说不好的，但网上骂的那么多真的让人怀疑是不是出租车司机
或水军。
u家非senior面试主要还是coding加一点点design，题目感觉中等偏难。如果senior的
话design类问题比重大大增加，而且会有些很难回答的非算法问题，感觉比较考全方位
的软实力。u家基本是一票否决，所以不能弄砸某一轮。最近还在大量招人，不过面的
人也很多，所以还是比较挑剔的导致议价空间也很小。
u家面试很高效，onsite当天或第二天给offer，过两天没消息基本就是挂了，它家
经过5月最新50b估值后standard package慢慢开始low ball了，最近的2级（比senior
低一级）standard range大概是
base： 125-130K
rsu：12000-14000 unit 按39/unit来的
传说中它家基本不negotiate，但个人经验还是可以的，但是你要有比较好的competing
offer。它家现在和g抢人抢的挺凶，所以有好的GF之类的offer还是可以讲的但是操作
空间也不是很大，最后g家给的包裹基本快赶上u了而且全是cash（签uber的第二天g股
票就飙了），选他家主要是在养老公司呆怕了，希望能有点impact，但愿以后不会后悔。 |
G***o
发帖数: 5158 | 2 恭喜恭喜
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
b*****i
发帖数: 262 | 3 谢谢lz
lz什么经验？
[发表自未名空间手机版 - m.mitbbs.com]
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
a***y
发帖数: 852 | |
f**********e
发帖数: 288 | |
f**********e
发帖数: 288 | |
w*********e
发帖数: 49 | 7 帖子里面筋后面补充了点背景，不敢说太详细，圈子很小怕被认出
【在 b*****i 的大作中提到】
: 谢谢lz
: lz什么经验？
:
: [发表自未名空间手机版 - m.mitbbs.com]
|
J*******o
发帖数: 741 | |
V**********i
发帖数: 82 | |
z*******o
发帖数: 4773 | |
|
|
S*********9
发帖数: 541 | 11 赞 + 欢迎！
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
A*******e
发帖数: 2419 | 12 有几道题没看懂。
L
第二题find minimum distance between two words in a string array
e.g (“the”, “quick”, “brown”, “fox”, “quick”)
distance(“fox”,”the”) = 3
distance(“quick”, “fox”) = 1
距离是怎么定义的？为何第一对是3，第二对是1？
G
给定一个binary search tree，返回range内所有key，key可以有重复。
BST怎么可能有重复？
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
m******s
发帖数: 1469 | |
a*******k
发帖数: 261 | |
r****7
发帖数: 2282 | 15 最后去了哪一家？
G的base也是有比较大的谈的空间的，我最后的offer比第一个lowball的offer base也
多了3万块钱。但是最好谈的sign on却没有谈动...
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
r****7
发帖数: 2282 | 16 哦，看到你选的是U，感觉被lowball了...
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
w*********e
发帖数: 49 | 17 确实被lowball了，因为u是第一个offer我现在工作compensation很差所以直接给我来
了个low ball，最后g的offer来的太晚没机会慢慢谈只提了一次价就签了，最后还是比
较low ball。不过个人工作经验和去得组没有任何直接联系，没底气要太多也只能认了
。另外去uber不全是为了compensation，不然g还可以再谈基本可以match u但是实际更
多因为是cash。
【在 r****7 的大作中提到】
: 哦，看到你选的是U，感觉被lowball了...
|
C*7
发帖数: 234 | 18 好多干货，赞！
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
r****7
发帖数: 2282 | 19 赞心态，你这样去U应该挺适合。U这种公司在里边好好干，应该会很快的把lowball的
部分给补上！
【在 w*********e 的大作中提到】
: 确实被lowball了，因为u是第一个offer我现在工作compensation很差所以直接给我来
: 了个low ball，最后g的offer来的太晚没机会慢慢谈只提了一次价就签了，最后还是比
: 较low ball。不过个人工作经验和去得组没有任何直接联系，没底气要太多也只能认了
: 。另外去uber不全是为了compensation，不然g还可以再谈基本可以match u但是实际更
: 多因为是cash。
|
w*********e
发帖数: 49 | 20 距离是按在array里的index算的，这题的point在于可以有重复的word
binary search tree也可以有重复key，看你怎么定义了，比如c++std里的multiset就
是有重复key的rb tree
【在 A*******e 的大作中提到】
: 有几道题没看懂。
: L
: 第二题find minimum distance between two words in a string array
: e.g (“the”, “quick”, “brown”, “fox”, “quick”)
: distance(“fox”,”the”) = 3
: distance(“quick”, “fox”) = 1
: 距离是怎么定义的？为何第一对是3，第二对是1？
: G
: 给定一个binary search tree，返回range内所有key，key可以有重复。
: BST怎么可能有重复？
|
|
|
T*****9
发帖数: 2484 | 21 没事，可以最后再去G的
hm
senior
competing
悔。
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
A*******e
发帖数: 2419 | 22 1.明白了。
2.直接在普通rb-tree上加个计数器不就好了吗？何必重复key？而且一直没搞懂，
multiset/multimap有什么必需应用么？
【在 w*********e 的大作中提到】
: 距离是按在array里的index算的，这题的point在于可以有重复的word
: binary search tree也可以有重复key，看你怎么定义了，比如c++std里的multiset就
: 是有重复key的rb tree
|
y******s
发帖数: 92 | 23 听lz这么一说，看来F今年是招满了啊。。。下一轮要从10月开始？
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
k**l
发帖数: 2966 | 24 最近刚开始要换工作
想问问现场coding咋实现的，自带笔记本开 eclipse ，那谁给测试？
leetcode 刷了20%了，感觉中等难度的题半小时写成 accepted 还是有些难度的。还
有时写了一半发现有个trick没想清楚， stuck 半天
你们面的都刷到啥水平，比如n个房子刷m个颜色这题 现场要测试通过么，我倒是有些
想法，感觉写完程序还得半天。
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
s********a
发帖数: 1447 | 25 恭喜 lz~
问一下 这道题
1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
片的下一个位置
e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
能得话要多少次。
这道题 是求 最少多少次得到原来的card deck吗？还是随便多少次都可以呢？
这道题你怎么答的呢？
还有这道题 怎么答的？
5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。 |
n******n
发帖数: 12088 | 26 洗牌题本质就是置换群，最后是数论问题。
第二个之前讨论过吧。
【在 s********a 的大作中提到】
: 恭喜 lz~
: 问一下 这道题
: 1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
: 片的下一个位置
: e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
: 话下个卡片位置是EDCBA。
: 问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
: 能得话要多少次。
: 这道题 是求 最少多少次得到原来的card deck吗？还是随便多少次都可以呢？
: 这道题你怎么答的呢？
|
k**l
发帖数: 2966 | 27 1. how about 挨个字母算出多少次归位，最后求common denominator?
【在 s********a 的大作中提到】
: 恭喜 lz~
: 问一下 这道题
: 1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
: 片的下一个位置
: e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
: 话下个卡片位置是EDCBA。
: 问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
: 能得话要多少次。
: 这道题 是求 最少多少次得到原来的card deck吗？还是随便多少次都可以呢？
: 这道题你怎么答的呢？
|
w*********e
发帖数: 49 | 28 multimap比较好理解，就是一样的key不同的value
multiset确实等同于可key－count的map，但是据说在combinatorics里有应用，看了看
wiki没看懂
【在 A*******e 的大作中提到】
: 1.明白了。
: 2.直接在普通rb-tree上加个计数器不就好了吗？何必重复key？而且一直没搞懂，
: multiset/multimap有什么必需应用么？
|
w*********e
发帖数: 49 | 29 差不多就是这么个意思，可以找出所有的置换群求每个群size的LCM
比如shuffle array 是43210，置换群是｛AE｝，｛BD｝，｛C｝，每个群中元素在经过
群size次置换后回到原点，所以最少LCM（1，2，2） ＝ 2次后回到初始deck
找置换群的方法类似dfs
【在 k**l 的大作中提到】
: 1. how about 挨个字母算出多少次归位，最后求common denominator?
|
w*********e
发帖数: 49 | 30 所有面试中算法游戏题都是一个套路，推荐看下topcoder相关tutorial
https://www.topcoder.com/community/data-science/data-science-tutorials/
algorithm-games/
【在 s********a 的大作中提到】
: 恭喜 lz~
: 问一下 这道题
: 1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
: 片的下一个位置
: e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
: 话下个卡片位置是EDCBA。
: 问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
: 能得话要多少次。
: 这道题 是求 最少多少次得到原来的card deck吗？还是随便多少次都可以呢？
: 这道题你怎么答的呢？
|
|
|
w*********e
发帖数: 49 | 31 flg不需要现场run code，只有UA可能会要。
比较保险点的话，lc medium最好能15－20分钟内搞定，hard最好25-30分钟。实际live
coding时test case是自己写的，有问题要当场debug，加上和面试官扯淡聊天，基本
剩不下多少时间code
【在 k**l 的大作中提到】
: 最近刚开始要换工作
: 想问问现场coding咋实现的，自带笔记本开 eclipse ，那谁给测试？
: leetcode 刷了20%了，感觉中等难度的题半小时写成 accepted 还是有些难度的。还
: 有时写了一半发现有个trick没想清楚， stuck 半天
: 你们面的都刷到啥水平，比如n个房子刷m个颜色这题 现场要测试通过么，我倒是有些
: 想法，感觉写完程序还得半天。
|
s********a
发帖数: 1447 | 32 多谢 大牛讲解~
【在 w*********e 的大作中提到】
: 所有面试中算法游戏题都是一个套路，推荐看下topcoder相关tutorial
: https://www.topcoder.com/community/data-science/data-science-tutorials/
: algorithm-games/
|
Y******g
发帖数: 16 | |
E********e
发帖数: 63 | 34 版上出现多次的longest consecutive sequence in tree
follow up 如何加速，memory放不下怎么办。
加速是什么意思 这题不时是递归走一边遍O（N）么 |
A*******e
发帖数: 2419 | 35 一样的key不同value也很奇怪啊。直接key到unique value set不就可以了？无非是一
个key返回所有value，或者第k个，或者随机返回一个。
平时写代码从来没用过multimap/set。而且unordered_map/set里不存在对应的结构。
【在 w*********e 的大作中提到】
: multimap比较好理解，就是一样的key不同的value
: multiset确实等同于可key－count的map，但是据说在combinatorics里有应用，看了看
: wiki没看懂
|
E********e
发帖数: 63 | 36 设计个用bit形式表示时间（小时：分钟）的clock，
e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的
时间，e.g. n＝0就只有0:0一种可能。
这道题怎么做，我用nextiteration 写快１００行，有更好的办法么 |
A*******e
发帖数: 2419 | 37 我也看了一下wiki。感觉这玩意不是必需的，像一个syntactic sugar。存一个元素和
其个数 vs 存多个同样元素，信息是等价的。
【在 A*******e 的大作中提到】
: 一样的key不同value也很奇怪啊。直接key到unique value set不就可以了？无非是一
: 个key返回所有value，或者第k个，或者随机返回一个。
: 平时写代码从来没用过multimap/set。而且unordered_map/set里不存在对应的结构。
|
w*********e
发帖数: 49 | 38 这题是combination变种，
小时需要4bit，分钟6bit，一共10bit
先求｛9，8，。。。，1，0｝的10选n所有combination，
然后用bit operation得到相应值即可，三四十行内可以搞定
【在 E********e 的大作中提到】
: 设计个用bit形式表示时间（小时：分钟）的clock，
: e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的
: 时间，e.g. n＝0就只有0:0一种可能。
: 这道题怎么做，我用nextiteration 写快１００行，有更好的办法么
|
c*g
发帖数: 634 | 39 '版上出现了多次的把一个数拆成任意个平方和的最小拆法。'
请问这道题的最优解是什么啊？有讨论链接吗？
我面试的时候碰到过，用类似combination sum的暴力列举的方法，然后选出最小的说
。 但好像不是最好的解法？
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
A*******e
发帖数: 2419 | 40 dp
【在 c*g 的大作中提到】
: '版上出现了多次的把一个数拆成任意个平方和的最小拆法。'
: 请问这道题的最优解是什么啊？有讨论链接吗？
: 我面试的时候碰到过，用类似combination sum的暴力列举的方法，然后选出最小的说
: 。 但好像不是最好的解法？
|
|
|
A*******e
发帖数: 2419 | 41 十选三是什么意思？
【在 w*********e 的大作中提到】
: 这题是combination变种，
: 小时需要4bit，分钟6bit，一共10bit
: 先求｛9，8，。。。，1，0｝的10选n所有combination，
: 然后用bit operation得到相应值即可，三四十行内可以搞定
|
j******g
发帖数: 1428 | |
w*********e
发帖数: 49 | 43 弄错了，是10选n，更正了
【在 A*******e 的大作中提到】
: 十选三是什么意思？
|
k***a
发帖数: 1199 | 44 这两题的状态空间都很大呀，比如第一题状态是每个数有没有被取，总数是2^n，第二
题就把每次操作完的string或bitset作为状态吗？
有什么办法优化呢
【在 w*********e 的大作中提到】
: 所有面试中算法游戏题都是一个套路，推荐看下topcoder相关tutorial
: https://www.topcoder.com/community/data-science/data-science-tutorials/
: algorithm-games/
|
l*****v
发帖数: 122 | |
l******s
发帖数: 3045 | 46 请教DP具体的做法及复杂度？
【在 A*******e 的大作中提到】
: dp
|
w*********e
发帖数: 49 | 47 个人认为如果数组和target sum是任意给定的话很难再优化。从面试角度讲，知道
naive solution space是n！并懂得用dp优化到2^n应该就是面试官想看的。
【在 k***a 的大作中提到】
: 这两题的状态空间都很大呀，比如第一题状态是每个数有没有被取，总数是2^n，第二
: 题就把每次操作完的string或bitset作为状态吗？
: 有什么办法优化呢
|
h*********n
发帖数: 11319 | |
w*********e
发帖数: 49 | 49 递推公式大概长这样：
f(n) = min_{1<= i <= sqrt(n)}{f(n - i*i)} +1
f(0) = 0
O(n^1.5)
【在 l******s 的大作中提到】
: 请教DP具体的做法及复杂度？
|
k***a
发帖数: 1199 | 50 居然2^n就是面试官想要的答案，让我很吃惊 ＝）
多谢lz的面筋，恭喜lz的offer！
第二
【在 w*********e 的大作中提到】
: 个人认为如果数组和target sum是任意给定的话很难再优化。从面试角度讲，知道
: naive solution space是n！并懂得用dp优化到2^n应该就是面试官想看的。
|
|
|
w*******z
发帖数: 39 | 51 这个复杂度应该是pseudo polynomial吧
有真正p的解法吗
递推公式大概长这样：f(n) = min_{1
【在 w*********e 的大作中提到】
: 递推公式大概长这样：
: f(n) = min_{1<= i <= sqrt(n)}{f(n - i*i)} +1
: f(0) = 0
: O(n^1.5)
|
w*********e
发帖数: 49 | 52 面试官就是这么问的，比较隐晦，后来我猜他想问multithreading，得到了他的肯定，
假设k个thread，大概可以优化到O（k+n/k）这个样子，重点是如何做multithreading
【在 E********e 的大作中提到】
: 版上出现多次的longest consecutive sequence in tree
: follow up 如何加速，memory放不下怎么办。
: 加速是什么意思 这题不时是递归走一边遍O（N）么
|
A*******e
发帖数: 2419 | 53 有啥好吃惊的。面试官并非个个都是奥赛金牌。:)
【在 k***a 的大作中提到】
: 居然2^n就是面试官想要的答案，让我很吃惊 ＝）
: 多谢lz的面筋，恭喜lz的offer！
:
: 第二
|
T*****9
发帖数: 2484 | 54 我猜UA可能会要的原因是面试官看不懂code:)
live
有些
【在 w*********e 的大作中提到】
: flg不需要现场run code，只有UA可能会要。
: 比较保险点的话，lc medium最好能15－20分钟内搞定，hard最好25-30分钟。实际live
: coding时test case是自己写的，有问题要当场debug，加上和面试官扯淡聊天，基本
: 剩不下多少时间code
|
w*********e
发帖数: 49 | 55 还真有可能，哈哈，感觉现在年轻一代码农既不懂c++也不懂java的并不少见
【在 T*****9 的大作中提到】
: 我猜UA可能会要的原因是面试官看不懂code:)
:
: live
: 有些
|
e*******i
发帖数: 56 | 56 大牛。 恭喜lz的offer！
这经典题url shortener要注意哪些地方？
难道不是一个DHT, something like Cassandra?
::经典题url shortener。
::开始上网上看过的一个做法，直接被shadow面试官全盘否定 |
T*****9
发帖数: 2484 | 57 反正都是一顿瞎写裸写，懂不懂code不重要
【在 w*********e 的大作中提到】
: 还真有可能，哈哈，感觉现在年轻一代码农既不懂c++也不懂java的并不少见
|
y******s
发帖数: 92 | 58 这两题求思路，多谢多谢：
1. algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩
家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set choosable，target）
2. 算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
l******s
发帖数: 3045 | 59 谢谢，算是top down的递归dp+backtracking，跟我的想法一致了。
【在 w*********e 的大作中提到】
: 递推公式大概长这样：
: f(n) = min_{1<= i <= sqrt(n)}{f(n - i*i)} +1
: f(0) = 0
: O(n^1.5)
|
c**********8
发帖数: 1052 | |
|
|
t*******2
发帖数: 182 | 61 多谢lz的面经！！最近马上要面L家application track，这信息简直太有用了～～
lz能说说url shortner他们想要的答案是什么样吗？我也只知道网上最常见的做法。 |
d*****v
发帖数: 72 | 62 感觉lz再多讲讲 算法游戏的思路吧，看了你发的tutorial感觉还是挺没思路的。 |
h******6
发帖数: 76 | |
s********l
发帖数: 998 | 64 我也没太明白。。。 :(
【在 d*****v 的大作中提到】
: 感觉lz再多讲讲 算法游戏的思路吧，看了你发的tutorial感觉还是挺没思路的。
|
w*********e
发帖数: 49 | 65 我觉得我也没法比tutorial讲的更好了。。。是比较费解，但多看几遍就慢慢理解
首先是这类游戏里假设双方的目标都是自己要赢，那每个当前state（position）就只
有必赢和必输两种状态，不存在中间态。首先在游戏结束的state，必赢和必输对两方
玩家都是显而易见的，如果倒推回去，你发现一个玩家A在state X如果它的所有【下一
个state Y】（玩家A
在state X make move之后）都是会使游戏结束的必赢state（因为这时候轮到对手行动
了，他什么都不用做就已经赢了），则玩家A必输，反之只要
任意一个state Y是必输state则玩家A
必赢，因为玩家A可以自由选择自己的move，确保下一个是必输state。以此类推。
【在 d*****v 的大作中提到】
: 感觉lz再多讲讲 算法游戏的思路吧，看了你发的tutorial感觉还是挺没思路的。
|
w*********e
发帖数: 49 | 66 system design也是我的弱项，我的理解是system design并不是为了考你是不是真的懂
design，而是考你懂多少基础知识而且是否能灵活运用，没有标准答案，全看面试官喜
好和运气，另外system design is all about trade-off，搞清楚面试官想要的
tradeoff里面侧重点是什么就好了
【在 t*******2 的大作中提到】
: 多谢lz的面经！！最近马上要面L家application track，这信息简直太有用了～～
: lz能说说url shortner他们想要的答案是什么样吗？我也只知道网上最常见的做法。
|
m******3
发帖数: 346 | 67 求问下面的题目
L的
algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set choosable，target）
还有G的
2. 给定一个binary search tree，返回range内所有key，key可以有重复。
版上出现了多次的把一个数拆成任意个平方和的最小拆法。
这题目具体是什么？有相关讨论么？
3. 版上出现多次的longest consecutive sequence in tree
follow up 如何加速，memory放不下怎么办。
这个题目具体是什么啊？
4. 设计个用bit形式表示时间（小时：分钟）的clock，
e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的
时间，
e.g. n＝0就只有0:0一种可能。
5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。 |
p****6
发帖数: 724 | 68
L这道就是recursive, pass in 个total value，一次对手，一次自己。思路和
combination sum很像。
【在 m******3 的大作中提到】
: 求问下面的题目
: L的
: algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
: 数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
: boolean isWin（Set choosable，target）
: 还有G的
: 2. 给定一个binary search tree，返回range内所有key，key可以有重复。
: 版上出现了多次的把一个数拆成任意个平方和的最小拆法。
: 这题目具体是什么？有相关讨论么？
: 3. 版上出现多次的longest consecutive sequence in tree
|
m******3
发帖数: 346 | 69 能详细说说么，以前没见过类似题目。另外“如果某个玩家取数后所有已经取出的数和
超过给定值则胜出”是说两个玩家所有取出数的和，还是只有这个玩家自己取出数的和
啊? |
p****6
发帖数: 724 | 70
public static boolean canIWin(int rangeMax, int target) {
if(rangeMax * (rangeMax + 1) /2 < target)
return false;
boolean[] visited = new boolean[rangeMax+1];
return recursive(0, rangeMax, target, visited);
}
private static boolean recursive(int cur, int rangeMax, int target,
boolean[] visited){
if(cur >= target) return false;
for(int i = 1; i <= rangeMax; i++){
if(!visited[i]){
visited[i] = true;
boolean heWin = recursive(cur + i, rangeMax, target, visited
);
visited[i] = false;
if(!heWin) return true;
}
}
return false;
}
【在 m******3 的大作中提到】
: 能详细说说么，以前没见过类似题目。另外“如果某个玩家取数后所有已经取出的数和
: 超过给定值则胜出”是说两个玩家所有取出数的和，还是只有这个玩家自己取出数的和
: 啊?
|
|
|
y******s
发帖数: 92 | 71 请lz再解释解释这个题，看了你后面的讨论，也没能理解啊：
onsite
1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
片的下一个位置e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是
ABCDE，43210的话下个卡片位置是EDCBA。问给定一个shuffle array，不断用这个
array去shuffle，能否得到最初的card deck，能得话要多少次。
十分感谢！
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
m******3
发帖数: 346 | 72 非常感谢，结合楼主发的tutorial,基本懂了,加点我理解的吧
public static boolean canIWin(int rangeMax, int target) {
if(rangeMax * (rangeMax + 1) /2 < target)
return false;
boolean[] visited = new boolean[rangeMax+1];
return recursive(0, rangeMax, target, visited);
}
private static boolean recursive(int cur, int rangeMax, int target,
boolean[] visited){
if(cur >= target) return false;
// 说明对手拿完以后，和>=target,所以对手获胜，我输
//尝试我所有可能的拿法，如果我拿了以后，对其中一个拿法，有heWin=false,则我可
以保证获胜，因为我一定会选择让对手输的方法
for(int i = 1; i <= rangeMax; i++){
if(!visited[i]){
visited[i] = true;
boolean heWin = recursive(cur + i, rangeMax, target, visited
);
visited[i] = false;
if(!heWin) return true;
}
}
// 如果尝试所有可能拿法以后，都不能保证我获胜，return false,表示这个状态不能
保证获胜
return false;
}
【在 p****6 的大作中提到】
:
: public static boolean canIWin(int rangeMax, int target) {
: if(rangeMax * (rangeMax + 1) /2 < target)
: return false;
: boolean[] visited = new boolean[rangeMax+1];
: return recursive(0, rangeMax, target, visited);
: }
:
: private static boolean recursive(int cur, int rangeMax, int target,
: boolean[] visited){
|
s********l
发帖数: 998 | 73 en?
这道题难道不是dp解嘛？
【在 p****6 的大作中提到】
:
: public static boolean canIWin(int rangeMax, int target) {
: if(rangeMax * (rangeMax + 1) /2 < target)
: return false;
: boolean[] visited = new boolean[rangeMax+1];
: return recursive(0, rangeMax, target, visited);
: }
:
: private static boolean recursive(int cur, int rangeMax, int target,
: boolean[] visited){
|
t*******2
发帖数: 182 | 74 说得在理，recruiter给的复习材料也是这个意思。
lz能说说这题的思路吗？
假设给一排n个房子paint，有m种不同颜色可选，相邻房子不能同色，给定一个mxn的
cost matrix，求最小cost的染色方法。
【在 w*********e 的大作中提到】
: system design也是我的弱项，我的理解是system design并不是为了考你是不是真的懂
: design，而是考你懂多少基础知识而且是否能灵活运用，没有标准答案，全看面试官喜
: 好和运气，另外system design is all about trade-off，搞清楚面试官想要的
: tradeoff里面侧重点是什么就好了
|
c******g
发帖数: 238 | 75 房子这题dp，dp[m][n],从1到n每步算到当前步，用当前color的最小total cost就可以
了。和LC偷房子类似，不难这题。 |
B********4
发帖数: 7156 | 76 Mark
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
k****i
发帖数: 128 | 77 5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。
面试官是做android前端的白人mm，非常活泼健谈，一路聊天愉快，面完就感觉她会给
强推。
========================
这题不就是数--的个数吗，奇数先走的就输偶数的就赢。哪理解错了？ |
t*******2
发帖数: 182 | 78 我也是这么想，不过这题复杂度应该是O(m*n)？
如果每往前走一步，看之前一步的最小cost都要把所有color过一遍的话，不就变成O(m
*m*n)了。。。
【在 c******g 的大作中提到】
: 房子这题dp，dp[m][n],从1到n每步算到当前步，用当前color的最小total cost就可以
: 了。和LC偷房子类似，不难这题。
|
s********l
发帖数: 998 | 79 - - - - -
- ++ - -
【在 k****i 的大作中提到】
: 5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
: 两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
: isWin（String s）判断先行动的玩家能否赢。
: followup 如何优化，时间上和空间上。
: 面试官是做android前端的白人mm，非常活泼健谈，一路聊天愉快，面完就感觉她会给
: 强推。
: ========================
: 这题不就是数--的个数吗，奇数先走的就输偶数的就赢。哪理解错了？
|
c******g
发帖数: 238 | 80 那就不知道了。我觉得思路还是挺学院的吧。跟最短距离一样。每个可能性，当前步不
同颜色总不能不check吧？本身的条件矩阵就是M*N了，俺比较弱鸡。我实在怀疑在这个
前提下能有算法能做到O(M N) ， dp这个算法中间应该没有什么废操作的。
(m
【在 t*******2 的大作中提到】
: 我也是这么想，不过这题复杂度应该是O(m*n)？
: 如果每往前走一步，看之前一步的最小cost都要把所有color过一遍的话，不就变成O(m
: *m*n)了。。。
|
|
|
k****i
发帖数: 128 | 81
【在 s********l 的大作中提到】
: - - - - -
: - ++ - -
|
m****t
发帖数: 23 | 82 can I ask why we can not do this problem using backtracking? as long as I
found a position when the 1st player picked at first will win, I can just
return that position.
not sure if that will work.
【在 w*********e 的大作中提到】
: 我觉得我也没法比tutorial讲的更好了。。。是比较费解，但多看几遍就慢慢理解
: 首先是这类游戏里假设双方的目标都是自己要赢，那每个当前state（position）就只
: 有必赢和必输两种状态，不存在中间态。首先在游戏结束的state，必赢和必输对两方
: 玩家都是显而易见的，如果倒推回去，你发现一个玩家A在state X如果它的所有【下一
: 个state Y】（玩家A
: 在state X make move之后）都是会使游戏结束的必赢state（因为这时候轮到对手行动
: 了，他什么都不用做就已经赢了），则玩家A必输，反之只要
: 任意一个state Y是必输state则玩家A
: 必赢，因为玩家A可以自由选择自己的move，确保下一个是必输state。以此类推。
|
w*********e
发帖数: 49 | 83 上点新鲜面经回馈版面
F家phone
中年亚裔，比较注重细节
3sum, 每个元素可用多次
ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
简单方法写了个recursive的
约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
L家
phone
两个老美都挺nice 一个主面一个shadow
第一题lowest common ancestor in binary tree with parent pointer
第二题find minimum distance between two words in a string array
e.g (“the”, “quick”, “brown”, “fox”, “quick”)
distance(“fox”,”the”) = 3
distance(“quick”, “fox”) = 1
onsite
1.host manager面，国人大叔，主要是些背景和behavior question
2.technical communication，亚裔小哥，讲自己的project
这里一点个人的经验是如果面试官不熟悉你的领域的话不一定要讲自己亲手做的东西，
但一定要懂细节（因为不是每个人都有拿得出手又适合展示的project），我就是讲自
己组产品的框架。重点是不要让面试官觉得你做的东西很简单没挑战性，但是也不能太
晦涩要让他能听懂。所以最好先讲大的框架不要抠细节，他如果对那个具体细节感兴趣
自己会问，然后你再和他讨论效果会比较好。最好从他感兴趣的某个点上展开体现下你
的知识深度。另外如果面试官问哪块是你做的可以适当吹牛。
3.lunch interview
陪同你吃饭的人要提供feedback所以开始以为会吃得很不自在，结果碰到超nice的国人
大哥，直接和我中文聊让我放松，最后一路聊天加饭后散步水过，非常感谢！
4. system design，两位国女面试官，经典题url shortener。
开始上网上看过的一个做法，直接被shadow面试官全盘否定。主面试官大姐人很好帮我
打圆场，重新开始设计。这里一点个人经验是有些面试官喜欢否定面试者，这样的人往
往不是大牛但自傲，这种时候哪怕你知道自己是对的也千万不要与之硬扛，否则必死无
疑。最好顺着他来拍个马屁什么的，还有一线生机。
5. coding interview one，面试官是酷酷的国人小哥和新来的印度小哥。
warm up 如果两个linked list intersect的话如何找到merge point。
follow up 有环的情况
假设给一排n个房子paint，有m种不同颜色可选，相邻房子不能同色，给定一个mxn的
cost matrix，求最小cost的染色方法。
6. coding interview two，白人小哥。
algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set choosable，target）
判断一个数组里是否存在三个数可以组成一个三角形
lc原题all permutation of array，array 可以有重复元素，结果不允许重复
G家
内部哥们强推，跳过phone
onsite
1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
片的下一个位置
e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
能得话要多少次。
吐槽下，面试官是个三哥，全程非常严肃／黑脸，我说句话就用小本子记下搞得我很紧
张。我说用java写可以吗，曰可以，刚写了两行问我add是啥意思，不知道是想考我基
础知识还是不懂java。
2. 给定一个binary search tree，返回range内所有key，key可以有重复。
版上出现了多次的把一个数拆成任意个平方和的最小拆法。
面试官是中年国人大叔，除了告诉我题目是啥就在电脑上自顾自工作，问话要问两遍才
有反应。写完说我程序有问题，查了半天查不出bug，然后指出我漏了个尖括号，跪了
。。
3. 版上出现多次的longest consecutive sequence in tree
follow up 如何加速，memory放不下怎么办。
国人小哥比较nice，但是只要我不和他主动说话绝不主动和我说话，因为前两场心情略
糟糕写完题目在白板前发呆，哥们就望着我啥也不说，尴尬。。当然也不怪他我自己比
较紧张，回家发现有很弱智的bug但小哥没提不知道怎么回事，可能放我水了
4. 设计个用bit形式表示时间（小时：分钟）的clock，
e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的
时间，
e.g. n＝0就只有0:0一种可能。
面试官是亚裔年轻mm，话不多人很cool，但是思路清晰会引导面试者，感觉碰到懂得引
导面试者或冷漠面试官对面试人表现会有很大影响，真的是看运气了。
5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。
面试官是做android前端的白人mm，非常活泼健谈，一路聊天愉快，面完就感觉她会给
强推。
之前发过了U的店面，最后签了offer，就不发onsite面筋了。
背景：phd1年多经验，非互联网养老公司,工作c/c++为主，为了面试专门去coursera上
了java（之前有人推荐的Princeton的算法课）和python的课，感觉多会几种语言后对
水平帮助很大，准
备过程中有什么不懂就stackoverflow，也很有帮助。之前没有任何互联网经验，唯一
经验就是自己在aws上做一个小blog网站
干货结束，之后是对各个公司和offer的看法，有很多主观因素，不喜勿喷。
G家
g家offer流程不确定性很大，快的一周内搞定，慢的要一个月也不稀奇（我自己亲身经
历没有team match还用了快一个月，中间recruiter换过一次，第一个面的g但别家
offer deadline都过了才出结果）。所以最好把g排在最早面试，但是坏处是拿g热身风
险太大，面专门的热身公司对骑驴找马的同学cost又比较高。
个人对g的看法比较neutral，觉得5年之内还是稳稳的业界老大，但是增长已经放缓，
暂时看不到第二春的迹象。坏处就是有明显的刷简历和养老公司的趋势，碰到许多ex－
googler对自由度低和没有存在感颇有微词。很多人升T5不久就走了。
g家默认发low ball offer，但是如果你有好的competing offer可以给的range比任何
一家都大，就看想不想抢你了。从我自己搜集的资料来看，T4的range大概是
base ： 130-150K
GSU：300-800
signon：0-50K
基本原则就是没好的competing offer往下限看齐，否则往上限看齐，当然可以更多，
但那基本是极少数牛人，不在讨论范围内。base是HC定的，negotiate空间很小，GSU和
signon有很大空间，senior的recruiter给个几万signon完全可以自己决定。所以有
competing尽管开口要不会有问题。
g家刷题还是有些用处的，但不是决定性的。对非大牛来说g offer运气成分很大，g家
的挑人原则和别人不一样，有strong hire很重要，有个把not hire不影响大局，总体
是1 strong hire ＋ 1 not hire 》1 hire ＋ 1 hire。如果一个strong没有哪怕全是
hire也可能过不了HC。从我自己的base可以推断feedback平均分很一般，但有人力挺我
才拿到的offer，因为recruiter专门和我提到impress some interviewer，并且自己感
觉很有可能有一个面试官给了我not hire。
L家
个人对L家印象不错，recruiter很热情，感觉对面试人比狗家上心，面完后两天就告诉
过了HC可以有offer，专门找了hm和director和我约谈，感觉都不错，最后据offer的时
候很不好意思。
L家是我面过所有里面coding比重较小的，它家题库不大，career cup和论坛上把他家
题都刷熟再加leetcode过coding面一点问题都没有。L家的重头戏在design和
communication，一定要好好准备，我有认识acm大牛没拿到L offer估计就是栽在这些
上面。
L家感觉作为第一份工作非常好：entry level package高，不low ball；app track很
多职位做的事情类似full stack engineer，从mobile到后端都管，是学习的好机会；
总体氛围不错，worklife balance好。缺点是：senior拿的／refresh不如g； 烙印hm
多，干活的都是老中；在普通人群中牌子不如g硬。当然每个人感受不同，其中很多缺
点也算不上缺点。个人聊过的烙印hm感觉人还不错。
U家
u家非senior面试主要还是coding加一点点design，题目感觉中等偏难。如果senior的
话design类问题比重大大增加，而且会有些很难回答的非算法问题，感觉比较考全方位
的软实力。u家基本是一票否决，所以不能弄砸某一轮。最近还在大量招人，不过面的
人也很多，所以还是比较挑剔的导致议价空间也很小。
u家面试很高效，onsite当天或第二天给offer，过两天没消息基本就是挂了，它家
经过5月最新50b估值后standard package慢慢开始low ball了，最近的2级（比senior
低一级）standard range大概是
base： 125-135K
rsu：12000-14000 unit 按39/unit来的
这个数比几个月前板上报的offer少不少，但它家估值变化太快几个月RSU数可以差很多。
传说中它家基本不negotiate，但个人经验还是可以的，但是你要有比较好的competing
offer。它家现在和g抢人抢的挺凶，所以有好的GF之类的offer还是可以讲的但是操作
空间也不是很大，最后g家给的包裹基本快赶上u了而且全是cash（签uber的第二天g股
票就飙了），选他家主要是在养老公司呆怕了，希望能有点impact，但愿以后不会后悔。 |
G***o
发帖数: 5158 | 84 恭喜恭喜
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
b*****i
发帖数: 262 | 85 谢谢lz
lz什么经验？
[发表自未名空间手机版 - m.mitbbs.com]
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
a***y
发帖数: 852 | |
f**********e
发帖数: 288 | |
f**********e
发帖数: 288 | |
w*********e
发帖数: 49 | 89 帖子里面筋后面补充了点背景，不敢说太详细，圈子很小怕被认出
【在 b*****i 的大作中提到】
: 谢谢lz
: lz什么经验？
:
: [发表自未名空间手机版 - m.mitbbs.com]
|
J*******o
发帖数: 741 | |
|
|
V**********i
发帖数: 82 | |
z*******o
发帖数: 4773 | |
S*********9
发帖数: 541 | 93 赞 + 欢迎！
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
A*******e
发帖数: 2419 | 94 有几道题没看懂。
L
第二题find minimum distance between two words in a string array
e.g (“the”, “quick”, “brown”, “fox”, “quick”)
distance(“fox”,”the”) = 3
distance(“quick”, “fox”) = 1
距离是怎么定义的？为何第一对是3，第二对是1？
G
给定一个binary search tree，返回range内所有key，key可以有重复。
BST怎么可能有重复？
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
m******s
发帖数: 1469 | |
a*******k
发帖数: 261 | |
r****7
发帖数: 2282 | 97 最后去了哪一家？
G的base也是有比较大的谈的空间的，我最后的offer比第一个lowball的offer base也
多了3万块钱。但是最好谈的sign on却没有谈动...
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
r****7
发帖数: 2282 | 98 哦，看到你选的是U，感觉被lowball了...
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
w*********e
发帖数: 49 | 99 确实被lowball了，因为u是第一个offer我现在工作compensation很差所以直接给我来
了个low ball，最后g的offer来的太晚没机会慢慢谈只提了一次价就签了，最后还是比
较low ball。不过个人工作经验和去得组没有任何直接联系，没底气要太多也只能认了
。另外去uber不全是为了compensation，不然g还可以再谈基本可以match u但是实际更
多因为是cash。
【在 r****7 的大作中提到】
: 哦，看到你选的是U，感觉被lowball了...
|
C*7
发帖数: 234 | 100 好多干货，赞！
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
|
|
r****7
发帖数: 2282 | 101 赞心态，你这样去U应该挺适合。U这种公司在里边好好干，应该会很快的把lowball的
部分给补上！
【在 w*********e 的大作中提到】
: 确实被lowball了，因为u是第一个offer我现在工作compensation很差所以直接给我来
: 了个low ball，最后g的offer来的太晚没机会慢慢谈只提了一次价就签了，最后还是比
: 较low ball。不过个人工作经验和去得组没有任何直接联系，没底气要太多也只能认了
: 。另外去uber不全是为了compensation，不然g还可以再谈基本可以match u但是实际更
: 多因为是cash。
|
w*********e
发帖数: 49 | 102 距离是按在array里的index算的，这题的point在于可以有重复的word
binary search tree也可以有重复key，看你怎么定义了，比如c++std里的multiset就
是有重复key的rb tree
【在 A*******e 的大作中提到】
: 有几道题没看懂。
: L
: 第二题find minimum distance between two words in a string array
: e.g (“the”, “quick”, “brown”, “fox”, “quick”)
: distance(“fox”,”the”) = 3
: distance(“quick”, “fox”) = 1
: 距离是怎么定义的？为何第一对是3，第二对是1？
: G
: 给定一个binary search tree，返回range内所有key，key可以有重复。
: BST怎么可能有重复？
|
T*****9
发帖数: 2484 | 103 没事，可以最后再去G的
hm
senior
competing
悔。
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
A*******e
发帖数: 2419 | 104 1.明白了。
2.直接在普通rb-tree上加个计数器不就好了吗？何必重复key？而且一直没搞懂，
multiset/multimap有什么必需应用么？
【在 w*********e 的大作中提到】
: 距离是按在array里的index算的，这题的point在于可以有重复的word
: binary search tree也可以有重复key，看你怎么定义了，比如c++std里的multiset就
: 是有重复key的rb tree
|
y******s
发帖数: 92 | 105 听lz这么一说，看来F今年是招满了啊。。。下一轮要从10月开始？
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
k**l
发帖数: 2966 | 106 最近刚开始要换工作
想问问现场coding咋实现的，自带笔记本开 eclipse ，那谁给测试？
leetcode 刷了20%了，感觉中等难度的题半小时写成 accepted 还是有些难度的。还
有时写了一半发现有个trick没想清楚， stuck 半天
你们面的都刷到啥水平，比如n个房子刷m个颜色这题 现场要测试通过么，我倒是有些
想法，感觉写完程序还得半天。
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
s********a
发帖数: 1447 | 107 恭喜 lz~
问一下 这道题
1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
片的下一个位置
e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
能得话要多少次。
这道题 是求 最少多少次得到原来的card deck吗？还是随便多少次都可以呢？
这道题你怎么答的呢？
还有这道题 怎么答的？
5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。 |
n******n
发帖数: 12088 | 108 洗牌题本质就是置换群，最后是数论问题。
第二个之前讨论过吧。
【在 s********a 的大作中提到】
: 恭喜 lz~
: 问一下 这道题
: 1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
: 片的下一个位置
: e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
: 话下个卡片位置是EDCBA。
: 问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
: 能得话要多少次。
: 这道题 是求 最少多少次得到原来的card deck吗？还是随便多少次都可以呢？
: 这道题你怎么答的呢？
|
k**l
发帖数: 2966 | 109 1. how about 挨个字母算出多少次归位，最后求common denominator?
【在 s********a 的大作中提到】
: 恭喜 lz~
: 问一下 这道题
: 1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
: 片的下一个位置
: e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
: 话下个卡片位置是EDCBA。
: 问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
: 能得话要多少次。
: 这道题 是求 最少多少次得到原来的card deck吗？还是随便多少次都可以呢？
: 这道题你怎么答的呢？
|
w*********e
发帖数: 49 | 110 multimap比较好理解，就是一样的key不同的value
multiset确实等同于可key－count的map，但是据说在combinatorics里有应用，看了看
wiki没看懂
【在 A*******e 的大作中提到】
: 1.明白了。
: 2.直接在普通rb-tree上加个计数器不就好了吗？何必重复key？而且一直没搞懂，
: multiset/multimap有什么必需应用么？
|
|
|
w*********e
发帖数: 49 | 111 差不多就是这么个意思，可以找出所有的置换群求每个群size的LCM
比如shuffle array 是43210，置换群是｛AE｝，｛BD｝，｛C｝，每个群中元素在经过
群size次置换后回到原点，所以最少LCM（1，2，2） ＝ 2次后回到初始deck
找置换群的方法类似dfs
【在 k**l 的大作中提到】
: 1. how about 挨个字母算出多少次归位，最后求common denominator?
|
w*********e
发帖数: 49 | 112 所有面试中算法游戏题都是一个套路，推荐看下topcoder相关tutorial
https://www.topcoder.com/community/data-science/data-science-tutorials/
algorithm-games/
【在 s********a 的大作中提到】
: 恭喜 lz~
: 问一下 这道题
: 1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
: 片的下一个位置
: e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
: 话下个卡片位置是EDCBA。
: 问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
: 能得话要多少次。
: 这道题 是求 最少多少次得到原来的card deck吗？还是随便多少次都可以呢？
: 这道题你怎么答的呢？
|
w*********e
发帖数: 49 | 113 flg不需要现场run code，只有UA可能会要。
比较保险点的话，lc medium最好能15－20分钟内搞定，hard最好25-30分钟。实际live
coding时test case是自己写的，有问题要当场debug，加上和面试官扯淡聊天，基本
剩不下多少时间code
【在 k**l 的大作中提到】
: 最近刚开始要换工作
: 想问问现场coding咋实现的，自带笔记本开 eclipse ，那谁给测试？
: leetcode 刷了20%了，感觉中等难度的题半小时写成 accepted 还是有些难度的。还
: 有时写了一半发现有个trick没想清楚， stuck 半天
: 你们面的都刷到啥水平，比如n个房子刷m个颜色这题 现场要测试通过么，我倒是有些
: 想法，感觉写完程序还得半天。
|
s********a
发帖数: 1447 | 114 多谢 大牛讲解~
【在 w*********e 的大作中提到】
: 所有面试中算法游戏题都是一个套路，推荐看下topcoder相关tutorial
: https://www.topcoder.com/community/data-science/data-science-tutorials/
: algorithm-games/
|
Y******g
发帖数: 16 | |
A*******e
发帖数: 2419 | 116 一样的key不同value也很奇怪啊。直接key到unique value set不就可以了？无非是一
个key返回所有value，或者第k个，或者随机返回一个。
平时写代码从来没用过multimap/set。而且unordered_map/set里不存在对应的结构。
【在 w*********e 的大作中提到】
: multimap比较好理解，就是一样的key不同的value
: multiset确实等同于可key－count的map，但是据说在combinatorics里有应用，看了看
: wiki没看懂
|
A*******e
发帖数: 2419 | 117 我也看了一下wiki。感觉这玩意不是必需的，像一个syntactic sugar。存一个元素和
其个数 vs 存多个同样元素，信息是等价的。
【在 A*******e 的大作中提到】
: 一样的key不同value也很奇怪啊。直接key到unique value set不就可以了？无非是一
: 个key返回所有value，或者第k个，或者随机返回一个。
: 平时写代码从来没用过multimap/set。而且unordered_map/set里不存在对应的结构。
|
w*********e
发帖数: 49 | 118 这题是combination变种，
小时需要4bit，分钟6bit，一共10bit
先求｛9，8，。。。，1，0｝的10选n所有combination，
然后用bit operation得到相应值即可，三四十行内可以搞定
【在 E********e 的大作中提到】
: 设计个用bit形式表示时间（小时：分钟）的clock，
: e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的
: 时间，e.g. n＝0就只有0:0一种可能。
: 这道题怎么做，我用nextiteration 写快１００行，有更好的办法么
|
c*g
发帖数: 634 | 119 '版上出现了多次的把一个数拆成任意个平方和的最小拆法。'
请问这道题的最优解是什么啊？有讨论链接吗？
我面试的时候碰到过，用类似combination sum的暴力列举的方法，然后选出最小的说
。 但好像不是最好的解法？
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
A*******e
发帖数: 2419 | 120 dp
【在 c*g 的大作中提到】
: '版上出现了多次的把一个数拆成任意个平方和的最小拆法。'
: 请问这道题的最优解是什么啊？有讨论链接吗？
: 我面试的时候碰到过，用类似combination sum的暴力列举的方法，然后选出最小的说
: 。 但好像不是最好的解法？
|
|
|
A*******e
发帖数: 2419 | 121 十选三是什么意思？
【在 w*********e 的大作中提到】
: 这题是combination变种，
: 小时需要4bit，分钟6bit，一共10bit
: 先求｛9，8，。。。，1，0｝的10选n所有combination，
: 然后用bit operation得到相应值即可，三四十行内可以搞定
|
j******g
发帖数: 1428 | |
w*********e
发帖数: 49 | 123 弄错了，是10选n，更正了
【在 A*******e 的大作中提到】
: 十选三是什么意思？
|
k***a
发帖数: 1199 | 124 这两题的状态空间都很大呀，比如第一题状态是每个数有没有被取，总数是2^n，第二
题就把每次操作完的string或bitset作为状态吗？
有什么办法优化呢
【在 w*********e 的大作中提到】
: 所有面试中算法游戏题都是一个套路，推荐看下topcoder相关tutorial
: https://www.topcoder.com/community/data-science/data-science-tutorials/
: algorithm-games/
|
l*****v
发帖数: 122 | |
l******s
发帖数: 3045 | 126 请教DP具体的做法及复杂度？
【在 A*******e 的大作中提到】
: dp
|
w*********e
发帖数: 49 | 127 个人认为如果数组和target sum是任意给定的话很难再优化。从面试角度讲，知道
naive solution space是n！并懂得用dp优化到2^n应该就是面试官想看的。
【在 k***a 的大作中提到】
: 这两题的状态空间都很大呀，比如第一题状态是每个数有没有被取，总数是2^n，第二
: 题就把每次操作完的string或bitset作为状态吗？
: 有什么办法优化呢
|
h*********n
发帖数: 11319 | |
w*********e
发帖数: 49 | 129 递推公式大概长这样：
f(n) = min_{1<= i <= sqrt(n)}{f(n - i*i)} +1
f(0) = 0
O(n^1.5)
【在 l******s 的大作中提到】
: 请教DP具体的做法及复杂度？
|
k***a
发帖数: 1199 | 130 居然2^n就是面试官想要的答案，让我很吃惊 ＝）
多谢lz的面筋，恭喜lz的offer！
第二
【在 w*********e 的大作中提到】
: 个人认为如果数组和target sum是任意给定的话很难再优化。从面试角度讲，知道
: naive solution space是n！并懂得用dp优化到2^n应该就是面试官想看的。
|
|
|
w*******z
发帖数: 39 | 131 这个复杂度应该是pseudo polynomial吧
有真正p的解法吗
递推公式大概长这样：f(n) = min_{1
【在 w*********e 的大作中提到】
: 递推公式大概长这样：
: f(n) = min_{1<= i <= sqrt(n)}{f(n - i*i)} +1
: f(0) = 0
: O(n^1.5)
|
w*********e
发帖数: 49 | 132 面试官就是这么问的，比较隐晦，后来我猜他想问multithreading，得到了他的肯定，
假设k个thread，大概可以优化到O（k+n/k）这个样子，重点是如何做multithreading
【在 E********e 的大作中提到】
: 版上出现多次的longest consecutive sequence in tree
: follow up 如何加速，memory放不下怎么办。
: 加速是什么意思 这题不时是递归走一边遍O（N）么
|
A*******e
发帖数: 2419 | 133 有啥好吃惊的。面试官并非个个都是奥赛金牌。:)
【在 k***a 的大作中提到】
: 居然2^n就是面试官想要的答案，让我很吃惊 ＝）
: 多谢lz的面筋，恭喜lz的offer！
:
: 第二
|
T*****9
发帖数: 2484 | 134 我猜UA可能会要的原因是面试官看不懂code:)
live
有些
【在 w*********e 的大作中提到】
: flg不需要现场run code，只有UA可能会要。
: 比较保险点的话，lc medium最好能15－20分钟内搞定，hard最好25-30分钟。实际live
: coding时test case是自己写的，有问题要当场debug，加上和面试官扯淡聊天，基本
: 剩不下多少时间code
|
w*********e
发帖数: 49 | 135 还真有可能，哈哈，感觉现在年轻一代码农既不懂c++也不懂java的并不少见
【在 T*****9 的大作中提到】
: 我猜UA可能会要的原因是面试官看不懂code:)
:
: live
: 有些
|
e*******i
发帖数: 56 | 136 大牛。 恭喜lz的offer！
这经典题url shortener要注意哪些地方？
难道不是一个DHT, something like Cassandra?
::经典题url shortener。
::开始上网上看过的一个做法，直接被shadow面试官全盘否定 |
T*****9
发帖数: 2484 | 137 反正都是一顿瞎写裸写，懂不懂code不重要
【在 w*********e 的大作中提到】
: 还真有可能，哈哈，感觉现在年轻一代码农既不懂c++也不懂java的并不少见
|
y******s
发帖数: 92 | 138 这两题求思路，多谢多谢：
1. algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩
家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set choosable，target）
2. 算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
l******s
发帖数: 3045 | 139 谢谢，算是top down的递归dp+backtracking，跟我的想法一致了。
【在 w*********e 的大作中提到】
: 递推公式大概长这样：
: f(n) = min_{1<= i <= sqrt(n)}{f(n - i*i)} +1
: f(0) = 0
: O(n^1.5)
|
c**********8
发帖数: 1052 | |
|
|
t*******2
发帖数: 182 | 141 多谢lz的面经！！最近马上要面L家application track，这信息简直太有用了～～
lz能说说url shortner他们想要的答案是什么样吗？我也只知道网上最常见的做法。 |
d*****v
发帖数: 72 | 142 感觉lz再多讲讲 算法游戏的思路吧，看了你发的tutorial感觉还是挺没思路的。 |
h******6
发帖数: 76 | |
s********l
发帖数: 998 | 144 我也没太明白。。。 :(
【在 d*****v 的大作中提到】
: 感觉lz再多讲讲 算法游戏的思路吧，看了你发的tutorial感觉还是挺没思路的。
|
w*********e
发帖数: 49 | 145 我觉得我也没法比tutorial讲的更好了。。。是比较费解，但多看几遍就慢慢理解
首先是这类游戏里假设双方的目标都是自己要赢，那每个当前state（position）就只
有必赢和必输两种状态，不存在中间态。首先在游戏结束的state，必赢和必输对两方
玩家都是显而易见的，如果倒推回去，你发现一个玩家A在state X如果它的所有【下一
个state Y】（玩家A
在state X make move之后）都是会使游戏结束的必赢state（因为这时候轮到对手行动
了，他什么都不用做就已经赢了），则玩家A必输，反之只要
任意一个state Y是必输state则玩家A
必赢，因为玩家A可以自由选择自己的move，确保下一个是必输state。以此类推。
【在 d*****v 的大作中提到】
: 感觉lz再多讲讲 算法游戏的思路吧，看了你发的tutorial感觉还是挺没思路的。
|
w*********e
发帖数: 49 | 146 system design也是我的弱项，我的理解是system design并不是为了考你是不是真的懂
design，而是考你懂多少基础知识而且是否能灵活运用，没有标准答案，全看面试官喜
好和运气，另外system design is all about trade-off，搞清楚面试官想要的
tradeoff里面侧重点是什么就好了
【在 t*******2 的大作中提到】
: 多谢lz的面经！！最近马上要面L家application track，这信息简直太有用了～～
: lz能说说url shortner他们想要的答案是什么样吗？我也只知道网上最常见的做法。
|
m******3
发帖数: 346 | 147 求问下面的题目
L的
algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set choosable，target）
还有G的
2. 给定一个binary search tree，返回range内所有key，key可以有重复。
版上出现了多次的把一个数拆成任意个平方和的最小拆法。
这题目具体是什么？有相关讨论么？
3. 版上出现多次的longest consecutive sequence in tree
follow up 如何加速，memory放不下怎么办。
这个题目具体是什么啊？
4. 设计个用bit形式表示时间（小时：分钟）的clock，
e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的
时间，
e.g. n＝0就只有0:0一种可能。
5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。 |
p****6
发帖数: 724 | 148
L这道就是recursive, pass in 个total value，一次对手，一次自己。思路和
combination sum很像。
【在 m******3 的大作中提到】
: 求问下面的题目
: L的
: algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
: 数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
: boolean isWin（Set choosable，target）
: 还有G的
: 2. 给定一个binary search tree，返回range内所有key，key可以有重复。
: 版上出现了多次的把一个数拆成任意个平方和的最小拆法。
: 这题目具体是什么？有相关讨论么？
: 3. 版上出现多次的longest consecutive sequence in tree
|
m******3
发帖数: 346 | 149 能详细说说么，以前没见过类似题目。另外“如果某个玩家取数后所有已经取出的数和
超过给定值则胜出”是说两个玩家所有取出数的和，还是只有这个玩家自己取出数的和
啊? |
p****6
发帖数: 724 | 150
public static boolean canIWin(int rangeMax, int target) {
if(rangeMax * (rangeMax + 1) /2 < target)
return false;
boolean[] visited = new boolean[rangeMax+1];
return recursive(0, rangeMax, target, visited);
}
private static boolean recursive(int cur, int rangeMax, int target,
boolean[] visited){
if(cur >= target) return false;
for(int i = 1; i <= rangeMax; i++){
if(!visited[i]){
visited[i] = true;
boolean heWin = recursive(cur + i, rangeMax, target, visited
);
visited[i] = false;
if(!heWin) return true;
}
}
return false;
}
【在 m******3 的大作中提到】
: 能详细说说么，以前没见过类似题目。另外“如果某个玩家取数后所有已经取出的数和
: 超过给定值则胜出”是说两个玩家所有取出数的和，还是只有这个玩家自己取出数的和
: 啊?
|
|
|
y******s
发帖数: 92 | 151 请lz再解释解释这个题，看了你后面的讨论，也没能理解啊：
onsite
1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
片的下一个位置e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是
ABCDE，43210的话下个卡片位置是EDCBA。问给定一个shuffle array，不断用这个
array去shuffle，能否得到最初的card deck，能得话要多少次。
十分感谢！
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
m******3
发帖数: 346 | 152 非常感谢，结合楼主发的tutorial,基本懂了,加点我理解的吧
public static boolean canIWin(int rangeMax, int target) {
if(rangeMax * (rangeMax + 1) /2 < target)
return false;
boolean[] visited = new boolean[rangeMax+1];
return recursive(0, rangeMax, target, visited);
}
private static boolean recursive(int cur, int rangeMax, int target,
boolean[] visited){
if(cur >= target) return false;
// 说明对手拿完以后，和>=target,所以对手获胜，我输
//尝试我所有可能的拿法，如果我拿了以后，对其中一个拿法，有heWin=false,则我可
以保证获胜，因为我一定会选择让对手输的方法
for(int i = 1; i <= rangeMax; i++){
if(!visited[i]){
visited[i] = true;
boolean heWin = recursive(cur + i, rangeMax, target, visited
);
visited[i] = false;
if(!heWin) return true;
}
}
// 如果尝试所有可能拿法以后，都不能保证我获胜，return false,表示这个状态不能
保证获胜
return false;
}
【在 p****6 的大作中提到】
:
: public static boolean canIWin(int rangeMax, int target) {
: if(rangeMax * (rangeMax + 1) /2 < target)
: return false;
: boolean[] visited = new boolean[rangeMax+1];
: return recursive(0, rangeMax, target, visited);
: }
:
: private static boolean recursive(int cur, int rangeMax, int target,
: boolean[] visited){
|
s********l
发帖数: 998 | 153 en?
这道题难道不是dp解嘛？
【在 p****6 的大作中提到】
:
: public static boolean canIWin(int rangeMax, int target) {
: if(rangeMax * (rangeMax + 1) /2 < target)
: return false;
: boolean[] visited = new boolean[rangeMax+1];
: return recursive(0, rangeMax, target, visited);
: }
:
: private static boolean recursive(int cur, int rangeMax, int target,
: boolean[] visited){
|
t*******2
发帖数: 182 | 154 说得在理，recruiter给的复习材料也是这个意思。
lz能说说这题的思路吗？
假设给一排n个房子paint，有m种不同颜色可选，相邻房子不能同色，给定一个mxn的
cost matrix，求最小cost的染色方法。
【在 w*********e 的大作中提到】
: system design也是我的弱项，我的理解是system design并不是为了考你是不是真的懂
: design，而是考你懂多少基础知识而且是否能灵活运用，没有标准答案，全看面试官喜
: 好和运气，另外system design is all about trade-off，搞清楚面试官想要的
: tradeoff里面侧重点是什么就好了
|
c******g
发帖数: 238 | 155 房子这题dp，dp[m][n],从1到n每步算到当前步，用当前color的最小total cost就可以
了。和LC偷房子类似，不难这题。 |
B********4
发帖数: 7156 | 156 Mark
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
k****i
发帖数: 128 | 157 5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。
面试官是做android前端的白人mm，非常活泼健谈，一路聊天愉快，面完就感觉她会给
强推。
========================
这题不就是数--的个数吗，奇数先走的就输偶数的就赢。哪理解错了？ |
t*******2
发帖数: 182 | 158 我也是这么想，不过这题复杂度应该是O(m*n)？
如果每往前走一步，看之前一步的最小cost都要把所有color过一遍的话，不就变成O(m
*m*n)了。。。
【在 c******g 的大作中提到】
: 房子这题dp，dp[m][n],从1到n每步算到当前步，用当前color的最小total cost就可以
: 了。和LC偷房子类似，不难这题。
|
s********l
发帖数: 998 | 159 - - - - -
- ++ - -
【在 k****i 的大作中提到】
: 5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
: 两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
: isWin（String s）判断先行动的玩家能否赢。
: followup 如何优化，时间上和空间上。
: 面试官是做android前端的白人mm，非常活泼健谈，一路聊天愉快，面完就感觉她会给
: 强推。
: ========================
: 这题不就是数--的个数吗，奇数先走的就输偶数的就赢。哪理解错了？
|
c******g
发帖数: 238 | 160 那就不知道了。我觉得思路还是挺学院的吧。跟最短距离一样。每个可能性，当前步不
同颜色总不能不check吧？本身的条件矩阵就是M*N了，俺比较弱鸡。我实在怀疑在这个
前提下能有算法能做到O(M N) ， dp这个算法中间应该没有什么废操作的。
(m
【在 t*******2 的大作中提到】
: 我也是这么想，不过这题复杂度应该是O(m*n)？
: 如果每往前走一步，看之前一步的最小cost都要把所有color过一遍的话，不就变成O(m
: *m*n)了。。。
|
|
|
k****i
发帖数: 128 | 161
【在 s********l 的大作中提到】
: - - - - -
: - ++ - -
|
m****t
发帖数: 23 | 162 can I ask why we can not do this problem using backtracking? as long as I
found a position when the 1st player picked at first will win, I can just
return that position.
not sure if that will work.
【在 w*********e 的大作中提到】
: 我觉得我也没法比tutorial讲的更好了。。。是比较费解，但多看几遍就慢慢理解
: 首先是这类游戏里假设双方的目标都是自己要赢，那每个当前state（position）就只
: 有必赢和必输两种状态，不存在中间态。首先在游戏结束的state，必赢和必输对两方
: 玩家都是显而易见的，如果倒推回去，你发现一个玩家A在state X如果它的所有【下一
: 个state Y】（玩家A
: 在state X make move之后）都是会使游戏结束的必赢state（因为这时候轮到对手行动
: 了，他什么都不用做就已经赢了），则玩家A必输，反之只要
: 任意一个state Y是必输state则玩家A
: 必赢，因为玩家A可以自由选择自己的move，确保下一个是必输state。以此类推。
|
A********d
发帖数: 558 | 163 如何用dfs找置换群？
比如shuffle array 是43210，置换群是｛AE｝，｛BD｝，｛C｝，每个群中元素在经过
群size次置换后回到原点，所以最少LCM（1，2，2） ＝ 2次后回到初始deck |
l*********r
发帖数: 10 | 164 谢谢楼主大神~求问 G 家免 phone interview, 什么样才能叫强推呢？ |
s**r
发帖数: 1660 | 165 5. coding interview one，面试官是酷酷的国人小哥和新来的印度小哥。
warm up 如果两个linked list intersect的话如何找到merge point。
follow up 有环的情况
请问楼主是怎么解有环的情况的？ |
w*********e
发帖数: 49 | 166 就是让人给你多吹nb但不要太假，所以还是真的比较熟较好，不然太假
【在 l*********r 的大作中提到】
: 谢谢楼主大神~求问 G 家免 phone interview, 什么样才能叫强推呢？
|
w*********e
发帖数: 49 | 167 有环只是个幌子，情况跟找一个自己成环的list是一样的，两个list分开找，略坑爹
【在 s**r 的大作中提到】
: 5. coding interview one，面试官是酷酷的国人小哥和新来的印度小哥。
: warm up 如果两个linked list intersect的话如何找到merge point。
: follow up 有环的情况
: 请问楼主是怎么解有环的情况的？
|
z**q
发帖数: 577 | 168 恭喜楼主！
你这面试挺凶险啊，L和G各有一道题比较难，放到十几年前的IOI day1里面也不掉价的。
L家
5. coding interview one，面试官是酷酷的国人小哥和新来的印度小哥。
warm up 如果两个linked list intersect的话如何找到merge point。
这题难点在于链的公共部分可能无限长（有环也是导致无限长的一种情况），俩分叉部
分的长度有限但也可能很长。所以没法保存已经访问过的节点。要想在线性时间和常数
空间内解决，可以先用交替倍增步长互相追赶的方法找到某一个公共点以及求出分叉部
分的长度差，然后从头开始一遍找到第一个公共点也就是merge point。或者是我想复
杂了？楼主有什么简单的方法解决？
G家
5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
这题至少可以做到 O(n^2)，需要用到Sprague–Grundy theorem以及独立局面取XOR的
性质。O(n^2)是因为我算那个SG函数的时候没找到什么太好的规律，就根据定义硬算的
。也许有更好的方法可以做到线性复杂度。
那个定理可以参考 https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_
theorem
很久以前Nim game当竞赛题也曾难倒一片的，这题比Nim game还要多绕一个弯。
我刚才洗澡的时候想了一下，在知道局面取XOR的前提下，自己推Sprague–Grundy
theorem需要半小时。而且我不太自信能在面试的时候跟面试官讲清楚。
或者我估计面试官自己也不知道这解法？
【在 w*********e 的大作中提到】
: 上点新鲜面经回馈版面
: F家phone
: 中年亚裔，比较注重细节
: 3sum, 每个元素可用多次
: ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
: 简单方法写了个recursive的
: 约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
: L家
: phone
: 两个老美都挺nice 一个主面一个shadow
|
S********t
发帖数: 3431 | 169 G家那题是
https://leetcode.com/problems/flip-game-ii/
不过放心，G家interviewer的水平没有大家想象的那么高，知道sprague-grundy
theory的不多。expectation就是做出普通backtracking的方法。除非是专门做游戏理
论的，普通人谁知道这个定理啊。我做这道题的时候是凭几年前做过nim的回忆，花了1
个小时凭感觉才推出sprague-grundy的解法，然后才去看讨论学习了这个理论。
的。
【在 z**q 的大作中提到】
: 恭喜楼主！
: 你这面试挺凶险啊，L和G各有一道题比较难，放到十几年前的IOI day1里面也不掉价的。
: L家
: 5. coding interview one，面试官是酷酷的国人小哥和新来的印度小哥。
: warm up 如果两个linked list intersect的话如何找到merge point。
: 这题难点在于链的公共部分可能无限长（有环也是导致无限长的一种情况），俩分叉部
: 分的长度有限但也可能很长。所以没法保存已经访问过的节点。要想在线性时间和常数
: 空间内解决，可以先用交替倍增步长互相追赶的方法找到某一个公共点以及求出分叉部
: 分的长度差，然后从头开始一遍找到第一个公共点也就是merge point。或者是我想复
: 杂了？楼主有什么简单的方法解决？
|
z**q
发帖数: 577 | 170 是，基本上没做过nim的话不太可能往正确的路子上想。即使做过了nim，推S-G定理也
还是需要一定功底。
G家面试官的水平有高有低吧。不过大家应该不会无聊到非得要求这题用S-G的地步。反
正我是没那么无聊，除非需要往难了去面烙印（然而一般二叉树遍历就能搞掉烙印，再
不行搞个树状动规也足够了）。
了1
【在 S********t 的大作中提到】
: G家那题是
: https://leetcode.com/problems/flip-game-ii/
: 不过放心，G家interviewer的水平没有大家想象的那么高，知道sprague-grundy
: theory的不多。expectation就是做出普通backtracking的方法。除非是专门做游戏理
: 论的，普通人谁知道这个定理啊。我做这道题的时候是凭几年前做过nim的回忆，花了1
: 个小时凭感觉才推出sprague-grundy的解法，然后才去看讨论学习了这个理论。
:
: 的。
|
