八八老东家Pinterest

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1436|回复: 36
收起左侧

狗家面试挂经 求安慰米

  [复制链接] |试试Instant~ |关注本帖
我的人缘0
浅漾 发表于 6 天前 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  100% (32)
 
 
0% (0)  踩

2018(7-9月) 码农类General 硕士 全职@Google - 网上海投 - Onsite  | Other | 在职跳槽

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

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

x
本帖最后由 nunuh89 于 2018-7-11 13:12 编辑 . 牛人云集,一亩三分地

给大家po个热气腾腾的狗家onsite
游客,本帖隐藏的内容需要积分高于 100 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

.本文原创自1point3acres论坛
. 1point 3acres 论坛
没有考到DP。。。刷了好久背包问题都没考到 不开心。。。. From 1point 3acres bbs
第一题上来就知道自己挂了。。。全天都沉浸在我的爱情还没开始就已经结束的悲痛中。。。. from: 1point3acres
. more info on 1point3acres
来年再战啦!祝大家面试顺利!


.本文原创自1point3acres论坛

补充内容 (2018-7-12 05:07):
sorry 我第一题打错了 矩阵长这样
. 围观我们@1point 3 acres
5   7    9  10
4   6    8   11
1   2   13  14. 一亩-三分-地,独家发布
0   3   12  15. 围观我们@1point 3 acres
. From 1point 3acres bbs

评分

参与人数 17大米 +129 收起 理由
ArtemisYY + 5 给你点个赞!
idatascience + 5 给你点个赞!
yyc0801 + 3 给你点个赞!
xiaozhu + 5 给你点个赞!
elephant31 + 5 给你点个赞!
reliveinfire + 5 给你点个赞!
suixinsuoyu + 5 给你点个赞!
designyyyy + 5 给你点个赞!
nunuh89 + 40
xiaomianyang + 5 加油
xsgs111 + 1 很有用的信息!
AnthonyNeu + 10 给你点个赞!
oceanator + 5 很有用的信息!
wtcupup + 10 给你点个赞!
edyyy + 5 给你点个赞!

查看全部评分


上一篇:微软电面
下一篇:奎配店面

本帖被以下淘专辑推荐:

我的人缘0
suixinsuoyu 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  98% (60)
 
 
1% (1)  踩
游客,本帖隐藏的内容需要积分高于 200 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.


时间复杂度常数级,每次棋盘横纵坐标各砍一半。
2^16 就进16次while循环。
已经测试跑通。

评分

参与人数 1大米 +5 收起 理由
marthew777 + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
wtcupup 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  61% (330)
 
 
38% (204)  踩
没太看懂第一题 拿4X4的举例子 如果左下是
1   2
0   3
. 1point 3acres 论坛
为啥左上是 ?
6   7
4   5
回复

使用道具 举报

我的人缘0
 楼主| 浅漾 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (32)
 
 
0% (0)  踩
wtcupup 发表于 2018-7-12 03:08.1point3acres网
没太看懂第一题 拿4X4的举例子 如果左下是-google 1point3acres
1   2
0   3

我写错了 应该是
5  6
4  7
多谢提醒
回复

使用道具 举报

我的人缘0
xsgs111 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
lz,第一题右下角的部分是
13,14
12,15
. Waral 博客有更多文章,吧?如果不是typo的话能解释一下为啥吗?
回复

使用道具 举报

我的人缘0
anoyanoy 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
我怎么感觉第一题应该是
5   6    9   10
4   7    8   11
1   2   13  14
0   3   12  15. Waral 博客有更多文章,


(3,3) = 15 (3,0) = 12
回复

使用道具 举报

我的人缘0
 楼主| 浅漾 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (32)
 
 
0% (0)  踩
anoyanoy 发表于 2018-7-12 04:37. From 1point 3acres bbs
我怎么感觉第一题应该是
. more info on 1point3acres5   6    9   10
4   7    8   11

5   7    9  10
4   6    8   11
1   2   13  14
0   3   12  15
对 抱歉打错了
回复

使用道具 举报

我的人缘0
suixinsuoyu 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (60)
 
 
1% (1)  踩
第一题,我觉得类似二分查找,每次4分一下矩阵可能可行。
我们可以把每一步看成类似直角坐标系的四象限。找到当前坐标在当前层哪个象限内。
因为这种填表的顺序,总可以保证四个象限内的数 0 < 1 < 2 < 3
找到以后确定这个象限的最小值与最大值。

稍微demo一下, 比如2 ^ 16 * 2 ^ 16。切完以后的数字是0 到 2 ^ 32 - 1, 四个象限可以等分。. from: 1point3acres
如果坐标落在第二象限,右上区域。start number 应该为 (2  ^ 32) / 4 * 2. end number 为 (2  ^ 32) / 4 * 3 - 1.
然后利用新的start end,继续切分当前象限。到收敛为止。
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
 楼主| 浅漾 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (32)
 
 
0% (0)  踩
suixinsuoyu 发表于 2018-7-12 05:11
第一题,我觉得类似二分查找,每次4分一下矩阵可能可行。
我们可以把每一步看成类似直角坐标系的四象限。 ...

然后呢 你是找到了x轴的值 在往上那个y是多少呢?x,y最后加起来输出的数又是谁呢? 二分直接找坐标不是很好找到具体值

