狗家SWE上门

距离面试已经过去一阵了，粗略发一下面筋：

1， 实现Bash命令的展开。
例如输入 "a{1, 2}{3, 4}"  输出 "a13a14a23a24"

2， 挖井取水， 已知有n个house [0, ..., n-1

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

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

求新的值覆盖旧值

给一个compressor 举例 3 8 0 2 1 5 --> 8885  ，实现hasNext()和next()

Lz为啥面Bash?这个要准备吗？还是楼主面的level比较高？

------- 可爱的分割线 求米 ----------
第2题，应该每个house都要挖井的，所以先直接加上sum of cost, 然后再考虑铺水管的费用。
所以这个题应该就是求最小生成树。用Kruskal's algorithm可以求最小生成树。视频解释见
Kruskal's algorithm for minimum spanning tree

文章解释见https://www.geeksforgeeks.org/kr ... ithm-greedy-algo-2/

简单来说就是把cost_pipe里的所有item用1D simulation的方式先排序。然后从最短的那个边开始，把顶点放在一个hashset里，total_cost += cost_pipe_sorted每加一条边之前, 检查是不是两个顶点都已经在hashset里存在了，如果是，说明如果加上这条边会形成环，那就跳过这个，去找下一个边最小的。

总共有v个顶点的话，一共加v-1条边就够了，可以停止了。rationale是一个connected graph有且仅有一个minimum spanning tree.
如果这个给出的每km建设pipe的费用，就单价乘以距离，然后按最小生成树的方式做就行。如果说得不对，烦请指正。我的疑惑是，如果这个题的设定是有向连通图，MST的求法和无向图一样吗？
附上第二题代码

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

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

只给了一个undirected的test case, 希望大家也贡献一点test case哇
最后，疯狂求米！

补充内容 (2019-9-26 09:48):
对不起，我发现我理解错题意了。 应该是每个house要么挖井，要么建pipe。这个好难啊

如果A B之间直线经过了障碍P, 那么最短距离是什么呢？

lz第二题能举个例子么？不是很明白

wtcupup 发表于 2019/09/17 13:49:58
如果A B之间直线经过了障碍P, 那么最短距离是什么呢？

A B可以是目标点，也可以是多边形的顶点，最短距离是两个目标点时间绕过障碍的最短路径

Betterman 发表于 2019/09/18 00:33:59
------- 可爱的分割线 求米 ----------
第2题，应该每个house都要挖井的，所以先直接加上sum of cost, 然后再考虑铺水管的费用。
所以这个题应该就是求最小生成树。...

是无向图，字数字数

poorkenny 发表于 2019-9-18 06:11
是无向图，字数字数

嗯，看wiki里说MST都说的是无向图。
对了，字数怎么了？（我是新人）
另外，关于第3题的回答我没看懂T-T, 可以再多说两句吗，谢谢！

Betterman 发表于 2019-9-18 00:33
------- 可爱的分割线 求米 ----------
第2题，应该每个house都要挖井的，所以先直接加上sum of cost, 然 ...

从题目上看，貌似如果每个房间都有丼，也就是都有水，应该就不用pipe了

ChrisGates23 发表于 2019-9-19 00:08
从题目上看，貌似如果每个房间都有丼，也就是都有水，应该就不用pipe了

你太皮了，决定录取你

Betterman 发表于 2019-9-19 00:11
你太皮了，决定录取你

为啥，难道在下理解错了。lz能否帮忙澄清一下