📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4481| 回复: 22
跳转到指定楼层
上一主题 下一主题
收起左侧

[高频题] 求助一个 G 家高频题的最优解

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 14417335 于 2019-5-2 13:15 编辑

OP 上个月面 G 的 L5 被低球了一个 L4, 主要原因是一轮算法没有写出最优解? 题是这样的:
您好!
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies


地里大神们能不能分享一下对这题的看法? 谢谢

评分

参与人数 1大米 +20 收起 理由
14417335 + 20

查看全部评分


上一篇:请问谁有每个tag必刷题列表?
下一篇:让刷题幸福感提高的一百个心得

本帖被以下淘专辑推荐:

推荐
raistlins 2019-5-3 10:41:24 | 只看该作者
全局:
这是一道LEETCODE原题,最优解应该是构建一个带权值的graph,然后当做旅行商问题,DP求解

补充内容 (2019-5-3 10:43):
943. Find the Shortest Superstring
回复

使用道具 举报

推荐
cai_lw 2019-5-3 11:06:36 | 只看该作者
全局:
以词为点,字符串为边,等价于任意图的最长路问题,是NP-complete的,不存在很快的解法,brute force问题不大
可以以“已经用过哪些边+现在位于哪个点”为状态做DP,复杂度是O(N^2*2^N),比搜索的O(N!)好一些但好得有限
回复

使用道具 举报

推荐
 楼主| lokilokiloki 2019-5-3 10:28:55 | 只看该作者
全局:
Vidda_小毛 发表于 2019-5-3 08:53
楼主~~是最后一个词还是有overlapping 的几个词都行呀?~~

只有最后一个词
回复

使用道具 举报

🔗
imiochen24 2019-5-3 02:09:02 | 只看该作者
全局:
brute force solution 不是建所有字的组合然后一个个查长度?
回复

使用道具 举报

🔗
14417335 2019-5-3 02:17:50 | 只看该作者
全局:
general graph 求最长path?
回复

使用道具 举报

🔗
 楼主| lokilokiloki 2019-5-3 02:22:27 | 只看该作者
全局:
backtrack 建所有组合是我能想到的最优解了, 因为要算最终词的长度而不是词数而且要求返回最终的词, 我就没往 DP 方向去想. 能否分享你的高见?
回复

使用道具 举报

🔗
 楼主| lokilokiloki 2019-5-3 02:24:51 | 只看该作者
全局:
14417335 发表于 2019-5-3 02:17
general graph 求最长path?

不太一样, 因为这个会有 loop, "abc" "abbc", "abbbc", "cba", "cbba", "cbbba" 就不好搞
回复

使用道具 举报

🔗
14417335 2019-5-3 02:26:38 | 只看该作者
全局:
lokilokiloki 发表于 2019-5-2 13:24
不太一样, 因为这个会有 loop, "abc" "abbc", "abbbc", "cba", "cbba", "cbbba" 就不好搞

是有loop,所以我说general graph。否则是DAG啊
回复

使用道具 举报

🔗
tinlittle 2019-5-3 02:37:51 | 只看该作者
全局:
无环有向图的最长路径问题有线性解。关键是这图是不是有环。面试官有提到输入的限制吗?比如这样的输入是否允许:"katie loves simon", "simon loves tracy", "tracy loves katie"。

补充内容 (2019-5-2 11:40):
问之前没刷新,原来不是DAG,这题考的比较奇怪,应该是NP hard。
回复

使用道具 举报

全局:
感觉分两种情况: 1.不带环的话,其实就是n-ary tree, 然后bottom up返回最长路径,中间过程中记录路径,应该是O(n)? n是node个数。2. 环的情况单独考虑,找最大环。最后两者取最大的。
回复

使用道具 举报

🔗
a87009751 2019-5-3 05:57:27 | 只看该作者
全局:
DFS没错,但要带一个memory。比如你算过了以String A为起始的最长结果,就存下来,下次算String B的时候,如果中间遇到了String A,直接加上就好了不用继续遍历。
回复

使用道具 举报

🔗
wisdompeak2 2019-5-3 08:15:39 | 只看该作者
全局:
既然题目给出的是list,那么我默认这些词是有顺序的。
如果是这样的话,那显然就是DP啊,而且就是个medium而已。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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