开ai电面题目

等了挺长时间的，似乎他们没有多的availability。好容易安排上了，结果对方还来晚了5分钟。是个老印，博士，做ml infra的。上来就是题目，没有太多寒暄。

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

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

感觉很难，类似traveling salesman的问题，但不相同：可以多次访问结点。不太确定在2d grid上是否有高效方法。请大家讨论。
请大家赠米，感谢！

补充内容 (2023-06-04 02:25 +08:00):

求米：之后能够参与更多面试题目的讨论和交流

匿名用户 发表于 2023-5-31 13:56
我的意思是按你给的条件，没有其他额外限制条件的话，顶多就是从求Hamiltonian path变成类似于求Hamilton ...

是，不知道出这题意义在哪里，明显是个NPC的问题

2维矩阵如果不存在奇数环，那么可能是有欧拉路径的，如果有奇数环可能就只有state compression DP能试试了。
感觉现在面试题目普遍都在往Hard+靠拢，以后刷leetcode都不管用了，得刷poj，洛谷之类

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

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

多谢楼主！ 想问"."和"*"的区别是啥？就是"." 不需要走到，但是可以通过是吗？

还有，楼主， “输出(xi, yi)坐标数组” 是指输出出发起始位置的坐标吗？

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

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

路过路过，看看各位大佬

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

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

匿名用户 发表于 2023-5-30 09:08
只有一个大概思路，数据量一大（*的数量超过20）就不管用了：
1）O(m*n) 建图, BFS或者DFS, *的坐标当node ...

嗯，这种方法只能做到比较少的*的数目。但题目给的过程中是说*可以到1000个。这种有更高效的办法吗？

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

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

匿名用户 发表于 2023-5-31 02:57
V = 1000只看复杂度限制差不多是V^2的样子，求个最小生成树（Prim O((V+E)log(V)) /Kruskal O(ElogE))刚 ...

嗯，由MST到TSP似乎并没有显著降低难度吧？而且，这里并不是要近似解，而要求是精确解。