一亩三分地论坛

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

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

Google(youtube)新鲜电面面经

[复制链接] |试试Instant~ |关注本帖
he2004365 发表于 2015-7-10 04:30:47 | 显示全部楼层 |阅读模式

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

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

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

x
前天电面的,不废话了, 直接上题:
给了一个UTF-8的pattern:
1byte - 0XXX, XXXX
2byte - 110X, XXXX, 10XX,XXXX. 鍥磋鎴戜滑@1point 3 acres
3byte - 1110, XXXX, 10XX,XXXX, 10XX,XXXX
4byte - 1111, 0XXX, 10XX,XXXX, 10XX,XXXX, 10XX,XXXX
.....
7byte - 1111, 1110, 10XX,XXXX, 10XX,XXXX, 10XX,XXXX, ..... 10XX,XXXX
8byte - 1111, 1111, 10XX,XXXX, 10XX,XXXX, 10XX,XXXX, ..... 10XX,XXXX

然后让写一个boolean 函数:
input: byte数组. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
output: trye or false;
boolean isvalidUTF-8(byte[] input){-google 1point3acres

}
做题前,问了问简历,然后问了问哪门课最changllege, 哪门课最喜欢。因为楼主没有实习经历,估计也没别的可问, why google之类的。然后就在doc上复制上这道题,一看就傻眼了,然后问了问byte数组里面是不是就是1和0,回答是。想啊想,貌似只能一位一位比,然后想半天,估计面试官比较无奈,又说给你一个函数leadingOnes,这个函数返回1的数目。这时候楼主开始犯二了,很自然的认为是返回所有1的个数。又在那想啊想,总觉得,给的这个函数没啥用,X可以为1啊。又问面试官能不能查api,用别的不用他给的函数,面试官说可以,去查了半天也没发现能用的(昨天才知道有bitset这种神器啊)。 然后时间就快到了,面试官说你何必不考虑用我给你的函数呢,我回答可是函数返回所有1的数目,X可以为1啊,很confused。 这会面试官的一句话,彻底把我打下了地狱,他说:leadingOnes是遇到0就停止继续往下找1了。我擦擦擦擦擦。 。 突然思路就来了,那不就是先判断前面1的个数,然后以8为单位开始扫input里面后面的字符,再查看前两个字符是不是10嘛。妈蛋的,啊啊啊。这会已经没时间写了,没写完,面试官说时间已经超时了,有没有什么问题想问我的。不得不说google面试水平就是高, 时间过了,还让问问题。可惜楼主被自己蠢哭了, 已经不会思考了。直接说了No, 面试官很礼貌的说我给你留个邮箱,你有事可以跟我联系。我噻,真是业界良心啊~~~今天收到电话, 挂的毫无悬念。进了小黑屋一年,怪自己太熊啊。 没怎么准备就敢投google。 至此第一阶段的找工作正式结束了,努力再去刷题吧。到九十月份再投。 哎~拿google练手,增长经验,我也真是。 小伙伴们,没准备好千万别投啊,内推回复速度神快啊,地里好多大大也说,google全年都在招人,准备好了再投啊。

评分

1

查看全部评分

stellari 发表于 2015-7-11 12:13:21 | 显示全部楼层
storm_hair 发表于 2015-7-11 11:23
没有看懂题目 怎么算valid

说白了就是三个规则:. visit 1point3acres.com for more.

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 1. 如果一个字节以0开头,那么这个字节自己算作一个整体。
2. 如果一个字节开头有连续的K个1(2<=K<=8),那么这个字节连同其后的K-1个连续字节算作一个整体,且这K-1个字节均必须以10开头。. from: 1point3acres.com/bbs
3. 如果一个字节开头只有1个连续的1(即K=1),那么这个字节绝对不能作为一个整体的开头出现。

主要检查序列是否违反规则2,3即可。遇到1的情况跳过该字符即可。
. 鍥磋鎴戜滑@1point 3 acres

