一亩三分地论坛

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

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

Airbnb 电面

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

2015(7-9月) 码农类 硕士 全职@Airbnb - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
今天面了Airbnb,网上他家的面经不多,发一个攒RP求onsite。

/**
* Given: An array of strings where L indicates land and W indicates water,
*   and a coordinate marking a starting point in the middle of the ocean.
*
* Challenge: Find and mark the ocean in the map by changing appropriate Ws to Os.
*   An ocean coordinate is defined to be the initial coordinate if a W, and
*   any coordinate directly adjacent to any other ocean coordinate.
*
* void findOcean(String[] map, int row, int column);
*
* String[] map = new String[]{
*  "WWWLLLW",
*  "WWLLLWW",
*  "WLLLLWW"
* };
* printMap(map);
*
* STDOUT:
* WWWLLLW
* WWLLLWW
* WLLLLWW
*
* findOcean(map, 0, 1);
*
* printMap(map);
*
* STDOUT:
* OOOLLLW
* OOLLLWW
* OLLLLWW
*/
先问了iteration的方法比recursion好在哪里,然后我用iteration写了一个DFS,当然还写好了main function,现场跑,有一点点小bug,马上就跑过了。然后面试官问了时间复杂度,不断问我如何优化来减少不必要的backtracking。对这道题而言,我说用BFS可能更快一点,每找到一个点就马上标记为‘O’。面试官还是不满意。又问在BFS的while loop里你还能做什么改进?你已经遍历过这个点了如何避免再次遍历它?额沉默。。。沉默了一会儿他说好了,就酱吧。
怒求RP~同时求问如何进一步优化。




补充内容 (2015-9-18 12:38):
已然被拒。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

海岸线 发表于 2015-9-18 12:35:49 | 显示全部楼层
        private void floodFill(char[][] board, int i, int j, char oldColor, char newColor) {
            if (board[i][j] != oldColor || board[i][j] == newColor) {. from: 1point3acres.com/bbs
                return;.鐣欏璁哄潧-涓浜-涓夊垎鍦
            }

            Queue<Integer> queue = new LinkedList<Integer>();
            queue.add(i * board[0].length + j);
            board[i][j] = newColor;

            while (!queue.isEmpty()) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                int pos = queue.poll();. 1point3acres.com/bbs
                int m = pos / board[0].length;.1point3acres缃
                int n = pos % board[0].length;
       
                if (m + 1 < board.length && board[m + 1][n] == oldColor) {.1point3acres缃
                    queue.add((m + 1) * board[0].length + n);
                    board[m + 1][n] = newColor;
                }
                if (m - 1 >= 0 && board[m - 1][n] == oldColor) {
                    queue.add((m - 1) * board[0].length + n);
                    board[m - 1][n] = newColor;
                }
                if (n + 1 < board[0].length && board[m][n + 1] == oldColor) {
                    queue.add(m * board[0].length + n + 1);
                    board[m][n + 1] = newColor;
                }
                if (n - 1 >= 0 && board[m][n - 1] == oldColor) {
                    queue.add(m * board[0].length + n - 1);
                    board[m][n - 1] = newColor;
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            }
        }
回复 支持 1 反对 0

使用道具 举报

kelvinzhong 发表于 2015-9-16 13:15:22 | 显示全部楼层
已经遍历过的点就已经被标记成O了,这不就已经避免再次遍历了吗? 没很理解面试官在想什么, 楼主是在hackerrank上跑的? 要当场跑出结果?
回复 支持 反对

使用道具 举报

 楼主| fordreamzju 发表于 2015-9-16 13:19:17 | 显示全部楼层
kelvinzhong 发表于 2015-9-16 13:15
已经遍历过的点就已经被标记成O了,这不就已经避免再次遍历了吗? 没很理解面试官在想什么, 楼主是在hacker ...

是在codePair上跑的。当场编译运行。
回复 支持 反对

使用道具 举报

iorisli 发表于 2015-9-17 09:09:28 | 显示全部楼层
LZ, 输入是string array, 那么dfs的时候每改变一个值, 那一行string就要重新copy一下. 楼主怎么处理的? 先转成char[][]吗?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-17 09:20:48 | 显示全部楼层
楼主,马上要电面了,但是HR一再强调说是技术类的,不是算法类。但是面试官已经发来coderpad的链接了,表明依然是算法。。。。请问,楼主也是这样的情况嘛?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-17 09:23:53 | 显示全部楼层
iorisli 发表于 2015-9-17 09:09. 1point 3acres 璁哄潧
LZ, 输入是string array, 那么dfs的时候每改变一个值, 那一行string就要重新copy一下. 楼主怎么处理的? 先 ...