补充内容 (2018-7-12 05:31):
感觉自己没说清楚 就是二分 没办法同时处理x y 你描述的思路其实是DFS,从每个象限转。。
. 留学申请论坛-一亩三分地
补充内容 (2018-7-12 05:54):-google 1point3acres
你要么就写俩二分? 但一旦分开处理就比较讨厌 就不知道在哪个象限了
要么写一个二分的话 你mid值怎么取嘞? 是按x值取还是按y值取嘞?. 一亩-三分-地,独家发布
还有就是用二分法求值的逼近?这种方法我掌握的不好 不知道能不能用在这
回复

使用道具 举报

我的人缘1
xiaozhu 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (77)
 
 
4% (4)  踩
请问lz,第二题是不是要先转换成后缀,然后建树?
回复

使用道具 举报

我的人缘0
 楼主| 浅漾 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (32)
 
 
0% (0)  踩
xiaozhu 发表于 2018-7-12 05:37
请问lz,第二题是不是要先转换成后缀,然后建树?

额 string已经是中序遍历了 主要是找根 要把符号放在数字上面。。。转换成后缀是什么意思嘞?

回复

使用道具 举报

我的人缘0
tinylic 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (47)
 
 
0% (0)  踩
浅漾 发表于 2018-7-12 05:29. 围观我们@1point 3 acres
然后呢 你是找到了x轴的值 在往上那个y是多少呢?x,y最后加起来输出的数又是谁呢? 二分直接找坐标不是很 ...
.1point3acres网
suixinsuoyu说的是对的,这题就是模拟quad tree的查找。楼主可以参考一下蠡口explore里的quad tree章节
https://leetcode.com/explore/learn/card/quad-tree/

评分

参与人数 1大米 +5 收起 理由
marthew777 + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| 浅漾 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (32)
 
 
0% (0)  踩
suixinsuoyu 发表于 2018-7-12 06:09
**** 本内容被作者隐藏 ****

时间复杂度常数级,每次棋盘横纵坐标各砍一半。

你是对的 确实可以二分 厉害。。
回复

使用道具 举报

我的人缘0
 楼主| 浅漾 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (32)
 
 
0% (0)  踩
suixinsuoyu 发表于 2018-7-12 06:09
**** 本内容被作者隐藏 ****

时间复杂度常数级,每次棋盘横纵坐标各砍一半。
. 1point 3acres 论坛
恩 我看到他po的代码了 确实是对的 感谢你们
回复

使用道具 举报

我的人缘0
xsgs111 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
第一题就二分就行。大概思路是这样的:给定的x,y看是比当前矩阵边长的一半大还是小,可以知道这个是在0123中间的哪块。然后递归进行,传递下新的边长跟变换以后的坐标,以及base_sum就行。
.本文原创自1point3acres论坛
拿题主的例子:比如说我们现在要找(2,1)(左上角为0,0,找到8)那就是1< 4/2 && 2>= 4/2. 所以可以判断2,1在2(右上角),他等价于右上角方格内的(0,1)。

对比右上角左下角2*2可知左下角矩阵加上一个数就是右上角,这个数就是base_sum=((边长/2)^2) * (0,1,2,3 base on loc) + base_sum.

然后就可以递归了,传进新的坐标,新的边长,base_sum.直到边长==2时停止,枚举出最后一次是0123中的哪一个,返回和base_sum的和就是答案。

因为限定了2^16所以是常数复杂的,如果不限定则是log边长

2,3,4 楼主都讲的很清楚了就不提了

5是 lc857
回复

使用道具 举报

我的人缘0
StevenXie 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (11)
 
 
0% (0)  踩
tinylic 发表于 2018-7-12 07:23
suixinsuoyu说的是对的,这题就是模拟quad tree的查找。楼主可以参考一下蠡口explore里的quad tree章节
...

怎么看不到这个链接?
回复

使用道具 举报

我的人缘0
gilgamesh999 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  72% (8)
 
 
27% (3)  踩
浅漾 发表于 2018-7-12 05:44
额 string已经是中序遍历了 主要是找根 要把符号放在数字上面。。。转换成后缀是什么意思嘞?
. 留学申请论坛-一亩三分地
所以这题是从后往前找+/- 作为根, 然后分割多项式成左右子树对吧. 如果前面有1X2X3X4X5X6X7X9+8楼主是怎么处理的
回复

使用道具 举报

我的人缘0
redpandaovo 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (42)
 
 
4% (2)  踩
第一题感觉有点像变形的Hilbert Curve?. more info on 1point3acres

第二题数组里存的符号的意思是?如果+在-前面就是+是根的意思么

第四题有点像利口叁啾啾

LZ很厉害啊~ 祝LZ顺利~
回复

使用道具 举报

我的人缘1
xiaozhu 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (77)
 
 
4% (4)  踩
浅漾 发表于 2018-7-12 05:44
.本文原创自1point3acres论坛额 string已经是中序遍历了 主要是找根 要把符号放在数字上面。。。转换成后缀是什么意思嘞?

那怎么确定跟是哪个符号呢  还有怎么确定乘除优先于加减啊
回复

使用道具 举报

我的人缘0
marthew777 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (55)
 
 
6% (4)  踩
tinylic 发表于 2018-7-12 07:23
suixinsuoyu说的是对的,这题就是模拟quad tree的查找。楼主可以参考一下蠡口explore里的quad tree章节
...

大神你真厉害哈~
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-7-18 16:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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