一亩三分地论坛

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

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

[实习] 12月2日 面经:Google intern Questions

[复制链接] |试试Instant~ |关注本帖
gracesrm 发表于 2015-12-3 11:52:28 | 显示全部楼层 |阅读模式

2016(7-9月)-[]CE博士+fresh grad 无实习/全职 - 内推| 码农类实习@Google其他

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

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

x
今天下午2轮面试题(2* 45min):

1. 中国人小哥:人很nice,及时给出hint,非常有耐心,非常helpful.
题目:给出一个array A,比如[4, 1, 5, 3, 2],  求出A[i] 之后比A[i] 更小的个数,得到新的Array C, 返回C的最大值!
          hint: 不需要一定求出C array,用binary search tree做,保证每次计算C[i]都是logN复杂度,不能用SortedSet/TreeSet.
我的做法:
(其实是小哥各种提示下才知道,再次感激!)    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
         从右往左扫描array, 每次将节点插入BST,这里的TreeNode除了记录value,还要记录比自己小的节点个数 cnt!
         如果插在某node左边,要更新node节点,如果插在某node右边,cnt就要加上node节点的cnt; 记得更新最大值!. 1point3acres.com/bbs
      

2. 美国爷爷:问了问平时用什么编程,用什么算法数据结构,然后根据我说的现场出了个题目!
爷爷是由浅入深递进型发问!. 鍥磋鎴戜滑@1point 3 acres
step 1: 我想有个element,里面存着一个名字,和下一个指向的element,建个类!(类似链表)
step 2: 如果name 和next是private,我从main函数想访问怎么办?(写getName() getNext() 函数)
.1point3acres缃step 3: 给出element e,找到他后面name为“one"的element 个数!  (while循环到null,string.equals, cnt++)
step 4: 如果next不是一个节点,而是很多节点,怎么办?   (Element[] next)
step 5: 同step 3, 怎么找个数? (DFS or BFS)
step 6: 如果里面有cycle, 怎么办?(adjacency matrix, topology search)
step 6快到45min了,就没有写代码,说了说思路!这一轮面的一般,题不难,但是花了很多时间才搞清楚爷爷问的是什么,导致最后一个没时间写!

希望对大家有用,祝好运!

评分

1

查看全部评分

vivaroma 发表于 2015-12-4 15:22:23 | 显示全部楼层
楼主是video面试嘛?怎么连年龄都知道。。
回复 支持 反对

使用道具 举报

 楼主| gracesrm 发表于 2015-12-9 20:54:51 | 显示全部楼层
vivaroma 发表于 2015-12-4 15:22
楼主是video面试嘛?怎么连年龄都知道。。

就是电话面试,听声音听出来的
回复 支持 反对

使用道具 举报

mikeyangh1992 发表于 2015-12-13 06:25:41 | 显示全部楼层
LZ你好,第一题按你说的方法如果插入一个很小的数那整个右边的每个节点都需要更新,那worst-case一次计算的复杂度应该是O(n)吧。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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