前两天在体育中心候车，忽然听到一段音乐，还不错，记得几个歌词“为了那得到又失去的美丽”。百度一下，原来叫做让泪化作相思雨，这名字也太肉麻了点，名字不好。 /让泪化作相思雨/ 南合文斗/ 这是一片很寂寞的天/ 下着有些伤心的雨/ 这是一个很在乎的我/ 和一个无所谓的结局/ 曾经为了爱而努力/ 曾经为了爱而逃避/ 逃避那熟悉的往事/ 逃避那陌生的你/ 这是一片很寂寞的天/ 下着有些伤心的雨/ 这是一个很在乎的我/ 和一个无所谓的结局/ 再也不知道你的消息/ 再也不知道你的秘密/ 只有那熟悉的往事/ 只有那陌生的你/ 在那些黑色和白色的梦里/ 不再有蓝色和紫色的记忆/ 在这个相遇又分手的年纪/ 总有些雨打风吹的痕迹/ 为了那苍白的爱情的继续/ 为了那得到又失去的美丽 就让这擦干又流出的泪水/ 化作漫天相思的雨/ 为了那苍白的爱情的继续/ 为了那得到又失去的美丽/ 就让这擦干又流出的泪水/ 化作漫天相思的雨/ 这是一片很寂寞的天/ 下着有些伤心的雨/ 这是一个很在乎的我/ 和一个无所谓的结局/ 再也不知道你的消息/ 再也不知道你的秘密/ 只有那熟悉的往事/ 只有那陌生的你/ 在那些黑色和白色的梦里/ 不再有蓝色和紫色的记忆/ 在这个相遇又分手的年纪/ 总有些雨打风吹的痕迹/ 为了那苍白的爱情的继续/ 为了那得到又失去的美丽/ 就让这擦干又流出的泪水/ 化作漫天相思的雨/ 为了那苍白的爱情的继续/ 为了那得到又失去的美丽/ 就让这擦干又流出的泪水/ 化作漫天相思的雨/ 为了那苍白的爱情的继续/ 为了那得到又失去的美丽/ 就让这擦干又流出的泪水/ 化作漫天相思的雨/ 为了那苍白的爱情的继续/ 为了那得到又失去的美丽/ 就让这擦干又流出的泪水/ 化作漫天相思的雨/ 虽然也是有点口水歌的感觉，但还是比“擦干眼泪陪你睡”好，哈哈。

给定n个大小各异的立方体，这些立方体每一个面的面积在1-n之间，将这些立方体堆积成两个塔，问这两个塔的高的最小差是多少? 假定这个问题为a，有个变体问题为b，b是这样，给定1-n之间的n个数，如何把他分为两列排序数，要求这两列树各自的和之差最少。现在能想到的方法的结果是1。如果n为偶数，如1234，就分为14，23；123456就分为1 45，23 6。如果n为奇数，如12345，就分为12 5，34；1234567就分为12 56，34 7。这样方法是能够达到1的。不过问题a有所不同，比如，12 56和34 7，12是能够同时放在5上面的，同理，34是能同时在7之上的。这样，两堆箱子的高度之差就不是1，而是2。如此类推，12 5，34两堆箱子高度之差就是0。1 45，23 6两堆箱子高度之差就是0。

好久没有写写生活了。还没上班，无聊在广州购书中心闲逛，看到有一本书，以前想看的，《程序员面试宝典》，翻了翻，对于应届生面试似乎有点用。不过现在没兴趣了。本来想看看有没有SICP来着，果然，没有，真是失望。不过有另一本书，美国佬写的，《算法分析》，md，太贵了，80几块，不买了。又转了转，有本《数论初步》，就差点买了。还是懒惰战胜了求知欲。最后只买了个魔方，好久没玩过了，4块钱的，质量好差。上面说的那些书都和面试算法有关，还有些不错的网站，如http://www.techinterview.org 。 p.s. 说说现在暂住的地方，天河岑村。没有想象中差，不过比桂庙还是有差距，特别是下大雨，关键的路口老实积水，操。从岑村坐公车到天河体育中心要30分钟多点，也不算很久，因为是始发站，也是有地方坐的。明天上班。

用什么数据结构恰当的描述一个n阶魔方？用什么算法来把一个魔方还原？

不多说，贴图。

