男生找男友:我希望你至少是0.628,如果是0.942那就更好了。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 3834|回复: 10
收起左侧

google pittsburgh onsite

[复制链接] |试试Instant~ |关注本帖
mulinyang 发表于 2016-10-9 07:18:10 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Other | fresh grad应届毕业生

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

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

x
google campus onsite, 只有两轮. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一轮:白人大哥,输入一组边,根据边,输出一棵树
例子:输入(b,a),(b,g),(f,b),(b,c),(c,e),构建的树是:
                f
               |
                b.鐣欏璁哄潧-涓浜-涓夊垎鍦
            /      |   \
          g      a    c
                       \
                        e
输出应该是:(不同的层,前面有不同的空格)
f
b
  c
   e
  g
  a
思路:用两个stack,一个存node,一个存level

第二轮:国人大哥:
1.给一堆list,竖排输出结果. 1point 3acres 璁哄潧
例子:list1: a1,a2,a3
list2:b1
list3:c
输出:a1,b1,c1,a2,c2,a3
用一个queue即可
2.实现substr. 1point 3acres 璁哄潧
扩展:如果输入的是list of string,如何降低时间复杂度?
应该用trie tree
可惜我不会构建trie tree,面试官说我假设tree已经构建好了,让我写接下来的代码。这轮估计挂了
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


评分

4

查看全部评分

本帖被以下淘专辑推荐:

小飞侠我去 发表于 2016-10-11 16:03:29 | 显示全部楼层
楼主,substr能不能详细说一下啊?具体实现什么?是给一个开始和结束的index吗?扩展到list of string又是什么意思?每一个string都给一个开始和结束的index?那和trie tree有什么关系?谢谢了
回复 支持 反对

使用道具 举报

 楼主| mulinyang 发表于 2016-10-11 21:36:47 | 显示全部楼层
小飞侠我去 发表于 2016-10-11 16:03
楼主,substr能不能详细说一下啊?具体实现什么?是给一个开始和结束的index吗?扩展到list of string又是 ...

写错了,是实现strstr,判断一个string是不是另一个string的子字符串,扩展到list,是问这个list中的string,有几个是给定string的子字符串,list的时候,不能是简单的3重for循环,时间复杂度太高了,要用trie tree降低时间复杂度
回复 支持 反对

使用道具 举报

jocelyna 发表于 2016-10-11 22:59:36 | 显示全部楼层
怎么用trie降低时间复杂度?没懂
回复 支持 反对

使用道具 举报

 楼主| mulinyang 发表于 2016-10-11 23:41:59 | 显示全部楼层
jocelyna 发表于 2016-10-11 22:59
怎么用trie降低时间复杂度?没懂

.1point3acres缃其实我也没懂,但是面试官说建trie tree可以降低时间复杂度~
回复 支持 反对

使用道具 举报

 楼主| mulinyang 发表于 2016-10-11 23:42:19 | 显示全部楼层
jocelyna 发表于 2016-10-11 22:59
怎么用trie降低时间复杂度?没懂

其实我也没懂,但是面试官说建trie tree可以降低时间复杂度~
回复 支持 反对

使用道具 举报

jocelyna 发表于 2016-10-12 03:18:00 | 显示全部楼层
mulinyang 发表于 2016-10-11 23:42
其实我也没懂,但是面试官说建trie tree可以降低时间复杂度~
. from: 1point3acres.com/bbs
第一题很像longest absolute file path,可是用两个stack怎么做??输入的时候怎么能够知道每个node的level呢?
回复 支持 反对

使用道具 举报

sophie729 发表于 2016-10-13 18:25:11 | 显示全部楼层
楼主觉得在pitt面和mtv有啥区别么,我也在pitt😢
回复 支持 反对

使用道具 举报

wopani007 发表于 2016-10-14 07:57:45 | 显示全部楼层
第一题楼主能帮忙解释下吗?.1point3acres缃

比如(a,b)(c,d)(b,c)
怎么流程呢?. 1point 3acres 璁哄潧

补充内容 (2016-10-14 08:14):
我,我懂了,用一个map来存所有char,node pair,问题是最后怎么才能找到root呢?我的想法是在node里面加一个field,isroot
回复 支持 反对

使用道具 举报

chishui 发表于 2016-10-14 08:33:13 | 显示全部楼层
wopani007 发表于 2016-10-14 07:57. 鍥磋鎴戜滑@1point 3 acres
第一题楼主能帮忙解释下吗?

比如(a,b)(c,d)(b,c)

类似于leetcode 210,找入度为0的node应该就是root
回复 支持 反对

使用道具 举报

zxyviopond 发表于 2017-2-13 12:21:24 | 显示全部楼层
用Trie优化,比如List<abc, abcde, abfg>, 在blahblahab中的substring, 你查abc的时候,发现abc不靠谱,所以所有Prefix是abc的串就不用查了。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-22 22:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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