一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2017|回复: 20
收起左侧

GOOGLE 4/14 电面

[复制链接] |试试Instant~ |关注本帖
Hualiang 发表于 2016-4-15 08:45:58 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
发个google 跪经, 一个三哥面的。感觉他人应该不错,有试着提示我,可是那英语好难理解呀。。。
好了,上题:
Find the total number of patterns of the Android lock screen. The number of key used has to be at least 4, and max 9.
Example: -google 1point3acres
use 5 keys:
OAB
OOC
OED

OAB
OCD
OOE....

Same thing goes with 4, 6, 7, 8, 9 keys. Count the total possible pattern. The order of keys used matters.. 鍥磋鎴戜滑@1point 3 acres

看到这个题一点想法都没有。。。

评分

1

查看全部评分

Fustang 发表于 2016-4-15 09:37:13 | 显示全部楼层
不用Android 理解了半天 要第一次面这个我肯定也跪
弄懂题意后感觉是DFS
不过看了大神解法又跪了 好多case 还考虑到knight move 真是牛b. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
https://www.careercup.com/question?id=5663422257561600
回复 支持 反对

使用道具 举报

woridage1 发表于 2016-4-15 09:37:32 | 显示全部楼层
啥意思,没看明白题目......
回复 支持 反对

使用道具 举报

jerry_lin324 发表于 2016-4-15 09:41:10 | 显示全部楼层
兄弟你这题的确有点难。。。。. visit 1point3acres.com for more.

补充内容 (2016-4-15 09:51):
DFS,从任意点[x][y]开始遍历,当距离等于5的时候,count+1。遍历的时候有8个方向。。。我记着实际中这个lock好像可以是这样:
比如
012
345
678
一个五步path为1->2->4->3->4
回复 支持 反对

使用道具 举报

Fustang 发表于 2016-4-15 09:42:22 | 显示全部楼层
woridage1 发表于 2016-4-15 09:37
啥意思,没看明白题目......

OAB
OOC. Waral 鍗氬鏈夋洿澶氭枃绔,
OED

这个的意思是对于键盘.鏈枃鍘熷垱鑷1point3acres璁哄潧
012
345
678

一个五步的path是 1->2->5->8->7
回复 支持 反对

使用道具 举报

woridage1 发表于 2016-4-15 10:03:30 | 显示全部楼层
. 鍥磋鎴戜滑@1point 3 acres
是用递归加回溯吗,分别从9个点开始9次,然后每次分别往四个方向进行检索,访问过的给设置成一个特殊的符号,直到层数为 4或者其他要求的层数就计数器加一,然后返回。
回复 支持 反对

使用道具 举报

Fustang 发表于 2016-4-15 10:09:48 | 显示全部楼层
woridage1 发表于 2016-4-15 10:03
是用递归加回溯吗,分别从9个点开始9次,然后每次分别往四个方向进行检索,访问过的给设置成一个特殊的符 ...

不仅是相邻的方向
还可以diag move(斜线)和knight move(日字)-google 1point3acres
以及jump已经lit的点
参见我上面给的careercup链接
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-15 11:27:45 | 显示全部楼层
Fustang 发表于 2016-4-15 10:09
不仅是相邻的方向
还可以diag move(斜线)和knight move(日字)
以及jump已经lit的点

感觉careerup那哥们的解法也不太对吧。。
回复 支持 反对

使用道具 举报

moonstone 发表于 2016-4-15 12:19:34 | 显示全部楼层
感觉像subset啊
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-15 14:07:37 | 显示全部楼层
看见 这种题目 太容易 让人懵了。其实 应该问清楚 需不需要考虑knight move
回复 支持 反对

使用道具 举报

Eclat 发表于 2016-4-19 10:37:38 | 显示全部楼层
如果各种方向都可以走的话,而且Android lock screen不是如果已经走了一个点,再路过它的时候就不算了么,这样的话,总的pattern数不是C(4,9) *A(4,4) +C(5, 9) * A(5,5) + C(6, 9)*A(6,6) + C(7,9)*A(7,7) + C(8,9)*A(8,8) + C(9,9)*A(9,9) ?
回复 支持 反对

使用道具 举报

 楼主| Hualiang 发表于 2016-4-19 11:01:42 来自手机 | 显示全部楼层
不可以跳着走的
回复 支持 反对

使用道具 举报

oh_yee 发表于 2016-4-19 11:56:59 | 显示全部楼层
首先根据9宫格, 建立无向图。
从任意一点开始, BFS (默认不能jump), 并且记录下已经走过的步数。
每经过一个节点, 剩余步数减1. (经过一个节点后, 此节点是否还能再被Visit,需要和面试官确认)
当步数为0时,停止。

取步数为4,5,6,7,8,9, 分别记录下pattern。


根据要求,返回不同的pattern, 或者返回一个总数。
. 鍥磋鎴戜滑@1point 3 acres

My two cents
回复 支持 反对

使用道具 举报

kiviljc 发表于 2016-4-19 21:58:21 | 显示全部楼层
Fustang 发表于 2016-4-15 10:09
不仅是相邻的方向
还可以diag move(斜线)和knight move(日字).鐣欏璁哄潧-涓浜-涓夊垎鍦
以及jump已经lit的点

肯定是8个方向,,,玩下安卓解锁就都知道了。
回复 支持 反对

