247. 有10个unsorted array, 分给10太不同的机器处理，这10台机器之间不能通信，但可以和总机通信，如何求总的median. 如何减少数据量的传输。

TO LEARN, 设计题

248. You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create another array ar_low[] such that ar_low[i] = number of elements lower than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0} Time complexity : O(n) use of extra space allowed.

等价于前面一个求逆序对的题的吧，感觉不可能做到O(N),

249. 给一串数字（比如说1，4，10，22，30，表示4个区间：[1，4]，（4，10]，（10，22]，（22，30]）。现在给很多个数字，要设计一个快速算法，能用最快的速度告诉那些数字分别落在哪个bucket那里。比如说前面这个例子输入double数13，算法返回string: “(10,22]”；输入double[]序列13，8，25，返回string[] “(10,22]” “(4,10]” “(22,30]”

TO LEARN， INTERVAL TREE

250. Given Numerator and Denominator. After division you might get a recurring decimal points float as the answer. You need to identify the recurring part For example 23.34563456 … return 3456

CODE

251. A positive integer is said to be square free if it is divisible by no perfect square larger than 1. For example, the first few squarefree numbers are {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, …}. Find the nth smallest squarefree number. Note n can be very large such as 1M.

先找出sqrt(n)以内的所有质数。。再想想

252.判断一个string是否是某个pattern的周期循环

TO LEARN，后缀树？

253. 在一个N Dimensional 的正方形里面，Assume the top right point is (n,n,…. n) and bottom left point is (0, 0, 0…. 0), given any point in the cube, find all the paths inside the cube to the (n, n,…n) around it, change its value to 1. Otherwise, mark its value to 0 (cannot recall exactly anymore). how to do it. Given a very big such matrix and n computer, how to do it efficiently. Assume each computer has very limited memory, how to do it.

TO LEARN

254. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个数组排序

TO LEARN, Shell排序？

255.两个线段数组，求common区间 A［1，5］［10，15］B [3,12] return [3,5],[10,12]

TO LEARN, Interval tree

256. minimum window cover

TO LEARN

257. Given a sorted array of n integers, pick up k elements so that the minimal difference between consecutive elements is maximal (that is choose the elements to maximize the quantity min(a[i+1] – a[i]))

DP题，写递推公式