一亩三分地论坛

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

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

[技術店面] 谷歌

[复制链接] |试试Instant~ |关注本帖
b00901192 发表于 2016-11-16 01:20:31 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 网上海投 - 技术电面 |Other其他

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

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

x
昨天剛面完 google 的暑假實習兩場 phone interview,上來發面經攢人品,希望能進 pool,並期許下週 BB onsite 順利拿 offer。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1. NY Office 打來的,美國小哥,口語慢,很開心的樣子,人很好,先過 5 分鐘簡歷,然後只有一道題:

給你一個 m x n 的 grid,上面只有整數 1 和 0,其中 1 代表 pixel,0 代表空白,要你找所有的 lonely pixel (一個 pixel 在同行或同列上沒有其他 pixel) 的座標。

時間複雜度要求: O(m*n)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
舉個例子:.鏈枃鍘熷垱鑷1point3acres璁哄潧

A 3 x 3 grid:

100
010
101
. From 1point 3acres bbs
在 (0, 0) 那個 1 因為在第 0 行有其他 1,所以他不是 lonely. 1point3acres.com/bbs
在 (1, 1) 那個 1 因為同行同列沒有其他 1,所以他是 lonely
以此類推。

2. 從 Mountain View 打來的,國人小哥,一接起電話,倍感親切,以後當面試官鐵定要好好照顧同胞!. more info on 1point3acres.com
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
沒問簡歷,直接上題 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

1. Find the last index of target from a sorted array.

Ex: [1, 2, 2, 2, 2, 4], target = 2, return 4

用 binary search

2. Detect cycle in direcyed graph.

用 topological sort

希望對大家有幫助!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

pwwpche 发表于 2016-11-16 05:22:35 | 显示全部楼层
第一题可以用两个数组,存每一行每一列的lonely pixel的index,如果没有lonely pixel(同一行或同一列有两个1或者没有1)就存-1
比方说
0 0 0 -> -1. From 1point 3acres bbs
0 0 1 -> 2
1 0 0 -> 0.鐣欏璁哄潧-涓浜-涓夊垎鍦
|  | |
2 -1 1

然后扫一次行/列数组,扫列数组时到行数组里找这个位置的lonely index在哪,如果两个cross了就输出index
比如列数组m[-1,2,0],
m[0] = -1跳过
m[1] = 2, n[2] = 1,输出(2,1)
.1point3acres缃m[2] = 0, n[0] = 2,输出(0,2)
. visit 1point3acres.com for more.
复杂度也是O(m*n),但如果用适当方法的话,只用扫一遍整个数组就能得到每个行/列的lonely pixel的index,然后扫一遍行数组或列数组就能得到所有lonely pixel的index了。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-11-16 02:38:50 | 显示全部楼层
第一道题用BFS ?
回复 支持 反对

使用道具 举报

 楼主| b00901192 发表于 2016-11-16 03:03:38 | 显示全部楼层
wtcupup 发表于 2016-11-16 02:38. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一道题用BFS ?

我是用兩個 array 存每個 row 和 col 的 1 的數量,如果大於 1 就全部不要,反之就要。
回复 支持 反对

使用道具 举报

woshigtc 发表于 2016-11-16 03:09:58 | 显示全部楼层
请问一下第二题是要找到环,还是检查是不是有环?
回复 支持 反对

使用道具 举报

 楼主| b00901192 发表于 2016-11-16 04:51:32 | 显示全部楼层
woshigtc 发表于 2016-11-16 03:09
请问一下第二题是要找到环,还是检查是不是有环?

檢查有沒有就可以了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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