应该是这样的,第一件事情就是把string变成char[][]
回复 支持 反对

使用道具 举报

 楼主| fordreamzju 发表于 2015-9-17 09:27:48 | 显示全部楼层
jiebour 发表于 2015-9-17 09:20
楼主,马上要电面了,但是HR一再强调说是技术类的,不是算法类。但是面试官已经发来coderpad的链接了,表明 ...

个人觉得技术类不就是算法类吗。。。我的HR直接就说是算法和数据结构相关了。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-17 09:44:31 | 显示全部楼层
fordreamzju 发表于 2015-9-17 09:27.鏈枃鍘熷垱鑷1point3acres璁哄潧
个人觉得技术类不就是算法类吗。。。我的HR直接就说是算法和数据结构相关了。

我的HR直接说的是more practical的,不是algorithmic,然而面试官给了我一个coderpad的链接。。。

补充内容 (2015-9-17 09:44):. more info on 1point3acres.com
BTW,楼主你投的是什么职位?maybe和职位有关
回复 支持 反对

使用道具 举报

 楼主| fordreamzju 发表于 2015-9-17 09:47:21 | 显示全部楼层
jiebour 发表于 2015-9-17 09:44
我的HR直接说的是more practical的,不是algorithmic,然而面试官给了我一个coderpad的链接。。。

补充 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
software engineer
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2015-9-17 12:53:58 | 显示全部楼层
lz好,DFS不是本身不是recursive的吗?lz如何实现iterative的?能share一下code吗?
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2015-9-17 12:54:05 | 显示全部楼层
lz好,DFS不是本身不是recursive的吗?lz如何实现iterative的?能share一下code吗?
回复 支持 反对

使用道具 举报

iorisli 发表于 2015-9-17 13:41:13 | 显示全部楼层
luzhuzeng 发表于 2015-9-17 12:54
lz好,DFS不是本身不是recursive的吗?lz如何实现iterative的?能share一下code吗?

这个可以看做是pre-order dfs, 所以比较容易用stack来iterative实现
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-17 23:10:21 | 显示全部楼层
iorisli 发表于 2015-9-17 13:41
这个可以看做是pre-order dfs, 所以比较容易用stack来iterative实现

请问一下楼主在BFS的while loop里面做了什么改进啊?
回复 支持 反对

使用道具 举报

xujun 发表于 2015-9-18 01:25:32 | 显示全部楼层
楼主,dfs就是recursion啊,他的意思是不是recursion可能会stackoverflow
回复 支持 反对

使用道具 举报

 楼主| fordreamzju 发表于 2015-9-18 01:41:54 | 显示全部楼层
luzhuzeng 发表于 2015-9-17 12:54
lz好,DFS不是本身不是recursive的吗?lz如何实现iterative的?能share一下code吗?

可以用stack实现iteration的DFS
回复 支持 反对

使用道具 举报

 楼主| fordreamzju 发表于 2015-9-18 01:42:37 | 显示全部楼层
xujun 发表于 2015-9-18 01:25
楼主,dfs就是recursion啊,他的意思是不是recursion可能会stackoverflow

我本身就是用stack+iteration的方法实现的DFS。并没有recursion。
回复 支持 反对

使用道具 举报

lianguasth 发表于 2015-9-24 05:55:36 | 显示全部楼层
这个题目离散数学学过。。就是扫一遍做的,先把独立的岛屿标号,然后扫的过程中将相邻的岛屿命名相同符号。然后如果遇到两个岛屿在某点连接在一块就做一个pair标记这两个岛屿实际上一样。最后整理这个set就好了
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-27 02:03:34 | 显示全部楼层
lianguasth 发表于 2015-9-24 05:55
这个题目离散数学学过。。就是扫一遍做的,先把独立的岛屿标号,然后扫的过程中将相邻的岛屿命名相同符号。 ...

没能理解,这个做法能比BFS快吗?
回复 支持 反对

使用道具 举报

lianguasth 发表于 2015-9-27 09:44:12 | 显示全部楼层
kelvinzhong 发表于 2015-9-27 02:03
没能理解,这个做法能比BFS快吗?

这个所有元素只要扫一遍
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 17:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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