推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3568|回复: 38
收起左侧

Uber 电面, 没见过的题目

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

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

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

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

x
看了很久的面经,来回馈一下地里。
一个白人面试官。迟到了大概5分钟。然后上来问了下简历。就开始做题目了。从来没有见过的题目。题目是这样的:
假设给你一个2D array由'\'和'/'构成。让你求这些slashes把整个区域分成了几个区间。举个例子:
假设输入是:. 鍥磋鎴戜滑@1point 3 acres
/\/. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
\/\
那么需要返回6。我一开始没听懂题目意思,让他解释一番。他说你可以这样看:. 鍥磋鎴戜滑@1point 3 acres
----------
A/F\B/C
D\F/E\C. from: 1point3acres.com/bbs
-----------
其中字母代表的是区域的标号。
如果各位没看懂的话我再举个例子。input是这个
/\\
/\/
/\\
. more info on 1point3acres.com
返回还是6。,因为整个可以分成这样:
----------. visit 1point3acres.com for more.
B/\C\D
/CC\C\
C/\CC/
/EE\/F
E/\E\F
/GG\E\. from: 1point3acres.com/bbs
----------。
给我解释了大概十分钟后我终于明白要干什么了。开始想思路。想了一会没想法,面试官提示说你可以写一个函数

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

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷如果有什么不清楚得尽管问。求大神指点这题啊!另外求点大米啊!


评分

4

查看全部评分

maplain 发表于 2015-10-16 14:21:26 | 显示全部楼层
dylanwen 发表于 2015-10-16 08:47.鐣欏璁哄潧-涓浜-涓夊垎鍦
不是很理解你怎么确定字母可以改的。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
你能试下这个case嘛?
/\/

感觉就是沿着边dfs。。只不过就是dfs的时候分类写的比较烦。。下面是代码,求大神指点。
  1. class Slashes {-google 1point3acres
  2.     private final byte LEFT = 0X1; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3.     private final byte RIGHT = 0X2;
  4.     public int num(char[][] slashes) {
  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.                 }
  15.                 if ((infos[i][j] & RIGHT) == 0) {
  16.                     dfs(infos, slashes, i, j, RIGHT, n, m);
  17.                     result++;
  18.                 }
  19.             }
  20.         }
  21.         return result;
  22.     }
  23.     private void dfs(byte[][] infos, char[][] slashes, int x, int y, byte pos, int n, int m) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  24.         infos[x][y] |= pos;. Waral 鍗氬鏈夋洿澶氭枃绔,
  25.         if (slashes[x][y] == '/') {
  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) {.1point3acres缃
  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.                     }. 鍥磋鎴戜滑@1point 3 acres
  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.                 }
  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.                     }. more info on 1point3acres.com
  47.                 }
  48.             }. 1point3acres.com/bbs
  49.         } else {
  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.                 }. 鍥磋鎴戜滑@1point 3 acres
  54.                 if (y+1<m) {
  55.                     if (slashes[x][y+1] == '/') {. Waral 鍗氬鏈夋洿澶氭枃绔,
  56.                         if ((infos[x][y+1] & LEFT) == 0) dfs(infos, slashes, x, y+1, LEFT, n, m);
  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);-google 1point3acres
  64.                 }
  65.                 if (y-1>=0) {
  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) {
  76.         Slashes s = new Slashes();
  77.         char[][] e1 = {. 1point3acres.com/bbs
  78.             {'/', '\\', '/'},
  79.             {'\\', '/', '\\'},. more info on 1point3acres.com
  80.         };
  81.         char[][] e2 = {
  82.             {'/', '\\', '\\'},
  83.             {'/', '\\', '/'},
  84.             {'/', '\\', '\\'},
  85.         };
  86.         char[][] e3 = {
  87.             {'/', '\\', '/'},
  88.             {'\\', '\\', '\\'},
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  89.         };.鏈枃鍘熷垱鑷1point3acres璁哄潧
  90.         System.out.println(s.num(e1));
  91.         System.out.println(s.num(e2));
  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行?
-google 1point3acres
那个不是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 | 显示全部楼层
初始化:
每个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
G\H         G\D
. visit 1point3acres.com for more.
数字母:
A/B, B\C, C/D ==> A, B, C, D, E, G ==> 6个
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嘛?. more info on 1point3acres.com
/\/
\\\
这样应该返回5
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 12:50:44 | 显示全部楼层
f1371342385 发表于 2015-10-16 12:49. from: 1point3acres.com/bbs
LZ,你的面试官是谁呀

一个叫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端么?
. visit 1point3acres.com for more.
哈哈,终于等到一个人骂这题得了。我当时网上填表得时候填得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
电面就出这种题实在是没啥意义,很多其实是很合适的人才就被这样莫名其妙的灭掉了。

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

使用道具 举报

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

补充内容 (2015 ...

谢谢!. from: 1point3acres.com/bbs

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

使用道具 举报

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

1) 将初始的Array变形, 在每个/和\之前、之后还有中间加入*
比如  /\/ 变成 */*\*/*
-google 1point3acres
比如 初始 2D Array
/\\\
\///
\\/\. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
/\//
会变为.1point3acres缃
*/*\*\*\*
*\*/*/*/*
*\*\*/*\*
*/*\*/*/*

2)查找连通区域
从第一行第一列的*开始,初始方向为向右, 将*改为空格后移动一步。
当前方向为向右的时候,移动一步后,如果碰到/则方向变为向上, 碰到\则变为向下
当前方向为向上的时候,移动一步后,如果碰到/则方向变为向右, 碰到\则变为向左
当前方向为向左的时候,移动一步后,如果碰到/则方向变为向下, 碰到\则变为向上
当前方向为向下的时候,移动一步后,如果碰到/则方向变为向左, 碰到\则变为向左

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

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

上面的例子查找完后是这样的(为了说明,将空格变为连通区编号)

1/2\3\3\4. 鍥磋鎴戜滑@1point 3 acres
5\2/3/3/6
7\5\3/5\6. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
7/8\5/5/9



回复 支持 反对

使用道具 举报

 楼主| dylanwen 发表于 2015-10-16 23:05:21 | 显示全部楼层
bchen2008 发表于 2015-10-16 15:08
这样做行不行
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1) 将初始的Array变形, 在每个/和\之前、之后还有中间加入*

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-18 05:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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