10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 3423|回复: 10
收起左侧

google pittsburgh onsite

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

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

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

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

x
google campus onsite, 只有两轮
第一轮:白人大哥,输入一组边,根据边,输出一棵树.鏈枃鍘熷垱鑷1point3acres璁哄潧
例子:输入(b,a),(b,g),(f,b),(b,c),(c,e),构建的树是:
                f
               |
                b-google 1point3acres
            /      |   \
          g      a    c
                       \
                        e
输出应该是:(不同的层,前面有不同的空格)
f. 1point3acres.com/bbs
b
  c
   e
  g
  a
思路:用两个stack,一个存node,一个存level

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


. 1point3acres.com/bbs

评分

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降低时间复杂度?没懂
-google 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. 鍥磋鎴戜滑@1point 3 acres
其实我也没懂,但是面试官说建trie tree可以降低时间复杂度~

第一题很像longest absolute file path,可是用两个stack怎么做??输入的时候怎么能够知道每个node的level呢?
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

比如(a,b)(c,d)(b,c). Waral 鍗氬鏈夋洿澶氭枃绔,
怎么流程呢?

补充内容 (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
第一题楼主能帮忙解释下吗?

比如(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的串就不用查了。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-18 08:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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