There is a link list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. http://www.ddj.com/dept/architect/184404464 //几种抽样方法. 1.2.1 水库抽样(reservoir sampling) 水库抽样方法 [21] 单遍扫描数据集,生成均匀抽样集合.令样本集合的容量为 S,在任一时刻 n,数据流中的元素都以 S/n 的概率被选取到样本集合中去.如果样本集合大小超出 S,则从中随机去除一个样本.可以证明,各元素的入选几率相同.文献[21]同时推荐了一个技巧来提高算法效率:在原算法中,对于流中的每一个元素都需要 “扔骰子”,判断该元素是否以 S/n 概率被选中;改进的算法转而判断一次需要略过多少个后续元素,从而大大减少了扔骰子的次数. 1.2.2 精确抽样(concise sampling) 在水库抽样方法中,样本集合中各个元素单独占据一个位置,即使它们具有相同的数值,因而表达的效率并不高.举例来说,假设元素 1 出现了 8 次,元素 2 出现了 1 次,则样本集合被表示为(1,1,1,1,1,1,1,1,2,…).精确抽样方法 [22] 改进了样本集合的表示方法.对于仅出现一次的元素,类似于水库抽样,仍然用元素代码表示;而对于多次出现的元素,则利用结构〈value,count〉表示,value 代表元素代码,count 表示样本集合中该元素的数目.这样,在精确抽样中,上面样本集合就表示为(〈1,8〉,2,…).很明显,精确抽样方法比水库抽样方法更节约空间.精确抽样算法维护一个初始值为 1 的概率参数 T,各元素以概率 1/T 加入到样本集合中去.如果该元素已经存在于样本集合中,则相应的计数器加 1(对于仅出现一次的元素,需要改由结构〈value,count〉进行表示,且 count 值为 2);否则,将该元素添加到样本集合中去.一旦样本集合溢出,改变参数 T 到 T′,T′>T.样本集合中的各个元素均以概率 T/T′ 被删除,从而腾出空间以便存放新数据.精确抽样方法通过逐步提高参数 T 的值,实现数据流上的均匀抽样. 1.2.3 计数抽样(counting sampling) 计数抽样方法 [22] 是精确抽样方法的一个变种.二者的区别在于样本集合溢出时如何处理.在计数抽样算法中,当样本集合溢出时,首先将参数 T 提高到 T′.对于其中的任意一个元素,都是首先以概率 T/T′,之后以概率 1/T′ 判断是否减去 1.一旦该计数器值已经降为 0,或者某一次随机判断之后计数器的值并没有减小,则结束对该元素的操作.计数抽样方法不是均匀抽样方法,但却能有效地获得数据集中的热门元素列

Two reverse sorted arrays A and B have been given. such that size of A is m and size of B is n. You need to find the k th largest sum (a+b) where a is taken from A and b is taken from B. such that k < m*n It can be done in O(m*n) but it can also be done in really optimal way.

给一个n长的数组，判断它是否为一个的全排列，要求在线性时间，常数空间内实现。 可以对每个a[i]进行操作： 如果a[i]不在1,n范围内，则不对； 如果a[i] == i，则i++； 如果a[i] > i，判断a[i]和a[a[i]]是否相等，如果不相等则交换，相等则不对； 如果a[i] < i,则不对； 分摊复杂性是O(1),时间复杂度是O(n），还是in place algorithm

Write an algorithm to remove the duplicate entries from a sorted, null-terminated array of integers. 1|2|2|2|3|3|5|7|7|7|8|8|8|9|9|9|10|10|11|null void remove_dupes(int ints[]) { int i = 0; int j = 0; while(ints[i]!=0) { ++i; ++j; while(ints[j]==ints[j-1]) { ++j; } ints[i] = ints[j]; } }

Largest sum sub-matrix This is very similar to the largest sum sub list but here goes: Given a matrix filled with +ve and -ve Integers.. now find the largest possible continous sub-matrix having maximum sum... matrix or the sub-matrix need not be a square matrix.. I have a dynamic programming solution. The complexity is O(m*n*n), which is not a significant improvement over the brute force method whose complexity is O(m*m*n*n). Let a[m][n] be the 2D array. Let M[i, p, q] be the maximum sum of all sub-matrices with bottom row a[i][p:q], then the following optimal substructure exists: M[i, p, q] = max{ M[i-1, p, q] + sum(a[i][p:q]), sum(a[i][p:q]) }; 0 <= i < m; 0 <= p < n; p <= q < n; OK, this is exactly what we did to find the maximum subarray for 1D case. The next thing to do is to define and calculate the following: L[i, p, q] = sum(a[i][p:q]). Now the program is: int maxSumSubMatrix( int *a, int m, int n ) { int *b = new int[ m * n ]; int i, p, q; for( i = 0; i < m; ++i ){ b[ i * n ] = a[ i * n ]; for( p = 1; p < n; ++p ){ b[ i * n + p ] = a[ i * n + p ]; b[ i * n + p ] += b[ i * n + p - 1 ]; } } int *L = new int[ m * n * n ]; for ( i = 0; i < m; ++i ) { for( q = 0; q < n; ++q ) L[ i * n * n + q ] = b[ i * n + q ]; for( p = 1; p < n; ++p ){ for( q = p; q < n; ++q ){ L[ i * n * n + p * n + q ] = b[ i * n + q ] - b[ i * n + p - 1 ]; } } } int *M = new int[ m * n * n ]; int maxSum = -65535; for ( p = 0; p < n; ++p ){ for ( q = 0; q < n; ++q ){ M[ p * n + q ] = L[ p * n + q ]; if( maxSum < M[ p * n + q ] ) maxSum = M[ p * n + q ]; } } for ( i = 1; i < m; ++i ){ for ( p = 0; p < n; ++p ){ for ( q = p; q < n; ++q ){ if( M[ (i-1) * n * n + p * n + q ] > 0 ){ M[ i * n * n + p * n + q ] = M[ (i-1) * n * n + p * n + q ] + L[ i * n * n + p * n + q ]; } else { M[ i * n * n + p * n + q ] = L[ i * n * n + p * n + q ]; } if ( maxSum < M[ i * n * n + p * n + q ] ) maxSum = M[ i * n * n + p * n + q ]; } } } return maxSum; } The driver is: int main() { int a[] = { 8, 5, -1, -2, -3, -1, -5, 8, 1, 3, -2, 2 }; cout << maxSumSubMatrix( a, 3, 4 ); cout << endl; return 0; } Running result = 13.