一亩三分地论坛

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

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

google pittsburgh onsite

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

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

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

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

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. Waral 鍗氬鏈夋洿澶氭枃绔,
  a
思路:用两个stack,一个存node,一个存level.鐣欏璁哄潧-涓浜-涓夊垎鍦
. from: 1point3acres.com/bbs
第二轮:国人大哥:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1.给一堆list,竖排输出结果. more info on 1point3acres.com
例子:list1: a1,a2,a3
list2:b1
list3:c. 1point3acres.com/bbs
输出:a1,b1,c1,a2,c2,a3
用一个queue即可
2.实现substr
扩展:如果输入的是list of string,如何降低时间复杂度?
应该用trie tree
可惜我不会构建trie tree,面试官说我假设tree已经构建好了,让我写接下来的代码。这轮估计挂了


. more info on 1point3acres.com

评分

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. 鍥磋鎴戜滑@1point 3 acres
楼主,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.鏈枃鍘熷垱鑷1point3acres璁哄潧
怎么用trie降低时间复杂度?没懂

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

使用道具 举报

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

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

使用道具 举报

jocelyna 发表于 2016-10-12 03:18:00 | 显示全部楼层
mulinyang 发表于 2016-10-11 23:42
其实我也没懂,但是面试官说建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)
怎么流程呢?
.1point3acres缃
补充内容 (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
第一题楼主能帮忙解释下吗?
. From 1point 3acres bbs
比如(a,b)(c,d)(b,c)

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 19:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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