一亩三分地论坛

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

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

Uber 电面, 没见过的题目

[复制链接] |试试Instant~ |关注本帖
dylanwen 发表于 2015-10-16 06:20:23 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Uber - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
看了很久的面经,来回馈一下地里。
一个白人面试官。迟到了大概5分钟。然后上来问了下简历。就开始做题目了。从来没有见过的题目。题目是这样的:
假设给你一个2D array由'\'和'/'构成。让你求这些slashes把整个区域分成了几个区间。举个例子:
假设输入是:
/\/
\/\
那么需要返回6。我一开始没听懂题目意思,让他解释一番。他说你可以这样看:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
----------.鐣欏璁哄潧-涓浜-涓夊垎鍦
A/F\B/C
D\F/E\C
-----------
其中字母代表的是区域的标号。
如果各位没看懂的话我再举个例子。input是这个. From 1point 3acres bbs
/\\
/\/. from: 1point3acres.com/bbs
/\\

返回还是6。,因为整个可以分成这样:
----------
B/\C\D
/CC\C\. from: 1point3acres.com/bbs
C/\CC/
/EE\/F
E/\E\F
/GG\E\
----------。. 1point 3acres 璁哄潧
给我解释了大概十分钟后我终于明白要干什么了。开始想思路。想了一会没想法,面试官提示说你可以写一个函数

def find_neighbors(i, j, is_left)
返回这个矩阵中i,j可以到的其他位置,is_left表示的是这个位置是在slash的左边还是右边,到这里我大概知道这是一个DFS或者是BFS的问题了。开始写,这时候时间已经过去半个小时了。结果还在整理思路,考虑各种相邻的\/情况的时候,白人告诉我时间到了,你问我几个问题吧。然后随便问了几个问题就挂电话了。
总共加上他迟到的5分钟才面了40分钟。其中五分钟简历,十分钟弄清楚题意。真是挂得惨啊,白人geek伤不起。

如果有什么不清楚得尽管问。求大神指点这题啊!另外求点大米啊!

. 1point 3acres 璁哄潧

评分

4

查看全部评分

maplain 发表于 2015-10-16 14:21:26 | 显示全部楼层
dylanwen 发表于 2015-10-16 08:47
不是很理解你怎么确定字母可以改的。
你能试下这个case嘛?. 1point3acres.com/bbs
/\/

