【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4169|回复: 29
收起左侧

电面 Google

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

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

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

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

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

这位小哥一来先介绍自己的组,然后完全没问我任何东西直接上题:

第一题:给一个array,找出最长的连续片段   比如:[5,2,3,4,5,8,9]   就是2,3,4,5,返回4.鏈枃鍘熷垱鑷1point3acres璁哄潧
我觉得这道题很眼熟,但是忘了最优解了,所以最开始写了一个看似两层循环但是time O(n),space O(n)的。但是小哥觉得还可以优化,所以开始提示我了,然后我在自己代码的基础上改了改最后改成了time:O(n),space:O(1)最优解

第二题:还是找最长连续片段,但是是在树里面。因为第一天调到最优解就已经花了35分钟了,第二题讲了一下思路,准备用pre-order traver加stack来做,小哥说这个解不是最优但是勉强还行。就没有写代码了,写了一下步骤就结束了.鐣欏璁哄潧-涓浜-涓夊垎鍦
. visit 1point3acres.com for more.
祝愿能来个onsite吧。。。Amazon和Bloomberg onsite全跪了。。。纽约没剩下几家可以面的了。。。

要是还有哪位看到这个帖子的仁兄在纽约工作,公司对一年工作经验的base能上11W的同志帮忙内推一下吧。。。本人的公司工资实在是有点不好谈。。。但是又不想离开纽约。。。



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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

10  少了加1
                   .-' _..`.
                  /  .'_.'.'
                 | .' (.)`.
                 ;'   ,_   `.
.--.__________.'    ;  `.;-'
|  ./               /
|  |               /
`..'`-._  _____, ..'
     / | |     | |\ \
    / /| |     | | \ \
   / / | |     | |  \ \
  /_/  |_|     |_|   \_\. Waral 鍗氬鏈夋洿澶氭枃绔,
|__\  |__\    |__\  |__\
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

dimi 发表于 2016-4-2 12:09:16 | 显示全部楼层
第二题:还是找最长连续片段,但是是在树里面。

请问楼主,按什么顺序的最长自序列?pre-order?
回复 支持 反对

使用道具 举报

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

补充内容 (2016-4-2 12:22):
先Bless楼主
回复 支持 反对

使用道具 举报

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

请问楼主,按什么顺序的最长自序列?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里,难道我记错啦? ...

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

  1.         public int findLongestConsecutive(int[] arr) {
  2.                 if (arr.length < 2)
  3.                         return arr.length;
  4. . more info on 1point3acres.com
  5.                 int dp = 1;
  6.                 int largest = 0;

  7.                 for (int i = arr.length-2; i > 0; i--) {. more info on 1point3acres.com
  8.                     int len = 1;
  9.                     if (arr[i] == arr[i+1] - 1) {
  10.                                 len += dp;
  11.                                 largest = Math.max(largest, len);
    . 1point 3acres 璁哄潧
  12.                                 dp = len;
  13.                     } else {
  14.                             dp = len;
  15.                             largest = Math.max(largest, len);
  16.                     }
  17.             }
  18.                 return largest;
  19.         }
复制代码
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

adiggo 发表于 2016-4-2 12:41:17 | 显示全部楼层
fsr0023120 发表于 2016-4-2 12:34. 1point 3acres 璁哄潧
谢谢。
为什么需要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。谢谢楼主
.1point3acres缃
握手,我也以为是这道
回复 支持 反对

使用道具 举报

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的。。给个降序的楼上代码就不 ...
. 1point3acres.com/bbs
看来我有必要重新写一下题目的描述了。。。。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 | 显示全部楼层

        public int FindLongestConsecutive(int[] nums)
        {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            if (nums == null) return 0;
            if (nums.Length < 2) return nums.Length;. Waral 鍗氬鏈夋洿澶氭枃绔,
.鐣欏璁哄潧-涓浜-涓夊垎鍦
            int maxLen = 0, len = 1;
            for (int i = 1; i < nums.Length; i++)
            {.1point3acres缃
                if (nums[i] == nums[i - 1] + 1) len++;
                else
                {
                    if (maxLen < len) maxLen = len;
                    len = 1;
                }
            }
            if (maxLen < len) maxLen = len;
. 1point3acres.com/bbs
            return maxLen;
        }
回复 支持 反对

使用道具 举报

alpher 发表于 2016-4-3 09:12:51 | 显示全部楼层
2:. 1point3acres.com/bbs
        public int FindLongestConsecutive(TreeNode root, int parentVal, int len, ref int maxLen)
        {
            if (root == null)
            {
                if (maxLen < len) maxLen = len;
            }
            else
            {
                if (root.val + 1 == parentVal) len++;
                else
                {
                    if (maxLen < len) maxLen = len;
                    len = 1;
                }

                FindLongestConsecutive(root.left, root.val, len, ref maxLen);
                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为开始的最大递增序列长度
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷遍历过程中记录node为开始,结束,和中间的递增序列长度最大值
回复 支持 反对

使用道具 举报

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

【5, 0, 2, 1, 2】 是返回
2 [1, 2]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
还是
3 [0, 1, 2]. 1point3acres.com/bbs
啊?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-21 00:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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