s***i
发帖数: 49 | 1 How can I give algorithm that checks whether a graph is bipartite (a graph
whose nodes can be divided into two sets N1 and N2, and every edge is
between a member of N1 and N2)?
And since non-bipartite means there must be a cycle of odd length, how can I
check bipartite, and if false, prints a cycle of odd length?
Thanks in advance. |
|
s***i
发帖数: 49 | 2 How can I give algorithm that checks whether a graph is bipartite (a graph
whose nodes can be divided into two sets N1 and N2, and every edge is
between a member of N1 and N2)?
And since non-bipartite means there must be a cycle of odd length, how can I
check bipartite, and if false, prints a cycle of odd length?
Thanks in advance. |
|
p**v
发帖数: 853 | 3 【 以下文字转载自 EE 讨论区,原文如下 】
发信人: parv (yaner), 信区: EE
标 题: 最好的max-weighted bipartite matching的复杂度是?
发信站: Unknown Space - 未名空间 (Thu Oct 7 16:41:18 2004) WWW-POST
是什么复杂度呢？有人用过LEDA的code吗？那里面有这个函数，但是不知道
是什么数量级的，好像还挺快，不过manual里面没有具体提到算法，
不会还是O(n**3)吧？
多谢了！ |
|
s*****u
发帖数: 284 | 4 我有一个二分图(Bipartite Graph)储存在邻接矩阵A里, 100行300列，100行表示100个
因素A, 300行表示300个因素B. 即为一个100*300的二分图。
现在有一个方法找到因素B的overlap，我想看看对于因素Ai 和因素Aj, 他们所链接的
因素B中有多少是相同的。
方法如下: 取A的转置T(A), 算A' = T(A)*A, 则A'[i,j]即为因素A i 和 j 链接的元素
B的个数。
这个算法我从别人听来的，可是为什么呢？能给点证明或者是给个链接说明这个算法吗？
可能我的翻译不好，大家请轻拍。 |
|
s*****u
发帖数: 284 | 5 我有一个二分图(Bipartite Graph)储存在邻接矩阵A里, 100行300列，100行表示100个
因素A, 300行表示300个因素B. 即为一个100*300的二分图。
现在有一个方法找到因素B的overlap，我想看看对于因素Ai 和因素Aj, 他们所链接的
因素B中有多少是相同的。
方法如下: 取A的转置T(A), 算A' = T(A)*A, 则A'[i,j]即为因素A i 和 j 链接的元素
B的个数。
这个算法我从别人听来的，可是为什么呢？能给点证明或者是给个链接说明这个算法吗？
可能我的翻译不好，大家请轻拍。 |
|
T**********y
发帖数: 157 | 6 http://www.ccse.uestc.edu.cn/teacher/teacher.aspx?id=414
所有已经发表论文清单
（发表时间序）
【1】 周涛，傅忠谦，周佩玲，张建荣，张德学，”基于遗传算法的大规模流量
工程问题求解”，计算机应用，2003年第6期，43－45
【2】 杨春霞，周涛，周佩玲，刘隽，基于Multi_Agent的股市经济系统建模与
分析，自动化理论、技术与应用卷十，中国科学技术大学出版社，2003年，596-601（
中国自动化学会第18届青年学术年会会议论文集）
【3】 周佩玲，许民，赵亮，周涛，”混沌信号奇异性检测与外界冲击度量”，
数据采集与处理，Vol.19，195-198，2004
【4】 周涛，徐俊明，刘隽，”图直径和平均距离极值问题研究”，中国科学技
术大学学报，Vol.34，410-413，2004
【5】 周佩玲，杨春霞，周涛，李立文，”虚拟股市建模与混沌分析”，中国科
学技术大学学报，Vol.34，442-448，2004
【6】 T. Zhou, P. ... 阅读全帖 |
|
T**********y
发帖数: 157 | 7 【 以下文字转载自 Faculty 讨论区 】
发信人: TenMilesADay (郭十迈), 信区: Faculty
标 题: 快来看牛逼的27岁教授
发信站: BBS 未名空间站 (Sun Mar 11 13:14:59 2012, 美东)
http://www.ccse.uestc.edu.cn/teacher/teacher.aspx?id=414
所有已经发表论文清单
（发表时间序）
【1】 周涛，傅忠谦，周佩玲，张建荣，张德学，”基于遗传算法的大规模流量
工程问题求解”，计算机应用，2003年第6期，43－45
【2】 杨春霞，周涛，周佩玲，刘隽，基于Multi_Agent的股市经济系统建模与
分析，自动化理论、技术与应用卷十，中国科学技术大学出版社，2003年，596-601（
中国自动化学会第18届青年学术年会会议论文集）
【3】 周佩玲，许民，赵亮，周涛，”混沌信号奇异性检测与外界冲击度量”，
数据采集与处理，Vol.19，195-198，2004
【4】 周涛，徐俊明，刘隽，”图直径和平均距离极值问题研究”，... 阅读全帖 |
|
u******g
发帖数: 89 | 8 When is a bipartite graph, prove that the constraint matrix of this IP is
totally unimodular. Hence conclude that the natural linear programming
relaxation of this IP is integral, implying that Minimum Weighted vertex
cover is polynomially solvable on bipartite graphs.
http://trueshelf.com/exercise/214/vertex-cover-in-bipartite-gra
给跪了。。这个解释我几乎一般都没听懂。。 |
|
n*****y
发帖数: 361 | 9 DP won't work, because there is no ordering for those sentences.
The problem is combinatorial in nature.
Given the simple description of the problem, I thought it must be a well
known problem or equivalent to some of the well known set covering or
bipartite graph matching problems, but I cannot find the answer - I kind of
suck at these algorithms.
As far as interview goes, I believe if you can formulate it as a bipartite
graph and provide some search heuristics (greedy, branch and bound), it
sho... 阅读全帖 |
|
f*****e
发帖数: 2992 | 10 (N-1) regular bipartite matching，node i连接另一半里除i之外的nodes，随机
产生一个matching(i,j);然后去掉(j,i)形成(N-2)regular bipartite matching，再随
机产生一个matching，以此类推，这样可以产生随机矩阵。
然后挖掉方块后，剩余行和列元素的重合程度，(行-方块)交(列-方块)和方块大小决定
difficulty。
difficulty |
|
v****c
发帖数: 29 | 11 来自主题: JobHunting版 - G家面试题 矩阵看成是一个bipartite graph的adjacency matrix.
行是一边的顶点，列是另外一边的顶点
这个问题相当于min weight matching in bipartite graph
Hungarian method O(n^3)时间可解 |
|
v****c
发帖数: 29 | 12 来自主题: JobHunting版 - G家面试题 矩阵看成是一个bipartite graph的adjacency matrix.
行是一边的顶点，列是另外一边的顶点
这个问题相当于min weight matching in bipartite graph
Hungarian method O(n^3)时间可解 |
|
l******n
发帖数: 30 | 13 1. recruiter
2. host manager 老墨？ 讲项目，behavior，问了一道 brain storm 所有翻转数组的
方法
3. technical communication 两白男，讲项目
4. lunch 国人小哥，直接中文聊天
5. coding 一中一印，(1) product without the element itself, 我先讲了不用除法的
方法, 然后是用除法的方法，需要考虑没有0，一个0和多于一个0的情况 (2) 判断一个
graph 是不是 bipartite, 我用了 BFS 的方法，起始结点标左边，然后相邻标右边，
再相邻标左边，如顺利标完则是 bipartite，发现冲突则不是
6. system design: tiny URL. 先写了 URL 表示，数据模型。然后聊了后端存储，
NoSQL，怎么 partition，怎么判重。然后聊了 cache 和前端的 LB。
7. coding 同样一中一印, (1) 找出DNA序列中出现多以一次的长度为10的碱基序列，
和面试官讨论最后用bitmap实现。(2) 两个排序数组找 i... 阅读全帖 |
|
M*****e
发帖数: 11621 | 14 这个图应该是bipartite的，我查了一下wiki,
Andreas Bjrklund provided an alternative approach using the inclusion–
exclusion principle to reduce the problem of counting the number of
Hamiltonian cycles to a simpler counting problem, of counting cycle covers,
which can be solved by computing certain matrix determinants. Using this
method, he showed how to solve the Hamiltonian cycle problem in arbitrary n-
vertex graphs by a Monte Carlo algorithm in time O(1.657^n); for bipartite
graphs this algorithm can be fur... 阅读全帖 |
|
d*******g
发帖数: 36 | 15 Hi, guys,
Could anyone tell me about the optimal or fast known algorithms on maximum
bipartite matching and maximum weighted bipartite matching?
I mean their time complexities.
Thanks in advance. |
|
l****y
发帖数: 4773 | 16 全体人类作为一个集合，将其identify with nodes on a graph。如果有关系，则连一
条边，得一bipartite graph （忽略同性恋）。边上可加次数及时间为weight。设计算
法计算连通分支size。 |
|
i********r
发帖数: 12113 | 17 complete bipartite graph
[在 Texcat (德州猫) 的大作中提到：]
:感觉比红楼梦还乱，比如谁喜欢谁，谁和谁是冤家。
:谁和谁见面比撕逼。 |
|
|
l***i
发帖数: 1309 | 19 You can construct a graph and show that it cannot be bipartite. The Graph
Theory book by D. West has this problem as an exercise. |
|
P********l
发帖数: 452 | 20 It is a kind of bipartite matching problem. You can google it.
The solution can be very tricky. (net flow?) |
|
Y*****y
发帖数: 361 | 21 如果要求每个人最多分一个东西，那么就是一个maximum weighted bipartite
matching问题。Hungarian algorithm以
及后来派生出来的算法都可以解。
但是看楼主的描述，好像没有限制每个人最多分几个东西，也没有限制最多花多少钱。
那这个问题应该就很简单了。对每个
产品，scan一遍所有人的bid，谁最高就分给谁。O(n^2)的时间复杂度。 |
|
n*****y
发帖数: 361 | 22 It's interesting to think it as feature selection.
But your solution is only a heuristic, not guaranteed to find the minimum
set.
Notice the optimal solution not only prefers shorter sentence, but also
prefers words that are shared among multiple sentences.
Image there are 10 sentences, and 8 words as the following, the solution
will keep the longer sentences.
楼上的 bipartite graph 是正解. just my 2 cents.
S1 (W1, W2)
S2 (W1, W3)
S3 (W1, W4)
S4 (W2, W3)
S5 (W2, W4)
S6 (W3, W4)
S7 (W5)
S8 (W6)
S9 (W7)... 阅读全帖 |
|
c******c
发帖数: 2 | 23
Two questions regarding this problem:
1. Is the question asking for EXACTLY half of the sentences to be readable?
Or
just AT LEAST half to be readable? The latter seems to make more sense.
2. For the bipartite graph solution, how do we choose which of the Type A
nodes
to delete from graph G? I’m thinking of using a greedy approach, but not
sure
if this finds the minimum set of Type A nodes:
a. Find node n in A such that n’s degree is minimum
b. For each edge (n, b) where b in B
b.1 Delete ed... 阅读全帖 |
|
b********h
发帖数: 119 | 24 似乎可以用bipartite graph matching。 |
|
Y******l
发帖数: 19 | 25 断断续续找了三个月工作（从一月份开始找的），大公司，小公司都有尝试，最后拿到
3个offer。
第一个月，我人在加州某公司实习。利用了地理优势（属于local candidate）和朋友
的ref，拿到了不少面试机会。但是，由于准备的不充分，很多好的机会就这么错过了
，比如说google和twitter。不过失败是成功知母，这些失败的经验，终于给我带来了
一月末的两个offer。一个是just so so 的startup A，一个是一个dying的大公司。。
。他们给的答复时间也非常紧。没办法，我只好做了决定。。。
第二个月。。。很平静。。之前投出去没回音的还是没回音。。安心写我的博士论文。
第三个月，突然另外一个start up B 找上我。。B比A要promising很多。我心动了，心
想反正试试也没什么损失。当然，为了发挥出比较好的水平，（1）跟踪本版信息，（2
）花了1周时间过了leetcode和careerstack 的题。很幸运，最后拿到了offer。。
下面我分享一些，我面过的题目，不确定是哪家的，大家就题论题：
1. Given a graph, how to det... 阅读全帖 |
|
|
j*****o
发帖数: 394 | 27 min cost flow 是一个SOURCE,一个DESTINATION吧？
这个图是说学生都是源点，那共有9个源点？
我没搞清楚这个BIPARTITE GRAPH怎么画。。
REQ DETAIL
THX |
|
h**********y
发帖数: 1293 | 28 tripartite graph,
三个组每个组有8，9，11个节点
求所有可能的联通graph数目（，满足从任何一个点可以到达任何另外一个点。由于是
tripartitie graph，就像bipartite一样，组内点不能直接连）
1，1，2可以自己画出来。。 |
|
r*******e
发帖数: 7583 | 29 你这个明显不对
比如 男 3 4 5
女 1 2 6
按你的挑法，假定总是男的挑，3-2， 4-6， 5-1，差是7
就算男女轮流挑也不对，随便换个例子就知道了
这个问题应该是min weight matching of bipartite graph
最常见的解法是Hungarian algorithm，复杂度O(n^3)
http://en.wikipedia.org/wiki/Hungarian_algorithm
greedy如果只要O(n^2)，肯定是不对的。。 |
|
e****g
发帖数: 1 | 30 assignment problem. use modified shortest path search in bipartite graph |
|
l***i
发帖数: 1309 | 31 Babyknight has the right idea. In his/her construction, every vertex cover
maps to a cut of the graph, so min weight vertex cover is min cut.
If the vertex is unweighted, then the answer is simply the size of a maximum
matching (unweighted), see Konig's theorem in wikipedia.
Bipartite vertex cover or independent set, weighted or not, is in P. totally
unimodular implies there is always an optimal solution that is integral,
just like max-flow-min-cut. This was once an MIT algorithm homework proble... 阅读全帖 |
|
|
n**s
发帖数: 2230 | 33 bipartite的充要条件是没有odd cycle |
|
c**y
发帖数: 73 | 34 小公司，有点research性质的。面了6,7个人吧，问了很多关于之前的research
projects，不具有代表性。就把记得的算法题汇报一下吧。很多也没要求写code。
1. 给定一个sorted array，如何查找所有pair，他们的和等去一个给定sum。
要求给一个不用hash table的方法
给了一个用binary search加速查找过程的方法。
2. 如何用一个1G内存sort一个10G的文件，假设硬盘空间足够大。
刚开始给了一个pair-wise sort，后经讨论improve成K-way sort。相比K-way sort，
pair-wise sort要求更多的硬盘访问次数。
后来讨论一下如果硬盘空间有限，例如只有10.5G，如何做K-way sort。
3. 给定一个有向图，如何判定是不是bipartite，只讨论的算法，没有要求写code
这里是Wiki上定义http://en.wikipedia.org/wiki/Bipartite_graph
4. 如何判定一个binary search tree
5. 给定一个array和一个sum，如何找到所有个... 阅读全帖 |
|
r*c
发帖数: 167 | 35 来自主题: JobHunting版 - 给个算法题 看不出1和2有矛盾。
如果矛盾的话，那就很像个Bipartite graph problem. |
|
M*******a
发帖数: 1633 | 36 这么神奇？
是更什么bipartite matching一个意思么？ |
|
l***i
发帖数: 1309 | 37 5分钟写dijkstra不用他，我都能写。要是几个月之前写bipartite matching都没问题。
他的blog我看过，水平在那儿摆着呢，板上骂他的这么多，有几个能写个code search
在google里面给上万engineer用的。大家要骂人也就事论事，说说他在技术上有什么不
足，或者他的那些关于programming language的论点有什么不对的，人身攻击就没意思
了。不是只有ken thompson这种才可以说自己是牛人的。 |
|
l***i
发帖数: 1309 | 38 5分钟写dijkstra不用他，我都能写。要是几个月之前写bipartite matching都没问题。
他的blog我看过，水平在那儿摆着呢，板上骂他的这么多，有几个能写个code search
在google里面给上万engineer用的。大家要骂人也就事论事，说说他在技术上有什么不
足，或者他的那些关于programming language的论点有什么不对的，人身攻击就没意思
了。不是只有ken thompson这种才可以说自己是牛人的。 |
|
l******a
发帖数: 14 | 39 This is a max/ min flow problem from mouse to hole(bipartite graph) |
|
M******9
发帖数: 10 | 40 上面部分没有具体说的题目真心不难，其实Leetcode上的题目真正理解了肯定没问题，
我列下类似方法的题目或者变形(绝大部分对应leetcode上的题目，有些是实际问题背
景，稍微转化下就是了):
One Edit Distance
Binary Search in Rotated Sorted Array
Sqrt, Power using binary search
Regular Expression Matching
LRU
Max number of Points on line
Combination Sum
Decode ways
K-th biggest/smallest number in unsorted stream/array
Log hit类题目
给定一个string，在字典中查找共同前缀最长的单词
判断树是否BST, 是否symmetric, root到最大值节点路径
判断图是否bipartite,判断有向图是否tree |
|
M******9
发帖数: 10 | 41 上面部分没有具体说的题目真心不难，其实Leetcode上的题目真正理解了肯定没问题，
我列下类似方法的题目或者变形(绝大部分对应leetcode上的题目，有些是实际问题背
景，稍微转化下就是了):
One Edit Distance
Binary Search in Rotated Sorted Array
Sqrt, Power using binary search
Regular Expression Matching
LRU
Max number of Points on line
Combination Sum
Decode ways
K-th biggest/smallest number in unsorted stream/array
Log hit类题目
给定一个string，在字典中查找共同前缀最长的单词
判断树是否BST, 是否symmetric, root到最大值节点路径
判断图是否bipartite,判断有向图是否tree |
|
v********o
发帖数: 67 | 42 第二题感觉是maximum bipartite matching啊，用maximum flow算法做
Firewall |
|
l******n
发帖数: 30 | 43 有道理，看来今后得好好审题。
应该基本 bug free，大部分题面试官都开始 follow up bug 之外的东西了，比如怎么
省空间之类。
不过 graph bipartite 那题没见过，写完和面试官过了一遍代码就到时间了。 |
|
l*******t
发帖数: 79 | 44 Pinterest 电面
1. 多叉树的serialize & unserialize
2. 判断一个graph是不是bipartite
Dropbox电面
1. 1) bool match(string pattern, string data)
test case:
pattern = 'abba', data = 'red blue blue red' true
pattern = 'abba', data = 'red blue yellow red' false
pattern = 'aaaa', data = 'red red red red' true
pattern = 'abba', data = red red red red' false
2) followup，remove spaces
pattern = 'abba', data = 'redbluebluered' true
pattern = 'abba', data = 'redblueyel... 阅读全帖 |
|
S********t
发帖数: 3431 | 45 带restrict的index／search，general的说其实是一个push和pull的优化问题(
indexing = push, query = pull)，两个极端就是celebrity(too many followers),
以及疯狂follow别人的人。
可以用bipartite图来model，最优解是push+pull的hybrid，push端的cost跟pull端的
cost可以根据fan-in/fan-out degree, read/write frequency，甚至user activity等
等信息来score，然后贪心的选哪些edge用来
push，哪些edge用来
pull。 |
|
h******k
发帖数: 810 | 46 bipartite graph union-find？ |
|
g********e
发帖数: 1638 | 47 196 阳晓宇
(ME) 男 1976/03/18 武汉理工大学 工程与材料科学 2007年12月
毕业于[比利时]鲁汶大学联盟和平圣母大学和吉林大学(联合培养) [比利时]比利时
国家科学研究基金委员会 责任研究员/Chargé de Recherch
这位青年千人喜欢写书，有两本。Journal文章不多，会议的不少。
本人有主页。
https://sites.google.com/site/kevnyang/publications
Selected Publications
Book
1. Author: Xiaoyu Yang
Book Title: “Toward Environmental Sustainability and Energy Efficiency: A
Methodology and Tools for Realising Product Service Systems Using Software
Agent”
Publisher: Lambert Academic publishing, Ger... 阅读全帖 |
|
f******6
发帖数: 68 | 48 来自主题: Immigration版 - 审稿转让 现转让一篇英国皇家化学学会的杂志的稿子.
如果有相关的经验,又需要审稿,请把你的名字,单位,非个人的email发到我的邮箱.
Molecular BioSystems
TITLE: Prediction of drug-target interaction by label propagation with
mutual interaction information derived from heterogeneous network
ABSTRACT:
Identification of potential drug-target interaction pairs is very important,
which is not only for providing greater understanding of protein function,
but also for enhancing drug research, especially for drug function
repositioning. Recently, numerous machine learning... 阅读全帖 |
|
s*********b
发帖数: 815 | 49 简单算法还是有用的。举几个例子：
- 前东家匹配广告的时候，第一版用到bipartite graph
- 给客户的网上商店生成Google Sitemap的时候，用depth first search
- 给客服的一个工具需要高亮表单差异，用的是改动过的longest common sequence
- 做负载平衡的时候实现了phi accrual failure detection
- 检查分布系统一致性的时候，实现了Merkle tree
- 系统间的multicasting用了gossip protocol
- 多台机器，要看哪台有问题，用了Grubb's Test来检测异常
- 处理错误或者负载问题时总得实现滑动窗口，bounded exponetial backoff一类的东
东吧？
专业的算法在startup里就更多了。比如前东家的clustering detection把统计物理的
某个模型套在图上，据说效果不错。
了。 |
|