感觉就是沿着边dfs。。只不过就是dfs的时候分类写的比较烦。。下面是代码,求大神指点。
  1. class Slashes {
  2.     private final byte LEFT = 0X1;
  3.     private final byte RIGHT = 0X2;
  4.     public int num(char[][] slashes) {. more info on 1point3acres.com
  5.         int n = slashes.length;
  6.         int m = slashes[0].length;
  7.         byte[][] infos = new byte[n][m];
  8.         int result = 0;
  9.         for (int i=0; i<n; ++i) {
  10.             for (int j=0; j<m; ++j) {
  11.                 if ((infos[i][j] & LEFT) == 0) {
  12.                     dfs(infos, slashes, i, j, LEFT, n, m);
  13.                     result++;
  14.                 }. 1point3acres.com/bbs
  15.                 if ((infos[i][j] & RIGHT) == 0) {. From 1point 3acres bbs
  16.                     dfs(infos, slashes, i, j, RIGHT, n, m);
  17.                     result++;
  18.                 }
  19.             }
  20.         }
  21.         return result;
  22.     }
    . 1point 3acres 璁哄潧
  23.     private void dfs(byte[][] infos, char[][] slashes, int x, int y, byte pos, int n, int m) {
  24.         infos[x][y] |= pos;. From 1point 3acres bbs
  25.         if (slashes[x][y] == '/') {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  26.             if (pos == LEFT) {
  27.                 if (x-1>=0 && (infos[x-1][y] & RIGHT) == 0) {
  28.                     dfs(infos, slashes, x-1, y, RIGHT, n, m);
  29.                 }
  30.                 if (y-1>=0) {
  31.                     if (slashes[x][y-1] == '/') {
  32.                         if ((infos[x][y-1] & RIGHT) == 0) dfs(infos, slashes, x, y-1, RIGHT, n, m);
  33.                     } else {
  34.                         if ((infos[x][y-1] & LEFT) == 0) dfs(infos, slashes, x, y-1, LEFT, n, m);
  35.                     }
  36.                 }
  37.             } else {
  38.                 if (x+1<n && (infos[x+1][y] & LEFT) == 0) {
  39.                     dfs(infos, slashes, x+1, y, LEFT, n, m);
  40.                 }.1point3acres缃
  41.                 if (y+1<m) {
  42.                     if (slashes[x][y+1] == '/') {
  43.                         if ((infos[x][y+1] & LEFT) == 0) dfs(infos, slashes, x, y+1, LEFT, n, m);
  44.                     } else { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  45.                         if ((infos[x][y+1] & RIGHT) == 0) dfs(infos, slashes, x, y+1, RIGHT, n, m);
  46.                     }
  47.                 }
  48.             }
  49.         } else {. more info on 1point3acres.com
  50.             if (pos == LEFT) {
  51.                 if (x-1>=0 && (infos[x-1][y] & RIGHT) == 0) {
  52.                     dfs(infos, slashes, x-1, y, RIGHT, n, m);
  53.                 }. from: 1point3acres.com/bbs
  54.                 if (y+1<m) {
  55.                     if (slashes[x][y+1] == '/') {.1point3acres缃
  56.                         if ((infos[x][y+1] & LEFT) == 0) dfs(infos, slashes, x, y+1, LEFT, n, m);. visit 1point3acres.com for more.
  57.                     } else {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  58.                         if ((infos[x][y+1] & RIGHT) == 0) dfs(infos, slashes, x, y+1, RIGHT, n, m);
  59.                     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  60.                 }
  61.             } else {
  62.                 if (x+1<n && (infos[x+1][y] & LEFT) == 0) {
  63.                     dfs(infos, slashes, x+1, y, LEFT, n, m);.1point3acres缃
  64.                 }
  65.                 if (y-1>=0) {. 1point 3acres 璁哄潧
  66.                     if (slashes[x][y-1] == '/') {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  67.                         if ((infos[x][y-1] & RIGHT) == 0) dfs(infos, slashes, x, y-1, RIGHT, n, m);
  68.                     } else {
  69.                         if ((infos[x][y-1] & LEFT) == 0) dfs(infos, slashes, x, y-1, LEFT, n, m);
  70.                     }
  71.                 }
  72.             }
  73.         }
  74.     }
  75.     public static void main(String[] args) {. visit 1point3acres.com for more.
  76.         Slashes s = new Slashes();
  77.         char[][] e1 = {
  78.             {'/', '\\', '/'},
  79.             {'\\', '/', '\\'},-google 1point3acres
  80.         };
  81.         char[][] e2 = {
  82.             {'/', '\\', '\\'},
  83.             {'/', '\\', '/'},
  84.             {'/', '\\', '\\'},
  85.         };.鏈枃鍘熷垱鑷1point3acres璁哄潧
  86.         char[][] e3 = {
  87.             {'/', '\\', '/'},
  88.             {'\\', '\\', '\\'},
  89.         };
  90.         System.out.println(s.num(e1));
  91.         System.out.println(s.num(e2));. visit 1point3acres.com for more.
  92.         System.out.println(s.num(e3));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  93.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  94. }
复制代码

补充内容 (2015-10-16 14:22):
感觉和LC Number of Islands(200): https://leetcode.com/problems/number-of-islands/
一样。。
回复 支持 1 反对 0

使用道具 举报

mlfma 发表于 2015-10-16 06:42:26 | 显示全部楼层
这个第2个例子input有3行,为什么output有6行?
回复 支持 反对

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 06:44:02 | 显示全部楼层
mlfma 发表于 2015-10-16 06:42
这个第2个例子input有3行,为什么output有6行?

那个不是output。只是举个例子为什么需要返回6。最后只需要返回一个int,就是有多少个regions
回复 支持 反对

使用道具 举报

maplain 发表于 2015-10-16 07:05:04 | 显示全部楼层
沿着边dfs咩。
回复 支持 反对

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 07:05:54 | 显示全部楼层
mlfma 发表于 2015-10-16 06:42
这个第2个例子input有3行,为什么output有6行?

这个需要对应那个3x3的input看一下。这样子就能看得清楚一些。
回复 支持 反对

使用道具 举报

Aaron_Liu 发表于 2015-10-16 08:11:14 | 显示全部楼层
初始化:. more info on 1point3acres.com
每个cell放两个字母,即array[i][j] 包含两个字母,同时在i行上相邻的两个cell有一个字母相同,即array[i][j][1] == array[i][j+1][0],那么初始化后如下:
A/B, B\C, C/D
E\F, F/G, G\H

for循环:
array[i][j] 和 array[i][j+1]去比较,同时把array[i][j+1]中某一个字母改成和array[i][j]中的某一个字母
array[0][0]
A/B ==> A/B
E\F         E\B

array[0][1]
B\C ==> B\C
F/G         B/G

array[0][2].鐣欏璁哄潧-涓浜-涓夊垎鍦
C/D ==> C/D. 鍥磋鎴戜滑@1point 3 acres
G\H         G\D-google 1point3acres

数字母:
A/B, B\C, C/D ==> A, B, C, D, E, G ==> 6个.1point3acres缃
E\B, B/G, G\D

时间:O(n)
空间:O(n)
回复 支持 反对

使用道具 举报

Aaron_Liu 发表于 2015-10-16 08:22:39 | 显示全部楼层
Aaron_Liu 发表于 2015-10-16 08:11
初始化:
每个cell放两个字母,即array[j] 包含两个字母,同时在i行上相邻的两个cell有一个字母相同,即ar ...

应该在数字母以后,再加上一步,去检查array[j][1] 是否和 array[j][0]相等,如果不相等,就需要-1,这是通过第二个例子测试出来的。
回复 支持 反对

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 08:47:55 | 显示全部楼层
Aaron_Liu 发表于 2015-10-16 08:11
初始化:
每个cell放两个字母,即array[j] 包含两个字母,同时在i行上相邻的两个cell有一个字母相同,即ar ...

不是很理解你怎么确定字母可以改的。
你能试下这个case嘛?
/\/
\\\
这样应该返回5
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-10-16 12:49:19 | 显示全部楼层
LZ,你的面试官是谁呀
回复 支持 反对

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 12:50:44 | 显示全部楼层
f1371342385 发表于 2015-10-16 12:49
LZ,你的面试官是谁呀
. 鍥磋鎴戜滑@1point 3 acres
一个叫Ivan得。查了下好像是从波兰来的。
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-10-16 12:55:04 | 显示全部楼层
dylanwen 发表于 2015-10-16 12:50
一个叫Ivan得。查了下好像是从波兰来的。

感谢LZ哈
回复 支持 反对

使用道具 举报

猥琐的老吴 发表于 2015-10-16 13:46:12 | 显示全部楼层
这题看上去实在是好贱,楼主面的啥职位呀,是server端么?
回复 支持 反对

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 13:49:35 | 显示全部楼层
猥琐的老吴 发表于 2015-10-16 13:46
这题看上去实在是好贱,楼主面的啥职位呀,是server端么?

哈哈,终于等到一个人骂这题得了。我当时网上填表得时候填得backend和real time。貌似面试官是backend得。
PS:他最后要我问问题得时候,我真想问你干嘛给我出一个这种题。
回复 支持 反对

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 14:31:34 | 显示全部楼层
maplain 发表于 2015-10-16 14:21
感觉就是沿着边dfs。。只不过就是dfs的时候分类写的比较烦。。下面是代码,求大神指点。

补充内容 (2015 ...

我感觉你这个应该是对的
回复 支持 反对

使用道具 举报

猥琐的老吴 发表于 2015-10-16 14:54:15 | 显示全部楼层
dylanwen 发表于 2015-10-16 13:49
哈哈,终于等到一个人骂这题得了。我当时网上填表得时候填得backend和real time。貌似面试官是backend得 ...

电面就出这种题实在是没啥意义,很多其实是很合适的人才就被这样莫名其妙的灭掉了。
回复 支持 反对

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 15:04:30 | 显示全部楼层
猥琐的老吴 发表于 2015-10-16 14:54. more info on 1point3acres.com
电面就出这种题实在是没啥意义,很多其实是很合适的人才就被这样莫名其妙的灭掉了。

谢谢安慰啊。另外14楼贴得代码是正解。大家可以学习学习。
回复 支持 反对

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 15:07:04 | 显示全部楼层
maplain 发表于 2015-10-16 14:21
感觉就是沿着边dfs。。只不过就是dfs的时候分类写的比较烦。。下面是代码,求大神指点。

补充内容 (2015 ...

谢谢!

这题关键是要想到把array里面得每个position看成是graph里头得两个nodes。然后根据左右上下相邻得/ 和 \ 情况分析联通性。能想到这个,这题就没啥问题了。不过find neighbor分析起来真是挺烦的,紧张的时候不容易一下子写对。
回复 支持 反对

使用道具 举报

bchen2008 发表于 2015-10-16 15:08:34 | 显示全部楼层
这样做行不行

1) 将初始的Array变形, 在每个/和\之前、之后还有中间加入*
比如  /\/ 变成 */*\*/*.鏈枃鍘熷垱鑷1point3acres璁哄潧

比如 初始 2D Array
/\\\. from: 1point3acres.com/bbs
\///
\\/\-google 1point3acres
/\//. visit 1point3acres.com for more.
会变为
*/*\*\*\*
*\*/*/*/*
*\*\*/*\*
*/*\*/*/*

2)查找连通区域
从第一行第一列的*开始,初始方向为向右, 将*改为空格后移动一步。
当前方向为向右的时候,移动一步后,如果碰到/则方向变为向上, 碰到\则变为向下.鏈枃鍘熷垱鑷1point3acres璁哄潧
当前方向为向上的时候,移动一步后,如果碰到/则方向变为向右, 碰到\则变为向左
当前方向为向左的时候,移动一步后,如果碰到/则方向变为向下, 碰到\则变为向上. 1point 3acres 璁哄潧
当前方向为向下的时候,移动一步后,如果碰到/则方向变为向左, 碰到\则变为向左

碰到/或\时依据改变的方向继续走下一步。碰到*则将其改为空格,并依据原来方向继续。
如果走出界或碰到空格,则查找停止。这时一个联通区域就找到了。

然后再从第一行里找到里第一列之后的第一个*作为新起点,进行下一个连通区域的查找。需要注意的是以最后一列的*作为起点时,初始方向应该是向左。

上面的例子查找完后是这样的(为了说明,将空格变为连通区编号)
.1point3acres缃
1/2\3\3\4
5\2/3/3/6.鏈枃鍘熷垱鑷1point3acres璁哄潧
7\5\3/5\6. From 1point 3acres bbs
7/8\5/5/9
. more info on 1point3acres.com


回复 支持 反对

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 23:05:21 | 显示全部楼层
bchen2008 发表于 2015-10-16 15:08
这样做行不行

1) 将初始的Array变形, 在每个/和\之前、之后还有中间加入*

具体思路看起来行。但是不知道实现起来好不好弄。感觉你这个本质上也是一个graph search。但是建图的时候好像和上面那个给的答案不一样。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 15:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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