J*****n
发帖数: 4859 | 1
Kadane算法知道吧，那个是用来求最大连续和的。
你把初始数组相邻的求一个差，再对得到的新数组用Kadane，所得的就是最大的差。
不过Kadane是有顺序的，也就是总是用大下标去减小下标。所以你还要从右往左的在用
一遍。
得到两个最大差（左——〉右，右——〉左），比较一下就可以了。
空间和时间都是线性的，如果你不要原数组了，那空间就是O(1)。 |
|
j**l
发帖数: 2911 | 2 当前各大IT公司的面试题，基本就是考察名题，或者稍加修改和包装。所以准备名题是
很有必要的。
但是，现场面试的时候，如果面试者A事先看过做过这道名题，他就可以游刃有余的和
面试官探讨，可以故意先给个通常的解法，不需要提示就能够迅速写出简洁正确的代码
。于是面试官给了他高分。反观面试者B, 他的算法和思考能力实际都强于A。可惜他只
坚信万变不离其宗，宁可自己想出来怎么做。他没有看过和准备过那道名题，结果给面
试官的表现是:
这个人可以做出这道题，可惜用到了一些提示
这个人可以做出这道题，可惜花费了过多时间
这个人可以做出这道题，可惜结果不是最优
这个人可以做出这道题，可惜一开始走了弯路
这个人可以做出这道题，可惜。。。
于是A拿到了offer, B收到了"Thank you for apply"
很多名题的解答看起来简单，但第一个吃螃蟹的人就不简单
比如测试链表有环的Floyd算法（龟兔赛跑，快慢指针)
比如Maximum sum的Kadane算法 (题目提出两年后才被天才的Kadane在CMU举行的一场研讨会后几分钟内就提出线性的解法，成为现在面试必考的经典题目)
没看过名题的人，能够 |
|
|
w****j
发帖数: 5581 | 4 字面上看, Freemasonry，就是自由石匠工会啊。石匠的工具是啥？不就是尺规么?当然
各个分支组织正式的解释就各有不同了。4000BC这事情就是 anno lucis,拉丁文就是in
the year of light。我觉得就是来自圣经的创世纪吧。此纪年称为Ancient Craft
Mason Masonic calendar。Freemason的仪式里面有King Solomon's Temple。所以，一
些历史学家也致力于把Freemason的起源和圣殿骑士团联系起来。圣殿骑士团的英文全
称是The Poor Fellow-Soldiers of Christ and of the Temple of Solomon。Knights
templar可是无数西方传奇故事的源泉啊。这帮家伙就是太有钱了，于是后来被缺
钱的法王Philip IV和教皇Clement V给合伙做掉了。于是圣殿骑士转入地下，这倒也和
Freemason的地下运作方式吻合。当然，这不是一个必然的解释。法王1307年开始动手逮捕圣殿骑士，1312年教皇正式宣布解散骑士团。有意思的是1314年大骑士Ja... 阅读全帖 |
|
w****j
发帖数: 5581 | 5 Peter Jackson叙述入侵匈牙利也说是5路，不过具体情况和元史大不同。我看到他引了一
些现代蒙古史的论文，当为近来比较主流的认识。根据他的叙述，我做了一个地图。截
图见附件。红色地名是我特别加注的。1-4红色箭头是蒙古军队行军的大致路线。4号路
线特别粗一些，因为这路的具体地理位置不清楚，而且包括了两路军队。
总结如下：
1. Orda 斡儿答 - 朮赤系 和Baidar 拜答儿 - 察合台系
这路进入波兰为的是分散敌人的兵力为主力减轻压力，Legnica之战算是超额完成任务
。Legnica大胜后向南通过Moravia（摩拉维亚）一路劫掠，一度攻击多瑙河左岸一些城
市，包括维也纳北边的门户城市Korneuburg（地图上看离维也纳可是真够近的）。
Jackson在这里引了奥地利国王Frederick II和Constance主教Henry之间的通信。所以
这一路的时间和路线应该说是比较清晰的。
2. Batu 拔都 - 朮赤系老大和Subutai 老将速不台
3. Qadan(又做Kadan) 哈丹 - 窝阔台系 和 Buri 不里 - 察合台系
这两路都是从匈牙利的东方屏障... 阅读全帖 |
|
|
d**z
发帖数: 3577 | 7
你作为军版的常驻疣托就别装了。
当年米国驻雅加达的大使就是米疣。
许多互联网关于这方面的史实都被封了。
不过后清国今天情况非常相似米国。
今天要颠倒黑白篡改历史比过去容易。
因为搜索机器全被米国掌权族裔控制。
现在已经把五十多万篡改为二十五万。
http://www.namebase.org/kadane.html
过几年华人被屠人数就会变成不到十万。 |
|
r**u
发帖数: 1567 | 8 check kadane's 2d algorithm |
|
r**u
发帖数: 1567 | 9 2. check kadane's 2-D algorithm |
|
x***y
发帖数: 633 | 10 来自主题: JobHunting版 - 求解算法题 This is a 2D-Kadane problem, O(n^3)... BTW, do you have the pdf of that book
? All I found in the internet is incomplete..thanks.... |
|
k***u
发帖数: 42 | 11 http://en.wikipedia.org/wiki/Maximum_subarray_problem
Kadane's algorithm consists of a scan through the array values, computing at
each position the maximum subarray ending at that position. This subarray
is either empty (in which case its sum is zero) or consists of one more
element than the maximum subarray ending at the previous position. Thus, the
problem can be solved with the following code, expressed here in Python:
def max_subarray(A):
max_so_far = max_ending_here = 0
for x in A: |
|
s*****9
发帖数: 303 | 12 从来没看过这俩题，第一题没做出来，第二题很简单嘛，Kadane也没啥牛的。 |
|
V*********n
发帖数: 198 | 13 Jay Kadane 到底有多有名。。。
今天刚听过他做的演讲，感觉思路很清晰，语气很大。是个牛人，但不知道有多牛。 |
|
|
j**l
发帖数: 2911 | 15 开国大老级吧。
另外，像Floyd的龟兔赛跑算法检链表的环，以及Kadane的经典Maximum Sum，事后看起
来都很简单，比这题要好理解的多，代码也很短。就看你是不是第一个想到的人。 |
|
J*****n
发帖数: 4859 | 16 对sequence取差，然后用Kadane Algo，从头到尾，再从尾到头的各用一遍就可以了。
时间复杂度是线性的。 |
|
x***y
发帖数: 633 | 17 old question, you can check 2D-Kadane algorithm... |
|
|
e*****3
发帖数: 610 | 19 的确不是每个算法都是论文级的。象这个MAXIMUM SUBARRAY的算法应该算是超级简单
的吧？可是
WIKIPEDIA上还留下了发现者的大名，说明在没发现之前想出来还是不容易的。面试的
人指望你没见
过又能在30分钟里想出来，在白板上把CODE写出来？这样是不是太虚伪了？
http://en.wikipedia.org/wiki/Maximum_subarray_problem
The problem was first posed by Ulf Grenander of Brown University in
1977, as a simplified model for maximum likelihood estimation of
patterns in digitized images. A linear time algorithm was found soon
afterwards by Jay Kadane of Carnegie-Mellon University (Bentley 1984). |
|
K*******i
发帖数: 399 | 20 如果准备不充分，经典题也会翻船的。我先贡献一个。
经典的数组求连续元素的最大和(Kadane算法)，面试官是老印。
我当然很快就写出那个标准的O(n)解法，但这个解法在所有数都为负数的情况下返回0
。老印随后要求所有数都为负数的情况返回最大的那个负数，我马上给了如下方法：
// step 1, 判断是否全部是负数，如果是，设置flag
for (...)
{
}
// step 2, 如果flag为false, 最初的解法
for (...)
{
}
// step 3, 如果flag为true, 遍历寻找最大的负数
for (...)
{
}
虽然我和他说了，这个三次循环是并列的，整体复杂度其实还是O(n)的。但老印显然非
常不满，问我能否减少为一个循环。我思考了一下，又给出方案如下，
在最初的解法的一次循环里头增加一些操作
bool all_neg = true;
for (...)
{
largest_sum还是用最初的解法更新
用一个变量largest_neg keep当前最大的负数
如果有非负的数, all_neg = false
}
if (all_neg... 阅读全帖 |
|
O******i
发帖数: 269 | 21 题目很水，就是那个泛滥的maximum subarray sum (1D array)的题。
Gayle可是一上来各种自我介绍都免了直接问这题。也不知道那个白人老兄是真没见过
这题的O(n)解法还是故意装不知道，反正吭哧吭哧费了好大尽用了很复杂的方法，然后
又一一否决。连我看的人都为他着急啊。
最后在Gayle的提示下，bingo! 在30多分钟的时候他终于想到了那个对大家来说都已不
是秘密的Kadane算法O(n)完成了白板代码并进行了test
不料Gayle的评价很高，说他的commnunication很好，对这个结果很满意。
要是换成我们，如果整个40分钟才做这一水题，或者不会做，或者后续问题做不好，早
让面试官鄙视了。
看来面试的主观性很大，关键是要遇到一个赞赏而不是鄙视你的面试官。 |
|
f*******w
发帖数: 1243 | 22 1. Throw twice until get head+tail or tail+head
2. No idea
3. Did this before. But cannot remember...
4. Two pointers
5. Kadane's algorithm
6. Binary search
7. Use Hash for dictionary?
8. Classic Top K
9. Prime: 2k+1, p^2 - 1 = 2k(2k+2)
10. No idea |
|
d********t
发帖数: 9628 | 23 来自主题: JobHunting版 - 烙印太烂了 Onsite面人的题找max subarray，周围的烙印没人知道怎么用Kadane Algo做，包括出
题的烙印manager。标准答案是对的，他们都看不懂。当然答题的烙印candidate也没做
对的，也不妨碍被录取。 |
|
a********9
发帖数: 129 | 24 之前稍微收集了一下
glassdoor
===================
edit distance
level traverse tree(高频）
1) Calculate the square root of a double（高频）
2) Given n intervals [si, fi], find the maximum number of overlapping
intervals.
3) Print all the paths from root to every leaf in a binary tree.
4) Print the sum of all the numbers at every vertical level in a binary tree
5) Given a set of n jobs with [start time, end time, cost] find a subset so
that no 2 jobs overlap and the cost is maximum ?
6) Given 1 trillion messages ... 阅读全帖 |
|
d********t
发帖数: 9628 | 25 绿皮书原题，kadanes algo
CC150
must |
|
I**********s
发帖数: 441 | 26 如果求最大的 B[i][j], 已有kadane函数 maxSubArray() 找最大连续子数组和，对最
大的 B[i][j]解法可以是：max( abs( maxSubArray(A) ), abs( maxSubArray( - A) )
).
现在求最小的 B[i][j]。暴力解法复杂度是O(n^2)。下面的方法可以做到O(nlog(n))
time, O(n) space: 先求部分和序列 S[i] = A[0] + A[1] + ... + A[i]，i = 0 to n
-1。所有n^2部分和可以由S序列中两项相减得到。对S排序，找相差最小的两项S[i], S
[j], B[i][j] 即得。 |
|
t*******y
发帖数: 637 | 27 2 画histogram？
3 kadan
-
summation? |
|
d********t
发帖数: 9628 | 28
嗯，奇怪的是绿皮书上没提算法的名字kadane |
|
w**********y
发帖数: 1691 | 29 google maximum subarray problem or Kadane's algorithm.
可以稍微改造写出一个O(n)的算法..
多年未用SAS了..依稀记得有scan这个函数..那么就可以遍历了...具体怎么写要问SAS
高人了... |
|
w******e
发帖数: 142 | 30 水木上看见的推荐列表，小多，呵呵。
入门：
Pattern Recognition And Machine Learning
Christopher M. Bishop
Machine Learning : A Probabilistic Perspective
Kevin P. Murphy
The Elements of Statistical Learning : Data Mining, Inference, and Predictio
n
Trevor Hastie, Robert Tibshirani, Jerome Friedman
Information Theory, Inference and Learning Algorithms
David J. C. MacKay
All of Statistics : A Concise Course in Statistical Inference
Larry Wasserman
优化：
Convex Optimization
Stephen Boyd, Lieven Vandenberghe
Numerical Opti... 阅读全帖 |
|
