r*******k
发帖数: 1423 | 1 你是说，边界也可以随便乱转?
不过还是没太明白为什么一定有解
另外，这个跟dijkstra应该没啥关系啊 |
|
y***n
发帖数: 1594 | 2 For unweighted graph, dijkstra is essentially BFS |
|
a***n
发帖数: 623 | 3 不能dijkstra吧，原题说“you can only go straight from the previous direction
, unless you hit an obstacle.”，还是BFS。 |
|
c*****n
发帖数: 53 | 4 dijkstra也行，但不能改变时间复杂度，n*m matrix一样是O(n*m)
direction |
|
y***n
发帖数: 1594 | 5 讲一讲dijkstra如何保持“you can only go straight from the previous
direction”把. |
|
r*******k
发帖数: 1423 | 6 第一个题，是双向dijkstra搜索么？
从s走2步
t走1步
是n^2级的
判断是否有正反向都搜到的节点
距离
，并
.. |
|
g*********e
发帖数: 14401 | 7 maxflow mincut
dijkstra
a*
interval tree
btree
然后看几个典型的npc问题
概率 随机过程 |
|
l***i
发帖数: 1309 | 8 5分钟写dijkstra不用他，我都能写。要是几个月之前写bipartite matching都没问题。
他的blog我看过，水平在那儿摆着呢，板上骂他的这么多，有几个能写个code search
在google里面给上万engineer用的。大家要骂人也就事论事，说说他在技术上有什么不
足，或者他的那些关于programming language的论点有什么不对的，人身攻击就没意思
了。不是只有ken thompson这种才可以说自己是牛人的。 |
|
s*****r
发帖数: 108 | 9 现在大家都知道 Avenssi 是什么水平了
一开始拿 Github 没有一个老外 follow 这种东西说事 后来发现自己眼神不太好删帖
改改说辞
然后又拿他不写英文博客这种东西说事 后来又发现自己错了
然后又来说市面上没有他的东西 这似乎是有点分量的东西 结果又说错了
然后又说“他自称是世界上最伟大的程序员”请给找出这句话来
然后用 SQL 写 dijkstra 自己 Google 就好了 又不会
还有就是说屎说 SB 比较在行
请不要继续暴露自己的水平了
另外被 Google senior staff engineer & manager 推荐说是见过的最聪明之一，20
年来和 intern 合作最有技术含量的 project 在一些人眼里就不值一提 |
|
l***i
发帖数: 1309 | 10 5分钟写dijkstra不用他，我都能写。要是几个月之前写bipartite matching都没问题。
他的blog我看过，水平在那儿摆着呢，板上骂他的这么多，有几个能写个code search
在google里面给上万engineer用的。大家要骂人也就事论事，说说他在技术上有什么不
足，或者他的那些关于programming language的论点有什么不对的，人身攻击就没意思
了。不是只有ken thompson这种才可以说自己是牛人的。 |
|
D****3
发帖数: 611 | 11 wangyin说的sql写dijkstra最短路径
lol 娱乐下 |
|
w***n
发帖数: 58 | 12 linear schedule 都可以planar graph 然后dijkstra 每个edge weight 就是end
vertex weight |
|
r*****e
发帖数: 30 | 13 终于知道为啥没过了
原来换乘站A和B之间走的时间还可能不一样，而且要用最少的走路时间，用floyd和
dijkstra做了，都能过
本来是道很不错的题，这个坑实在是无语，太无厘头了 |
|
r****7
发帖数: 2282 | 14 只求两点间距离，而且都是正数，为啥不直接dijkstra |
|
m********t
发帖数: 13072 | 15 下面我给出的list上的内容，都属于基本常识，无论对方考不考，你都应该了解优越性
和弱点的, 术语中文我不太会说
我脑海里能想到的（有很多我暂时没想起来的，不等于你就不该掌握了）
topological sorting
direct acyclic graph
relaxation method
floyd-warshall
Dijkstra's
Prim
Bellman-ford
Strongly/Weakly connected components
depth/breadth first search
Minimum spanning tree
and so on , heap, binary heap, B-tree, BST, linked-list
所有这些东西，无论考不考，你都该已经知道了，才可以预约面试
刷题是没什么本质性作用的，你刷了200多道题，很可能都是tree structure的，其他
部分没刷到，就傻眼了
除此之外，你要掌握scheduling的相关知识，
然后再去学一些常见的机器语言，C＋＋或者java，这才是正确的学习顺序
一上来就用IDE/eclip... 阅读全帖 |
|
t*****a
发帖数: 106 | 16 多谢。不过面试真没准，有的人就瞎问。我CV上没写任何data base，file system还被
人问过I-NODE, D-NODE，以及如何实现。写Dijkstra算法，让自己实现heap(这个还好)
，然后再解释A*。
key |
|
|
T*******h
发帖数: 112 | 18 恩,topological sort是计算机数据结构的基础图论算法,和dijkstra程度差不多，反而
动态规划啥是相对高级的，LZ如果继续面偏CS的职位或许可以在多弄熟点数据结构那块。
不过，LZ作为统计学生已经面的是machine learning scientist，感觉专业知识应该更
重要吧。。。。。。 |
|
n*****5
发帖数: 984 | 19 跪谢板上国人内推orz。在吃饭的时候还有国人MM给我加油...还是挂了 lol
一轮电面
1.If database need to be scale up, how to scale up database tables.
What if sql querys can not handle what need to do?
2. How to test your query whether it is right or not. How to run the
testcase? ..
3. Word Break II
面试：
1 Code at computer : Pronunce 123 212 312 → into one hundred twenty-three
million ….
2. Design question : given series of jobs, if timeout figure out which job
may be the key point of the series job.
He suggested using heap to find ... 阅读全帖 |
|
|
b*****n
发帖数: 618 | 21 这个题目转化一下，就是一个图里求最短路径。
如果A和B相邻，那么A和B之间有一条边相连，假如B是1，那么从A到B的边weight就是1
，否则weight是0，所以最基本的想法就是dijkstra
不过这个是可以优化成breadth first search的，如果知道一个值为1的点的最短路径
，那么从这个点出发BFS/DFS可以到达的所有0的点其实跟这个点的最短路径是一样的，
所以可以直接把这些点放到queue里面就行了，breadth first search的当前queue里面
是当前最短路径的所有点，这样一层一层遍历就行。时间复杂度O(n)，n是矩阵的大小 |
|
s********7
发帖数: 200 | 22 之前在这个版发过两次帖子，得到很多意见，也因此转了CS
一亩三分地有好多提供内推的帖子，发了10多个，只3个回复的。
先问一个问题，我现在身份是统计的，做cs的实习有没有问题？
自我介绍：
我叫宋洋，本科学的金融学，罗格斯大学二年级硕士，现在希望找个16年的暑期实习，
希望做码农类和数据科学类的工作，我的专业是统计学，因为觉得计算机的机会多自己
又很喜欢，所以下定决心在修计算机的双学位，14秋季入学，因为双专业需要修课比较
多，所以预计16年末毕业。
会用R,SAS,JAVA,PYTHON,SQL，水平是自己看书学习，上公开课，加上做学校的课堂作
业。我有着很不错的统计学基础，例如概率论，回归分析，数据分析，和多元回归分析
，统计推断，做过相关10多个项目。计算机方面在Udacity上学的java和python，做了
上面的作业和项目，平时做AI 和数据库作业时候也会用到这两种语言，上过算法课，
懂得DFS,BFS,A*,Dijkstra等算法，并打算这个冬天刷leetcode的题。统计学课堂上做
过很多应用项目，都需要用R，SAS编程读入输出数据，画图表及分析和写报告。英语听
说能力... 阅读全帖 |
|
e********t
发帖数: 144 | 23 我是学工程的背景，做行业软件，具体的产品开发
了解类似机械电子土木行业软件的同胞都能理解，反正是在单机上跑，比如photoshop
就是个经典例子，当然人家现在也“互联网”了。对应地，我们这些人力资源也需要
Change, 原有知识基本过气。
基于自己经历，简单地写写，非科班专用，科班生见笑了。
1. 非科班生如何上路基础知识。
工科大学生其实也修过计算机的课程，不过很肤浅罢了。在做工程软件的时候，我
们的强项是领域知识。但是很多人确实地需要补补计算机方面的课程了。
先说数据结构和算法课程。很多教材光讲原理和伪代码，学习了以后会出现“眼高
手低”的现象。
推荐几本代码驱动的数据结构书籍，当然它们不一定是最好的书，但是确实是“有
码可依”
- 喜欢C语言的建议读 : "数据结构C语言版(台湾)-陈峰棋"
这本书难度不高，但是全程教学案例是完整运行的C代码，比如 dijkstra 寻路，
Toplogy 排序，通过debug可以让读者明白到底“idea”是如何变成“code”的。网上
有scan下载。
- 喜欢java的推荐"data stru... 阅读全帖 |
|
y*********e
发帖数: 518 | 24 想了下，这个题用greedy算法解。有点类似dijkstra算法求最短路径。
首先用一个priority queue来装已经发现的字符串，按照字典序排序。
比如输入是cbacdcbc，
scan到了第三个字符的时候，p_queue里面只有一个值 cba。
当scan到第四个字符c的时候，有了重复。这个时候有两个选择：
a. 把 c 从 cba 里面删除，变成 bac。
b. 不理会新遇到的 c，还是 cba。
把a选项和b选项再重新丢回p_queue。
如此重复一直到字符串结尾。返回p_queue的第一个值。因为p_queue是一个按照字典序
排好的priority queue，所以返回的结果一定就是答案。
伪代码如下：
let q = p_queue
for each c in string:
let s = q.empty() ? "" : q.dequeue()
if not c in s
s += c
q.push(s)
else:
s1 = del c in s
s1 += c
q.push(s)
q.push(s1... 阅读全帖 |
|
Y*********d
发帖数: 47 | 25 我试了一下用Dijkstra把从银行0到其他每个银行的最短路线算出来，然后把银行1到银
行K的所有最短路线上的非末端节点银行从1到K里面剔除，剩下的应该是只有一个司机
去过的银行，凡是最后到达这些银行的司机，肯定在某段路上单独行驶过，那么这些银
行数量就等于不安全行驶的司机数量。但是运行一些test case出来的结果总是比题目
的expected output要来的大，有没有牛人来指点一下应该怎么做？小弟在这多谢了啊
！ |
|
Y*********d
发帖数: 47 | 26 好像不对吧，司机都要走最短路线，而且司机的所有目的地必须是1到K的银行。这样的
走法每个司机不一定是最短路线而且不一定到指定的目的地，还是需要用Dijkstra算法
算出从银行0分别到 银行1，银行2，...银行K的最短路线吧，然后从这些最短路线里看
哪条路段只有一个司机走过？ |
|
Y*********d
发帖数: 47 | 27 要在所有司机都开最短路线的前提下，使得单独开车的司机数量最少，对应于每个
input, 这个数量应该是固定的。
Dijkstra的算法除了算出0节点到i节点的最短路线距离外，还会记录在这个最短路线上
i节点的前一个节点是什么。我的理解是，既然有K个司机最终分别到达1节点至K节点，
那么从1节点到K节点中，剔除那些作为前节点出现过的，剩下的应该是只有1个司机访
问过的节点，也就是那个司机单独开过到达此类节点的路段，所以剩下的节点数量应该
是单独开车的司机数量。但是我的结果在大多数test case上运行都比标准答案大，不
明白这个算法错在哪里。
原题：
There are R bank locations and there are K drivers to transfer deposits to
those locations. R >= K+1 and all bank locations are numbered from 0 to R-1.
Location 0 is the branch where all drivers start at time 0 and take t... 阅读全帖 |
|
i******t
发帖数: 22541 | 28 这个用最短路径计算不就完了dijkstra shortest path
作 k 次 不久完了？ |
|
c********t
发帖数: 5706 | 29 来自主题: JobHunting版 - 面试题求解 dijkstra's algorithm
shortest
be
you |
|
r*****s
发帖数: 1815 | 30 RMQ模版背得不熟
LCA就写不快
Tarjan不写了，烦，还是去搞dijkstra变种了。。 |
|
r*****s
发帖数: 1815 | 31 然后我一个刷盘子的会dijkstra。。。
: 太厉害了
: 我记得保洁阿姨都会算张量。。。。
: 门卫安徽河南的小保安巧用斯特林公式以及扩散方程。。。。
|
|
f****e
发帖数: 923 | 32 我怎么感觉如果你年轻的时候刷过题,而且刷的很好,也不会很快忘掉, 题目套路就那么
多,虽然题目数量在不断增加
我两年前开始刷题, 感觉dp和 递归非常难理解, 现在感觉容易很多
刷题难度不是经验积累吗?
为什么lc竞赛的前几名, 经常半个小时能写完4道题, 我经常两三道, 有些题目还看不
明白的原因
我不相信我未来5年之后会忘的一干二净
本人除了刷lc, 为了准备面试刷了不少公司面经,现在总共累计起来有1000多道题目了,
感觉是虽然题目数量是越来越多,但是对我个人总体而言,题目没有之前感觉那么难了,
因为套路熟悉了, 定期参加lc 竞赛, 最好的成绩是14, 最差的好几百名
本人30+, 是穷N代,国内只有几亩薄田
本人 准千老(因为博士毕业之后没找到博士后, 汗), 转读 cs ms, 刷题两年多, 海投
500多
份简历, 电面20个左右, 大小公司都有, on site 4个, offer 2 个, 全部考刷题为主,
少量behavior
, 我的个人体验是, 不能很快做出题目的, 基本都挂.
贴一个startup的面试, 可以参考一下, 如果不是lc 刷的熟练基本就挂了, 电... 阅读全帖 |
|
发帖数: 1 | 33 乖乖，dijkstra都出来了，下次是啥？floyd？ |
|
z*********n
发帖数: 1451 | 34
我上次面O家时，code完两题，面试官没得聊了，临时想题目，可能有点尴尬加过度紧
张，急中生智来了句给我讲讲dijkstra吧。讲完还不过瘾，你再给我证明下正确性？。
。。 |
|
i*****9
发帖数: 3157 | 35 Dijkstra 还算好证吧，我上次被要求证明minimum spanning tree 的算法正确性。
：
：【 在 yizhongxunhu (刷题转码 工资翻倍) 的大作中提到: 】 |
|
z*********n
发帖数: 1451 | 36
都是贪心，思路一样，都是反证，都不难。不过这俩非要比，显然还是Dijkstra难点。
MST这个算法太直白了。 |
|
|
|
z*********n
发帖数: 1451 | 39 以前还做过Dp on Graph呢，外层是遍历所有节点循环，内层是对每个节点用Dijkstra
更新新值，最后找到最优。好像是个大湖什么的题，记不清了。 |
|
发帖数: 1 | 40 去年的fb hackercup好像也有一道类似的，不过是Floyd做预处理，具体题目忘记了
Dijkstra |
|
s********e
发帖数: 893 | 41 多谢BJD补充。
我来试着解释一下啥叫save distance like a graph。Graph是离散数学里的一个概念
，学计算机的应该都多少接触过图论。比方说有5个城市，有的城市是直接相连的，有
的不是。那数据存放时，可以5个城市（结点）存一个array里。每个城市和它邻接的城
市和距离也存在一个array里。比如5个城市V=(A,B,C,D,E). 距离存放在E={(A,B,150),
(A,D,200)， （D,E，100）...}. 现在你想计算从A到E，有可能有多种path，有多种
算法来计算哪个最短。那个著名的Travelling salesman problem就是解决这个问题的
。常见的有基因算法，模拟熄火等，还有路由器里用的Dijkstra's algorithm。你说的
这个人估计就是用的这个原理。也就是他说的不是随便run 一个sql query就能解决的
，因为数据不是按照关系型数据库的方式来存放的。 |
|
a****b
发帖数: 3588 | 42 【 以下文字转载自 Joke 讨论区 】
发信人: ici (艾西), 信区: Joke
标 题: 这就是传说中让理科生沉默，让文科生落泪的文史综合题
发信站: BBS 未名空间站 (Wed Apr 13 14:53:41 2011, 美东)
程序员文史综合题目一，选择题（皆为单选）：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，java script ；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？
a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。
6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪
一种？
a，神经网络；b，遗传算法；c，... 阅读全帖 |
|
O**l
发帖数: 12923 | 43 算法自动化设计 核心理论是formal method
用的是 dijkstra weakest precondition， loop invariant...
和尼玛AI 关系不大 |
|
l*y
发帖数: 21010 | 44 是这样的，我研究生期间实现了一个算法，是一种平行dijkstra的算法，大概意思是这
样：
地图上，有好几个小人，分别位于不同的地点，这个算法能在很短时间内，给他们安排
出一个相遇的地点，使得这个地点到他们初始位置的路程之和最小。
这个地图是OSM（Open Street Map）上拿下来的真实地图，路程也都是真实的道路。小
人的数量可以任意多，地图可以任意复杂。以后还可以加上考虑限速啊、交通拥堵状况
什么的，这些都能handle，只要有数据。
我现在能想到的这个玩也的用处就是，比如说我们家租房选地点，要离我和老婆的上班
地点、孩子的学校、mall、医院什么的都近，那就用我这个程序找。
我毕业很多年了，现在就是个屌丝程序员。我想发财，你们能不能帮我想想我这个玩还
有什么实际用处，我能不能靠它发点小财？因为我目前还没看见哪个网站有提供这个功
能的。一次性卖给哪个大公司也行呀。 |
|
A**A
发帖数: 3392 | 45 哈哈，这个好玩
我试试看：
1，a,伏羲
2，b,数组
3，c,java, javascript
4, a,递归
5，d,Dijkstra 算法
6，
7，d,不会定义自己的需求
8，c,衍生类未重载
9，a,继承
10，c,统一接口 |
|
G***Y
发帖数: 9698 | 46 转载自“侨报周末”
苹果活动看板(2012-08-12)
发布于： 2012年8月13日 星期一 13:56
戏剧 表演
★★★★★无线电城太阳马戏团表演（Zarkana by Cirque du Soleil）。8月8日至9月
2日。地点：无线电城（Radio City Music Hall）。地址：50 W44th St., NY, NY
10036。票价：59-230元。电话：212-626-2680。网站：www.radiocity.com。
★★★★免费电影《夏娃的诱惑》（All About Eve，2000)，8月12日晚上天黑时放映
。草坪5点开放。1950年的老电影，时长：138分钟。地点：曼哈顿布莱恩公园（Bryant
Park）大草坪。交通：地铁Times Square站。电话：212-620-0619。网站：www.
bryantpark.org。
★★★赛德尔·沃尔顿五重奏（Cedar Walton Quintet，w/Steve Turre and Willie
Jones III），8月14日-19日。地点：林肯中心爵士乐演奏厅（Jazz a... 阅读全帖 |
|
t**********g
发帖数: 3388 | 47 【 以下文字转载自 Joke 讨论区 】
发信人: ici (艾西), 信区: Joke
标 题: 这就是传说中让理科生沉默，让文科生落泪的文史综合题
发信站: BBS 未名空间站 (Wed Apr 13 14:53:41 2011, 美东)
程序员文史综合题目一，选择题（皆为单选）：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，java script ；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？
a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。
6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪
一种？
a，神经网络；b，遗传算法；c，... 阅读全帖 |
|
b*******y
发帖数: 12791 | 48 我觉得一视同仁才是不歧视啊。
既然没人提 Dijkstra是异性恋，为什么一定要提图灵是同性恋呢？他们的性取向和计
算机发展有关系吗？
难道被认为是弱势群体，就是不被歧视吗？ |
|
b***e
发帖数: 4591 | 49 原创： LeftEye
（上部）
今天开始八迪爷爷。谁是迪爷爷？就是那个和老婆和咖啡，一不小心喝出了个最短路径
算法的Edsger W. Dijkstra爷爷。之所以想起先八他，是因为他在很多方面是高爷爷的
死对头，当然，不是在个人恩怨方面，而是学术观点方面。
现在先忙去了，看下午下班前能八两段不。。。
二. 迪爷爷
坑待填...
和NND一样，迪爷爷名字的发音也困扰了我将近半年，每次和同学谈到迪爷爷，我都是
含混其词，或者用the creator of the shortest path algorithm来代替。和NND不同
的是，我倒没有以为迪爷爷是印度人，我以为他是德国人，因为我当时的印象里，德国
专产数学和物理大牛，像爱爷爷和冯爷爷（不是咱们的冯帅哥，而是说冯.诺伊曼）。
第一次听说迪爷爷，当然是在学习迪爷爷的最短路径算法的时候，当时的印象就是：这
厮真TMD聪明！怎么想出来的？当然，那个时候是我最初接触算法这个概念的时候，所
以难免大惊小怪。事实上，迪爷爷算法虽然可称得上是最短路径算法的一个里程碑，但
确实是迪爷爷的妙手偶得而已。据迪爷爷自述，那个算法是他和迪奶奶在一家咖啡 |
|
e****a
发帖数: 4783 | 50 我每次写
int i,j,k;
的时候，都想：
1.这是对fortran的致敬
2.这是对Dijkstra的致敬 |
|
