|
g*****g
发帖数: 34805 | 2 你又不知道被放进什么圈子。其实这就是把无向图变成有向图，用户
有更多的控制。
google |
|
b******y
发帖数: 2729 | 3 【 以下文字转载自 JobHunting 讨论区 】
发信人: nirvana21 (nirvana21), 信区: JobHunting
标 题: 国内逆天大神，M, G, F, T, H...通吃！
发信站: BBS 未名空间站 (Tue Mar 12 17:21:55 2013, 美东)
Microsoft， Google， Facebook， Hulu， Twitter 通吃。
人家国内硕士在读，从国内申请的，所向披靡啊，最后从了Facebook.
以下为原文：
最近签掉了 offer，找工作的事情算是告一段落。在这里写一点面试体验和心得，希望
对有兴趣去北美工作的朋友有所帮助。
先简单介绍下自己，国内硕士在读，明年毕业，没有牛 paper，也没参加过 ACM-ICPC
竞赛。在实验室做过内核、虚拟机和 Android 底层相关的研究工作，接过一些网页和
移动开发的外包，2011 年开始在字节社兼职负责后台开发。另外也经常上
Stackoverflow 和 GitHub。
这次决定直接申请美国的职位后，由于心里没底，不知道国外公司招聘的难度，所以一
开始投了很多公司。几个大公... 阅读全帖 |
|
|
p****s
发帖数: 3184 | 5 数据男系列的续集啦
假设A,B两队, 本赛季都输过, 那么如何判别A强于B, 还是相反呢?
在一个有向图里, 图的节点集是所有NCAA Division I的队,
图的边集是这样构造滴: 如果两个队之间有过比赛, 则有一边从赢的节点指向
输的节点.
算有多少条multi-path从A指向B, count一下所有这些multi-path上的distinct
节点数, denote as #AB.
另算有多少条multi-path从B指向A, count一下所有这些multi-path上的distinct
节点数, denote as #BA.
若#AB > #BA, 则 A强于B
若#AB < #BA, 则 B强于A
若#AB = #BA, A和B必须打上一架才能定输赢, 何如?
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈 |
|
t*******r
发帖数: 22634 | 6 dijastra 也可以在小尺寸 directed graph 上跑袖珍问题。。。
其实这玩意儿也是能用基本 BASIC 写的，用数组和下标代替结构和指针。。。只不过
麻烦很多倍。。。
这个破 dijastra 算法至少还不增加有向图的节点。。。增加甚至删除节点的算法更麻
烦。。。 |
|
h*****n
发帖数: 1630 | 7 牵强的地方太多。
不过抛开这些迷信，从数学上讲五行说还是有些有意思的地方。
五个“元素”之间相生相克满足以下规律：
相生相克都构成一个完整的环。
没有两个元素互生或互克。（不象西方的四元素说是两两互克。两个元素互生的话，会
无法抑制。互克的话，会无法激励。）
如果元素A克元素B，则B必然能生出克A的元素。（动态平衡？不存在一个元素把另一个
克得死死的情况）
如果要满足以上条件，最少的元素数量为五。不过仔细思考之后可以发现对任何大于五
的奇数都可以构造一个有向图满足以上条件。 |
|
D****y
发帖数: 2207 | 8 北美求职记（三）：Hulu & Twitter
DEC 27TH, 2012 • Permalink
北美求职记系列文章
北美求职记（一）：Microsoft
北美求职记（二）：Google & Facebook
北美求职记（三）：Hulu & Twitter
Hulu
Hulu 是这几个公司里唯一一个我没有找人内推而拿到面试机会的，也是面试体验最好
的一个公司。Hulu 和 Twitter、Zynga、Foursquare 等公司一样，用了 jobvite 接受
和追踪职位申请。因为是申请的第一家公司，我在申请 Hulu 时的 cover letter 写得
很详细，针对职位需求上的每一条都写了我的相关工作经验，这也许是最后能拿到面试
机会的原因吧。其他公司的 cover letter 都写得很简单，短短两段就结束了。
Hulu 的第一轮电面和其他公司的有些不同。45 分钟里要做四个题。面试官提前十分钟
发了一封邮件给我，上面有两段代码。第一段代码是一个检查两个字符串是否是
anagram 的程序，写得很绕而且性能很差。面试官先问我这段代码的用途，然后问有什
么方法优化，... 阅读全帖 |
|
|
r**i
发帖数: 2328 | 9 不算弱问:D 很好的问题。
简单来讲，tree是一种特殊的graph,所谓的acyclic graph，没有self-loop or
circuits。
你那张图里，可以把人看成节点(vertex），把人和人之间的relation看成边（edge)，
gossip传播过程即是由Vertex A到B的一个ordered pair（A, B）。这样就构成了一张
有向图(directed graph)。如果该图没有loop，就是个DAG(directed acyclic graph)
，也就是一颗tree。:)
现在问题，在一个directed graph里面怎样能detect loop，也就是发现gossip从
melisma传出后又传回到melisma那里？:DDDD |
|
a****a
发帖数: 5763 | 10 经过6年时间，4个发行版，苹果终于完成了向64位的迁移，并随着Snow Leopard的发布
推出了解决并行编程问题的Grand Central Dispatch（简称GCD）技术，释放了多核系
统的潜力。
和10.5一样，在10.6 Snow Leopard中，苹果继续利用64位的迁移砍掉了诸多老技术，
很多新技术仅以64位的模式被支持。例如重写的QuickTime X框架，虽然QuickTime X应
用程序以32位和64位的模式发布，但其API仅暴露给64位。另一个例子是Objective-C 2
.1的运行库，快速Vtable调度，新的和C++统一的异常处理模型，以及彻底解决对象的
FBI问题等，都仅限64位程序使用。
内核的64位化
读者应该发现，经过这4个发行版，Mac OS X自下而上地对整个系统向64位迁移。10.3
内核空间提供了64位整数运算的支持。10.4允许程序以64位模式运行在用户空间，并且
提供了64位的libSystem使得开发者可以开发64位的Unix程序，而10.5中系统所有未废
弃的函数库、框架都提供64位版本，到了10.6，所有用户空间的程序，包括... 阅读全帖 |
|
a****a
发帖数: 5763 | 11 http://bbs.weiphone.com/read.php?tid=517864
Mac OS X 10.6即所谓的Snow Leopard操作系统已正式发售。一如既往，Apple产品
光鲜的外表下凝聚了太多艰辛的劳作。ArsTechnic的John Siracusa以其独特的、专业
的、全面的视角深入翔实地体验这款最新的操作系统。
Weiphone.com将对该综述进行翻译整理并独家连载。欢迎关注
Grand Central Dispatch
上一篇连载《并行难题：一封19年前的挑战书(连载11/23)》中，我们讨论了
并行编程(parallel programming)的问题，以及该问题所导致的另一个更为深远问题，
那就是：近一二十年以来，尽管计算机硬件的发展已经迈上了一个新的台阶，然而“软
件”层面的发展却裹足不前，最终成为了限制计算机性能的主要因素之一。
针对这一问题，Snow Leopard的应对方案是Grand Central Dispatch(GCD)。
GCD是刚刚发布的Snow Leopard的一项新特性... 阅读全帖 |
|
s***e
发帖数: 2 | 12 【 以下文字转载自 Mathematics 讨论区 】
【 原文由 jollyl 所发表 】
我不知道下面的问题的难度如何，是不是某种NP的？
给定有向图，一个点s和若干点的集合D，要求判断有向steiner树的存在性。
一个约束是对每个点v，都规定了其孩子集合的所有可能，在steiner树中的
孩子集合必须是给定的若干可能中的一个。
我只知道，如果对无向图，当D包含剩下所有点，任意不超过k个孩子都允许，
问题称为degree limited spanning tree，是NPC
对我的这个问题，有没有高手知道答案？ |
|
|
D********g
发帖数: 650 | 14 一个有向图模型一个是无向图模型
可以Wiki或是Google |
|
a***n
发帖数: 404 | 15 有没有啥 famous 的现成的代码或者工具包呢？
谢谢~~ |
|
|
m***n
发帖数: 2154 | 17 呵呵，谢了。我去看看，可能我对这个算法理解还不够。 |
|
|
s*****w
发帖数: 1527 | 19 不是所有节点都相连的,
2个节点之间的连线是有方向的，很多是单向，
每个连线的cost不一样。
请问这是什么算法? |
|
c**t
发帖数: 2744 | 20 Someone claimed there is a solution for 4-coloring, which is equivalent to
NP-Complete.
Regardingless this, there are a lot approximations.. |
|
s***t
发帖数: 113 | 21 depends on what your graph is. There are TSP instances of 3,000 nodes that
got solved. |
|
|
k****f
发帖数: 3794 | 23 悟空你又调皮了。。。
这是数据结构的课本上的题目 |
|
|
c*****t
发帖数: 1879 | 25 你在自学 algorithm ？基本功太弱。多做点题。
这道题其实就是先弄个 topological graph （已给）。然后就是用 greedy
的办法取时间最短的 root 。
and |
|
t**********s
发帖数: 930 | 26 到哪儿能找到这样的题和讲解呢？
topological graph=directed acyclic graph? |
|
c*****t
发帖数: 1879 | 27 看那本 Introduction to Algorithms 啊。 |
|
|
N********n
发帖数: 8363 | 29 DFS on a DAG, the mother of all scheduling algorithms.
and |
|
m***t
发帖数: 254 | 30 为啥我觉得就是做min-spanning-tree呢？
and |
|
m***t
发帖数: 254 | 31 i was wrong, cormen 24.2...sigh. |
|
|
n*******r
发帖数: 444 | 33 Divide & Conquer应该可以解决这个问题．把矩阵一分为二，递归地解决每一个
sub-matrix, 再考虑across sub-matrix border的方案，这应该是一个
O(N^2lgN)的算法．
另外一个方法是对每一个black cell分类，即：可以为lowerLeft, upperRight,
lowerRight and upperLeft的cell,然后对他们做配对处理，（可以考虑把它
转成图的问题，即求有向图最大的circle). |
|
b***y
发帖数: 2799 | 34 ☆─────────────────────────────────────☆
kukutf (五脚蟹★酷酷豆腐) 于 (Fri May 9 14:08:06 2008) 提到:
无圈的有向图，如何估计比较长的路径（从source到sink）的分布？
每个边就算距离1
比如最长的路径个数，第二长的路径个数，第三长的路径个数？
只要大概的就可以了。因为增长的速度很可能是个指数。
有没有什么好办法估计一下？
☆─────────────────────────────────────☆
wdong (cybra) 于 (Fri May 9 16:30:29 2008) 提到:
严格计算可能更容易。大致思路是给每个节点维护一个分布。source的分布是什么都没
有。
然后从source开始遍历整个图。每次找前驱节点都已经被访问的节点。该节点的分布就
是所有前驱节点分布在加上这些分布的距离都加1得到的分布之和。访问完所有节点后
，总得路径分布就是所有sink的分布之和。算法复杂度应该是O(节点数x最大出/入度x
最大路径长度）。
☆────────────────── |
|
o****h
发帖数: 324 | 35 我需要算有向图中的min cut，而且我的edge capacity都是实数（即有小数点的），在
网上搜了一下， B. Cherkassky& A.B.Goldberg得算法应该是可以的，但是他们的相关
网页现在却不可以用了，请用过他们code的，或是由相关信息的同学帮助，或是知道其
他算法可以解决我的问题的都可以。万分感谢！！！ |
|
x*j
发帖数: 271 | 36 一个强连通的有向图（任意两个点互相都存在path），每条边有个weight，如何删除掉
一些边以后使得剩下的子图依然保持强连通，并且weight的总和最小。
没想出什么好的办法来，似乎就是穷举。不知道有什么好的办法么？ |
|
w***u
发帖数: 156 | 37 版上牛多，特来请教
1. 给定一个有向图， 边是有非负权重的，找最短路径，这个简单，用Dijkstra算法
2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是有且只隔了一个点
）不能同时出现在path中， 这时候最短路径如何求？
约束条件比如 n2不能和n5同时出现在路径中
n1----n2---n4---n5---n7
| | |
|-----n3----|---n6----| |
|
s*****n
发帖数: 5488 | 38 最短路径的实质是动态变成如果有约束条件不能使用公开人员的四有结果的话,我上的
问题可能就是运动车多少是时间解决的
版上牛多，特来请教1. 给定一个有向图， 边是有非负权重的，找最短路径，这个简单
，用Dijkstra算法2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是
有且只隔了........ |
|
g*****g
发帖数: 34805 | 39 这有啥复杂的，不就是有向图的树，作个先序遍历即可。 |
|
N******K
发帖数: 10202 | 40 Contextobject 内部要有什么信息？ object的有向图？
比如
Class A 有个成员变量m_classB， 是指向class B的指针
那么 是否要写
m_classB=ContextObject.CreatObj(this, new ClassB)
this指向Class A
这样就可以建立图 this是父节点 m_classB是子节点
有什么参考设计么？
database这个方法不太了解 能否讲讲？
impossible
is
one |
|
T********i
发帖数: 2416 | 41 这东东也就1-20000行代码搞定的。就是有向图的最小路径算法。每个节点带一些
attributes。
其他的都能通过message queue分布出去。
外围打酱油的那些花里胡哨的雇你这样的民工去做我还是放心的。 |
|
T********i
发帖数: 2416 | 42 这就是有向图的算法。
我一直强调区间段的 。
至于座位，则是简单的attribute。讨论可忽略。 |
|
|
b*******s
发帖数: 5216 | 44 他的一致性就是在那个有向图上做的
如果我正确理解了他 |
|
z****e
发帖数: 54598 | 45 就像小菊花说的，一碗泡面毁了全部人民的火车票
别告诉我这个有向图不在内存里面 |
|
g*****g
发帖数: 34805 | 46 到了读写分离，按线路分，按天数分，还离线处理这个程度。一天总共几千张票。
考虑啥有向图，就是数据库transaction，也就是锁表row足以，性能也够。
再大白话说一遍，就是每小段一个row，有个计数器。订票所有段row锁住，-1, 退票+1，
数据库就是干这个的。要啥算法，切。 |
|
g*****g
发帖数: 34805 | 47 这用得着他吹吗？分表都分到每天几千张票了，一天几千个transaction 单线程也没压
力。事实上几秒就弄完了。还有向图呢。 |
|
z****e
发帖数: 54598 | 48 我觉得这里的人背景不一样
很多人是完全没有相关行业的从业经验，就瞎说
就像楼主总是把这种系统比作股票交易一样
两个完全不同的行业，数据格式要求精度以及来源什么都不一样
如果死搬经验就是邯郸学步
而我总是把火车票的买卖跟飞机票的买卖做比较
因为我相信，飞机票跟火车票的买卖是类似的
股票的交易还有web公司平台，都不是一回事
因为数据格式不一样，要求也不一样，差别很大
所以最好的办法就是参考飞机票的买卖，而不是淘宝等web公司
也不是股票交易市场的系统
如果真想做这个系统，最先应该做的是了解一下现有火车票的数据格式是什么样子的
而不是假设这个数据格式应该是某一种格式
就这么大的系统而言，在短时间内
往往是连最简单的数据格式的转换都几乎是个不可能完成的任务
更不要说重新构建一个有向图，再读到内存中去了 |
|
z****e
发帖数: 54598 | 49 如果你拿到这个需求
你第一反映是什么？
我的第一反映是，我需要了解一下当前的it系统是怎么运作的
尤其是数据格式，是怎样的，然后再根据当前系统提出后续处理的方案
对不对？
但是，这个最基本的问题，魏老师是不考虑的，因为这是别人的问题
然后是魏老师的新的数据格式
那么一个很本能的问题：如果你要新构建一个数据结构，那么如何保证旧的数据结构
平滑地过渡到新的这个数据结构中去呢？还有如何保持新旧数据一致呢？
我相信在铁道部几十年的建设中，他们肯定会有那么一套现存的
而且运转得相对不错的it系统在运作，那么他们的数据肯定有一个存放格式
而且更重要的是，这个核心的数据存放，外面会有相关依赖于这个数据格式的系统
很正常嘛，你现在打开随便一个运作十年以上的公司的数据库schema
哪个不是密密麻麻跟蜘蛛网一样的各种关联关系？
一个破公司尚且如此，更何况铁道部
那你认为，做一个哪怕是最简单的parse工具，去parse现有的各种数据格式
是不是都很难？更不要说重新构建一个新的数据格式了
所以估计铁道部网站就是在这个数据格式外层，再单独做web server
然后跟现有的数据格式做一个衔接，以这种方式来先... 阅读全帖 |
|
z****e
发帖数: 54598 | 50 就是假设现有it系统不存在
需要一个从无到有的过程去实现一个售票系统
而实际上现有的售票系统肯定存在
要不然售票处难道是手工售票？
而且新的系统必需兼容现有系统
而不是对现有系统做一个革命性的改造
换句话说，如果要制作有向图读入内存的话
那现有的系统该怎么改造？
怎么保证两个系统内存里面的数据是一致的？
就这么一个问题，魏老师就没考虑
总之就是各种不考虑，遇到问题就是别人的问题 |
|
