狗家面试挂经 求安慰米

给大家po个热气腾腾的狗家onsite

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

没有考到DP。。。刷了好久背包问题都没考到 不开心。。。
第一题上来就知道自己挂了。。。全天都沉浸在我的爱情还没开始就已经结束的悲痛中。。。

来年再战啦！祝大家面试顺利！




补充内容 (2018-7-12 05:07):
sorry 我第一题打错了 矩阵长这样

5   7    9  10
4   6    8   11
1   2   13  14
0   3   12  15

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

第一题感觉有点像变形的Hilbert Curve？

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

第四题有点像利口叁啾啾

LZ很厉害啊~ 祝LZ顺利~

浅漾 发表于 2018-7-12 05:44
额 string已经是中序遍历了 主要是找根 要把符号放在数字上面。。。转换成后缀是什么意思嘞？

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

没太看懂第一题 拿4X4的举例子 如果左下是
1   2
0   3

为啥左上是 ？
6   7
4   5

wtcupup 发表于 2018-7-12 03:08
没太看懂第一题 拿4X4的举例子 如果左下是
1   2
0   3

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

lz，第一题右下角的部分是
13，14
12，15
吧？如果不是typo的话能解释一下为啥吗？

我怎么感觉第一题应该是
5   6    9   10
4   7    8   11
1   2   13  14
0   3   12  15


（3,3） = 15 （3，0） = 12

anoyanoy 发表于 2018-7-12 04:37
我怎么感觉第一题应该是
5   6    9   10
4   7    8   11

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

第一题，我觉得类似二分查找，每次4分一下矩阵可能可行。
我们可以把每一步看成类似直角坐标系的四象限。找到当前坐标在当前层哪个象限内。
因为这种填表的顺序，总可以保证四个象限内的数 0 < 1 < 2 < 3
找到以后确定这个象限的最小值与最大值。

稍微demo一下， 比如2 ^ 16 * 2 ^ 16。切完以后的数字是0 到 2 ^ 32 - 1， 四个象限可以等分。
如果坐标落在第二象限，右上区域。start number 应该为 （2  ^ 32） / 4 * 2. end number 为 （2  ^ 32） / 4 * 3 - 1.
然后利用新的start end，继续切分当前象限。到收敛为止。

suixinsuoyu 发表于 2018-7-12 05:11
第一题，我觉得类似二分查找，每次4分一下矩阵可能可行。
我们可以把每一步看成类似直角坐标系的四象限。 ...

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

补充内容 (2018-7-12 05:31):
感觉自己没说清楚 就是二分 没办法同时处理x y 你描述的思路其实是DFS，从每个象限转。。

补充内容 (2018-7-12 05:54):
你要么就写俩二分？ 但一旦分开处理就比较讨厌 就不知道在哪个象限了
要么写一个二分的话 你mid值怎么取嘞？ 是按x值取还是按y值取嘞？
还有就是用二分法求值的逼近？这种方法我掌握的不好 不知道能不能用在这

请问lz，第二题是不是要先转换成后缀，然后建树？

xiaozhu 发表于 2018-7-12 05:37
请问lz，第二题是不是要先转换成后缀，然后建树？

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