脸熟电面+昂赛

店面（圣诞节前）：

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

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

有个地方算法没有解释清楚。一直以为挂了。一月中搜email 发现人家两周前就告诉我过了。赶快联系hr 定昂赛。

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

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

现在还没有消息。

那个图的题，是这样的解法么：
public class ShortestCycle {  
    private int minlen = Integer.MAX_VALUE;  
    public int findShortestCycle(List<List<Integer>> adj, int src) {  
        List<Integer> path = new ArrayList<>();  
        path.add(src);  
        List<Integer> neighbors = adj.get(src);  
        for (int nb : neighbors) {  
            dfsHelper(adj, path, src, nb);  
        }  
        return minlen;  
    }  
      
    private void dfsHelper(List<List<Integer>> adj, List<Integer> path, int src, int node) {  
        if (node == src) {  
            minlen = Math.min(minlen, path.size());  
        } else {  
            path.add(node);  
            List<Integer> neighbors = adj.get(node);  
            for (int nb : neighbors) {  
                dfsHelper(adj, path, src, nb);  
            }  
            path.remove(path.size() - 1);  
        }  
    }  
}  

xelliotpenguin 发表于 2019-2-7 10:04
第二轮的那个环的题的一些想法

一个环如果包括 source, 那一定有两条相邻的paths 1) source -> x 2) x-> ...

但是有可能是这种情况。比如A到g 有两条path。 但是A 不在那个环上。我都考虑了这种情况。加了一个判断。如果两条path 提前合并。则不是。还是fail 了。 可能还是DFS 直观一点。

    /c-d
A-b     \ g
    \e-f/

面试的时候。还有一个小细节。就是面试官是写c 的。我用的java。 他问我空间复杂度。我的方法是是把对象直接传进去。他对我的的空间复杂度的答案不满意。问我我那个是 pass value 还是 pass reference。我说java 对象pass 是reference。好像他有怀疑。

还有就是他说我把值打印出来就可以。明白意思就行。然后有一些方法我就println了， 没返回。我估计这也会让最后的代码很难看。最后的comment 就是我的 code 不clean。 不optimize。哎。

第二轮的那个环的题的一些想法

一个环如果包括 source, 那一定有两条相邻的paths 1) source -> x 2) x-> source

x 是紧邻 source 的neighbor点.

这个题只要求出所有从source开始的最短距离distance(source, x) 然后在加上 x->source(direct look up) 距离就可以求出最小环.

如果是edge有weight(非negative), 要用Dijkstra, 没有weight 就是bfs

请问lz几年经验？

LZ工作多久啦？

美国6年+

dlwlrma 发表于 2019-2-5 15:55
请问lz几年经验？

大于5年。

楼主，图找一个节点最小环该怎么做呢？

jhdyss 发表于 2019-2-5 22:32
楼主，图找一个节点最小环该怎么做呢？

我用的是BFS。 从那个节点 BFS 遍历图，同时记下每一个节点的父亲节点。如果遇到某个被visit 过的几点。则。可能找到一个 环。两条path 合起来。但是有一个情况就是 如果path 提前合并了。说明节点不在环上。要继续找。

同125昂赛 不过是DS 等消息 好慢啊

onlyljy2 发表于 2019-2-6 03:12
同125昂赛 不过是DS 等消息 好慢啊

刚发email 问了。HR 今天PTO。 明天打电话。估计挂了。哎。

图那道题DFS的同时记录当前节点到给定节点的路径长度，如果遇到给定节点并且路径更短就更新，是不是就可以了？