一亩三分地论坛

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

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

g家intern电面

[复制链接] |试试Instant~ |关注本帖
williamdotyang 发表于 2016-10-27 05:25:41 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
1. 给个int array,找它subarray(中间indexes连续的那种)里满足 min(array)*2 > max(array)的那些,return最长的subarray(的长度)。
2. 一些tree的简单问题。。比如,给个tree,还有should_delete(),删掉某些node 把这个tree 分解成若干个tree,返回各个root。-google 1point3acres

第一个是个中国人,一开始闲聊了好久(大概10~15min?)简历上project还有为啥不想读phd啦之类的。。(他说他当年也没有接着读博 可能有点共鸣)然后做题。。当时一开始挺紧张的,所以就先brute force了。。recursive那种,写着写着觉得应该dp,他说是的,然后就加了个hashtable。然后改成了iterative的那种,用2d array存中间结果。后来他说可以改进一下memory,发现其实只需要存O(1)的信息即可。没问问题(没时间了),直接结束。。说实话挺慌的,当时有点小磕绊,还好国人照顾些,有很多hint和交流,人也特别nice。

第二个是个美国人(应该是白人男),他貌似感冒了,全程除了说题几乎没怎么出声,我就一直边码边讲以免场面过冷。。还好题很基础,他也没准备很多问题,最后一看时间还有点干脆让写几个test case。。少有的一些交流也还算顺畅。. 1point 3acres 璁哄潧
-google 1point3acres
如果要总结一些经验的话就是,千万不要冷场吧。。边码边讲说思路,这样人家一听觉得你思路不对可以避免走弯路。说实话这两轮都挺幸运的,遇到的面试官都很nice。。不像fb那个三哥哥,迟到15分钟,甩题就跑去开会了。。。人品还是很重要😂

加油刷题,共勉

求match 求match。。🙏. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

3

查看全部评分

本帖被以下淘专辑推荐:

jacky841102 发表于 2016-10-27 11:09:59 | 显示全部楼层
第一题可以在O(n)时间内解决?用min/max queue,可以在O(1)得到min/max的queue,类似leetcode上的min stack
用法类似two pointers,若是min * 2 > max 就一直push,若min * 2 <= max就pop掉最左边的,直到min * 2 > max

看一下有没有问题?input: [4,3,5,6,4] => output: 3, input: [4,2,1,1,6,3] => output: 2
  1. class minMaxQueue:
  2.     def __init__(self):. more info on 1point3acres.com
  3.         self.minq = deque()
  4.         self.maxq = deque()
  5.         self.q = deque()
  6. . Waral 鍗氬鏈夋洿澶氭枃绔,
  7.     def push(self, i): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.         self.q.append(i)

  9.         while self.maxq and self.maxq[-1] < i: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10.             self.maxq.pop(). visit 1point3acres.com for more.
  11.         self.maxq.append(i)

  12.         while self.minq and self.minq[-1] > i:-google 1point3acres
  13.             self.minq.pop()
  14.         self.minq.append(i)
  15. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.     def pop(self):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  17.         i = self.q.popleft()

  18.         if self.maxq[0] == i:
  19.             self.maxq.popleft()

  20.         if self.minq[0] == i:
  21.             self.minq.popleft()
  22. . Waral 鍗氬鏈夋洿澶氭枃绔,
  23.         return i

  24.     def getMin(self):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  25.         if self.minq:
  26.             return self.minq[0]

  27.     def getMax(self):
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.         if self.maxq:
  29.             return self.maxq[0]
  30. . more info on 1point3acres.com
  31. def solve(array):
  32.     q = minMaxQueue()
  33.     ans = 0
  34.     for n in array:
  35.         q.push(n)
  36.         while q.q and q.getMin() * 2 <= q.getMax():
  37.             q.pop()
  38.         ans = max(ans, len(q.q))
  39.     return ans
复制代码
回复 支持 1 反对 0

使用道具 举报

jacky841102 发表于 2016-10-27 13:13:02 | 显示全部楼层
第一题可以O(n)? 用min/max queue, 类似two poitners
from collections import deque
class minMaxQueue:
    def __init__(self): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        self.minq = deque().1point3acres缃
        self.maxq = deque()
        self.q = deque()

    def push(self, i):
        self.q.append(i)

        while self.maxq and self.maxq[-1] < i:
            self.maxq.pop()
        self.maxq.append(i)

        while self.minq and self.minq[-1] > i:
            self.minq.pop()
        self.minq.append(i)

    def pop(self):
        i = self.q.popleft()

        if self.maxq[0] == i:
            self.maxq.popleft(). from: 1point3acres.com/bbs

        if self.minq[0] == i:. more info on 1point3acres.com
            self.minq.popleft()
        return i. From 1point 3acres bbs

    def getMin(self):
        if self.minq:
            return self.minq[0]

    def getMax(self):
        if self.maxq:.鐣欏璁哄潧-涓浜-涓夊垎鍦
            return self.maxq[0]

