Google实习背靠背

。。第一轮因为原题打得不错 第二轮跪了。。

第一轮：白人小哥 感觉很开朗 很舒服
上来问你你见过最不可思议的bug是什么

地里面经原题
1 .给一个randBetween(double d1, double d2) 返回一个矩形中任意一个点 输入输出自己定义
2. 给一堆矩形， 用randBetween输出这堆矩形中一个点
follow up: 如果call这个func很多次怎么办

第二轮： 白人 吞吞吐吐的  感觉没睡醒 必须要催他才会和你说话。。知道的时候已经浪费了很久
给一个 interface Node {
              Node getLeft();
              Node getRight();
              String toString();
}
给一个树 根节点Node root
           ＊
         ／  \
        +     -
       /  \   /  \
      1   2  3  4
返回(1+2)＊(3－4)

如果（1+2）＋（3＋4）不用去括号
只有叶结点才是数字

一开始用最简单的recursion做的， 发现string＋＝复杂度太高了。。然后我说现在的java string＋底下都是stringbuilder。。试图挽回尊严

然后在他的提示下，改用StringBuilder 做inorder traversl 复杂度降下来了。。

然后在我的追问下才拿出了第二题

给你＊＋12-34 把这个树返回了
简单的不行 所有数字都是1digit。。

求点吃的。。

yuxiang1515 发表于 2017-12-6 09:19
没什么优化 就是把第一次生成的区间存起来 以后每次都做一次binary search就行了

比如两个矩形面积 ...

楼主第一题第二问，用两次getRandom可以么？先把面积累积起来，每一个矩形对应一个区间，第一次对面积random决定在哪个矩形里找，第二次random就是第一问。
第二轮第二问的意思就是perorder重建树咯？

Elina_huang 发表于 2017-12-6 07:00
就是说相当于要call多次randBetween找到多个点嘛？这个能怎样优化呢？

没什么优化 就是把第一次生成的区间存起来 以后每次都做一次binary search就行了

比如两个矩形面积分别是1.0 2.0
第一次call  
存下区间[0.0, 1.0) 是第一个矩形 [1.0, 3.0)是第二个矩形

这样以后每次就从区间里面找就行了

prince123 发表于 2018-1-2 13:57
请问这个怎么“用randBetween输出这堆矩形中一个点”？不是很明白题意

写一个函数，输入是很多矩形（输入要自己定义），然后返回值是这堆矩形中任意一个矩形中的任意一个点（也是自己定义）， 中间过程要用randbetween这个函数

想问一下楼主第一题的foolow up “如果call这个func很多次怎么办” 怎么回答？

Elina_huang 发表于 2017-12-6 06:08
想问一下楼主第一题的foolow up “如果call这个func很多次怎么办” 怎么回答？

我没说清楚 他的意思是还是同样的几个矩形不变 要从同样的矩形里面重新找一个

yuxiang1515 发表于 2017-12-6 06:36
我没说清楚 他的意思是还是同样的几个矩形不变 要从同样的矩形里面重新找一个

就是说相当于要call多次randBetween找到多个点嘛？这个能怎样优化呢？

yuxiang1515 发表于 2017-12-6 09:19
没什么优化 就是把第一次生成的区间存起来 以后每次都做一次binary search就行了

比如两个矩形面积 ...

哦哦谢谢楼主

charlie.wuhan 发表于 2017-12-8 05:02
楼主第一题第二问，用两次getRandom可以么？先把面积累积起来，每一个矩形对应一个区间，第一次对面积ran ...

对 准确地说是三次getRandom 第一次确定是哪个矩形 第二次确实x轴 第三次确定y轴

对

楼主有消息了么现在

请问这个怎么“用randBetween输出这堆矩形中一个点”？不是很明白题意