《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 3907|回复: 20
收起左侧

GOOGLE 4/14 电面

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

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

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

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

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: . more info on 1point3acres.com
use 5 keys:
OAB
OOC
OED. From 1point 3acres bbs

OAB
OCD
OOE....

Same thing goes with 4, 6, 7, 8, 9 keys. Count the total possible pattern. The order of keys used matters.

看到这个题一点想法都没有。。。.1point3acres缃

评分

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 | 显示全部楼层
兄弟你这题的确有点难。。。。. 1point3acres.com/bbs
. more info on 1point3acres.com
补充内容 (2016-4-15 09:51):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
DFS,从任意点[x][y]开始遍历,当距离等于5的时候,count+1。遍历的时候有8个方向。。。我记着实际中这个lock好像可以是这样:
比如
012
345. more info on 1point3acres.com
678
一个五步path为1->2->4->3->4
回复 支持 反对

使用道具 举报

Fustang 发表于 2016-4-15 09:42:22 | 显示全部楼层
woridage1 发表于 2016-4-15 09:37
啥意思,没看明白题目......
. 1point3acres.com/bbs
OAB
OOC.鐣欏璁哄潧-涓浜-涓夊垎鍦
OED. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

这个的意思是对于键盘
012
345. from: 1point3acres.com/bbs
678. 1point3acres.com/bbs

一个五步的path是 1->2->5->8->7. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

woridage1 发表于 2016-4-15 10:03:30 | 显示全部楼层

是用递归加回溯吗,分别从9个点开始9次,然后每次分别往四个方向进行检索,访问过的给设置成一个特殊的符号,直到层数为 4或者其他要求的层数就计数器加一,然后返回。
回复 支持 反对

使用道具 举报

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

不仅是相邻的方向
还可以diag move(斜线)和knight move(日字)
以及jump已经lit的点. from: 1point3acres.com/bbs
参见我上面给的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), 并且记录下已经走过的步数。. 1point 3acres 璁哄潧
每经过一个节点, 剩余步数减1. (经过一个节点后, 此节点是否还能再被Visit,需要和面试官确认). visit 1point3acres.com for more.
当步数为0时,停止。

取步数为4,5,6,7,8,9, 分别记录下pattern。. from: 1point3acres.com/bbs

. visit 1point3acres.com for more.
根据要求,返回不同的pattern, 或者返回一个总数。.1point3acres缃


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单独拿出来考虑。。。额 这个思路感觉还挺复杂的。.1point3acres缃

123
456
789

补充内容 (2016-4-19 22:21):
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;. From 1point 3acres bbs

  2. import java.util.*;

  3. public class AndroidKeyBoard {
  4.         char[][] board = { { '1', '2', '3' }, { '4', '5', '6' }, { '7', '8', '9' } };
  5. .1point3acres缃
  6.         public List<String> generate() {. 1point 3acres 璁哄潧
  7.                 // Set<String> result = new HashSet<String>();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.                         }. from: 1point3acres.com/bbs
  13.                 }
  14.                 System.out.println(result.size()); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.                 return result;
  16.         }
  17. . more info on 1point3acres.com
  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;

  22.                 char t = board[x][y];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  23.                 temp += board[x][y];. 1point3acres.com/bbs
  24.                 if (temp.length() >= 4) {
  25.                         result.add(temp);
  26.                 }

  27.                 board[x][y] = '*';. from: 1point3acres.com/bbs
  28.                 helper(result, temp, x - 1, y + 1);
  29. . more info on 1point3acres.com
  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);
  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);. 1point 3acres 璁哄潧
  38. -google 1point3acres
  39.                 // cross!.鐣欏璁哄潧-涓浜-涓夊垎鍦
  40.                 helper(result, temp, x - 2, y - 1);
  41.                 helper(result, temp, x + 2, y - 1);
    . visit 1point3acres.com for more.
  42.                 helper(result, temp, x - 2, y + 1);
  43.                 helper(result, temp, x + 2, y + 1);

  44.                 helper(result, temp, x + 1, y - 2);
  45.                 helper(result, temp, x - 1, y - 2);
  46.                 helper(result, temp, x + 1, y + 2);. visit 1point3acres.com for more.
  47.                 helper(result, temp, x - 1, y + 2);
  48. . Waral 鍗氬鏈夋洿澶氭枃绔,
  49.                 // allow jump
  50.                 if (x + 1 < board.length && board[x + 1][y] == '*')
  51.                         helper(result, temp, x + 2, y);
  52.                 if (y + 1 < board[0].length && board[x][y + 1] == '*')
  53.                         helper(result, temp, x, y + 2);
  54.                 if (x > 0 && board[x - 1][y] == '*')
  55.                         helper(result, temp, x - 2, y);
  56.                 if (y > 0 && board[x][y - 1] == '*')
  57.                         helper(result, temp, x, y - 2);
  58.                 if (x > 0 && y > 0 && board[x - 1][y - 1] == '*').鐣欏璁哄潧-涓浜-涓夊垎鍦
  59.                         helper(result, temp, x - 2, y - 2);.1point3acres缃
  60.                 if (x + 1 < board.length && y + 1 < board[0].length
  61.                                 && board[x + 1][y + 1] == '*')
  62.                         helper(result, temp, x + 2, y + 2);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  63.                 if (x > 0 && y + 1 < board[0].length && board[x - 1][y + 1] == '*')
  64.                         helper(result, temp, x - 2, y + 2);
  65.                 if (x + 1 < board.length && y > 0 && board[x + 1][y - 1] == '*')
  66.                         helper(result, temp, x + 2, y - 2);
  67.                 board[x][y] = t;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  68.         }

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

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-24 10:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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