c******0
发帖数: 260 | 1 我写了一下，不知道对不对。。。求指教
struct Node{
int val;
Node *left, *right;
Node(int v): val(v), left(NULL), right(NULL){}
};
void maxNodeHelp(Node *root, int &direct, int &undirect){
if(!root) return;
int nextDirect = 1, nextUndirect = 0;
maxNodeHelp(root->left, nextDirect, nextUndirect);
maxNodeHelp(root->right, nextDirect, nextUndirect);
direct += nextUndirect;
undirect += max(nextDirect, nextUndirect);
}
int maxNode(Node *root){
if(!root) return 0;
int di... 阅读全帖 |
|
s********x
发帖数: 914 | 2 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},... 阅读全帖 |
|
p*****2
发帖数: 21240 | 3 Given an undirected graph G having N (1
weights. Find the shortest path from vertex 1 to vertex N, or state that
such path doesn't exist.
区别是这个是undirected。解法一样吗？ |
|
f*******4
发帖数: 64 | 4 最近在做一个 social network data analysis 的project
我自己想的算法效率很低，跪求大神指教。。
一个超大的txt文件（4G吧）(ID有10^6个，edge有10^8个)
全部是如下格式：
1 5
1 6
2 7
1 7
都是无序的。。这些ID
数字代表ID，我要做的是找出一个概率P（分数）： （A->C）/(A->B , B->C)，也就是
传递性，找到这个txt里 三角形（传递关系）的概率
比如，如果这个txt里只有1、5、8、9、2、6.
1 5
5 8
5 9
1 8
2 6
1认识5,5认识8,1认识8,；1认识5,5认识9,但1不认识9。 这个P就等于0.5。。（A->C）
/(A->B , B->C)（因为2、6无法和另一个ID产生关系，因此不要）我的target就是要求
出这个P。。
因为这些ID肯定都是long型，然后edge估计有个N*10^8,我不确定是否可以用内存（我
们服务器内存15Gb）。
目前，我是这么做的：把这个大txt，按ID的除余，分成0-19999两万个hash txt，然后
操作，这种做I/O明显是很大的，然后... 阅读全帖 |
|
l****o
发帖数: 315 | 5 DFS 和 BSF 的都写了，已过OJ
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<
UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if (node == null) return null;
Ha... 阅读全帖 |
|
f*******4
发帖数: 64 | 6 最近在做一个 social network data analysis 的项目
我自己想的算法效率很低，跪求大神指教。。
一个超大的txt文件（4G吧）(ID有10^6个，edge有10^8个)
全部是如下格式：
1 5
1 6
2 7
1 7
都是无序的。。这些ID
数字代表ID，我要做的是找出一个概率P（分数）： （A->C）/(A->B , B->C)，也就是
传递性，找到这个txt里 三角形（传递关系）的概率
比如，如果这个txt里只有1、5、8、9、2、6.
1 5
5 8
5 9
1 8
2 6
1认识5,5认识8,1认识8,；1认识5,5认识9,但1不认识9。 这个P就等于0.5。。（A->C）
/(A->B , B->C)（因为2、6无法和另一个ID产生关系，因此不要）我的target就是要求
出这个P。。
因为这些ID肯定都是long型，然后edge估计有个N*10^8,我不确定是否可以用内存（我
们服务器内存15Gb）。
目前，我是这么做的：把这个大txt，按ID的除余，分成0-19999两万个hash txt，然后
操作，这种做I/O明显是很大的，然后处理，又因... 阅读全帖 |
|
r*****s
发帖数: 59 | 7 老公的精液检查报告出来了，医生什么都没说。
我看了一下，Progression分值只有1+到2 。
网上查了一下，看到以下的标准：
Motility and forward progression: normally >50% of sperm in the specimen are
motile. Forward progression describes how fast the motile sperm
are moving (normal 2+ in the scale from 0 to 4)
0 No movement
1 Movement, none forward
1+ Occasional movement of a few sperm
2 Slow, undirected
2+ Slow , directly forward movement
3- Fast, but undirected movement
3 Fast, directed forward movement
3+ Very fast forward movement
4 Extremely fast |
|
z********i
发帖数: 568 | 8 一个博后工资6万，benefit20%吧，就7.2万。再加学校的undirect cost 40%，就每年9
万多一点了。何况学校连phd都没有，很难想象能找到博后。 |
|
g*******y
发帖数: 1930 | 9 看了一晚上精华区，发现这道题有问题啊。
5。Given a graph (any type - Directed acyclic graph or undirected graphs
with loops), find a minimal set of vertices which affect all the edges of
the graph.
An edge is affected if the edge is either originating or terminating from
that vertex.
The time should be less Q(n^2)
这个题就是最小顶点覆盖问题吧？
或者是我对最小顶点覆盖问题理解有误？或者对这题理解有误？ |
|
h***t
发帖数: 2540 | 10 Given a graph (any type - Directed acyclic graph or undirected graphs with
loops), find a minimal set of vertices which affect all the edges of the
graph. An edge is affected if the edge is either originating or terminating
from that vertex. |
|
k***e
发帖数: 556 | 11 你平常是在哪找到的这些题目？能告知一下吗？我只知道careercup。
bfs can be used only for the undirected graph. it is easy to give a counter
example of directly graph that bfs did not work.
dfs works in both cases.
marking is definitely needed. |
|
s*****e
发帖数: 36 | 12 Can we construct a undirected graph and then find a Hamilton path of length
10? |
|
g******d
发帖数: 511 | 13 最后一题的graph是directed还是undirected? |
|
|
e**********6
发帖数: 78 | 15 给一个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加入进来 |
|
c******n
发帖数: 4965 | 16 last question (root of tree) is not clear
if the "connected pair" in ur spec is not directional, then the given
undirected graph can be represented as multiple trees, so the root is
not fixed.
for example
A
| \
| \
B C
is a tree
but it can be rotated to
C
|
|
A
|
B
if it's directional, it's super easy
in the |
|
s*****n
发帖数: 5488 | 17 depends on how longest path is defined.
assume that he asked a path in undirected graph.
the best solution for binary three is always recusrive solution since it is
elegant and simple for the interview purpose.
Hight (i) = 1 + max(Height(i.leftNode), Height(i.rightNode))
Height (null node) =0;
LongthestPath(i) = 1+ Height(i.left) + Height(i.right). |
|
S**I
发帖数: 15689 | 18 Sent by Amazon recruiter:
Thank you for the interest in Amazon.com and taking the time to speak with
us about some of the exciting opportunities that we have available. We've
put this document together to help give you an idea of what types of
knowledge we expect some level of familiarity with.
Preparing for Your Interview
At Amazon.com we're looking for talented engineers that can apply the
knowledge that they've learned in school and in industry to solving some of
the world's most complicated ... 阅读全帖 |
|
C***U
发帖数: 2406 | 19 Given an undirected tree T = (V;E) with weights on edges: fi nd the maximum
weight set M of edges such that no two edges in M share a vertex.
应该可以用dynamic programming吧
但是还是觉得时间花费很大
greedy不可行，我可以举出反例
有什么好的办法么？ |
|
d*******r
发帖数: 208 | 20 名单上列了11个人。见了10个,跟名单上有临时改动，有一个的shadow没来。
1. given such a structure,
id -- list of friend ids (sorted), similar to bi-directional or
undirected graph eg.
1 -- 3 5 6
2 -- 5 8
3 -- 1 8
5 -- 1 2
6 -- 1
8 -- 2 3 9
9 -- 8
find an efficient way to decide if two ids are connected by 1 hop or 2
hop. for instance.
one hop: 1 -> 3 -> 8
two hop: 1 -> 3 -> 8 -> 9
2. design a hashtable, get, put, etc. consider thread-safety and hash
capacity resizing.
3. some introduction of th... 阅读全帖 |
|
m**q
发帖数: 189 | 21 ==> 谢谢分享
名单上列了11个人。见了10个,跟名单上有临时改动，有一个的shadow没来。
1. given such a structure,
id -- list of friend ids (sorted), similar to bi-directional or
undirected graph eg.
1 -- 3 5 6
2 -- 5 8
3 -- 1 8
5 -- 1 2
6 -- 1
8 -- 2 3 9
9 -- 8
find an efficient way to decide if two ids are connected by 1 hop or 2
hop. for instance.
one hop: 1 -> 3 -> 8
two hop: 1 -> 3 -> 8 -> 9
==> BFS
2. design a hashtable, get, put, etc. consider thread-safety and hash
capacity resizing.
==> has... 阅读全帖 |
|
f*******l
发帖数: 66 | 22 copy an undirected graph
each node only contains its neighbor information. |
|
f*********y
发帖数: 376 | 23 If you want to get an offer for MGFLA, please check the requirements..
Although algorithm is very important, if you do not know (at least the basic
)other topics, you can fail the interview and onsite very easily.
Sent by Amazon recruiter:
Thank you for the interest in Amazon.com and taking the time to speak with
us about some of the exciting opportunities that we have available. We've
put this document together to help give you an idea of what types of
knowledge we expect some level of familiar... 阅读全帖 |
|
l***i
发帖数: 1309 | 24 put an undirected edge from a person to his/her father, and one edge to the
mother. Then two persons are related iff there is a path from one person to
the other. You can do either bfs or dfs assume the graph is small enough.
Basically the connectivity problem. |
|
|
d**********x
发帖数: 4083 | 26 obviously undirected
because there is no path 7-->2 if directed.
so bfs, dfs, union-find, any one of them should work... |
|
j*****y
发帖数: 1071 | 27 undirected 比较 easy, dfs 就行了
总感觉 directed的时候有点不好办。 |
|
m*********g
发帖数: 170 | 28 如果是directed，你可以把它改成undirected--复杂度 O(E)。
然后用DFS. 复杂度O(V+E). |
|
t****a
发帖数: 1212 | 29 I have a graph matching problem that I want to solve. This problem involves
a weighted undirected graph and is very similar to the maximum weighted
graph matching problem http://jorisvr.nl/maximummatching.html
With respect to a weighted graph, a maximum weight matching is a matching
for which the sum of the weights of the matched edges is as large as
possible. I can find some software for solving this problem.
However, my problem is a little bit different from the standard one in that
I wish the... 阅读全帖 |
|
J*****5
发帖数: 69 | 30
这题目不是求 undirected graph 里面有没有 cycle 而已吗? 怎么会出现别的高级数
学算法? |
|
i*b
发帖数: 43 | 31 好吧，懒得另开贴了。
Y面的比较夸张，第一面试官临时有事，耽误了１５分钟临时抽了个其他人。面到第四
个之后，他告诉我后面没有人了。我说email里写的是５个啊，他就说那你等一等没人
就闪了。我关起门来等了１５分钟还没人，于是拎包要走，开门后看到门口站一老头.
我hi了一下，他问我你是不是XX（小弟的first name）。恍然大悟刚最后一个人走之后
不该关门。当时觉得悲剧了，他一个技术问题没问，瞎聊了一会儿。２０分钟之后问我
有木有问题要问他的，我随便问了一个。然后就把我送出去了。
以下是记得住的onsite题目(三个onsite放一起写了, 自己猜哪个是哪个吧，总觉得分
享题目对不起公司，但对的起同胞就好了。)
给了一个序列（据说有规律），和一个叠带表达式，然后可以用来计算自然低数e。算
法给了,让实现code。讨论了big num和精度问题。
计算有理数循环节，比如２／３＝０.（６）
打印电话号码产生的所有string，recursive 和iterative都要
二纬grid上有数，输出从左上都右下的最佳路线（和最大）。
不同机器上的array求中值
以上三题面完之后才知道有个东... 阅读全帖 |
|
r****7
发帖数: 2282 | 32 You should use undirected graph for SCC detection. |
|
G******n
发帖数: 572 | 33 娃满月了，看着他对这个世界的好奇，我无法入睡。
物理phd最后一年，早已对学术界失望，对学术生涯失去热情。老板很supportive，今
年之内完成论文。之前三天打鱼准备了一会儿编程，面了几个，都没有结果。可能是之
前太多事情让自己分心，而且比较迷茫，没有一个准确的目标。（现在也不确定。。。）
现在生活慢慢稳定下来，虽然赶不上summer intern了，还是希望能在毕业之前找到工
作。
地点：大波士顿地区（至少暂时不能离开），纽约地区也可以试试
目标：entry-level 大公司码工，quant，data scientist （支持H1b和opt extension
的）
背景：top20 Physics phd，本科国内top3，成绩和学习能力没问题，数学和解题能力
不错，但没有实习经历。phd方向实验和理论，显微镜成像图像处理，数据分析，MC数
值模拟
技能：C++很熟练，Matlab。其他的都会一些，core java/j2ee, machine learning,
sql都有听过公开课和做作业，数据结构和算法会的有限。leetcode做（看）过20%，没
有认真去刷
差不多... 阅读全帖 |
|
s******7
发帖数: 1758 | 34 undirected graph, BFS, 用两个queue控制分层, 第一层，第二层，第n层都没问题 |
|
x****k
发帖数: 34 | 35 还是不很明白。如果是undirected graph这没问题。可这是direcetd graph，所以
source点 distance 为2的点集合 与 destination点 的O（N） 邻居集合 完全可以没
有交集，但是destination点距离source为3。 |
|
y***e
发帖数: 32 | 36 对不起，你们的分析是对的，原题是undirected graph。上面的分析也都是对的。我已
经把原题的表示改了。 |
|
r****7
发帖数: 2282 | 37 要这么麻烦么。。。
不就是建一个undirected graph然后找scc么。。 |
|
k****r
发帖数: 807 | 38 the total degrees of all vertexes in undirected graph should be even number,
so f*n is even is a necessary condition. |
|
m**********2
发帖数: 6 | 39 其实应该是这样一个思路，标记当前可走的，如果没有就返回，但是这样并不能保证图
形是match的，因为起点可以是任意一个点，需要找个方法判断所有的边都被访问过了
。默认是undirected graph。一直到现在都没什么思路。LC上貌似graph的题不多啊。 |
|
m****i
发帖数: 650 | 40 一个undirected network without cycle，要求求得节点具有到其他节点的最小
distance，也就是node with min(sum_of_distance_to_other_nodes)。这道题弄了一
些时间，开始直接说对每个点BFS。然后慢慢的讨论优化，因为图无环，最后弄出来的
算法是O(n)的。但是代码只写出来了一半，不过之前跟他讨论得很详细了，也先给出了伪
代码，所以感觉他也满意了。
有人答过如下，没有理解：）
想成是个tree，找出所有的leaf，然后把所有leaf放到一个list里
做reverseBFS, 从leaf开始每走一层就加一个weight（sum(child weight) * 2 + 1)，
最终会找到一个root。
然后就是balance tree by weight，
从root开始试每个child，如果把那个child假设成root，
child_weight = root.weight - child.weight + (# of root's child - 1)
找出最小的child_weight，把那个child变成... 阅读全帖 |
|
c*******t
发帖数: 123 | 41 正在刷题的菜鸟说说我的想法：
第一题：笨办法，找出一对，踢掉这个或者那个。 或者用图，别人都指向这个人，这
个人不能指向任何人。这个人是sink point. topological sort.这个人是最后一个。
但问题是这个题目有比O（n）更优的算法吗？n是问问题的个数，比如一对人，你问a认
识b吗, b认识a吗，这算两个问题。如果能知道其他人之间互相熟识的程度，那就可以
用概率。
第二题： 键盘是3乘3， 密码可以从任何点开始，但不能成为闭环，就是访问过得不能
再访问。
不要用矩阵的思想去想，那样受制几何形状太复杂。做一个9个节点的
图，undirected. 比如1可以连到2，4，5.
问题变为从1出发，有多少种不同的路径？访问过得不能在访问。这个
应该是个经典算法问题吧？
9个不同出发位置加起来。 |
|
发帖数: 1 | 42 老中面试官，问了个这个题目：
Find all connected components in an undirected graph.
我尝试了DFS和BFS，不知道对不对，最后挂了。
大家有啥好解法？ |
|
r*****s
发帖数: 1815 | 43 Union-Find is O(alpha(E)*E).
the process is
foreach edge in edges:
union(edge.source, edge.target) //undirected... you can name whatever..
The complexity of union is not O(1) but O(alpha) which grows very slowly.
Comparing with DFS/BFS it might actually have performance advantage because
of compact implementation (implies smaller "constant" multiplier). |
|
o******0
发帖数: 105 | 44 如果图很大，分布在多个机器上，任何一台的内存都不够大，怎么办？ |
|
R*********d
发帖数: 34 | 45 把图分割，在边界构造虚拟点，在每台机器上并行计算每个子图的连通分量，最后合并
各个子图的虚拟点 |
|
o******0
发帖数: 105 | 46 怎么构造虚拟点呢？理论上讲，一台机器上所有点都有可能和另一台机器上的图相连。 |
|
p**r
发帖数: 5853 | 47 不是BSO，我23岁的时候就当过CTO，40多个人的小公司。
之前一份工作的title是VP，当然都是中小公司。
其实都是打工仔，没什么区别。
还有一点我从来没觉得director这种层面的好做，
中层就像undirected graph，永远是最累的，
又要哄着管着下面的，又要看上面的脸色。
底层或高层反而容易，只要看一个方向。 |
|
o*q
发帖数: 630 | 48 Google
Show problem tags Hide locked problems
#
Title
Acceptance
Difficulty
Frequency
66 Plus One 35.4% Easy
146 LRU Cache 15.8% Hard
200 Number of Islands 29.7% Medium
288 Unique Word Abbreviation 15.7% Easy
163 Missing Ranges 30.3% Medium
56 Merge Intervals 26.7% Hard
228 Summary Ranges 26.0% Medium
308 Range Sum Query 2D - Mutable 20.8% Hard
279 Perfect Squares 34.1% Medium
388 L... 阅读全帖 |
|
o*q
发帖数: 630 | 49 # Title Editorial Acceptance Difficulty Frequency
1
Two Sum 28.3% Easy
292
Nim Game 54.4% Easy
344
Reverse String 57.3% Easy
136
Single Number 52.2% Easy
2
Add Two Numbers 25.6% Medium
371
Sum of Two Integers 51.6% Easy
4
Median of Two Sorted Arrays
20.4% Hard
6
ZigZag Conversion 25.6% Easy
13
Roman to Integer 42.7% Easy
237
... 阅读全帖 |
|
w********1
发帖数: 3492 | 50 there is some strategy not rely on IV and not rely on market direction
reading.
as one simple example, the carry trade style stuff..
there also a lot of undirectional bet need some reading, but not a lot of
reading.
market is tougher for a lot of strategies after 2008-2010 and with so many
more powerful cmputers taking control of the short term trading, but there
should still be some low risk and high tolerance strategies out there to
make reliable money.
besides those trading ideas, some deep F... 阅读全帖 |
|
