一亩三分地论坛

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

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

电面 Google

[复制链接] |试试Instant~ |关注本帖
fsr0023120 发表于 2016-4-2 08:33:58 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
刚刚面完:本人已经工作了一年了,公司很多印度同事,跟他们交流完全没什么问题,但是今天这个印度哥哥真心口音重,而且开免提有回声我跟他说能不能关免提他说他没带耳机。。。然后我就听了45分钟自己的回声。。。

这位小哥一来先介绍自己的组,然后完全没问我任何东西直接上题:
. 1point3acres.com/bbs
第一题:给一个array,找出最长的连续片段   比如:[5,2,3,4,5,8,9]   就是2,3,4,5,返回4. visit 1point3acres.com for more.
我觉得这道题很眼熟,但是忘了最优解了,所以最开始写了一个看似两层循环但是time O(n),space O(n)的。但是小哥觉得还可以优化,所以开始提示我了,然后我在自己代码的基础上改了改最后改成了time:O(n),space:O(1)最优解
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题:还是找最长连续片段,但是是在树里面。因为第一天调到最优解就已经花了35分钟了,第二题讲了一下思路,准备用pre-order traver加stack来做,小哥说这个解不是最优但是勉强还行。就没有写代码了,写了一下步骤就结束了. 1point 3acres 璁哄潧

祝愿能来个onsite吧。。。Amazon和Bloomberg onsite全跪了。。。纽约没剩下几家可以面的了。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
要是还有哪位看到这个帖子的仁兄在纽约工作,公司对一年工作经验的base能上11W的同志帮忙内推一下吧。。。本人的公司工资实在是有点不好谈。。。但是又不想离开纽约。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧


. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2016-4-1 23:56):
第一题“不是”leetcode上面的longest consecutive sequence,同志们不要搞混了,要是那道题我也不敢大言不惭说是最优解了。。。请看清楚例子。。。后一个元素必须是前一个元素+1。。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
陈润鹏 发表于 2016-4-10 06:52:09 | 显示全部楼层
oceanator 发表于 2016-4-10 06:45
写了一个two pointers的解法。跪求大牛们指点!

10  少了加1
                   .-' _..`.
                  /  .'_.'.'
                 | .' (.)`.
                 ;'   ,_   `.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
.--.__________.'    ;  `.;-'
|  ./               /
|  |               /
`..'`-._  _____, ..'
     / | |     | |\ \
    / /| |     | | \ \. 1point3acres.com/bbs
   / / | |     | |  \ \
  /_/  |_|     |_|   \_\
|__\  |__\    |__\  |__\
回复 支持 1 反对 0

使用道具 举报

dimi 发表于 2016-4-2 12:06:10 | 显示全部楼层
这题目能做到O(n)楼主能拿图灵奖了。。。
回复 支持 反对

使用道具 举报

dimi 发表于 2016-4-2 12:09:16 | 显示全部楼层
第二题:还是找最长连续片段,但是是在树里面。
. 1point 3acres 璁哄潧
请问楼主,按什么顺序的最长自序列?pre-order?
回复 支持 反对

使用道具 举报

liberwang 发表于 2016-4-2 12:20:42 | 显示全部楼层
我记得第一题的最优解就是Time O(n), space 也是O(n),因为要把所有的数字放入到Hashset里,难道我记错啦?. from: 1point3acres.com/bbs
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-4-2 12:22):
先Bless楼主
回复 支持 反对

使用道具 举报

 楼主| fsr0023120 发表于 2016-4-2 12:22:08 | 显示全部楼层
dimi 发表于 2016-4-1 23:09
第二题:还是找最长连续片段,但是是在树里面。. 1point3acres.com/bbs

请问楼主,按什么顺序的最长自序列?pre-order?

leetcode原题 Binary Tree Longest Consecutive Sequence
回复 支持 反对

使用道具 举报

 楼主| fsr0023120 发表于 2016-4-2 12:23:09 | 显示全部楼层
dimi 发表于 2016-4-1 23:06
这题目能做到O(n)楼主能拿图灵奖了。。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
看来图灵很好拿嘛
回复 支持 反对

使用道具 举报

liberwang 发表于 2016-4-2 12:34:11 | 显示全部楼层
楼主答个疑,第一题如何做到Space O(1)?    Thanks,
回复 支持 反对

使用道具 举报

 楼主| fsr0023120 发表于 2016-4-2 12:34:26 | 显示全部楼层
liberwang 发表于 2016-4-1 23:20
我记得第一题的最优解就是Time O(n), space 也是O(n),因为要把所有的数字放入到Hashset里,难道我记错啦? ...

谢谢。.1point3acres缃
为什么需要hashset呢?这道题不需要去重复的,因为一定要连续的,而且必须只比前一个大1.
直接从右往左遍历。 下面的代码就是当时优化完了之后的结果:

  1.         public int findLongestConsecutive(int[] arr) {
  2.                 if (arr.length < 2)
  3.                         return arr.length;. visit 1point3acres.com for more.

  4.                 int dp = 1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.                 int largest = 0;

  6.                 for (int i = arr.length-2; i > 0; i--) {
  7.                     int len = 1;-google 1point3acres
  8.                     if (arr[i] == arr[i+1] - 1) {
  9.                                 len += dp;
  10.                                 largest = Math.max(largest, len);
  11.                                 dp = len;
  12.                     } else {
  13.                             dp = len;
  14.                             largest = Math.max(largest, len);
  15.                     }
  16.             }
  17.                 return largest;
  18.         }
