回复: 15
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

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

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

x


第一轮
给一个矩阵, 找到和最大的子矩阵, 只要求返回最大的和, 用dp方法, O(n3)的时间可以解, follow up是怎么继续优化时间, 因为时间不多了 我只是说了几个简单的想法, 最后也没想出
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
的子即可
然后写了一个简单的DFS



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

评分

参与人数 4大米 +18 收起 理由
cc.wang + 3 很有用的信息!
yiliaobailiao + 3 给你点个赞!
jy_121 + 10 很有用的信息!
cexq + 2 很有用的信息!

查看全部评分


上一篇:脸熟+奥克油乐斯单电面双黄蛋昂塞新鲜面筋小礼包
下一篇:新鲜果果昂塞

本帖被以下淘专辑推荐:

  • · google|主题: 216, 订阅: 124
推荐
jack213 2018-2-26 15:28:45 | 只看该作者
全局:
CankerHereAgain 发表于 2018-2-26 14:14
想法的都是一样的 就是 bfs的时候 稍稍改一下规则, 如果遇到相同的棋子就压栈, 如果遇到空白的就返回没有 ...

楼主你这个LIS不太对啊,比如输入数据是
2, 3, 1, 4
你一开始把 2, 3 压进去了
到 1 的时候把 2, 3 都弹出来了
最后把 4 压进去
你这样stack里面最多的时候元素为 2
但实际上 2, 3, 4 是一个长度为3的 LIS
回复

使用道具 举报

推荐
 楼主| CankerHereAgain 2018-2-26 10:12:18 | 只看该作者
全局:
Augustus 发表于 2018-2-26 08:25
楼主,没看懂第一题dp怎么解的,求问

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

使用道具 举报

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

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

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

使用道具 举报

🔗
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.最后一题 ...

House Robber多行的话 可以用一个参数记录前一列的选择, 然后在选择当前列
比如0表示前一列没有选, 0101表示前一列选了第二行和第四行, 那么就可以根据这个参数选择当前列的房子
每一列有差不多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
请问最大子矩阵有时间复杂度比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??
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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