一道亚麻电面题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道亚麻电面题目

一道亚麻电面题目# JobHunting - 待字闺中

m*22015-04-29 07:04

1 楼

上周面亚麻，一个犹太人，上来先是一道常规OOD，还没讲完就被打断，说时间有限，
下一道。
然后是道coding的题目。这道题目看似简单，但是感觉有不少边界条件要考虑。
题目如下：
安卓手机解锁画面，给定任意一个解锁图形，不知道起始点，输出所有可能的path。
本能的觉得应该用DFS遍历，但是花了很多时间思考何时应该backtrack返回。估计这题
应该是挂了。
有没有大神能给点思路啊

r*g2015-04-29 07:04

2 楼

不是标记当前可走的, 没有了就返回吗?
还是我题意理解错了

【在 m**********2 的大作中提到】

: 上周面亚麻，一个犹太人，上来先是一道常规OOD，还没讲完就被打断，说时间有限，
: 下一道。
: 然后是道coding的题目。这道题目看似简单，但是感觉有不少边界条件要考虑。
: 题目如下：
: 安卓手机解锁画面，给定任意一个解锁图形，不知道起始点，输出所有可能的path。
: 本能的觉得应该用DFS遍历，但是花了很多时间思考何时应该backtrack返回。估计这题
: 应该是挂了。
: 有没有大神能给点思路啊

e*72015-04-29 07:04

3 楼

亚麻最近变难了？

x*u2015-04-29 07:04

4 楼

LZ上个图吧, 有图比较好说.

m*22015-04-29 07:04

5 楼

其实应该是这样一个思路，标记当前可走的，如果没有就返回，但是这样并不能保证图
形是match的，因为起点可以是任意一个点，需要找个方法判断所有的边都被访问过了
。默认是undirected graph。一直到现在都没什么思路。LC上貌似graph的题不多啊。

【在 r*g 的大作中提到】

:
: 不是标记当前可走的, 没有了就返回吗?
: 还是我题意理解错了

y*32015-04-29 07:04

6 楼

给定任意一个解锁图形，不知道起始点，输出所有可能的path。
感觉没太懂什么意思…………
如果我没理解错的话，以及以安卓解锁图案必需一笔画为前提
之前网上有过一个破解安卓开机手势的教程，方法就是9个点标号0-8，所有组合跑一边。
0 1 2
3 4 5
6 7 8
所以：
1）如果图形是闭合的，比如 0367840 这种，那就每个点都作为起点输出一个path
2）如果图形不闭合，正向反向各一种，就两种。
但隐隐感觉自己这种方法哪里不对…………就当抛砖引玉吧…………