一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 452|回复: 9
收起左侧

狗家电面

[复制链接] |试试Instant~ |关注本帖
johnsysu 发表于 2017-12-7 06:16:07 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 本科 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚面完狗家,back to back的电面。
第一轮的面试官比较和善,问的问题也没有太刁难,利口吴柳奇。让我介绍了项目,大概10分钟,然后开始coding。我没有用滑窗去解,hashmap应该能work,过程比较轻松友好,基本在自己节奏。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第二轮gg了,问了一些我简历上项目的问题,开始coding,stream observer,已知一组字符串,每次观察一个输入的字符,若输入的字符顺序和字符串组里的match,就返回match的list,否则返回空。问题的形式让我有点懵,涉及到了interface,然后让我自己定义一个class,自定member variable, hierarchy等等。转专业刷Leetcode的楼主表示很受伤,被问得一丝不挂,非科班鉴定完毕。
面试完基本是喜忧参半
liuchen1701 发表于 2017-12-7 15:18:10 | 显示全部楼层
唔 第二题没有看太懂,能否麻烦楼主详细解释一下题目的意思?谢谢了。
回复 支持 反对

使用道具 举报

get_bits 发表于 2017-12-7 17:08:52 来自手机 | 显示全部楼层
马克一下 谢谢楼主!
回复 支持 反对

使用道具 举报

 楼主| johnsysu 发表于 2017-12-7 22:19:33 | 显示全部楼层
解释一下第二道题,有点类似于Trie,但好像又不是。比方说我有一个字符串,让你判断字符串里是否存在关键词。但是这里的字符串变成了单个连续输入的字符。例如我连续输入‘a’,'b','b','c','a',我的字符串组里面有bbc,当我输入c的时候就返回bbc。字符串匹配的问题,就是形式让我比较捉鸡。
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-7 22:43:58 | 显示全部楼层
johnsysu 发表于 2017-12-7 22:19. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
解释一下第二道题,有点类似于Trie,但好像又不是。比方说我有一个字符串,让你判断字符串里是否存在关键词 ...

那就建立suffix tree吧
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-7 22:48:29 | 显示全部楼层
hychin 发表于 2017-12-7 22:43. From 1point 3acres bbs
那就建立suffix tree吧

貌似不需要你直接把input cache起来 查的时候按照逆序去trie里面查就ok
回复 支持 反对

使用道具 举报

hychin 发表于 2017-12-7 22:49:59 | 显示全部楼层
trie建立的时候也是正逆序都建一个
回复 支持 反对

使用道具 举报

ydybati 发表于 7 天前 | 显示全部楼层
楼组第二题和这里面的第四题一样吗? http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=303144&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
回复 支持 反对

使用道具 举报

huangya2 发表于 7 天前 | 显示全部楼层
感谢楼主分享!
回复 支持 反对

使用道具 举报

Fightandweight 发表于 6 天前 | 显示全部楼层
这个问题很tricky啊,这个叫StreamObserver是因为流很大没有办法在内存存完全部的流吗?
初步思路是对字典倒序建Trie, 然后在内存中用LinkedList来作为队列缓存Stream的一部分,队列的最大size为字典中最大单词的长度,类中再定义一个叫matched的hashSet,每次put的时候向队列末尾push这个char, 队列容量超限后pop第一个char,用Trie做一个后缀搜索,找到的单词加到matched里面去,将matched作为ArrayList返回即可。这样put的复杂就是O(size),还算可以接受且不违背内存限制。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-15 14:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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