def solve(array):
    q = minMaxQueue()
    ans = 0
    for n in array:
        q.push(n)
        while q.q and q.getMin() * 2 <= q.getMax():
            q.pop()
        ans = max(ans, len(q.q)). visit 1point3acres.com for more.
    return ans
回复 支持 1 反对 0

使用道具 举报

minggr 发表于 2016-10-27 12:59:37 | 显示全部楼层
第一题,Time O(n^2), Space O(1)

  1. int longest_subarray(vector<int> &nums). from: 1point3acres.com/bbs
  2. {   
  3.     int max_len = 0;

  4.     int n = nums.size();.鐣欏璁哄潧-涓浜-涓夊垎鍦

  5.     for (int i = 0; i < n; i++) {
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.         int min_num = nums[i];
  7.         int max_num = nums[i];

  8.         for (int j = i + 1; j < n; j++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.             min_num = min(min_num, nums[j]);
  10.             max_num = max(max_num, nums[j]);
  11.          
  12.             if (min_num * 2 > max_num)
  13.                 max_len = max(max_len, j-i+1);
  14.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.     }
  16.    
  17.     return max_len;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  18. }

  19. int main().1point3acres缃
  20. {   
  21.     vector<int> nums = {1, 3, 4, 4, 3, 5, 5, 6};
  22.    
  23.     cout << longest_subarray(nums) << endl;

  24.     return 0;. 鍥磋鎴戜滑@1point 3 acres
  25. }. 鍥磋鎴戜滑@1point 3 acres
复制代码
回复 支持 1 反对 0

使用道具 举报

whdawn 发表于 2016-10-27 13:12:59 | 显示全部楼层
看名字感觉好眼熟                 
回复 支持 1 反对 0

使用道具 举报

shenji2012 发表于 2016-10-27 09:50:00 | 显示全部楼层
第一题时间复杂度是多少? O(nlgn) 吗?
回复 支持 反对

使用道具 举报

 楼主| williamdotyang 发表于 2016-10-27 10:19:09 | 显示全部楼层
shenji2012 发表于 2016-10-27 09:50
第一题时间复杂度是多少? O(nlgn) 吗?

我做的是O(n^2)。。二维的dp。。
回复 支持 反对

使用道具 举报

bananapancake 发表于 2016-10-27 10:31:09 | 显示全部楼层
请问楼主第一题怎么用dp做的?
回复 支持 反对

使用道具 举报

bananapancake 发表于 2016-10-27 10:42:24 | 显示全部楼层
好吧,这题是不是每次看(i,j )的时候,只需要看一看(i + 1, j)和(i,j - 1)就好了?如果这其中有合法的,还要更新一下min max?我就想出这种2d DP求解答。
回复 支持 反对

使用道具 举报

 楼主| williamdotyang 发表于 2016-10-27 10:46:07 | 显示全部楼层
bananapancake 发表于 2016-10-27 10:31
请问楼主第一题怎么用dp做的?

min(array[i:j+1]) 其实是等于 min(min(array[i:j]), array[j]). max的情况同理。所以可以用O(1)时间填充一个二维dp matrix的一个cell。。你要存的是i th 到 j th 的subarray的min和max,一行一行从对角元素填充。还可以发现这个递归关系只用到了前一个的信息,所以能优化到O(1)空间复杂度。。
回复 支持 反对

使用道具 举报

bananapancake 发表于 2016-10-27 10:51:53 | 显示全部楼层
williamdotyang 发表于 2016-10-27 10:46
min(array) 其实是等于 min(min(array), array[j]). max的情况同理。所以可以用O(1)时间填充一个二维dp m ...

楼主这道题能不能直接nested for loop做呢?固定起始位置,然后一直往后找,更新min,max就好了?然后同时update最大长度?是不是也是O(n^2)?我是不是又有什么地方没想到呢?
回复 支持 反对

使用道具 举报

 楼主| williamdotyang 发表于 2016-10-27 10:57:35 | 显示全部楼层
bananapancake 发表于 2016-10-27 10:51
楼主这道题能不能直接nested for loop做呢?固定起始位置,然后一直往后找,更新min,max就好了?然后同 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
对 iterative就行了。。当时一开始是recursive,后来改成iterative了。。
回复 支持 反对

使用道具 举报

bananapancake 发表于 2016-10-27 10:59:40 | 显示全部楼层
williamdotyang 发表于 2016-10-27 10:57
对 iterative就行了。。当时一开始是recursive,后来改成iterative了。。

谢谢!恭喜楼主了!祝match成功!
回复 支持 反对

使用道具 举报

 楼主| williamdotyang 发表于 2016-10-27 11:10:53 | 显示全部楼层
bananapancake 发表于 2016-10-27 10:59
谢谢!恭喜楼主了!祝match成功!
. 1point3acres.com/bbs
没事!借吉言~
回复 支持 反对

使用道具 举报

sccnju 发表于 2016-10-27 11:36:54 | 显示全部楼层
多谢楼主分享经验哈。第一题DP我写了一个2D版本的,就是dp[j]存着从i到j的最大值和最小值。能不能帮忙看一下差不多是不是这个意思哈?多谢哈
  1. . from: 1point3acres.com/bbs
  2. def max_subarray(nums):. from: 1point3acres.com/bbs
  3.     n = len(nums)
  4.     dp = [[{"min":float("inf"), "max":-float("inf")} for i in range(n)] for j in range(n)]. from: 1point3acres.com/bbs
  5.     ans = -1
  6.     for i in range(n): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.         dp[i][i]["min"] = nums[i]
  8.         dp[i][i]["max"] = nums[i]

  9.     for i in range(n):
  10.         for j in range(i+1,n):. 1point3acres.com/bbs
  11.             dp[i][j]["min"] = min(dp[i][j-1]["min"], nums[j])
  12.             dp[i][j]["max"] = max(dp[i][j-1]["max"], nums[j])
  13.             min_tmp = dp[i][j]["min"]. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.             max_tmp = dp[i][j]["max"]
  15.             if dp[i][j]["min"] != float("inf") and min_tmp*2 > max_tmp:
  16.                
  17.                 ans = max(ans, j-i+1)
  18.    
  19.     return ans
复制代码
回复 支持 反对

使用道具 举报

 楼主| williamdotyang 发表于 2016-10-27 11:52:36 | 显示全部楼层
sccnju 发表于 2016-10-27 11:36
多谢楼主分享经验哈。第一题DP我写了一个2D版本的,就是dp[j]存着从i到j的最大值和最小值。能不能帮忙看一 ...

是这个意思 我看着没啥问题
回复 支持 反对

使用道具 举报

sccnju 发表于 2016-10-27 12:11:00 | 显示全部楼层
williamdotyang 发表于 2016-10-27 11:52
是这个意思 我看着没啥问题
. from: 1point3acres.com/bbs
多谢哈。然后优化空间就是这二维数组里面的i其实都没有用直接去掉就行了哈?. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

回复 支持 反对

使用道具 举报

cookielee77 发表于 2016-10-27 12:27:50 | 显示全部楼层
williamdotyang 发表于 2016-10-27 10:46
min(array) 其实是等于 min(min(array), array[j]). max的情况同理。所以可以用O(1)时间填充一个二维dp m ...

但是brutal force的话难道不也是O(n^2)?
回复 支持 反对

使用道具 举报

jacky841102 发表于 2016-10-27 13:12:41 | 显示全部楼层
第一题可以O(n)? 用min/max queue, 类似two poitners
  1. from collections import deque
  2. class minMaxQueue:
  3.     def __init__(self):
  4.         self.minq = deque()
  5.         self.maxq = deque()
  6.         self.q = deque()

  7.     def push(self, i):
  8.         self.q.append(i).鐣欏璁哄潧-涓浜-涓夊垎鍦
  9. .1point3acres缃
  10.         while self.maxq and self.maxq[-1] < i:. visit 1point3acres.com for more.
  11.             self.maxq.pop()
  12.         self.maxq.append(i).1point3acres缃
  13. . visit 1point3acres.com for more.
  14.         while self.minq and self.minq[-1] > i:
  15.             self.minq.pop()
  16.         self.minq.append(i)

  17.     def pop(self):
  18.         i = self.q.popleft()

  19.         if self.maxq[0] == i:
  20.             self.maxq.popleft()

  21.         if self.minq[0] == i:
  22.             self.minq.popleft()
  23.         return i. 1point 3acres 璁哄潧
  24. . 1point3acres.com/bbs
  25.     def getMin(self):. more info on 1point3acres.com
  26.         if self.minq:
  27.             return self.minq[0]. 鍥磋鎴戜滑@1point 3 acres

  28.     def getMax(self):
  29.         if self.maxq:
  30.             return self.maxq[0]

  31. def solve(array):
  32.     q = minMaxQueue()
  33.     ans = 0
  34.     for n in array:
  35.         q.push(n)
  36.         while q.q and q.getMin() * 2 <= q.getMax():
  37.             q.pop()
  38.         ans = max(ans, len(q.q))
    . 鍥磋鎴戜滑@1point 3 acres
  39.     return ans
复制代码
回复 支持 反对

使用道具 举报

lic10 发表于 2016-10-27 13:28:27 | 显示全部楼层
楼主能具体说说第二轮吗?谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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