Pinterest 2018.10.25 OA详细描述 求加米

Pinterest给了四小时，结果只有一个题。我做了两小时就交了，事后在想是不是还有更优解法。我当时是写了一个bfs。

给定一个由字母组成的矩阵，从任意一格出发，找出由相邻字母组成的最长路径。
相邻字母的定义是当前格子字母的前后字母，例如B的相邻字母就是A和C。
在矩阵中移动时，可以向上下左右四个方向移动。
例如：

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

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

ong>
对不起我把例子写错了
ABEF
ECDD
ADXC
BCXE
应该是这样
然后最长路径是ABCDCB

补充内容 (2018-10-28 12:00):
请问有没有办法编辑原帖，我想给内容加一个101分的阅读限制。

收藏2 淘帖0

好苗1 杂草0

评分

参与人数 13	大米 +52	收起 理由
蓝豚子	+ 5	给你点个赞！
spaCycraft	+ 5	很有用的信息！
zhangy405	+ 3	很有用的信息！
MatchaCake	+ 5	给你点个赞！
AngelSeven	+ 3	很有用的信息！

查看全部评分

上一篇：关于dropbox电面后的下一步
下一篇：推理哦 OA 近期题型总结

相关帖子

• Amazon AS Phone-screen挂
• figma 全套挂
• RADAI挂经
• 72点经典套策略面试
• tt usds sde一轮挂经
• tiktok三面 sd轮面筋
• grammarly sd轮
• 简街新鲜电面
• 狗家店面挂
• 微末刚刚技术店面
• Nuro SWE Coding Interview
• Pinterest VO面完没消息
• Nvidia intern 面经
• 请问有人高盛面试两轮coder pad 吗？
• TT 二面
• Hackerrank MLE OA
• plaud面试难搞啊，打了个电话就没消息了烦死了
• Equinix AI Platform Engineer 面经
• 气床 电面
• plaid 全套挂

论坛匿名用户 发表于 2018-10-28 11:38
我在BFS的路径记录了坐标，已经访问过的坐标不再访问。最后再从坐标变成答案。
如果你是说不同路径经过 ...

试试这个：
ABC
BCD

最长应该是ABCDCB。

其实想想用BFS也可以，但是每一个在QUEUE里的元素要track自己这条线访问过的点。一般的BFS是用一个global的vistied矩阵，空间复杂度是O(n^2），这题要每一条线都要有自己的visited矩阵，空间复杂度会大很多，时间复杂度和DFS一样，所以用DFS更好。

tudoucc86 发表于 2018-10-28 10:31
这道题如果真的允许ABCBA这样的话，用BFS 不行。BFS 如何保证你不会陷入无限循环 ？你只能记录曾经到过的点 ...

我在BFS的路径记录了坐标，已经访问过的坐标不再访问。最后再从坐标变成答案。
如果你是说不同路径经过同一个点的话，我不明白为什么这是不允许的。
就好像例子里ABCCBA是一条路径，ABCDE是另一条路径，它们起始三个点是一样的。

补充内容 (2018-10-28 11:50):
不好意思我把例子写错了，请看原帖的补充。C-C是不允许的。

Arjen 发表于 2018-10-28 13:24
想问一下大佬，我也想到了DFS，但只能到在每个点都进行一次DFS的方法。这样显然有很多重复搜索，大佬有什 ...

没想到什么量级上可以提高时间复杂度的算法，虽然有办法可以剪枝以减少运算量。

这道题如果真的允许ABCBA这样的话，用BFS 不行。BFS 如何保证你不会陷入无限循环 ？你只能记录曾经到过的点并保证以后不再到这些点，可是，这种情况下你可能找不到最长的那条路径，因为最长的那条路径可能用到已经到过的点。比如，一条最长线可能是ABCCBABCD，而可能这个D已经早先被另外一ABCD用过了。用DFS不会有这个问题。

谢谢楼主！

请问一下楼主！什么叫“由相邻字母组成的最长路径”？ABCCBA中，C和C为啥是相邻字母啊？而且这题ABCDEF在这题里也是符合要求的吧～

Arjen 发表于 2018-10-28 11:37
请问一下楼主！什么叫“由相邻字母组成的最长路径”？ABCCBA中，C和C为啥是相邻字母啊？而且这题ABCDEF在这 ...

我把例子写错了，不好意思，你看补充。

论坛匿名用户 发表于 2018-10-28 11:49
我把例子写错了，不好意思，你看补充。

已加米！谢谢

tudoucc86 发表于 2018-10-28 12:00
试试这个：
ABC
BCD

想问一下大佬，我也想到了DFS，但只能到在每个点都进行一次DFS的方法。这样显然有很多重复搜索，大佬有什么更好的方法吗～