一亩三分地论坛

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

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

9.19 Google 电面

[复制链接] |试试Instant~ |关注本帖
ssc317 发表于 2016-9-21 04:51:43 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
昨天刚刚结束google 电面,发一下题目求点大米。1. 给一个 32bit的integer, convert 成 IP address, like 1.2.3.4 。 其中每8bit代表IP里的一个数字。
2. 给一个binary tree, 求maximum consecutive increasing path length.
比如                                 
                1. 1point 3acres 璁哄潧
              /    \
             2      3                                               
                    /                                             
                   4                                               
                     \                                             
                       5
最长连续的路劲的3-4-5,长度为3,所以output 3
follow up:
时间复杂度是多少?回答O(n)
如果是directed acycle graph, 会有什么不同, 时间复杂度是多少?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这里他主要问这种情况下时间复杂度是多少. 1point 3acres 璁哄潧
                 1
              /    \.鏈枃鍘熷垱鑷1point3acres璁哄潧
             2      3                                               
                    /   \                                          
                   4     4                                          
                     \   /                                          
                       5

                      /|\. visit 1point3acres.com for more.
                     6 7 8
因为这边5678 tranverse了2次,所以我回答O(n^m), m<n。然后和他说m比较难求。有谁知道怎么求吗. 鍥磋鎴戜滑@1point 3 acres

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
今天google打电话来了,但是没接到……所以不知道结果如何。
有人知道他打电话代表过还是不过吗?因为题目都答出来了,希望应该是过的。但是他打电话而不是发邮件,就搞的有点心慌了



评分

1

查看全部评分

larry_cn 发表于 2016-9-21 05:07:22 | 显示全部楼层
这个是 额 onsite的 题。。。
有向图的 话 没个 node的 income 都算完后 在往后走
按 topological order 做就可以了

补充内容 (2016-9-21 05:07):
每个

补充内容 (2016-9-21 05:37):. 1point 3acres 璁哄潧
说的 不太全 就是 求的 时候只看 increase的 边就可以了
回复 支持 1 反对 0

使用道具 举报

 楼主| ssc317 发表于 2016-9-21 05:19:28 | 显示全部楼层
larry_cn 发表于 2016-9-21 05:07
这个是 额 onsite的 题。。。
有向图的 话 没个 node的 income 都算完后 在往后走
按 topological order  ...
.1point3acres缃
follow up没有叫我写具体算法,就问我有什么地方不同。你说onsite的题目是指第二题还是follow up的?
回复 支持 反对

使用道具 举报

larry_cn 发表于 2016-9-21 05:25:04 | 显示全部楼层
ssc317 发表于 2016-9-21 05:19
follow up没有叫我写具体算法,就问我有什么地方不同。你说onsite的题目是指第二题还是follow up的?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
对 第二题是 onsite 题目 然后 follow up 也一样
开始 想问无向图 刚想好怎么做 又改成了 有向图
不过 也是 说想法


补充内容 (2016-9-21 05:25):. 1point 3acres 璁哄潧
不过 不是binary tree 是 tree 差不多
回复 支持 反对

使用道具 举报

xiayewang 发表于 2016-9-21 05:26:04 | 显示全部楼层
有向图能不能存每个node为起始点的最长连续路径来做?
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-21 06:22:27 | 显示全部楼层
follow up我觉得应该也可以o(n)做出来吧? top down做dfs
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-9-21 06:35:13 | 显示全部楼层
为什么我觉得第二题用BFS解的话,followup和原题其实没差别。
回复 支持 反对

使用道具 举报

1370786136.1.3 发表于 2016-9-21 07:17:46 | 显示全部楼层
LZ请问第一题是下面的这种实现方式吗?

class Solution {
    public static String toIPAddress(int i) {
        int[] addr = new int[4];
        addr[0] = (i >> 24) & 0xff;
        addr[1] = (i >> 16) & 0xff;
        addr[2] = (i >> 8) & 0xff;. 1point3acres.com/bbs
        addr[3] = i & 0xff;
        return "" + addr[0] + "." + addr[1] + "." + addr[2] + "." + addr[3];
    }
   
    public static void main(String[] args) {
        int i = 2123244257;. 鍥磋鎴戜滑@1point 3 acres
        System.out.println(toIPAddress(i));
    }
}-google 1point3acres
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-4 03:55:02 | 显示全部楼层
这题不是LEETCODE 原题吗?FOLLOW UP我觉得是一样啊,就是用BFS解的
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-10-4 05:10:54 | 显示全部楼层
gg打电话一般都是据人。。。
回复 支持 反对

使用道具 举报

大古1234 发表于 2016-10-5 08:16:44 | 显示全部楼层
感觉follow up的复杂度是O(n^2)
回复 支持 反对

使用道具 举报

virpro 发表于 2016-10-6 05:11:14 | 显示全部楼层
Follow up有假设能直接access graph里的每一个node吗?如果可以,那可以从每个节点开始DFS,并记住每个点出发的最长的路径,同时update global max。这样worst case是O(N^2)。如果只有一个node的access,那只能从该node开始search,但是貌似DFS仍然可解?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 10:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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