一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 863|回复: 11
收起左侧

狗家电面

[复制链接] |试试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
那就建立suffix tree吧

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

使用道具 举报

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

使用道具 举报

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

使用道具 举报

huangya2 发表于 2017-12-8 07:53:43 | 显示全部楼层
感谢楼主分享!
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| johnsysu 发表于 2017-12-29 12:19:00 | 显示全部楼层
ydybati 发表于 2017-12-8 01:08
楼组第二题和这里面的第四题一样吗? http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=3031 ...
. 鍥磋鎴戜滑@1point 3 acres
差不多,不过要返回匹配的字符串
回复 支持 反对

使用道具 举报

g00dm0rning 发表于 2018-2-10 21:49:10 | 显示全部楼层
感觉用ac自动机就可以?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-2-21 13:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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