. Waral 鍗氬鏈夋洿澶氭枃绔,
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2015-7-11 12:16):
不过楼主遇到的输入是用“字节”来表示“位”的。所以楼主说的byte数组中的“8个字节”相当于我此楼中说的“1个字节”。
回复 支持 2 反对 0

使用道具 举报

dmsehuang 发表于 2015-7-10 05:50:09 | 显示全部楼层
pat pat,没事楼主继续加油。
回复 支持 反对

使用道具 举报

say543 发表于 2015-7-10 08:01:30 | 显示全部楼层
lz 太紧张了 下个会更好
回复 支持 反对

使用道具 举报

547690781 发表于 2015-7-11 06:56:56 | 显示全部楼层
for your problem, the pattern for 1 byte should be
1byte - 10XX, XXXX
I am not sure
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-11 09:18:28 | 显示全部楼层
547690781 发表于 2015-7-11 06:56
for your problem, the pattern for 1 byte should be
1byte - 10XX, XXXX
. 1point3acres.com/bbsI am not sure

不是的。UTF-8标准规定1byte的情况必须以0开头;以10开头的只能在多byte情况中出现。
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-7-11 11:23:36 | 显示全部楼层
没有看懂题目 怎么算valid
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-7-11 12:11:42 | 显示全部楼层
storm_hair 发表于 2015-7-11 11:23. 鍥磋鎴戜滑@1point 3 acres
没有看懂题目 怎么算valid
. 1point 3acres 璁哄潧
byte数组里面是[1,1,1,1,,1,1,1,1,1,0,X,X,X,X,X,X,...]这种形式的~
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-7-11 12:12:07 | 显示全部楼层
stellari 发表于 2015-7-11 09:18. 1point 3acres 璁哄潧
不是的。UTF-8标准规定1byte的情况必须以0开头;以10开头的只能在多byte情况中出现。

楼上正解~
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-7-11 12:12:30 | 显示全部楼层
dmsehuang 发表于 2015-7-10 05:50
pat pat,没事楼主继续加油。

恩~继续刷题把~
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-7-11 12:12:39 | 显示全部楼层
say543 发表于 2015-7-10 08:01
lz 太紧张了 下个会更好

恩~谢谢~
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-11 12:26:14 | 显示全部楼层
说起来,我记得UTF-8的标准最大只允许到6 byte的情况,7/8byte的情况是不存在的。确定面试官问你的时候包括了这两种情况么?另外,把UTF-8序列当成一个“每字节代表1位”的byte数组来传输也是很奇怪的一件事。可能面试官是为了取消掉“位操作”这个考察点。
回复 支持 反对

使用道具 举报

547690781 发表于 2015-7-11 15:07:02 | 显示全部楼层
stellari 发表于 2015-7-11 12:13
说白了就是三个规则:
.鐣欏璁哄潧-涓浜-涓夊垎鍦
1. 如果一个字节以0开头,那么这个字节自己算作一个整体。
. 鍥磋鎴戜滑@1point 3 acres
in this problem, can we consider the value of each byte, it may be easier to understand. 1point 3acres 璁哄潧
1 byte, 0 <= value <128,. more info on 1point3acres.com
2 byte, 192 <= value < 224
3 byte, 224 <= value < 240
4 byte, 240 <= value < 248
5 byte, 248 <= value < 252
6 byte, 252 <= value < 254
7 byte, value == 254
8 byte, value == 255

if we have k byte, check if the following k - 1 bytes are between 128 and 192.. more info on 1point3acres.com

Do you have any faster way to identify the leading zeros of a byte?
correct me if I am wrong. Thank you
回复 支持 反对

使用道具 举报

sunny_920520 发表于 2015-10-21 05:33:51 | 显示全部楼层
547690781 发表于 2015-7-11 15:07
in this problem, can we consider the value of each byte, it may be easier to understand
1 byte, 0 ...

是一个办法,不过还是还的考虑下符号位
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 16:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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