一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
查看: 2246|回复: 12
收起左侧

🐶家2021实习OA

[复制链接] |只看干货 |面试经验, google, 码农类general, 美国面经
地里的匿名用户
地里的匿名用户  发表于 2020-10-29 13:41:17 |阅读模式
本楼: 👍   100% (3)
 
 
0% (0)   👎

2020(7-9月) 码农类General 硕士 实习@Google - 内推 - 在线笔试  | Other | 其他

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 匿名 于 2020-10-29 14:01 编辑

喜笑颜开进去,愁眉苦脸出来。遇到的其中一题是19年变体,另一题变得稍微有点大,看到有点面生...

游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.


有用的话求加大米,看面经急需。感恩!



评分

参与人数 15大米 +27 收起 理由
florenz + 2 给你点个赞!
fmusk + 1 很有用的信息!
yuyangh + 2 给你点个赞!
rcraysun + 1 给你点个赞!
VincentRen + 1 很有用的信息!
GeminiJi + 3 很有用的信息!
ShikiiTyan + 2 很有用的信息!
924008712 + 1 给你点个赞!
wzl02 + 1 给你点个赞!
omq + 1 给你点个赞!

查看全部评分


上一篇:点击公司电面
下一篇:雨林New Grad一轮VO过经+timeline
我的人缘0
TWTXURI 2020-11-12 11:15:00 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (26)
 
 
0% (0)    👎
第一题为毛不能直接O(20 * 2 * n)
每个值扫一遍, 用two pointer
p1一直向前直到遇到第四个不一样的值
然后p2向前一直遇到一个不一样的值
随时更新maxlength就行,每个value最多被扫两遍所以是O(2n * 20)?
回复

使用道具 举报

我的人缘0

升级   0%

guamapi 2020-10-30 02:32:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (8)
 
 
0% (0)    👎
什么是最长的相等数列?和谁比呀?
回复

使用道具 举报

我的人缘0

升级   18.93%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (462)
 
 
4% (20)    👎
第一题是换三次数为任意数,使得原数列的所有数字都相等的subarray长度最大,是这个意思吗? subarray也要按原来的数列顺序, 只是可以更换element的值是嘛?
回复

使用道具 举报

我的人缘0

升级   3.29%

heiyu 2020-10-30 05:52:10 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (197)
 
 
0% (0)    👎
Thanks for sharing. The following is my thought.
```class Solution:
    def longestSubarray(self, nums, k):
        if len(nums) <= k: return len(nums)

        group = [[nums[0], 1]] #[num, count]
        #group adjacent elements
        for i in range(1, len(nums)):
            if nums[i] == group[-1][0]:
                group[-1][1] += 1
            else:
                group.append([nums[i], 1])

        #count the possible prefix of the subarray
        def helper(preGroup, count, num):
            if not preGroup: return 0
            if preGroup[-1][0] == num:
                res = preGroup[-1][1] + helper(preGroup[:-1], count, num)
            else:
                if preGroup[-1][1] > count:
                    res = count
                else:
                    count -= preGroup[-1][1]
                    res = preGroup[-1][1] + helper(preGroup[:-1], count, num)
            return res

        #count the max length of subarray which ends at the ith group  
        max_length = 0
        for i in range(len(group)):
            cur_length = group[i][1] + helper(group[:i][:], k, group[i][0]) #use the whole ith group as ending
            if i > 0:
                addon = min(k, group[i][1])
                for j in range(1, addon + 1): #use part of the ith group as ending
                    cur_length = max(cur_length, j + group[i - 1][1] + helper(group[:i - 1][:], k - j, group[i - 1][0]))
            max_length = max(max_length, cur_length)
        return max_length
```  

回复

使用道具 举报

地里的匿名用户
地里的匿名用户  发表于 2020-10-30 13:43:06
本楼: 👍   0% (0)
 
 
0% (0)   👎
熊猫杀很大缺积分 发表于 2020-10-29 12:24:50
第一题是换三次数为任意数,使得原数列的所有数字都相等的subarray长度最大,是这个意思吗? subarray也要按原来的数列顺序, 只是可以更换element的值是嘛?
是的。要按照原来的顺序,更换任意三个或以下element。
回复

使用道具 举报

我的人缘0

升级   18.93%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (462)
 
 
4% (20)    👎
匿名者 发表于 2020-10-30 13:43
是的。要按照原来的顺序,更换任意三个或以下element。

感谢楼主 祝早日move forward
回复

使用道具 举报

我的人缘0
AbbeWang 2020-11-3 04:36:29 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
heiyu 发表于 2020-10-30 05:52
Thanks for sharing. The following is my thought.
```class Solution:
    def longestSubarray(self, ...

大概能明白你的意思但是感觉有点复杂。。

我的思路是对每一个value:[-10, 10]做sliding window。复杂度是O(n * k), k是所有nums的范围。这里因为限定了[-10, 10],所以O(n * k)~O(20 * n)~O(n).
回复

使用道具 举报

我的人缘0

升级   3.29%

heiyu 2020-11-4 04:41:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (197)
 
 
0% (0)    👎
AbbeWang 发表于 2020-11-3 04:36
大概能明白你的意思但是感觉有点复杂。。

我的思路是对每一个value:[-10, 10]做sliding window。复杂 ...

Thanks for the response. Your idea of sliding window is much easier to implement. I think it should be the expected solution.
回复

使用道具 举报

我的人缘1

升级   8.71%

yidansheng 2020-11-4 08:55:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (33)
 
 
0% (0)    👎
本帖最后由 yidansheng 于 2020-11-4 08:56 编辑

我的想法差不多, dp在subarray end 在每一个index上的时候 使用掉k次替换后的最长的只有数字X的subarray
[Python] 纯文本查看 复制代码
def longest_unique_subarray(arr, k):
    dp=[[1 for i in range(k+1)] for j in range(-10, 11)]
    for i in range(-10, 11):
        dp[i][0]=0
    dp[arr[0]][0]=1
    ret=1
    for i in range(1, len(arr)):
        for target in range(-10, 11):
            if target==arr[i]:
                for replace in range(k+1):
                    dp[target][replace]+=1
                    ret=max(ret, dp[target][replace])
            else:
                for replace in range(k-1, -1, -1):
                    dp[target][replace+1]=dp[target][replace]+1
                    ret=max(ret, dp[target][replace+1])
                dp[target][0]=0
    return ret
arrs=[[9,-8],[1,2,10,3,10,10],[3,1,3,3,1,3,1,1]]
for arr in arrs:
    print(longest_unique_subarray(arr, 3))
回复

使用道具 举报

我的人缘0

升级   2.71%

hsierra 2020-11-7 16:31:06 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (74)
 
 
0% (0)    👎
第一题维护一个map
unordered_map<num, vector<pair<int, int>>

vector里是{start_index, len}的pair.

比如:input  = {3,1,3,3,1,3,1,1}, output = 7
3=> {0, 1}, {2, 2}, {5, 1}
1=>{1, 1}, {4, 1}, (6, 1}, (7, 1}

然后周游每个map element就好了。vector里间隔<=k的长度可以在一起,大于k就重新计数,这样可求出k次替换得到的最长串

每个map element周游完,可以得到最后的最长串
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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