m****o
发帖数: 182 | 1 1. java garbage collector
A: reference counts.
Q: circular reference. Any better solution?
A: treat each object like the nodes in the graph. and find separated
subgraph.
Q: How to determine which subgraph is "live", which is “dead”?
A: Use the objects stored in the current stack as the starting point in the
graph.
2. many many documents with unique ids, find duplicate documents.
A: Use hash table. If allowed, use multiple machines to do hashing
Q: Any other solutions?
A: Use prefix tree (word as... 阅读全帖 |
|
l***n
发帖数: 542 | 2 I guess it's some graph theory problem. First find a partition for the graph
so that each sub-graph is a connected graph and no two subgraph share the
same point. Next find the minimum tour path for each subgraph |
|
S********t
发帖数: 3431 | 3 第二个题对于面试来说太难了吧，我不认为大部分的candidate能在面试时间内解决。
理论上面试不应该涉及太深的图论的东西。我觉得你的面试官估计都把这个问题想简单
了。anyway，拿到
offer还是好事
反正我是不会把这题当作面试题考人的
我自己对图论并不太熟悉，曾经算法课学些最基础的东西但也已经有点忘了。我的idea
是，找isolated sub-graphs，然后单独比较各个subgraph；如果整个图是connected，
就算互补的图，然后互补的图一定是包含isolated subgraphs。这样每一步可以降低一
些问题的规模 |
|
s********x
发帖数: 914 | 4 Find the Connected Component in the Undirected Graph
Find the number connected component in the undirected graph. Each node in
the graph contains a label and a list of its neighbors. (a connected
component (or just component) of an undirected graph is a subgraph in which
any two vertices are connected to each other by paths, and which is
connected to no additional vertices in the supergraph.)
Example
Given graph:
A------B C
| |
| |
| |
| |
D E
Return {A,B,D},... 阅读全帖 |
|
c********t
发帖数: 5706 | 5 不行吧
【2，1】【4，3】
每个node存subgraph, subgraph永远挨着。能得到1,3,2,4这样的解吗？ |
|
z****n
发帖数: 486 | 6 The Bitcoin system is the best known and most widely used alternative
payment scheme, but so far it was very dicult to get accurate information
about how it is used in practice. In this paper
这篇论文太给力了，背后必然有人操盘。
=====================================
we describe a large number of statistical properties of the Bitcoin
transaction graph, which contains all the transactions which were carried
out by all the users until May 13 th 2012. We discovered
that most of the minted bitcoins remain dormant in ... 阅读全帖 |
|
x********i
发帖数: 905 | 7 Intel STS 2015 Finalists
Anandapadmanaban, Eswar
Dr. Ronald E. McNair Academic High School, Jersey City, NJ
The ThereNIM: A Touch-less Respiratory Monitor
Ashkin, Emily Lorin
Providence Day School, Charlotte, NC
A Novel Synergistic Approach for Enhancing Immunotherapy in the Treatment of
Melanoma
Chemparathy, Augustine George
Dougherty Valley High School, San Ramon, CA
Accumulation of the Biodiesel Precursor Triacylglycerol Offsets Oxidative
Stress in the Model Alga Chlamydomonas reinhardtii
Cui... 阅读全帖 |
|
T**********y
发帖数: 157 | 8 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. ... 阅读全帖 |
|
e**********6
发帖数: 78 | 9 给一个undirected graph，如何有效率的找出所有最大的full-meshed subgraph。full-meshed就是全连通的意思。比如：假设a,b,c,d四个节点中a,b,c是full-meshed。那么a,b,c中任意两个之间都是connected的。且a,b,c,d不是full-meshed，否则就要把d加入进来 |
|
g*********e
发帖数: 14401 | 10 subgraph isormorphism
以前实习的时候做过.recursion即可 |
|
l***i
发帖数: 1309 | 11 graph isomorphism is not known to be in P, nor is it known to be NP-hard.
subgraph isomorphism contains clique as a special case so it is easily shown
to be NP-hard. |
|
s********u
发帖数: 1109 | 12 话说，这个题用bfs比dfs有什么优势么？感觉不是最短路径之类问题的话，差不多吧？
dfs思路清晰，代码精简。其实就是D&C，假定subgraph已经建立好，那么如何求解
graph
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node,unordered_map<
UndirectedGraphNode *,UndirectedGraphNode *>& nodeMap ){
if(!node) return NULL;
if(nodeMap.count(node) > 0)
return nodeMap[node];
UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
nodeMap[node] = newNode;
vector阅读全帖 |
|
m**********j
发帖数: 610 | 13 靠，subgraph isomorphism？这怎么做？ |
|
l********1
发帖数: 990 | 14 有一个graph，每个node有自己的weight。如何找出subgraph， 让subgroup所有node的
weight和为k.
这道题属于什么难度呢？
菜鸟对graph很头痛，求大家指教。 |
|
l********1
发帖数: 990 | 15 Yes.
any solution for the question? how to most effectively find all the
subgraphs if any. |
|
r****7
发帖数: 2282 | 16 用动态规划，你还要在node里加上一个元素，是你处理的subgraph的weight之和
不过这个题是比较难的，我觉得面试中不会遇到 |
|
T**********y
发帖数: 157 | 17 【 以下文字转载自 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】 周涛，徐俊明，刘隽，”图直径和平均距离极值问题研究”，... 阅读全帖 |
|
i***l
发帖数: 468 | 18 【 以下文字转载自 Military 讨论区 】
发信人: xiaoxiaoxi (小小溪), 信区: Military
标 题: Re: 全美英特尔科学奖决赛名单公布 13名华裔入围
发信站: BBS 未名空间站 (Sat Jan 24 16:00:54 2015, 美东)
Intel STS 2015 Finalists
Anandapadmanaban, Eswar
Dr. Ronald E. McNair Academic High School, Jersey City, NJ
The ThereNIM: A Touch-less Respiratory Monitor
Ashkin, Emily Lorin
Providence Day School, Charlotte, NC
A Novel Synergistic Approach for Enhancing Immunotherapy in the Treatment of
Melanoma
Chemparathy, Augustine George
Dougherty Valley High School, Sa... 阅读全帖 |
|
a***n
发帖数: 404 | 19 有没有啥 famous 的现成的代码或者工具包呢？
谢谢~~ |
|
v********e
发帖数: 1058 | 20 Let X = (V, E) be a graph. A parttition \pi of V(X) with cells C_1, ..., C_r
is equitable if the number of neighbours in C_j of a vertex u in C_i is a
constant b_ij, independent of u. An equivalent definition is that the
subgraph of X induced by each cell is regular, and the edges joining any two
distinct cells form a semiregular bipartite graph. The directed graph with
the r cells of \pi as its vertices and b_ij arcs from the i-th to the j-th
cells of \pi is called the quotient of X over \pi. |
|
v****s
发帖数: 1112 | 21 What'll be the best algorithm for finding signed triad in large scale
graph, details as follows:
Given a graph with 1 million nodes and about 8 million edges (so, avg
degree is 8 ), 85% of the edges are marked as "+" and 15% as "-".
What will be the best algorithm or data structure involved to find
out the numbers of these 4 possible types of signed triad (a triangle
subgraph having 3 nodes and 3 edges) in this graph.
The four kinds of signed triad are:
+++
+--
++- |
|
h**x
发帖数: 34 | 22
http://en.wikipedia.org/wiki/NP-complete
非常粗略的说，就是算法上只能做到指数级运算时间，而不是多项式运算时间
Boolean satisfiability problem (Sat.)
N-puzzle
Knapsack problem
Hamiltonian path problem
Travelling salesman problem
Subgraph isomorphism problem
Subset sum problem
Clique problem
Vertex cover problem
Independent set problem
Dominating set problem
Graph coloring problem |
|
h**x
发帖数: 34 | 23 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
决某 NP-complete 问题的吗？
如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
谢谢！
http://en.wikipedia.org/wiki/NP-complete
非常粗略的说，就是算法上只能做到指数级运算时间，而不是多项式运算时间
Boolean satisfiability problem (Sat.)
N-puzzle
Knapsack problem
Hamiltonian path problem
Travelling salesman problem
Subgraph isomorphism problem
Subset sum problem
Clique problem
Vertex cover problem
Independent set problem
Dominating set problem
Graph coloring problem |
|
g*********e
发帖数: 14401 | 24 有啊 现在工作要对图进行优化，需要解决subgraph-isomorphism问题。
problem size很小啦，几百个节点以内吧。 |
|
c****l
发帖数: 88 | 25 Prove that if G is any graph with chromatic number k, then G contains all
trees of order k as subgraphs.
作业题。。。不大会做。。。还请大家帮帮忙！多谢了！ |
|
f*****e
发帖数: 2992 | 26 http://ocw.mit.edu/OcwWeb/Mathematics/18-997Spring2004/Assignments/index.htm
第一题怎么做?
Petersen's theorem (Lecture 3) says that every cubic bridgeless graph contai
ns a perfect matching. Show that for any even set T of vertices, a bridgeles
s cubic graph (V,E) contains a T-join of cardinality at most |V|/2 where a T
-join is a subgraph with odd degree at vertices in T and even at vertices no
t in T. |
|
p******k
发帖数: 11 | 27 http://ponyhawk.org/?p=10
SecDB就是security DB，Slang就是security langurage。SecDB就是一个数据库平台，
而Slang就是在这个平台上使用的语言。在网上找它的信息的时候发现很多讨论，但是
都很宏观，一旦深入进去总好像模模糊糊没有什么具体的东西可以了解，究其原因或许
是因为它的拥有者是另一个神秘的公司——高盛（Goldman Sachs）。曾经有个金融领
域的大佬曾经说过高盛（Goldman Sachs）就和某党差不多，在外面的人开来他很强大
，很神秘，虽然没做什么坏事，但基本上做的事都会被联想到邪恶。但就是这样一个“
邪恶“的角色被人们口口相传拥有一个赚钱的利器“SecDB/Slang”的时候，这件利器
本身也就成了世人追逐的对象。而这种说纷纭的千人千象更加增添了它“神器”传说。
既然讨论一个IT系统，我觉得还是IT人员最有发言权，仔细分析一下注解[1]中的讨论
和注解[2]中的描述，我觉得以下摘录值得进一步分析：
“They could also calculate the side effects of propo... 阅读全帖 |
|
d*z
发帖数: 150 | 28
It seems true, but u have not prove it.
First it is easy to proove that if we split the graph into
two subgraph A and B,
that the count of edges from A to B is the same as the count
of edges from B to A. Because we can split all edges into
four classes. Edges from A to A, from A to B, from B to A,
and from B to B. Because the count of edges from a vertex
of A is equal to the count of edges to a vertex. That means
Count(A to A)+Count(A to B) == Count(A to A) + Count(B to
A).
If there's a vertex |
|
