发两个蛮有意思的 Google 问题吧 ~

前阵子被Google 加面了，觉得其中两道题蛮有意思的  ，虽然过啦但是不打算去了 ，所以发出来一起讨论下 ，求点人品 ，感觉最近人品是不是不够用了 。。。。
这个是Kirkland Google 。。。

1. 一个一维数据可以看成一个棋盘  ，其中有两种棋子 ，或者也可以有空格，
第一种棋子是 L ，只可以向左走 ，
第二种棋子是 R，只可以往右走 ，
唯一的规则是 任何两个 L 和 R 不可以交叉 ， 比如

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

里要是去掉 (0, 4) 位置的1  ， 那么 (0,2) , (0,3)也就掉下去了 ，因为这两个点没办法链接到地板上了 ，也就作为一个树枝掉下去了 。

先给了个Brute Force ，然后给了个贪心的解法 ，貌似是最优解 ，面试官表示认可 。

这个更正一下 ，楼主方向搞错了 。。。 L 是像左，R 是像右  。。。所以图应该是_ R _ _ _ L_  ==== >  _ _ _ RL  _ _    ,   不好意思 诸位哈 ~~  

飞絮成霜 发表于 2018-6-21 08:36
两个都是利口原题  
表示为啥我没这么幸运 首面加面的题都没见过

第一题楼下提到了，第二题没找到额，还记得是哪一题么？

josephdesire 发表于 2018-6-27 04:10
应该是跟原来一样 但是要算L move的steps和R的steps要相同

我也是这么想的 但是不知道能不能严格证明没有反例的存在

能详细讲讲解法吗？两个题我都没搞明白

第一种棋子是 L ，只可以向左走 ，//我怎么感觉L是在向→走？

“ _ L _ _ _ R_  , 不可以走成 _ _ _ R L _ _ ”
L往左走啊，难道不是变成"L______R"?

因为这两个点没办法链接到地板上了//地板是在下面

第一种棋子是 L ，只可以向左走 ，
第二种棋子是 R，只可以往右走 ，
from：
_ L _ L _ _ R _ _ R
到：
_ _ L L R R _ _ _ _
这无解啊？方向不对啊？

两个都是利口原题  
表示为啥我没这么幸运 首面加面的题都没见过

cexq 发表于 2018-6-21 08:24
第一种棋子是 L ，只可以向左走 ，//我怎么感觉L是在向→走？

是的 。。。你说的对 。。。我typo 了 。。。

飞絮成霜 发表于 2018-6-21 08:36
两个都是利口原题  
表示为啥我没这么幸运 首面加面的题都没见过

是原题么 ？？ 好吧我out 了 ，hhh