狗家onsite

11月早些时候面的，一直拖着没写面经，补上

• 1. Currency calculation
• 给一堆货币转换作为输入，以及要做的query。leetcode上有相似度为99%的题，惊了：
• 
  
• 2. Game of life
• leetcode上也有这道题：
• 
  
• 3. Given a list of strings, design a model that would randomly generates a string. For example,
  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

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

总体面试体验不错，和面试官们聊的挺开心

少冰半糖谢谢 发表于 2018-11-28 10:04
1）是的 每个节点都服从先占原则。
2）surrounding的意思就是你理解的那样，可以往parent、left、right ...

感谢回复！现在清楚了。。 但是你在楼上说其实是求最大区间。 区间请问你是如何定义的？难道是指最大子树或者是出去一个子树其它node加起来也成为一个区间？ 但是最大不能保证就赢？ 我觉得是这样你看对不对。 比如说一个子树他的左子树有M个点， 右子树有N个点，除去这个子树之外有K个点。 必须满足 K < 1 + m + n && m < k + 1 + n && n < k + 1 + m。 中心思想就是我选了这个点之后，无论你选我的parent 还是我的某个child， 我都能赢。 我觉得要考虑到树unbalance的情况。。。

少冰半糖谢谢 发表于 2018-11-29 02:26
赞同你的理解！但不等式那里我仍然不能苟同。我们就考虑你先选点的情况。一旦你选好了点，其实游戏结果已 ...

我觉得确实我选好点了游戏结果就定了因为对手会选最优的解。正因为如此，我们要判断对手的最优解还是比我能占的点少。。
比如说我选了点A， A的左子树有8个点， A的右子树有一个点，除去A这颗子树有5个点。 如果这时候我的对手选了我的左子树的root， 我就输了， 但是如果他选的我的右子树的顶点或着我的parent （也就是占所有非A子树的点）。那我就赢了。
这也是我的那个不等式的初衷。你能具体说说你的解法吗？你一开始好像说的是最大区间？那以root为起点就是最大区间因为除去root这个字数的点数为0？ 我可能还是没理解你的算法？

lukuang 发表于 2018-11-28 21:41
那咱们先讨论区间的概念吧我觉得这是key， 也是我后面不等式的基础。我觉得区间需要是联通的，也就是说我 ...

赞同你的理解！但不等式那里我仍然不能苟同。我们就考虑你先选点的情况。一旦你选好了点，其实游戏结果已经出来了，这是因为你的对手会选一个最优解（你可以推断出你对手的move从而得到确定的游戏结果。因此，并不需要辅以不等式的判别来判定输赢。anyway，you get the idea！

楼主很棒哦！希望能进！我下个月也要onsite，紧张。想问楼主onsite之前是怎样复习的？

问下LZ第四题是什么思路？谢谢！

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

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

ootsuka 发表于 2018-11-28 06:08
楼主很棒哦！希望能进！我下个月也要onsite，紧张。想问楼主onsite之前是怎样复习的？

加油加油！从我个人观点出发，我觉得夯实基础比较重要吧，多思考一些数据结构、经典算法的应用场景会比刷题有用，还有就是能比较顺畅的把脑子里的逻辑撸成代码，就差不多了。另外放松紧张情绪也很重要，多和面试官说说话！onsite加油！

westcoastboy 发表于 2018-11-28 06:26
**** 本内容被作者隐藏 ****

这是树的题呀，那就是考察树的遍历

xbc1111 发表于 2018-11-28 06:24
问下LZ第四题是什么思路？谢谢！

这道题包装得很好，实则就是通过树的遍历来统计各个分区有多少个点，然后选最大的分区就行了

最后一题，首先我们是不是assume不能再去占别人的点了？楼主能解释一下surrounding具体是什么意思吗？也就是说能去父节点?这样的话是不是别人选了点我就选他的父节点。要我先选我就选root？

第一题题号是？

lukuang 发表于 2018-11-28 07:37
最后一题，首先我们是不是assume不能再去占别人的点了？楼主能解释一下surrounding具体是什么意思吗？也就 ...

1）是的 每个节点都服从先占原则。
2）surrounding的意思就是你理解的那样，可以往parent、left、right拓展
3）选root的策略未必有效，考虑unbalanced tree的情况就明白了。（第二问的assumption是你的对手和你一样机智，在你选完之后，他/她也会选一个对他/她自己最优的解作为starting node