10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2048|回复: 5
收起左侧

[技術店面] 谷歌

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

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

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

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

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)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
舉個例子:

A 3 x 3 grid:

100
. from: 1point3acres.com/bbs 010
101

在 (0, 0) 那個 1 因為在第 0 行有其他 1,所以他不是 lonely
在 (1, 1) 那個 1 因為同行同列沒有其他 1,所以他是 lonely. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
以此類推。

2. 從 Mountain View 打來的,國人小哥,一接起電話,倍感親切,以後當面試官鐵定要好好照顧同胞!

沒問簡歷,直接上題

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.. 1point 3acres 璁哄潧

用 topological sort
. 鍥磋鎴戜滑@1point 3 acres
希望對大家有幫助!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

pwwpche 发表于 2016-11-16 05:22:35 | 显示全部楼层
第一题可以用两个数组,存每一行每一列的lonely pixel的index,如果没有lonely pixel(同一行或同一列有两个1或者没有1)就存-1
比方说
0 0 0 -> -1
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)
m[2] = 0, n[0] = 2,输出(0,2)

复杂度也是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 | 显示全部楼层

我是用兩個 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
请问一下第二题是要找到环,还是检查是不是有环?
-google 1point3acres
檢查有沒有就可以了
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-20 21:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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