Google/Youtube跪经

WTYJack 发表于 2016-11-24 05:13
同想问第一题怎么做。。感觉可以分治 nlogn

麻烦问一下如果是两个点确定矩形的话，怎么分治， 能不能说下

zhan1612 发表于 2016-11-24 10:11
楼主最后是不是比较了一下所有点pi, pj? 按o(n^2) 做的？

嗯，我是这么做的

神罗天征 发表于 2016-11-23 12:18
我去年发帖问过，至今不会
http://www.1point3acres.com/bbs/thread-166111-1-1.html

这个题虽然没见过，但是之前看一篇博文说过一个二进制串的类似问题，用DFA做，我琢磨一下

jy_121 发表于 2016-11-24 11:41
嗯，我是这么做的

问下楼主消糖果的第二题有follow up 吗？？

zhan1612 发表于 2016-11-24 10:11
楼主最后是不是比较了一下所有点pi, pj? 按o(n^2) 做的？

我不是LZ.
这个应该就是将所有点存在hashset中，对任意两点(x1,y1), (x2,y2)，查找(x1,y2), (x2,y1)是否在hashset中。若在就用面积abs(x1-x2)*abs(y1-y2)更新最小值。
还有一种用平行线，再找sorted points 的公共坐标，但不如以上的直接。

jy_121 发表于 2016-11-23 12:18
第二题忘说了。。。要求初始游戏，所有珠宝的位置随机，种类也随机，放满棋盘。

第二轮，珠宝游戏。这个看来是高频的candy crush了。请问面试官是否要求要exactly等概率生成一个valid棋盘？也就是说若所以valid棋盘有N个，那么必须以1/N概率随机返回一个棋盘？

spwahaha 发表于 2016-11-24 12:20
问下楼主消糖果的第二题有follow up 吗？？

没有，字数字数

jy_121 发表于 2016-11-23 12:18
第二题忘说了。。。要求初始游戏，所有珠宝的位置随机，种类也随机，放满棋盘。

我写了一个4种candy随机生成棋盘：
http://www.1point3acres.com/bbs/thread-212722-1-1.html

但是我用简单例子测试了一下，好像不是exactly等概率返回棋盘的。请问面试官是要求等概率吗？这个好像很难。

zzgzzm 发表于 2016-11-24 12:32
第二轮，珠宝游戏。这个看来是高频的candy crush了。请问面试官是否要求要exactly等概率生成一个valid棋 ...

嗯，肯定是随机生成的。额，看面经时没见到这一道。。。

zzgzzm 发表于 2016-11-24 12:41
我写了一个4种candy随机生成棋盘：
http://www.1point3acres.com/bbs/thread-212722-1-1.html

我的思路和你相似，你这个为什么不是等概率的呢？？ 感觉应该是啊，每个位置都是完全随机的