男生找男友:我希望你至少是0.628,如果是0.942那就更好了。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 955|回复: 15
收起左侧

新鲜狗家面筋攒人品!! 求祝福!!!

[复制链接] |试试Instant~ |关注本帖
CankerHereAgain 发表于 2018-2-25 13:54:06 | 显示全部楼层 |阅读模式

2018(1-3月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Other | 在职跳槽

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

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

x


第一轮
给一个矩阵, 找到和最大的子矩阵, 只要求返回最大的和, 用dp方法, O(n3)的时间可以解, follow up是怎么继续优化时间, 因为时间不多了 我只是说了几个简单的想法, 最后也没想出来.

第二轮
给一个数列, 判断数列中是否存在长度为3的升序子序列, 只要求返回是或否
follow up是如果寻找的子序列的长度为k
用单调栈解
. 1point3acres.com/bbs
第三轮
蠡忑扣徳 其三思 其三齐
-google 1point3acres
第四轮.鏈枃鍘熷垱鑷1point3acres璁哄潧
上来先问了Hourse Robber, 然后说如果输入的是两行, 一旦抢了一家, 所有相邻的都不能抢. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后说如果是3行, 怎么解决, 如果是k行 怎么解决
这轮主要是偏向讨论, 和面试官交流想法, 最后只要求写了最简单的情况的代码

第五轮.鐣欏璁哄潧-涓浜-涓夊垎鍦
问了10分钟的简历
题目是给围棋的棋盘, 以及一个move, 判断是否有子死亡
死亡可能是这个move杀了对手的子, 也可能是这个move杀了自己的子
面试官说只要实现判断是否杀了对方的子即可
然后写了一个简单的DFS



总体来说面试不难
题目都写出来了 但是有些还是一些些小瑕疵
攒人品!!但愿能有好结果!!!

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · google|主题: 28, 订阅: 7
  • · GG|主题: 17, 订阅: 2
jack213 发表于 2018-2-26 15:28:45 | 显示全部楼层
CankerHereAgain 发表于 2018-2-26 14:14
想法的都是一样的 就是 bfs的时候 稍稍改一下规则, 如果遇到相同的棋子就压栈, 如果遇到空白的就返回没有 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主你这个LIS不太对啊,比如输入数据是
2, 3, 1, 4
你一开始把 2, 3 压进去了
到 1 的时候把 2, 3 都弹出来了
最后把 4 压进去
你这样stack里面最多的时候元素为 2
但实际上 2, 3, 4 是一个长度为3的 LIS
回复 支持 2 反对 0

使用道具 举报

 楼主| CankerHereAgain 发表于 2018-2-26 10:12:18 | 显示全部楼层
Augustus 发表于 2018-2-26 08:25
楼主,没看懂第一题dp怎么解的,求问

https://www.youtube.com/watch?v=yCQN096CwWM
这个视频解释的很详细!
回复 支持 1 反对 0

使用道具 举报

jasonyang04 发表于 2018-2-25 14:59:43 | 显示全部楼层
祝福楼主。有两个问题谢谢解答下。House Robber两行和k行怎么处理的?是用
回复 支持 反对

使用道具 举报

jasonyang04 发表于 2018-2-25 15:02:27 | 显示全部楼层
祝福楼主。有两个问题谢谢解答下。1.House Robber两行和k行怎么处理的?是用pure dfs去搜索吗?2.最后一题围棋怎么处理的?如何去判断一个子被包围而死亡了呢?
回复 支持 反对

使用道具 举报

 楼主| CankerHereAgain 发表于 2018-2-26 02:51:01 | 显示全部楼层
jasonyang04 发表于 2018-2-25 15:02.鐣欏璁哄潧-涓浜-涓夊垎鍦
祝福楼主。有两个问题谢谢解答下。1.House Robber两行和k行怎么处理的?是用pure dfs去搜索吗?2.最后一题 ...
. more info on 1point3acres.com
House Robber多行的话 可以用一个参数记录前一列的选择, 然后在选择当前列. from: 1point3acres.com/bbs
比如0表示前一列没有选, 0101表示前一列选了第二行和第四行, 那么就可以根据这个参数选择当前列的房子. from: 1point3acres.com/bbs
每一列有差不多2^k的选择, 一共有n列, 所以利用map存中间结果的话 时间复杂度是O(2^k*n)..鐣欏璁哄潧-涓浜-涓夊垎鍦

围棋题和LC130有点像 可以参考130的DFS解法
回复 支持 反对

使用道具 举报

tinylic 发表于 2018-2-26 04:05:33 | 显示全部楼层
请问最大子矩阵有时间复杂度比N^3更优的做法嘛?
回复 支持 反对

使用道具 举报

 楼主| CankerHereAgain 发表于 2018-2-26 04:57:40 | 显示全部楼层
tinylic 发表于 2018-2-26 04:05. 1point3acres.com/bbs
请问最大子矩阵有时间复杂度比N^3更优的做法嘛?

面试官说可以优化到N2LogN, 但是他说这个很challenging
回复 支持 反对

使用道具 举报

Augustus 发表于 2018-2-26 08:25:49 | 显示全部楼层
楼主,没看懂第一题dp怎么解的,求问
回复 支持 反对

使用道具 举报

jasonyang04 发表于 2018-2-26 13:27:01 | 显示全部楼层
CankerHereAgain 发表于 2018-2-26 02:51
House Robber多行的话 可以用一个参数记录前一列的选择, 然后在选择当前列
比如0表示前一列没有选, 0101 ...

谢谢楼主。我还是有两个问题,麻烦你能解答下。1. 围棋那题,我看了下LC130,是从边缘进行遍历,但是围棋每个点应该有三种情况吧,空白,黑子,白子。那我如何进行遍历去找那个死的棋子呢?2. 升序子序列这题我感觉和longest increasing subsequence是一样的吧,不应该用DP吗,如何用单调栈解这题啊?
回复 支持 反对

使用道具 举报

BigShaun 发表于 2018-2-26 13:53:27 | 显示全部楼层
同问第二题和LIS不一样吗? 难道是要subarray不是subsequence??
回复 支持 反对

使用道具 举报

 楼主| CankerHereAgain 发表于 2018-2-26 14:14:21 | 显示全部楼层
jasonyang04 发表于 2018-2-26 13:27
谢谢楼主。我还是有两个问题,麻烦你能解答下。1. 围棋那题,我看了下LC130,是从边缘进行遍历,但是围棋 ...

想法的都是一样的 就是 bfs的时候 稍稍改一下规则, 如果遇到相同的棋子就压栈, 如果遇到空白的就返回没有死亡, 如果遇到对方的棋子就跳过

第二题是应该就是 longest increasing subsequence.
从头到尾遍历, 每次判断遍历到的数和 stack 顶部的数的大小,
如果当前的数大于栈顶元素, 就压栈, 否则就出栈, 直到 stack 为空或者栈顶元素小于当前元素-google 1point3acres
然后只要在运行过程中记录 stack 中元素个数的最大值就行
回复 支持 反对

使用道具 举报

 楼主| CankerHereAgain 发表于 2018-2-26 14:22:41 | 显示全部楼层
BigShaun 发表于 2018-2-26 13:53
同问第二题和LIS不一样吗? 难道是要subarray不是subsequence??

第二题应该就是 LIS, subsequence.
面试官给我的原题是  x < y < z and num.indexOf(x) < num.indexOf(y) < num.indexOf(z)
回复 支持 反对

使用道具 举报

anica567 发表于 2018-2-27 11:38:09 | 显示全部楼层
CankerHereAgain 发表于 2018-2-26 10:12
https://www.youtube.com/watch?v=yCQN096CwWM
这个视频解释的很详细!

谢谢!!! 视频讲的很好!
回复 支持 反对

使用道具 举报

Augustus 发表于 2018-2-27 14:18:31 | 显示全部楼层
狗家bar这么高,感觉去了也是当分母。。。
回复 支持 反对

使用道具 举报

wb7 发表于 2018-2-27 14:42:53 | 显示全部楼层
jack213 发表于 2018-2-26 15:28
楼主你这个LIS不太对啊,比如输入数据是
2, 3, 1, 4-google 1point3acres
你一开始把 2, 3 压进去了

和我想的一样,出栈操作是可能改变当前的subsequence的起始位置的,如果扫array的时候看到了比栈底元素更小的元素会导致所有元素出栈,会错过可能的解。

就是说,单调栈解决不了之后看到的数据比栈里最小的数据更小,并且后来数据存在比当前栈里数据更大的情况。
. From 1point 3acres bbs
ps 楼主发的视频确实讲的非常好。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-22 05:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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