Google 加面 2.29

风格很诡异的面试，刷题的时候没见过，应该是安卓组的
安卓手机解图形锁的问题，当时看见题目有点懵。。。。然后反应了一下尝试和面试官交流，但是面试官不理我啊！！！摔！！！问啥都说他不能评价我的算法。。。。整个过程没有任何提示和feedback，一开始想要和他确认一下大方向对不对，也不理我。。。没办法了只能说can i start，然后勉强写了一个，也不知道对不对，然后就妥妥地挂了。。。最后一分钟不死心，问他有没有其他解法，还是不说啊。。。。

0 1 2

3 4 5

6 7 8

have to have at least 4 pins

no repeats

can only connect unobstructed pins

4025 <- not valid, 1 blocks 0 and 2  

14025 <- ok, 1 already visited, 0 and 2 are not blocked

input: string (ex: 0125)

output: boolean (true if valid)

楼主pat pat，曾经面Amazon也遇到过类似的面试官，写的过程完全不理你，给人感觉很差。楼主怎么解决的这题的？我感觉可以依次检查input string中相邻字符，看在graph中这两个位置中间有没有unvsited node。检查完就把已检查的标记为visited。

还可以走回走过的路径？那其实是不是只要数字在密码板上能连在一起（像一个island那样）就是valid的？

我有个比较笨的想法是先把input string里的数字存到HashSet里，然后从其中一个存在的数字那个cell开始做BFS（加个boolean数组记录visited），traverse到一个匹配的就从HashSet删除掉对应的数字，如果遇到不匹配的就不在那条路上继续走。这样到最后如果HashSet被删空了就证明是Valid的，不然就不valid？BFS的邻居可以用数字+3,-3,+1,-1来处理？

Ulu2005 发表于 2016-3-10 05:56
楼主pat pat，曾经面Amazon也遇到过类似的面试官，写的过程完全不理你，给人感觉很差。楼主怎么解决的这题 ...

我就直接按要求一步一步地判断，依次检查input，如果不相邻，找这两个字符的连接点，看连接它们的字符之前有没有被访问过。然后我卡在怎么找两个字符连接的地方很久很久。。。最后无奈写了一堆if else

这题面经有过的，写起来还是比较麻烦的

lc题目变种