（今日完成：Two Sum, Add Two Numbers, Longest Substring Without Repeating Characters, Median of Two Sorted Arrays, Longest Palindromic Substring）
恼人的median of two sorted arrays
前几年google的必考题，现在考的比较少了，思路就是binary search，具体来说，
- 如果是一个array，因为是sorted，找到第k个元素是trivial。如果2个array，可以把一个array B作为pivot而搜索另一个array A是否有第k个。因为已知array A中第ith，找array B中(k-i)th也是trivial的。
- 如果在array A中没找到，再交换两个array重新搜索。
- 这题恶心在corner case。找到的条件是A的第ith在B中k-1-i-1和k-1-i之间。另外两种情况是<B[k-1-i-1]和>B[k-1-i]。具体见code，建议大致明白三种情况后死记binary search的条件，反正过不久就忘了，呵呵。
google曾经的面试题是这个的简单扩展：如果给定两个数组中的某一个数，找到离这个数第k近的数。直接用binary search找到这个数后确定次序k’，然后用上面的方法找到第(k+k’)th
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
def median(nums1, nums2, low, high, k):
if low>high:
return median(nums2, nums1, 0, len(nums2)-1, k)
i = low+(high-low)/2
j = k-i-1-1
n = len(nums2)
if (j<0 or (j<n and nums1[i]>=nums2[j])) and (j>=n-1 or (j+1>=0 and nums1[i]<=nums2[j+1])):
return nums1[i]
elif j<0 or (j+1<n and nums1[i]>nums2[j+1]):
return median(nums1, nums2, low, i-1, k)
else:
return median(nums1, nums2, i+1, high, k)
n1,n2 = len(nums1),len(nums2)
if (n1+n2) & 1 == 1:
return median(nums1, nums2, 0, n1-1, (n1+n2)/2+1)/1.0
else:
return (median(nums1, nums2, 0, n1-1, (n1+n2)/2)+median(nums1, nums2, 0, n1-1, (n1+n2)/2+1))/2.0
这题还有个分布式的版本: n个data分布到s台机器上去做
https://www.quora.com/Distributed-Algorithms/What-is-the-distributed-algorithm-to-determine-the-median-of-arrays-of-integers-located-on-different-computers
- 就是master/slave的结构。
- analysis：
- 基本framework: 两个元素：单机上的量（O(n/s)），多少轮（O(log(n/s))：因为单机每次减半，那么这么多轮后就空了）。
- 多少台机器不是考虑因素：如果s台机器并行，假设同时进行，这样和一台的时间相同。
- 注意每台机器上可以先排序，也可以不排。不排就是O(n/s)
- 结果：O(n/s)+O(slog(n/s))
- O(n/s)：单机slave的总运算，superisingly，竟然和第一轮是同一量级的。主要利用1/(20)+1/(21)+...+1/(2^log(n/s))≈1。
- O(slog(n/s))：master的总运算量：每次都是从s机器上得到一个数量值，然后轮数。
- 基本framework: 两个元素：单机上的量（O(n/s)），多少轮（O(log(n/s))：因为单机每次减半，那么这么多轮后就空了）。