r******n
发帖数: 170 | 1 sorry,我自己有点混淆了。
有向图，必须有edge的概念，所以只能用topological sort判断，对吧？
判断tree还是graph,随便用dfs/bfs，看是否一个node会visit多次就知道了。 |
|
z*********n
发帖数: 1451 | 2 lz标题应该叫最少点，不是最小点吧。。
读了3遍lz算法才猜出来题目是啥。是说最少需要几个起点，就能dfs遍历一个有向图的
所有点，是这意思吗？
如果是这个意思，那应该确实跟SCC没啥关系，反例很简单。一个图:A->B。这里有俩
SCC，但一个root A就能遍历全图。
如果我没理解错lz意思，那下面这么做应该就行了，不需要什么union find，写起来多
麻烦。
1.DFS整个图，按每个点的完成顺序存下每个点。类似拓扑排序
2.按记录顺序的逆序开始DFS整个图，每一个新的起点都是一个root。 |
|
m***n
发帖数: 2154 | 3 一个有向图，N个节点。 每个节点都和其他N-1个节点中的若干个有一定的单向连通性
， 要计算从 A到B的最大可能流量，要怎么算？
谢谢。貌似max-flow 不能解决这个问题。 |
|
m***n
发帖数: 2154 | 4 平常解决max-flow 的Edmonds–Karp 算法好像不能用啊。能详细说说这种有向图的
data flow 问题要用哪个算法？谢谢 |
|
|
t**********s
发帖数: 930 | 6 问题是这样的：
Describe a mathematical model for the following scheduling problem.
Given tasks T1, T2,…, Tn, which require times t1, t2,…,tn to complete, and
a set of constraints, each of form “Ti must be completed prior to the
start of Tj,” find the minimum time necessary to complete all tasks.
我觉得这是个有向图问题。任务是图的顶点，花费时间是边的权，constraints 就是边
的方向。再往下，就找不到线索了。谁能提示我一下？
谢谢 |
|
l*****a
发帖数: 135 | 7 请教一个算法，请看附图，如果有一个有向图，每个点代表一个任务，任务有先后关系。
我要产生一个集合K, K中的每个元素代表了一个所有任务的状态。
（比如abcd代表“abcd这四个任务完成，其他的没完成”这一状态，并且abcd是符合图
中的先后关系的。又比如没有状态af,因为根据图中的关系，不可有“af这两个任务完
成，而其他的任务没完成”这一状态。）
请问最好的算法是什么？有python的package吗？
我能想到的是写个constraint programming(CP) model，让CP solver去解决，是不是
太傻了？ |
|
c*******t
发帖数: 1095 | 8 a Hamiltonian path (or traceable path) is a path in an undirected graph
which visits each vertex exactly once.
这跟我想找的相差太远了吧，随便一个cycle就行了，不需要经过每一个点（也不一定有这样的cycle），而且我的是有向图，hamiltonian的是无向图，我就是想找所有的cycle而已 |
|
p***o
发帖数: 1252 | 9 这条路不可能走通，你想想一个图里有多少个cycle，绝对不是多项式时间能枚举完的。
定有这样的cycle），而且我的是有向图，hamiltonian的是无向图，我就是想找所有的
cycle而已 |
|
R********0
发帖数: 780 | 10 这里有学运筹或图论的吗？谁知道怎么穷举有向图中两点间的所有简单路？谢谢！ |
|
|
b****d
发帖数: 1311 | 12
我认为可用环上的某种关联矩阵做乘法算出。设该有向图的点为1，2，。。。，n。定义交换环 $R = $。如果点i 到点j 有有向边，则关联矩阵 A 第(i,j)项为 $y_{ij}$，否则为 0。定义对角矩阵 $D=diag(x_1, x_2, ..., x_n)$。在此设定下，从p 到q 间的所有简单路可用矩阵 $B = D(AD) + D(AD)^2 + D(AD)^3 + ... + D(AD)^{n-1}$ 的第 (p,q) 项表示出来。 |
|
g****t
发帖数: 31659 | 13 【 以下文字转载自 EE 讨论区 】
发信人: catccaatt (堕落是魔鬼), 信区: EE
标 题: 求助如何检测有向图里面所有的回路
发信站: BBS 未名空间站 (Sat Jan 16 20:15:37 2010, 美东)
就是cycle detection
最好有现成的source能直接用的，没有的话请告诉我有没有稍微快一点的方法，我直接
用C语言 深度搜索 尝试了只有200个点的数据跑了一晚上都没出来，是在没辙了。有其
他方法请告知，例子如图：
谢谢了 |
|
c*******t
发帖数: 1095 | 14 a Hamiltonian path (or traceable path) is a path in an undirected graph
which visits each vertex exactly once.
这跟我想找的相差太远了吧，随便一种cycle就行了，不需要经过每一个点（也不一定
有这样的cycle），而且我的是有向图，hamiltonian的是无向图。我只是想找出所有的 |
|
d**k
发帖数: 114 | 15 我们知道minimum feedback vertex set problem是在一个有向图中去掉最少的点
使得剩下的图是无环有向图。这个问题是NP的，但是有现成的approximation algorithm
。
我现在的问题是：给出两个有向图，这两个图中的点一一对应。现在要去掉最少的点，
使得这两个图都变成无环有向图。
请问有没有对这样的问题的定义和现成的算法？ |
|
g**********y
发帖数: 14569 | 16 As a newbie on a particular internet discussion board, you notice a distinct
trend among its veteran members; everyone seems to be either unfailingly
honest or compulsively deceptive. You decide to try to identify the members
of the two groups, starting with the assumption that every senior member
either never lies or never tells the truth. You compile as much data as
possible, asking each person for a list of which people are liars. Since the
people you are asking have been around on the board ... 阅读全帖 |
|
c******w
发帖数: 1108 | 17 定义1000个node的有向图，每个node代表三位数字。每个node有10条outgoing edge，
对应0-9。每个node加上它的一条outgoing edge代表一组四位密码。
题目的最优解就是能遍历该有向图所有*edge*的最短的path。实际上就是要解这个图上的
chinese postman problem。
https://simple.m.wikipedia.org/wiki/Chinese_postman_problem
因为该有向图里每个node的in-degree和out-degree都等于10，其最优解为Eulerian
circuit ：visits every edge exactly once。可以在O（|E|）内找到。 |
|
h*******y
发帖数: 1563 | 18 假设现在有一个有权的强连通有向图(一个network), 取其中某一顶点作为起点构造一个包
含其它顶点的无环的有向图（比如以此点为起点到其它点的shortest path tree). 现在我
需要向这个无环有向子图里加入新的边（即新的边包含在原来的图中， 但不在这个无
环有向子图中），但是要保证加入这个边之后还是一个无环的有向图。如果加入之后会
形成环，则我就不能加入这条新边。
请问有什么快速的算法可以判断加入新边之后是否会在无环有向子图中形成环路？（我
不必知道如果有新的环，那么这个环具体是什么样，包含什么边和顶点之类的，只需要
知道会不会形成环）
请各位高手指点，如果没有现成的算法，给几个reference 也行， 多谢了！！ |
|
h**k
发帖数: 3368 | 19 题目是要根据排好序的字符串重构特定的字母顺序。
比如输入是
{“abce”, “bbdf”, “cceg”}
我们得到下列关系
a -> b -> c -> e 第一个字符串
b -> d -> f 第二个
c -> e -> g 第三个
组合起来，就是一个有向图，而且对某些输入可能会出现下面这样的情况：
a-> b -> d
a-> c -> d
我们不知道 b 和 c的关系，不知道这种情况面试官要求如何输出。
对于构建好的地有向图，我们可以发现一些字母，它是只有outedge 没有inedge，输出
它们；然后生成从它们到其他字母的最大路径，按照这个最大路径依次输出其他字母。 |
|
b***m
发帖数: 5987 | 20
纯属个人意见：
航空公司订票系统的核心应该是航段信息管理，具体展开说，就是以许多城市为点构成
的有向图，以及连接这许多点的线段（也即航班）。有向图在数据库中可以表现为一条
条与日期有关的记录，而航班的核心应该是舱位管理（每个舱位对应不同的价位，分别
售出多少，根据季节选择超售的比例）。航空公司一般只允许预订未来365天的机票，
大概就是因为这样可以维护一个合理数量的“未来数据库”。在这样的抽象基础上，我
觉得后面的设计相对就清晰和容易一些了。
大家都可以说说自己的看法，我觉得设计题没有必然的正确答案，合理性、易理解性、
可扩展性应该是最重要的。 |
|
d*******h
发帖数: 5065 | 21 盈利模式：主要靠挂信用卡广告，挂链到priceline/hotwire etc的link赚commission
。也可以自己当机票代理，chinatown雇几个小妹接电话成本也不高。
服务类型：用户提交自己的地理位置信息和自己的email地址，程序自动收集低于3
cents per mile的机票信息，然后发邮件提醒用户去订机票。
这样说吧，如果cost per mile低于1.8 cent，你去坐飞机实际上是在挣钱，因为你坐
飞机的同时也累积了里程，这些里程是可以拿到fleamarket上面去卖的。一般低于
3cents/mile的都算不错的deal
除了积攒里程，通过这种超低价格机票旅行也是一种生活时尚，培养一下的话估计能培
养出一个用户群。
现在网上暂时没有类似的服务，用了我的idea的记得分我点股份哈
机票API:
http://stackoverflow.com/questions/4011123/is-there-an-api-for-
算法也不复杂：
1，收集所有3cents/mile的机票
2，把机票当成一个edge，形成一个带有时间标签的有向图
3，在有向图里面找出一... 阅读全帖 |
|
l**h
发帖数: 893 | 22 想到一个，可以把跳跃关系转换成有向图，一个节点最多可以到达两外两个(左和右),
就成了有向图中，找两点是不是有路径到达。
by
then |
|
r*******t
发帖数: 99 | 23 试解一下最后一题：
step 1: 构造一个有向图。
每一个preference是一个denpendency，可以用一个link来表示：如果A prefers to
play with B，则建立一个link from A to B。这样所有的players构成一个有向图，每
个节点最多一条向外指的边。
step 2：找出所有互不连接的子图。
如果两个节点所在的linked lists相交，则此二节点位于同一个子图，反之则位于两个
不同的子图
step 3: 分析每一个子图。
若某子图中存在not playing的节点，ignore该子图
identify子图i中的环，记环大小为Ni，若无环则记Ni=1。记子图i总节点数为Mi
step 4: 匹配目标人数。
上一步得到一组区间：[N1,M1], [N2,M2], ..., [Ni, Mi], ...
问题归化为从每个区间中取一个数或不取数，是否能得到一组数，其和为目标人数 |
|
M**a
发帖数: 25 | 24 我也觉得是 有向图找环， 比如 A N C 可以转换为 A 的y坐标大于C的y坐标， B NE
C 就是 B 的x和y坐标都大与C的x,y坐标， 然后在这一堆不等式里面找冲突的， 可
以转换成有向图里面是否有环的问题。 |
|
l*******1
发帖数: 20 | 25 借朋友id报点面经吧，才注意到注册个id还需要等待才能发帖。
前前后后从开始刷题到现在有五个月的时间了，总算是有dream company的offer了，这
段骑驴找马的日子终于快到尾声了，但愿后头赶紧都顺顺利利的吧。
背景：板上一直被黑的某公司三年多经验。
结果：G, F, A(果), A(麻)
简述：阵线比原本计划的长了太多。四年前找工作的形势和现在大不同了，当年复习了
一下下就拿了当时的dream company offer，公司内换组的bar又不高依然只是稍准备下
就好了，导致这次上来想的倒简单却计划完全被打乱。
从开始的简历不够好内推就被刷(T & U)和干脆石沉大海(有点多)，到project不会讲重
点被hr刷(狗肉, salesforce, N)，到手感没练好就上战场挂了(S, 气床, apple另一个
组), 再到behavior的失误(P & DATA)，中间还夹了次被同胞黑了的L。一度在很接近终
点却倒下时竟然有过绝望感，不过总算是抖擞再爬起来不断的调整。
感谢内推的大哥们，尤其感谢G和P家帮着提建议的华人大哥们，感谢这个版的各种面经
贴经验贴虽然我一直潜水。
因... 阅读全帖 |
|
发帖数: 1 | 26 有一个流传已久的说法，如果你随机点开维基百科任何一篇文章，点进文章中第一个链接，进入之后再点击该文章中第一个链接，持续点下去，你最终会到达同一个页面，那便是——「哲学」。
是不是很有万法归一的终极归宿感？一路上你可能会经过「数学」、「科学」、「知识」、「知觉」，它们都只是路边风景。当你翻山越岭到达终点，惟有哲学在此等候多时。
就像神话中的英雄都逃不过自己的宿命。实际上，这个说法是真的。截至2016年统计，它的准确度高达97%。九十七分天注定，三分靠打拼，我们可以容忍这三分的随机性。而正是这份不确定，当我们最近一次荡起双桨，伙伴们玩起成语接龙时，让我很想找到它的隐藏秘辛：到底接龙接在什么地方，才最容易折戟沉沙，抑或，香消玉殒？
经典版本
简单梳理一下规则。各言其志嘛，最开始随便选一个成语，第一个人想到什么，比如很有慈悲心的Ta说了自己的「恻隐之心」。第二个人在暮春歌咏的畅快中，从所有心字开头的成语里，接上「心向往之」。第三个人没有很多选择，挠挠头接「之乎者也」。到了「也」字算是玩死啦，第四个人已经无话可说。
恻隐之心 → 心向往之 → 之乎者也 → Game Over!
这里故意举了一个... 阅读全帖 |
|
x***g
发帖数: 52 | 27 谢谢啊，感觉好像是对的。
这句话不太理解，能否展开说说？
：然后把原来的有向图里可以被传递律推导出来的边删掉
有元素，然后把原来的有向图里可
65533;1之间的路径，每一条就代表你 |
|
z****e
发帖数: 54598 | 28 汉字虽然是一个孤立的object
但是汉字和词的关系其实是一个有向图
那这个复杂度就高很多了，关键这个object没有封装其行为
就是封装不彻底，不像java，像脚本，就是func和object都孤立滴存在
func还是1st class citizen，谓语动词都是1st class citizen func
而且3000个汉字已经比常用的法语词汇（2000＋）多了
等汉字组成常用的词汇，就更要远超常用的法语词汇了
而真正说话的时候，其实听的不是字
而是词，比如说汉语，hanyu，你听到的重音只有一个，只在'hanyu上
而不是'han'yu，也就是这个词的重音不会出现在后一个字上
那人耳朵的敏感度就没那么高，所以最后不得不去记忆整个词
而非具体的字，写起来还好，但是object分解下去也是一个个具体的types
但是问题是汉字并不是由简单的types组成的，设计时候也没有考虑基本的字母一样的
组成
所以导致不同汉字写出来不一样，互相之间也没啥必然联系
所以无法再细分下去，class细分下去都可以具体到int, char这些
, |
|
|
g*******y
发帖数: 1930 | 30 DFS肯定是可以的，DFS用来找back edge，一个back edge就一定是回路
BFS对于有向图貌似不行，BFS只能找到cross edge，但是cross edge不一定构成回路。
不过对于无向图的话，cross edge就是回路了。 |
|
w********p
发帖数: 948 | 31 DFS可以用back edge来判断是否有loop
BFS 稍微改点code, 对有向图，无向图也都可以 |
|
z*****k
发帖数: 57 | 32 给定一有向图G=(V,E)，G中每条边都有非负权值，且G中至少存在一条过所有节点的回
路(circle,环)。请问有没有好的算法求过所有节点的最小权回路？
注意当G接近完全图的时候，存在O(|V|！)条回路.枚举所有回路是不可能的。 |
|
w****l
发帖数: 88 | 33 来自主题: JobHunting版 - 贴点面试题 第4题： 是不是根据dependency建立一个有向图，然后求topological order就可以了？ |
|
y******5
发帖数: 43 | 34 看来我对题意理解有误。我以为一个人只能给他的债主写check，也就是说，在有向图
中我们只能减少
某个点的已有出度边。
如果e可以代替b向"b的而非e的"的债主还钱，感觉总是有解啊，这题目还要我们判断什
么？能说说你的
理解么？ |
|
r*******h
发帖数: 315 | 35 面试中被问到，如果需要根据边的信息创建一个有1千万个节点的有向图的邻接表供后
续程序使用，问如何在创建过程中有效存储（邻接矩阵肯定大于物理内存），以及创建
好了，用什么方式存储最有效？
直观的想当然是邻接表存入文件，但是问题是等到图越来越大，添加信息就很费时费力
了，不知道啊各位高人有什么建议？请教了。 |
|
f****r
发帖数: 30 | 36 知名大公司， 不说名字大家也知道了。 由于签了NDA, 不好说太多细节。 若是有兴趣
的话，可以私下交流。
上次onsite结果不能move on, 最近要第二次onsite。 上来发第一次onsite面经， 为
第二次onsite求祝福， 希望这次能有个好结果。
第一次onsite见了5个人。
1.
a. design problem. 问了很多design的细节，包括api, system design，
communication protocols等等. 第一个人的问题我有点措手不及，原以为都是
algorithm 和coding.
2.
a. 一个有向图的问题, coding
b. 经典 string 问题， coding
c. extended problem b for large number of severs, cpus.
lunch
3.
a. 又是一个string的问题， 类似permutaions.
b. extend a to a DP problem.
c. a lot of c++ questions。
4.
a. 把一个树转化成一个矩阵, coding... 阅读全帖 |
|
s********y
发帖数: 161 | 37 MS校园面试
删除一个数组中重复的元素
Reverse words in a sentence
Onsite面Bing，每人一小时
Onsite 1 小印
Design a web crawler, 说说DFS， BFS不同的应用。
Check if a binary tree is balanced
External sort, 4G内存，100G数据
Onsite 2跟经理边吃边聊，探讨得很愉快
问了我的research work, 可以应用到哪些applications。说说一个购物网站的
database怎么设计，shopping cart怎么设计。如果1个苹果卖10c，5个苹果卖45c, 10
个苹果卖80c, 怎么改进你的设计。如果买10个苹果和10个梨，还能获得更多的折扣（
即比单独买10个苹果20% off更多的折扣），怎么改进设计满足要求。你比较喜欢MS的
哪些产品，这些产品还可以怎么改进。如果让你设计一个产品，你想要做什么。回答
online IDE，然后问怎样解决reliability的问题。另外怎样保证各个用户都能得到足
够的资源来运行程序。回答round ro... 阅读全帖 |
|
m*******e
发帖数: 9 | 38 攒rp, 发面经, 猛烈求bless.
除了我自己的，还汇总了几个朋友的G面试，多数都是一个月以内的,少数3个月以内的
。有phone有
onsite,请某狼13打小报告的时候好好data mining.
1.给字符串求频率最高字符。字符串大咋办，多核咋办。
2.俩数组交集。有序或无序。
3.实现cache.
4.给字符串，里边是几个单词中间没空格，输出所有可能的句子。比如“好运气”，输
出好空格运气。
5.数据流统计最近一个小时流量。
6.写程序找最大convex多边形。
7.复制无loop的有向图。
8.给字符串找最短一段出现过abc。
9.给一段内存，怎么设计malloc和free.
10.设计密码产生器，不能是字典里单词。
11.矩阵有障碍物找路径。
12。给一堆区间找有没有交集。
13. 有序数组找给定sum.
14. 实现hashtable.
15. 猜数字的，找使得最坏情况下猜的数字和最小的策略。
16。一管子硬币AB都只能从两边取求A最大值那个。
17. a[10] 和 malloc出来的区别
18. BT 俩节点最低祖先。
19. 给出生证明，求俩人最近的相同祖先。
... 阅读全帖 |
|
b*******y
发帖数: 232 | 39 有向图，从原点(一个字母开始)找最长的path?
find
dictionary
". |
|
J*********n
发帖数: 370 | 40 我觉得可以直接计算每个节点的入度。由树的性质，如果入度为0的节点数为1并且其余
节点的入度为1, 则该图为树，否者，如果入度为0的节点的数目为0或者大于1，或者有
节点的入度大于1,则不是树
必要性（树－》上面的性质）很容易证明
充分性：如果入度为0的节点数为1并且其余节点的入度为1＝》树
Proof: 显然这个图入度的总和为n-1, n为节点数
因为图为有向图，每一边贡献一个入度，故(1)图中有n-1条边
并且我们可以证明(2).图中不含回路 (3). 从一个节点到另一个节点最多只存在一条路
由(1),(2),(3)可知该图是一棵树
复杂度为O(E)
is |
|
i******s
发帖数: 301 | 41 反正是要被拒了，就发发面经吧。
电面：
三哥： 1. 一个大数组，怎么找前k个最大数。
2. coding实现pow(x, y)，x是double类型，y是int, 所有情况都要考虑
3. 有向图如何检测是否有环
三姐： 1. 问了些C++，Java基本概念，什么是虚函数，在C++中怎么实现，谈谈知道
哪几种GC实现方式。
2. 一个字典，给你一个word找出所有anagram
基本都是老题，电面后当晚就给了onsite。
一周后onsite
亚裔： 1. 设计single list api，并用C++实现
2. 一个字典，给你一个word找出所有anagram (汗死。。。)
3. 100G的数据，如何找median
亚裔2: 1. N个整数数组，每个数组中选一个数，打印所有组合。
2. LCA, 没parent指针。最简单有效率做法，hashtable+DFS
三哥: 基本都是puzzle, 比如两根绳子测45分钟，6根笔摆4个三角，还有一些，纯... 阅读全帖 |
|
r******n
发帖数: 170 | 42 有可以简单coding出来的实现吗？
觉得topological sortting之类的方法，可以说说，似乎不好code。但是面试官似乎要
code。 |
|
|
|
|
i******s
发帖数: 301 | 46 不一定哦，看我ebay search电面，三哥想搞你就会问。 |
|
i******s
发帖数: 301 | 47 对，关键在于图是怎样表示，是用矩阵还是邻接表，当时我就用的wiki的第一个算法，
因为之前写过。如果被问到，你先要搞清楚图怎么表示，剩下的其实还好，说实话我觉
得问这种问题的interviewer都有点想搞你的意思。 |
|
j********x
发帖数: 2330 | 48 topo sort 要在确定dag之后做，反过来干嘛。。。 |
|
l***i
发帖数: 1309 | 49 you can compute indeg[] for every node. Then start with any node with indeg=
0 and decrease all its neighbor's indeg by 1, push all indeg=0 nodes into a
queue and keep going. If you can exhaust all nodes, then it is DAG (assume
graph is connected, or you can use bfs/dfs to mark all nodes in current
connected component), otherwise there are cycles. Correctness can be proved
by induction. |
|
i******r
发帖数: 793 | 50 我觉得两种方法都行：
1.求强连通分量
2.拓扑排序 |
|