使用道具 举报

snakefly 发表于 2016-4-19 22:21:03 | 显示全部楼层
如果没有限制的话,感觉是permutationd的变种
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果不能夸数字, 比如1 不能到 3, 4, 9的话, 要把1,3,7,9单独拿出来考虑。。。额 这个思路感觉还挺复杂的。-google 1point3acres

123
456
789

补充内容 (2016-4-19 22:21):. 1point3acres.com/bbs
1 不能到3, 7 , 9
回复 支持 反对

使用道具 举报

laoxie09 发表于 2016-4-20 00:30:47 | 显示全部楼层
组合数学题啊……
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-20 01:04:44 | 显示全部楼层
电面考这个太难了吧。。。
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2016-5-4 03:14:45 | 显示全部楼层
  1. package google;
  2. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3. import java.util.*;. more info on 1point3acres.com

  4. public class AndroidKeyBoard {
  5.         char[][] board = { { '1', '2', '3' }, { '4', '5', '6' }, { '7', '8', '9' } };-google 1point3acres

  6.         public List<String> generate() {
  7.                 // Set<String> result = new HashSet<String>();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.                 List<String> result = new ArrayList<>();
  9.                 for (int i = 0; i < board.length; i++) {
  10.                         for (int j = 0; j < board[0].length; j++) {
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.                                 helper(result, "", i, j);
  12.                         }
  13.                 }
  14.                 System.out.println(result.size());
  15.                 return result;
  16.         }
  17. . From 1point 3acres bbs
  18.         private void helper(List<String> result, String temp, int x, int y) {
  19.                 if (x < 0 || y < 0 || x >= board.length || y >= board[0].length
  20.                                 || board[x][y] == '*')
  21.                         return;. visit 1point3acres.com for more.

  22.                 char t = board[x][y];

  23.                 temp += board[x][y];.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.                 if (temp.length() >= 4) {
  25.                         result.add(temp);
  26.                 }

  27.                 board[x][y] = '*';
  28.                 helper(result, temp, x - 1, y + 1);-google 1point3acres
  29. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  30.                 // 8 directional
  31.                 helper(result, temp, x - 1, y - 1);
  32.                 helper(result, temp, x - 1, y);
  33.                 helper(result, temp, x, y - 1);. visit 1point3acres.com for more.
  34.                 helper(result, temp, x, y + 1);
  35.                 helper(result, temp, x + 1, y + 1);
  36.                 helper(result, temp, x + 1, y);
  37.                 helper(result, temp, x + 1, y - 1);

  38.                 // cross!
  39.                 helper(result, temp, x - 2, y - 1);-google 1point3acres
  40.                 helper(result, temp, x + 2, y - 1);
  41.                 helper(result, temp, x - 2, y + 1);
  42.                 helper(result, temp, x + 2, y + 1);

  43.                 helper(result, temp, x + 1, y - 2);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  44.                 helper(result, temp, x - 1, y - 2);
  45.                 helper(result, temp, x + 1, y + 2);
  46.                 helper(result, temp, x - 1, y + 2);

  47.                 // allow jump
  48.                 if (x + 1 < board.length && board[x + 1][y] == '*')
  49.                         helper(result, temp, x + 2, y);
  50.                 if (y + 1 < board[0].length && board[x][y + 1] == '*')
  51.                         helper(result, temp, x, y + 2);
  52.                 if (x > 0 && board[x - 1][y] == '*')
  53.                         helper(result, temp, x - 2, y);. more info on 1point3acres.com
  54.                 if (y > 0 && board[x][y - 1] == '*')
  55.                         helper(result, temp, x, y - 2);
  56.                 if (x > 0 && y > 0 && board[x - 1][y - 1] == '*')
  57.                         helper(result, temp, x - 2, y - 2);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  58.                 if (x + 1 < board.length && y + 1 < board[0].length
  59.                                 && board[x + 1][y + 1] == '*'). 1point3acres.com/bbs
  60.                         helper(result, temp, x + 2, y + 2);
  61.                 if (x > 0 && y + 1 < board[0].length && board[x - 1][y + 1] == '*')
  62.                         helper(result, temp, x - 2, y + 2);
  63.                 if (x + 1 < board.length && y > 0 && board[x + 1][y - 1] == '*')
  64.                         helper(result, temp, x + 2, y - 2);
  65.                 board[x][y] = t;
  66.         }

  67.         public static void main(String args[]) {
  68.                 AndroidKeyBoard android = new AndroidKeyBoard();
  69.                 android.generate();
  70.         }
  71. }
复制代码
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-5-4 11:30:26 | 显示全部楼层
题意是遍历9宫格所有长度为4-9的pattern,并且点不重复?也不就是number of island的变种吗?抱歉,我看了10分钟的题目,还是看不懂。。。。
OAB
OOC
OED
请问上面这个pattern是什么意思?
回复 支持 反对

使用道具 举报

 楼主| Hualiang 发表于 2016-5-4 11:32:13 | 显示全部楼层
hison7463 发表于 2016-5-4 11:30. 1point3acres.com/bbs
题意是遍历9宫格所有长度为4-9的pattern,并且点不重复?也不就是number of island的变种吗?抱歉,我看了1 ...

就是从A到E,如果AB位置对调了就是别外一个pattern
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 21:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表