复制代码
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-2 12:39:55 | 显示全部楼层
fsr0023120 发表于 2016-4-2 12:34
谢谢。
为什么需要hashset呢?这道题不需要去重复的,因为一定要连续的,而且必须只比前一个大1.
直接 ...

我以为是leetcode的longest consecutive sequence。谢谢楼主
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-2 12:41:17 | 显示全部楼层
fsr0023120 发表于 2016-4-2 12:34. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
谢谢。
为什么需要hashset呢?这道题不需要去重复的,因为一定要连续的,而且必须只比前一个大1.
直接 ...

那第一题的确很简单。o(1) space
回复 支持 反对

使用道具 举报

liberwang 发表于 2016-4-2 12:41:49 | 显示全部楼层
哦。我们俩说的不是一个题。我以为是
https://leetcode.com/problems/longest-consecutive-sequence/

谢谢。
回复 支持 反对

使用道具 举报

liberwang 发表于 2016-4-2 12:42:52 | 显示全部楼层
adiggo 发表于 2016-4-2 12:39
我以为是leetcode的longest consecutive sequence。谢谢楼主

握手,我也以为是这道
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-4-2 12:48:38 | 显示全部楼层
hashset是用来判断是不是最优解的起始值,leetcode原题,又没说input是sorted的。。给个降序的楼上代码就不work了
回复 支持 反对

使用道具 举报

 楼主| fsr0023120 发表于 2016-4-2 12:52:43 | 显示全部楼层
mingzhou1987 发表于 2016-4-1 23:48
hashset是用来判断是不是最优解的起始值,leetcode原题,又没说input是sorted的。。给个降序的楼上代码就不 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
看来我有必要重新写一下题目的描述了。。。。LOL
回复 支持 反对

使用道具 举报

 楼主| fsr0023120 发表于 2016-4-2 12:55:12 | 显示全部楼层
补充一下:第一题“不是”leetcode上面的longest consecutive sequence,同志们不要搞混了,要是那道题我也不敢大言不惭说是最优解了。。。请看清楚例子。。。后一个元素必须是前一个元素+1。。
回复 支持 反对

使用道具 举报

alpher 发表于 2016-4-3 08:48:12 | 显示全部楼层
One solution for the first one:         public int FindLongestConsecutive(int[] nums)         {             if (nums == null) return 0;             if (nums.Length < 2) return nums.Length;              int maxLen = 0, len = 1;             for (int i = 1; i < nums.Length; i++)             {                 if (nums[i] == nums[i - 1] + 1) len++;                 else                 {                     if (maxLen < len) maxLen = len;                     len = 1;                 }             }             if (maxLen < len) maxLen = len;              return maxLen;         }
回复 支持 反对

使用道具 举报

alpher 发表于 2016-4-3 08:48:58 | 显示全部楼层
-google 1point3acres
        public int FindLongestConsecutive(int[] nums)
        {
            if (nums == null) return 0;
            if (nums.Length < 2) return nums.Length;

            int maxLen = 0, len = 1;
            for (int i = 1; i < nums.Length; i++)-google 1point3acres
            {
                if (nums[i] == nums[i - 1] + 1) len++;. 1point3acres.com/bbs
                else
                {. from: 1point3acres.com/bbs
                    if (maxLen < len) maxLen = len;
                    len = 1;
                }
            }
            if (maxLen < len) maxLen = len;
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            return maxLen;. visit 1point3acres.com for more.
        }
回复 支持 反对

使用道具 举报

alpher 发表于 2016-4-3 09:12:51 | 显示全部楼层
2:
        public int FindLongestConsecutive(TreeNode root, int parentVal, int len, ref int maxLen)
        {.鏈枃鍘熷垱鑷1point3acres璁哄潧
            if (root == null)
            {
                if (maxLen < len) maxLen = len;
            }. From 1point 3acres bbs
            else
            {
                if (root.val + 1 == parentVal) len++;
                else. visit 1point3acres.com for more.
                {
                    if (maxLen < len) maxLen = len;
                    len = 1;
                }. 鍥磋鎴戜滑@1point 3 acres

                FindLongestConsecutive(root.left, root.val, len, ref maxLen);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                FindLongestConsecutive(root.right, root.val, len, ref maxLen);
            }

            return maxLen;
        }
回复 支持 反对

使用道具 举报

zdhzh05 发表于 2016-4-3 10:08:50 | 显示全部楼层
第二题类似 leetcode 124. Binary Tree Maximum Path Sum
但要返回以当前node为结束的最大递增序列长度,和以当前node为开始的最大递增序列长度. From 1point 3acres bbs
遍历过程中记录node为开始,结束,和中间的递增序列长度最大值
回复 支持 反对

使用道具 举报

wangyf1990 发表于 2016-4-3 12:26:06 | 显示全部楼层
楼主,不太理解题意。允许中间出现间隔吗?

【5, 0, 2, 1, 2】 是返回
2 [1, 2]
还是
3 [0, 1, 2]
啊?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 03:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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