11家公司面试集合大放送

zedyeung 发表于 2018/12/22 02:30:36
给一个矩阵有0和1，1是墙，0是路。给一个把一面墙打破的机会（把一个1变成0），求左上角到右下角最近的路程。
这个题是不是左上 右下 开始bfs 记录最短距离 然后遍历1 加和两边

我的做法好像是在bfs的时候，一个位置记录两个值，使用打破技能的值和没使用的值，然后你在往队列里加东西的时候，面对1的墙可以加入没用过技能的那个值的路径长度+1

sdfuioy 发表于 2018-12-22 02:40
我的做法好像是在bfs的时候，一个位置记录两个值，使用打破技能的值和没使用的值，然后你在往队列里加东 ...

我想的是从两个角bfs 遇到墙就终止  你的是从一个角到另一个角吗 但是打破技能只能使用一次啊 如果路径上连续多个墙你怎么处理 这个题好像比预想的复杂  有原题吗

感谢楼主分享，楼主的效率挺高的，向你学习！祝好运！

saogen 发表于 2018/12/22 04:21:16
感谢楼主分享，楼主的效率挺高的，向你学习！祝好运！

谢谢恩，目前在纠结offer了。。

可否问下LZ snowflake SQL那道题最后的结果 - a1属于(1, 3)U [5, +Inf]为何不需要考虑 a2, a3。

DavidLi210 发表于 2018/12/29 04:29:16
可否问下LZ snowflake SQL那道题最后的结果 - a1属于(1, 3)U [5, +Inf]为何不需要考虑 a2, a3。

因为a2 a3没有出现在所有or的分支中

加米啦，请问lz snowflake第一题
1.     给一个自然数序列，一次求每个位置上已有数字组成的不相交的区间
1, 3 , 7,  2,  6
0: [1,1]
3: [1,1], [3,3]
7: [1,1], [3, 3], [7,7]
2: [1,3], [7,7]
6: [1,3], [6,6], [7,7]
例子有点不太懂呢，题目就是用当前位置已有数字组成的不相交的区间，所以1，3，7的例子都还明白，因为【1，1】，【3，3】，【7，7】都不算相交，但是到了2的时候这个【1，3】【7，7】是怎么出来的呢？是在前一步的基础上加了一个【2，2】，因为【1，1】【2，2】【3，3】是连续的就把他们merge起来了？如果是这样的话，最后一步为什么没有merge【6，6】和【7，7】呢？
也可能是我理解题目有点偏差，不知道lz是怎么解决的这个问题呢？

wulaoshi250 发表于 2019/01/10 05:25:56
加米啦，请问lz snowflake第一题
1.     给一个自然数序列，一次求每个位置上已有数字组成的不相交的区间
1, 3 , 7,  2,  6
0: [1,1]
3: [1,1], ...

啊，谢谢，是我写错了，6.7应该合起来

sdfuioy 发表于 2019/01/10 09:35:41


啊，谢谢，是我写错了，6.7应该合起来

所以做法就是先假定这个数这个区间是独立的，然后merge interval看看可以合并么？

再麻烦问一下LZ，snowflake onsite sql那道题是个怎样的思路呢？