Google/Youtube跪经

第四题也是我的onsite题，面试官引导用dfs做的
那轮feedback是strong hire
不过最后Youtube onsite没过就是了。。。三个老鹰。。。两轮被黑

daddyyang 发表于 2016-11-23 12:41
我擦...那还真的有点难啊...
我是用这个思路写的

哈哈哈！抓到野生的晟神

jy_121 发表于 2016-11-23 12:27
我认了

有人贴了这个链接讲得挺好的：
http://xwk.iteye.com/blog/2129621

基本意思是构造一个有10^3个节点，10^4个边的有向图，每个节点为三位数abc，并且只在相对形式为abc, bcd的节点有向连边abc->bcd，并且该边就表示四位数abcd。很容易看出任何节点的出边和入边都是10个（相等），所以该有向图一定是欧拉图（可以无重复边一笔画）。下面的工作就是怎么实现一个一笔画路径了。

spwahaha 发表于 2016-11-24 13:00
我的思路和你相似，你这个为什么不是等概率的呢？？ 感觉应该是啊，每个位置都是完全随机的

我的算法bias在于前2个格子是完全自由度的，但第3个格子的概率分布又依赖于前2个格子的candy相同与否。例如两个合理3X3棋盘（假设共4种candy）：
A:        B:
112     123
112     231
221     312
生成A的概率=((1/4)(1/4)(1/3))^2*(1/3)^3=1/62208;
生成B的概率=(1/4)^9=1/262144。
这个差异的形成从位置(0,2)就开始了，A(0,2)=2的概率为1/3，B(0,2)=2的概率为1/4。或者说candy(0,0)==candy(0,1)的合理棋盘个数其实不等于candy(0,0)！=candy(0,1)的合理棋盘个数，但我的算法中因为顺序的原因用独立1/4等概率分别生成candy(0,0)和candy(0,1)，这个无法保证整体棋盘的等概率。

还可以简化的用一个3X1长方形验证：4种candy，合理棋盘显然有4^3-4=60种，所以若严格等概率应该每个合理棋盘以1/60概率生成。但实际上“candy(0,0)==candy(0,1)”类型的棋盘有12个，每个以概率1/48生成，而“candy(0,0)！=candy(0,1)”类型的棋盘有48个，每个以概率1/64生成.

所以“同类型”的合理棋盘概率的确是均等的，但不同类型的却不是。就看面试官是要求exactly均等还是尽量均等了。

zzgzzm 发表于 2016-11-24 14:23
我的算法bias在于前2个格子是完全自由度的，但第3个格子的概率分布又依赖于前2个格子的candy相同与否。例 ...

恩，挺有道理的，我面到这一道题了，写的代码和你思路一样，面试官没有提出异议，所以觉得这个思路应该是可以的

spwahaha 发表于 2016-11-24 23:09
恩，挺有道理的，我面到这一道题了，写的代码和你思路一样，面试官没有提出异议，所以觉得这个思路应该是 ...

我也觉得这样应该就可以了。说实在的，就连求3X3合理棋盘有多少个都不是很容易。

zzgzzm 发表于 2016-11-24 13:09
有人贴了这个链接讲得挺好的：
http://xwk.iteye.com/blog/2129621

多谢，学习了

daddyyang 发表于 2016-11-23 12:41
我擦...那还真的有点难啊...
我是用这个思路写的

请问，用backtracking（其实也就是暴力）的具体时间复杂度是怎么分析的呢？应该不是O(10^k)吧？谢谢回复哦！

zzgzzm 发表于 2016-11-24 12:29
我不是LZ.
这个应该就是将所有点存在hashset中，对任意两点(x1,y1), (x2,y2)，查找(x1,y2), (x2,y1)是否 ...

(x,y)点对这样的东西怎么存到hashset里? 我知道至少python做不到, 难道用内存地址作为hashcode?

补充内容 (2016-12-28 14:00):
刚试了一下, python还真可以, 打脸了..

lhh_NJU 发表于 2016-12-28 13:59
(x,y)点对这样的东西怎么存到hashset里? 我知道至少python做不到, 难道用内存地址作为hashcode?

补充内 ...

C++是比较原始，不能直接定义unordered_set<pair<int,int>>，会有编译错误，应为没有默认的hash。
这种情况我是用unordered_map<int, unordered_set<int>> 来模拟，这样用 c.count(x) && c[x].count(y)就可以判断点(x,y)是否在container中。

PS：话说看来我必须开始学一下Python/Java了；C++真的是太原始了。