A queue (FILO) and a stack (FIFO) can be made from each other. Qs: ---Phone Numner - You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number? ---Special Debugging - You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one? ---Next Prime - Given a number, describe an algorithm to find the next number which is prime. ---O(n)- Order the functions in order of their asymptotic performance : 2^n, n^Googol ( 10^100), n! , n^n , ---BST- what is the best and worst performance time for a hash tree and binary search tree? ---String - What is the best and worst time for the operation 'equals' How do you speed up the 'equals' operation Write a function (and dictate it to your interviewer) that reverse the order of words in a sentence. The final algorithm should work in-place!! E.g.: "This is a sample" --> "sample a is This" ---Multi Threading- Trade offs between a multi threaded and single threaded implementation ? N threads .. n resources .. what protocol do you use to ensure no deadlocks occur? There are a set of 'n' integers. Describe an algorithm to find for each of all its subsets of n-1 integers the product of its integers. ---Sorting- Describe Sorting algorithms and their complexity - Quick sort, Insertion Sort, Merge Sort,Shell,Radix,Heap If you had a million integers how would you sort them and how much memeory would that consume? ---Check for Square- Describe an alogrithm to find out if an integer is a square? ---Adwords - How would you determine if adwords was up and running and serving contextual content ? ---N*N Matrix - Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements. ---Division - Implement division (without using the divide operator, obviously). ---Infinite Queries - You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it. ---Trees- Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state. ---Minimum of List- You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don't know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. ---Google Home Server- Design a web server that serves the Google homepage. a) What are the requirements. b) Design a multi threaded web server that uses shared memory instead of disk access. c) Design a work load balancer for their data centers. d) Design a DNS server that returns the IP address of a data center that has the best connectivity relative to your IP. ---Nth last- How would you find the nth to last element in a linked list? ---Card Shuffle- Explain algorithm to shuffle cards ---Jigsaw puzzle - Coding: Jig saw puzzle. What are the data structures? Assume you have some method which can tell you if two pieces fit together. How would you solve the puzzle, minimizing the number of times you have to call that function? ---Parsing phone numbers- You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numHow would you detect a repeated element in an integer array. ---Smoothening the curve - Write a function to smooth out stock fluctuations. ---Union - Given two sets, Write a function to provide the union of them. ---Most viewed - Design an algorithm to calculate the most user viewed pages ---BST Serialization- Design an algorithm and write code to serialize a binary tree. ---Numbers with Sum - Design an algorithm and write code to find two numbers in an array whose sum equals a given value Bits in Integer ---count bits in an integer.- ---Similar Trees- Given two binary trees, find whether or not they are similar. ---Random character from stream- assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability. ---Print Tree- You have a tree (not Binary) and you want to print the values of all the nodes in this tree level by level.bers?

How to implement 3 stacks in a single array as efficiently as possible ? w1: 3个变量分别当作三个stack的sp,初始化为a a+1 a+2(a[]就是这个数组），push就加3，pop就减3.这个方法最坏情况会浪费2/3的空间。 w2: 两个stack分别在两端向中间生长，第三个在array中间位置交替向两边生长。这个方法最坏情况会浪费1/2的空间。 w3: 首先把array分为若干块，一块大小为k，块的两端用做链接。第一个stack在0位置出分配一块空间，stack在快空间内可以简单快速操作；第二个stack在k+1处分配一个，第三个在2k+1处分配一个。最后在3k+1处做个记号，表示记号右边的空间都没有分配。如果哪个stack用完空间了就申请一个，把新空间和旧空间连接起来。这样子最多浪费2k大小的空间，如果k大小得当，那么操作速度和空间浪费都能有效控制。

BERKELEY, Calif., April 9 — It takes a particularly clever puzzle to stump a mind accustomed to performing mental gymnastics. So it's no ordinary puzzle that's spreading through networks of mathematicians like a juicy bit of gossip. Known as "the hat problem" in its most popular incarnation, this seemingly simple puzzle is consuming brain cycles at universities and research labs across the country and has become a vibrant topic of discussion on the Internet. The reason this problem is so captivating, mathematicians say, is that it is not just a recreational puzzle to be solved and put away. Rather, it has deep and unexpected connections to coding theory, an active area of mathematical research with broad applications in telecommunications and computer science. In their attempts to devise a complete solution to the problem, researchers are proving new theorems in coding theory that may have applications well beyond mathematical puzzles. "This puzzle is unique since it connects to unsolved mathematical questions," said Dr. Joe Buhler, deputy director of the Mathematical Sciences Research Institute here and a hat problem enthusiast. The hat problem goes like this: Three players enter a room and a red or blue hat is placed on each person's head. The color of each hat is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each person can see the other players' hats but not his own. No communication of any sort is allowed, except for an initial strategy session before the game begins. Once they have had a chance to look at the other hats, the players must simultaneously guess the color of their own hats or pass. The group shares a hypothetical $3 million prize if at least one player guesses correctly and no players guess incorrectly. The same game can be played with any number of players. The general problem is to find a strategy for the group that maximizes its chances of winning the prize. One obvious strategy for the players, for instance, would be for one player to always guess "red" while the other players pass. This would give the group a 50 percent chance of winning the prize. Can the group do better? Most mathematicians initially think not. Since each person's hat color is independent of the other players' colors and no communication is allowed, it seems impossible for the players to learn anything just by looking at one another. All the players can do, it seems, is guess. "I tell someone the problem and they think they don't have the conditions right," said Dr. Peter Winkler, director of fundamental mathematics research at Bell Labs of Lucent Technologies in Murray Hill, N.J. "But if you try to prove it's impossible, it doesn't quite work." Mathematicians credit the problem to Dr. Todd Ebert, a computer science instructor at the University of California at Irvine, who introduced it in his Ph.D. thesis at the University of California at Santa Barbara in 1998. Dr. Ebert said he discovered the problem's appeal only recently, when he offered extra credit to his students for solving a seven-player version he called the "seven prisoners puzzle." Next thing he knew, the problem was posted on Internet news groups and in chat rooms. "I started getting e-mail from all over the country," Dr. Ebert said. Meanwhile, Dr. Winkler, a well- known collector and distributor of clever puzzles, heard the problem from a colleague and spread it widely. It has cropped up at Microsoft Research in Redmond, Wash., at Hewlett-Packard Laboratories in Palo Alto, Calif., and at mathematics, statistics and computer science departments at universities across the country. The problem has even spread to the Caribbean. At a workshop at a research institute in Barbados, one hardy group of theoretical computer scientists stayed up late one rum- soaked night, playing a drinking game based on the puzzle. It spread to Berkeley after Dr. Winkler bumped into Dr. Elwyn Berlekamp, a professor in the Berkeley math department, at a conference in New Orleans in January. "I told him about the problem and next thing I knew he was leaving messages on my hotel phone saying, `Great problem, haven't gotten it yet,' then finally, `I got it,' " Dr. Winkler said. "I thought, with his knowledge of coding theory, he'd find that approach, and he didn't disappoint me." Dr. Berlekamp, a coding theory expert, said he figured out the solution to the simplest case in about half an hour, but he saw the coding theory connection only while he was falling asleep that night. "If you look at old things that you know from a different angle, sometimes you can't see them," he said. The first thing Dr. Berlekamp saw was that in the three-player case, it is possible for the group to win three- fourths of the time. Three-fourths of the time, two of the players will have hats of the same color and the third player's hat will be the opposite color. The group can win every time this happens by using the following strategy: Once the game starts, each player looks at the other two players' hats. If the two hats are different colors, he passes. If they are the same color, the player guesses his own hat is the opposite color. This way, every time the hat colors are distributed two and one, one player will guess correctly and the others will pass, and the group will win the game. When all the hats are the same color, however, all three players will guess incorrectly and the group will lose. "If you look at the total number of guesses made, it's still the case that half are right and half wrong," Dr. Winkler said. "You only make progress if, when players are guessing wrong, a great many are guessing wrong." The strategy gets far more complicated for larger numbers of players. Still, it all comes down to making sure that most of the time no one is wrong and occasionally everyone is wrong at once. As it turns out, this requirement can be perfectly met only when the number of players is one less than a power of two (three, seven, 15 and so on.) For example, in the game with 15 players, there is a strategy for which the group is victorious 15 out of every 16 times they play. This strategy can be described using elegant mathematical structures known as Hamming codes. Hamming codes, named after Richard Hamming, the mathematician who discovered them, are basic tools studied by engineering students all over the world. Hamming codes straddle the boundary between two types of mathematical objects: error correcting codes and covering codes. Error correcting codes, techniques for correcting errors in data sent across noisy channels, are used in everything from cell phones to compact discs. Covering codes can be used to compress data so they take up less space in a computer's memory. "Hamming codes are perfect structures, a lot like crystals, where you can't move an atom in them or they are completely destroyed," said Dr. Amin Shokrollahi, chief scientist at Digital Fountain, which uses coding theory to speed up Internet data transmissions. "When you take the hat problem apart and look at its core, you see what you need are exactly Hamming codes." When the game is played with fewer than nine players, the optimal solution can be determined using various types of codes. For larger numbers that aren't one less than a power of two, a strategy designed around the Hamming code solution works closer and closer to 100 percent of the time as the number of players grows. Dr. Hendrik Lenstra, a professor of mathematics at Berkeley, and Dr. Gadiel Seroussi, director of information theory research at HP Labs, have developed a new type of covering code to define an even better strategy for large numbers of players. While their strategy is the best so far, they don't know that it is always optimal. The optimal solution to the hat problem, for all numbers of players, is still unknown. "We're still working on it," Dr. Seroussi said. "And as a consequence of working on this problem, we've got some results in coding theory that are interesting in and of themselves." For now, researchers say, it seems unlikely that a solution will have immediate practical applications. Still, one never knows what the future might hold. "My experience is that any mathematics I've done is useful eventually," Dr. Seroussi said. Practically useful or not, for some researchers the hat problem has interesting social implications. "I like problems that have philosophical punch lines," Dr. Berlekamp said, citing two life lessons that can be gleaned from the puzzle: "The first is that it's O.K. to be wrong as long as you contrive not to be wrong alone," he said. "The other, more important lesson is a need for teamwork that goes against the grain of most mathematicians. If the evidence suggests someone on your team knows more than you, you should keep your mouth shut. "Most of us assume that each player's strategy is oriented toward him getting it right, and it's not. It's the whole team." http://www.msri.org/people/members/sara/articles/hat.html http://www.oursci.org/bbs/oursci/showthread.php?threadid=2395&perpage=15&pagenumber=2

把扑克牌从中间分成相等两份，然后把这两份相互交叉，一个压着一个，合成一份。这样就有两种可能。假设A是来自原来的牌上半部分，B来自下半部分，从中间分开，就是AA…A，BB…B两部分，交叉合在一起，就是ABAB..AB或者BABA..BA两种情况。我们先讨论ABAB..AB的情况，即最上面一张和最下面一张始终不动的perfect shuffle。 合并的过程就是： 1. if 1<=x<=26, then x -> 2x-1 2. if 27<=x<=52, then x -> 2(x-26) = 2x-52 ( x -> 2x-1表示在x处的牌被转换到2x-1处。 ) 注意到2x-1 = 2x-52 modulo 51， 所以我们可以把上面两个合并成一个方程： x -> 2x-1 mod 51 这个方程迭代若干次之后的结果如下： 1 iteration: 2x-1 2 iterations: 2(2x-1)-1 = 4x-3 3 iterations: 2(2(2x-1)-1)-1 = 8x-7 n iterations: (2^n)x - (2^n -1) 8 iterations: 256x - 255 256x-255 mod 51的结果，恰好就是x。（256x－255＝x+51*5x-51*5） 这样52张牌“完美”洗8次之后，就恢复到原来的排列了。颇为神奇，像许多莫名其妙的东西一样，这个不是一个巧合。 AB shuffle (1,2,...,n/2)->(1,3,...,n-1) (上半部分的牌被排到奇数位置) (n/2+1,n/2+2,...,n)->(2,4,...,n) (下半部分的牌被排到偶数位置) BA shuffle (1,2,...,n/2)->(2,4,...,n) (上半部分的牌被排到偶数位置) (n/2+1,n/2+2,...,n)->(1,3,...,n-1) (下半部分的牌被排到奇数位置) AB Shuffle 对于n张牌的AB洗牌方式，下面这两个公式 if 1 <= x <= n/2, then x -> 2x-1 if n/2+1 <= x <= n, then x -> 2x-n 等价于 x -> 2x-1 mod n-1 (since 2x-1 = 2x-n mod n-1) k次迭代之后，x变为 (2^k)x - ((2^k)-1) = x + ((2^k)-1)(x-1) mod (n-1). 这个可以用归纳法证明，如下： 1次迭代之后，x变为2x-1 mod n-1 = x + ((2^1)-1)(x-1). 假设k-1次迭代之后x变为x + ((2^(k-1))-1)(x-1) mod n-1. 那么k次迭代之后x就变为 2(x+((2^(k-1))-1)(x-1))-1 mod n-1 ＝2x + 2*(2^(k-1))(x-1) - 2(x-1) – 1 ＝x + ((2^k)-1)(x-1) mod n-1 一个经典的问题是，给出n张牌，问多少次AB方式的perfect shuffle之后这n张牌被洗回原样。它等价于 x = x + ((2^k)-1)(x-1) mod n-1 ( 1<=x<=n ). 这个问题即，求k，对于所有1<=x<=n，((2^k)-1)(x-1) = 0 mod n-1。或者描述成， 对于所有x属于[1,n],n-1能整除((2^k)-1)(x-1) 显然x-1<=n-1，这个问题就等价于求k,使n-1整除(2^k)-1. 结论就是：如果(2^k)-1 = 0 mod n-1,那么n张牌的AB perfect shuffle在k次之后就回到了洗之前的样子。 BA Shuffle 考虑最开始的描述，对n张牌进行AB shuffle的时候，实际上相当于对去掉最上和最下的两张牌之后的n-2张牌进行BA shuffle。根据AB shuffle的结论，推出BA shuffle的结论：如果(2^k)-1 = 0 mod n+1,那么n张牌的BA perfect shuffle在k次之后就回到了洗之前的样子。

传说中一个google的笔试题 题目: 长度为n的整数数组，找出其中任意(n-1)个乘积最大的那一组的乘积，只能用乘法，不可以用除法。要求对算法的时间复杂度和空间复杂度作出分析，不要求写程序. 很早以前在phpx上看到过,我也拿来面试过.当时煞有介事的把算法和php示例写出来了,如今要清理wwwroot目录了,立此存照. 程序: $integers = array(1, 2, 3, 0, 5, 6, 0, -1, -2, -3, 1); echo getmax($integers); /* * $postive_min 最小的正整数 * $negative_max 最大的负整数 * $negative_max 负整数的个数 * $zero_amount 0的个数 * $i 循环计数器 * 假定参数是一个数组 $integers，我用PHP写的，因为这里都是PHPer，但是并未调用任何PHP库函数，运算符和流程控制也是其他c family语言支持的，因此，基本可以视为C版本的算法描述 */ function getmax($integers) { $postive_min = 0; $negative_max = 0; $negative_amount = 0; $zero_amount = 0; $loopTimes = count($integers); for ($i=0; $i 0) { $postive_min = $postive_min < $integer ? $postive_min : $integer; } else if ($integer == 0) { $zero_amount ++; } else { $negative_max = $negative_max > $integer ? $negative_max : $integer; $negative_amount ++; } } if ($zero_amount > 1) // 如果有两个或者更多0，则无论N-1个整数怎么组合，乘积都是0，这样就不必进行乘法运算了，直接返回0。 { return 0; } else if ($zero_amount == 1) { if ($negative_amount % 2 == 1) // 如果存在一个0和奇数个负数，则无论N-1个整数怎么组合，乘积只能是0或者负数，最大乘积是0 { return 0; } else // 如果存在偶数个负数，除了0，剩下N-1个整数的乘积符合题意，计算并返回之 { return '除了0，剩下N-1个整数的乘积'; //计算乘积的过程我就不写了，再次遍历数组，并计算乘积，这个我没有什么好的优化策略 } } else // 如果没有0。看来逃不掉乘法运算了 { if ($negative_amount % 2 == 1) // 奇数个负数，去掉最大（绝对值最小）的负数，剩下N-1个数的乘积满足题意 { return '去掉最大（绝对值最小）的负数，剩下N-1个数的乘积'; } else // 偶数个负数，去掉最小正数，剩下N-1个数的乘积满足题意 { return '去掉最小正数，剩下N-1个数的乘积'; } } } 注释:原本的版本是不调用任何php函数的,但是for循环那个地方有点问题,我疏忽了,直接写的 while(false != ($integer = $integer[$i])) 但运行的时候,如果数组中有0元素,有点不对. 也可以用if (isset($integer[$i])),但终究还是用到php函数了,好多年不摸C,也不知道C里面该如何遍历一个数组了.

有关Strassen算法是这样来的： 两个n*n矩阵A和B相乘 首先，假设n是2的幂。将矩阵A，B和C中每一矩阵都分块成为4个大小相等的子矩阵，每个子矩阵都是n/2×n/2的方阵。由此可将方程C=AB重写为: 　(1) C11 C12 A11 A12 B11 B12 C21 C22 ＝ A21 A22 X B21 B22 由此可得:　 C11=A11B11+A12B21 (2) C12=A11B12+A12B22 (3) C21=A21B11+A22B21 (4) C22=A21B12+A22B22 (5) 如果n=2，则2个2阶方阵的乘积可以直接用(2)-(3)式计算出来，共需8次乘法和4次加法。当子矩阵的阶大于2时，为求2个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降为2。这样，就产生了一个分治降阶的递归算法。依此算法，计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。2个n/2×n/2矩阵的加法显然可以在c*n2/4时间内完成，这里c是一个常数。 这个递归方程的解仍然是T(n)=O(n3)。因此，该方法并不比用原始定义直接计算更有效。究其原因，乃是由于式(2)-(5)并没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要比矩阵加减法耗费的时间多得多。要想改进矩阵乘法的计算时间复杂性，必须减少子矩阵乘法运算的次数。按照上述分治法的思想可以看出，要想减少乘法运算次数，关键在于计算2个2阶方阵的乘积时，能否用少于8次的乘法运算。Strassen提出了一种新的算法来计算2个2阶方阵的乘积。他的算法只用了7次乘法运算，但增加了加、减法的运算次数。这7次乘法是:　 M1=A11(B12-B22) M2=(A11+A12)B22 M3=(A21+A22)B11 M4=A22(B21-B11) M5=(A11+A22)(B11+B22) M6=(A12-A22)(B21+B22) M7=(A11-A21)(B11+B12) 做了这7次乘法后，再做若干次加、减法就可以得到:　 C11=M5+M4-M2+M6 C12=M1+M2 C21=M3+M4 C22=M5+M1-M3-M7 以上计算的正确性很容易验证。例如:　 C22=M5+M1-M3-M7 =(A11+A22)(B11+B22)+A11(B12-B22)-(A21+A22)B11-(A11-A21)(B11+B12) =A11B11+A11B22+A22B11+A22B22+A11B12 -A11B22-A21B11-A22B11-A11B11-A11B12+A21B11+A21B12 =A21B12+A22B22　 由(2)式便知其正确性。 至此，我们可以得到完整的Strassen算法如下： procedure STRASSEN(n,A,B,C); begin if n=2 then MATRIX-MULTIPLY(A，B，C) else begin 将矩阵A和B依(1)式分块; STRASSEN(n/2,A11,B12-B22,M1); STRASSEN(n/2,A11+A12,B22,M2); STRASSEN(n/2,A21+A22,B11,M3); STRASSEN(n/2,A22,B21-B11,M4); STRASSEN(n/2,A11+A22,B11+B22,M5); STRASSEN(n/2,A12-A22,B21+B22,M6); STRASSEN(n/2,A11-A21,B11+B12,M7); end; end; 其中MATRIX-MULTIPLY(A，B，C)是按通常的矩阵乘法计算C=AB的子算法。 我现在的问题是，由于算法是采用分治法，用到递归，但是递归函数的参数传递中参数有整个矩阵 的，怎么表示这些子矩阵呢？ Top 5 楼fhp0917（剑心）回复于 2004-10-07 19:54:41 得分 0 我也想了解一下关于矩阵的一些算法，小弟可以写一些小程序完成工程数学的作业 Top 6 楼GavinLan（）回复于 2004-10-07 20:48:35 得分 0 刚才在那个算法里写少了一点东西，就是分治法中的“合并”语句，是这样的： C：＝ M5+M4-M2+M6 M1+M2 M3+M4 M5+M1-M3-M7

1.求直方图的最大内接矩形,假设每个细条的宽度为1.这题很难,没想出什么好的算法. 2.NxN行列有序的矩阵查找一个数. 先折半查找，找到所在哪一行；再用同样方法找到在哪一列；O(logN)*O(logN)=O(N). 3.给定一篇文章,求包含所有单词的最短摘要. 使用数据结构DST可以在O(N)内解决. 4.将MxN的矩阵转秩,要求O(1)的空间复杂度.参考群论中cyclic group,group generator. 10.实现两个N*N矩阵的乘法，矩阵由一维数组表示. 不算难. 11.找到单向链表中间那个元素，如果有两个则取前面一个. 两个步长不同的指针，一个为一，一个为二，步长为二走在前面；当他走到最末的时候，步长为一的恰走到中间. Q1. 找出二维n*n数组中所有鞍点。鞍点就是所在行为最大值，所在列同时为最小的那些位置。 如果每一行或每一列都没有相同元素，那么该矩阵中只有一个鞍点；如果有多个鞍点，那么鞍点同在一行或一列。先找 到一个鞍点再找其他鞍点。使用“深度优先”查找的话可以在O(n^2)时间复杂度内解决。 后面添加一点图片，是高手们对于第一题直方图的最大内接矩形的解释。

热身题:对于数100!, 末尾有几个0? 其实就是1到100每个整数分解质因数,有几个5就有几个0~~ Q: 说有N个数，这个N很大，比如有100000个，从这N个数中找出最大的10个数，它的复杂度大概为多少？ 答案：首先限制数列的前面10个位置。把这10个数排一下序，由于10远远小于N，所以排序时间可以忽略不计。后面的数逐个用二分法与前十个位置上的数比较，后面(N-10)个数平均消耗log10, 所以在比较3N次之后，前面10个位置的数就是最大的10个数。时间复杂度为O(n)。

google的一道面试题 这个题目的英文原题是: Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n? 翻译过来大体是这样： 有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？ 为什么f(13)=6, 因为1,2,3,4,5,6,7,8,9,10,11,12,13.数数1的个数，正好是6. 采用变步长调整法来搜索。 至于计算f(n)的值可用以下方法： 对任一自然数逐位求。拿1617来说，从左至右逐位计算：在1--1617之间，首位为1的数有617+1个； 在1--1617之间次位为1的数有(1+1)*100个；在1--1617之间第三位为1的数有16*10+17+1个； 在1--1617之间末位为1的数有161+1个。 总结规律： 对任意自然数n，从左至右逐位定为1，求其余为的所有组合数，相加即为f(n)。同时根据上面的计算过程 知： 1）如果n的k位是1，就采取将k位之前的数字组成的数(如果没有，置为0)乘以10^(k-1)(即10的k-1次方)再加上k位以后 的数字组成的数加一。 2）如果n的k位是0，就采取将k位之前的数字组成的数乘以10^(k-1)。 3）如果n的k位是其他的数，就采取将k位之前的数字组成的数(如果没有，置为0)加一乘以10^(k-1)。 由上面的分析可编制函数f(n)。 变步长调整法搜索主要是要找到合适的步长使搜索无遗漏。 想法是逐个数字数多少个1的同志统统去面壁~~

在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参加游戏。游戏中，主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色，可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人，可以看到其他人的帽子颜色，但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮，可以选择“黑色”“白色”或“弃权”(也就是 pass，不作猜测的意思)。小组成员彼此之间没有任何信息交流，他们必须各自独立地作出自己的选择，并且谁也不知道其他人的选择。如果小组成员全部选择了 pass，也就是每个人都弃权，则他们输了；如果有小组成员作出了明确的猜测，但某个人猜错了，则结果也是输。只有当小组中有人做出猜测，并且每个做出猜测的人都猜对了，他们才能获胜，一起获得最后的大奖。 这个游戏还有最关键的一点：在游戏开始前(帽子戴上之前)，有一个“协商时间”，小组成员可以聚在一起，讨论决定小组应采取什么样的策略。但这个交流过程在游戏开始时自然终止。 现在的问题是：小组选择什么样的策略，才有最大的机会获胜呢？ 首先可以肯定，这个最佳策略的获胜概率，肯定不会只是1/(2^n)。容易找到获胜概率为1/2 的策略，但是不是就没有更狡猾的办法了呢？ 我认真思考了一下，还真难，留给高手吧~~ 参看Why Mathematicians Now Care About Their Hat Color

A 98*98 chess board has the squares colored alternately black and white in the usual way. A move consists of selecting a rectangular subset of the squares( with boundary parallel to the sides of the board) and changing their color. What is the smallest number of moves required to make all the squares black? Solution: Answer:98. There are 4 97 adjacent pairs of squares in the border and each pair has one black and one white square. Each move can fix at most 4 pairs, so we need at least 97 moves. However, we start with two corners one color and two another, so at least one rectangle must include a corner sqaure. But such a rectangle can only fix two pairs, so at least 98 moves are needed. It is easy to see that 98 suffice: take 49 1*98 rectangles(alternate rows), and 49 98*1 rectangles(alternate columns).

Google的题目：(这道题真他妈变态，我看了好几回才知道说什么) 有一幢100层高的大厦，给你两个完全相同的玻璃围棋子。假设从某一层开始，丢下玻璃棋子就会摔碎。那么怎么利用 手中的两颗棋子，用一种什么样的最优策略，知道这个临界的层高呢？ 答：先从14楼开始抛第一次；如果没碎，再从27楼抛第二次；如果还没碎，再从39楼抛第三次；如果还没碎，再从50 楼抛第四次；如此，每次间隔的楼层少一层。这样，任何一次抛棋子碎时，都能确保最多抛14次可以找出临界楼层。 　　证明如下： 　　1、第一次抛棋子的楼层：最优的选择必然是间隔最大的楼层。比如，第一次如果在m层抛下棋子，以后再抛棋子 时两次楼层的间隔必然不大于m层（大家可以自己用反证法简单证明） 　　2、从第二次抛棋子的间隔楼层最优的选择必然比第一次间隔少一层，第三次的楼层间隔比第二次间隔少一层，如 此，以后每次抛棋子楼层间隔比上一次间隔少一层。（大家不妨自己证明一下） 　　3、所以，设n是第一次抛棋子的最佳楼层，则n即为满足下列不等式的最小自然数： 　　不等式如下： 1+2+3+...+(n-1)+n >= 100 　　由上式可得出n=14 　　即最优的策略是先从第14层抛下，最多抛14次肯定能找出临界楼层。 这道题可以抽象成这样。在100以内随机取一个正整数。 给你2次机会去猜这个数。 每次猜数的规则是这样的，如果你猜的数字比实际数字大。那么失去这次猜数机会。 如果你猜得数比实际的数小，那么可以继续猜。 猜完后把你猜过的所有的数相加。 问怎么样猜能使你猜出这个数，同时最后相加的数最小。 哈佛的超难逻辑题，I am fooled! ~~~~我被耍啦: 有A、B、C三个精灵，其中一个只说真话，另外一个只说假话。还有一个随机回答。你可以向这三个精灵发问三条是非 题，而你的任务是找出谁说真话谁说假话谁随机答话。精灵可以听懂你的英语，却不会用英语回答，精灵只会以“Da” 或“Ja”回答，但你并不知道它们的意思，只知道其中一个字代表“对”，另外一个字代表“错”。你应该怎样问这三 个问题呢? 第1个问题 如果我问你以下两个问题：“Da 表示Yes 吗？”和“如果我问你以下两个问题：‘你是True 吗’和‘B 是Random 吗 ’，你的回答是一样的，对吗？”，你的回答是一样的，对吗？ 如果A 是True 或False 并且回答是Da，那么B 是Random，从而C 是True 或False； 如果A 是True 或False 并且回答是Ja，那么B 不是Random，从而B 是True 或False； 如果A 是Random，那么B 和C 都不是Random！ 所以无论A 是谁，如果他的答案是Da，C 是True 或False；如果他的答案是Ja，B 是True 或False。(这里明明问了两个问题嘛，还说一个问题，操！) 继续第2个问题。 不妨设B 是True 或False。 向B 问第二个问题： Question2：如果我问你以下两个问题：“Da 表示Yes 吗？”和“罗马在意大利吗”，你的回答是一样的，对吗？ 如果B 是True，他会回答Da；如果B 是False，他会回答Ja。从而我们可以确认B 是True 还是False。 继续第三个问题。 向B 问第3个问题： Question3：如果我问你以下两个问题：“Da 表示Yes 吗？”和“A 是Random 吗”，你的回答是一样的，对吗？ 假设B 是True，如果他的回答是Da，那么A 是Random，从而C 是False；如果他的回答是Ja，那么C 是Random，从而 A 是False。 假设B 是False，如果他的回答是Da，那么A 是不是Random，从而C 是Random，A 是True； 如果他的回答是Ja，那么A 是Random，从而C 是True。 如何用10行左右的代码找出圆周率的第n位?(这个太难了，估计这辈子都做不出来)。 来一道很无赖的题目: O(1) 时间删除单向链表中指定节点 （假设这个节点已经用一个指针指向）? 答案: 真删除肯定不行，不过可以用假删除，就是把要删除节点的值用要删除节点的下一个节点值覆盖，然后删除下一个节点。 p->value=p->next->value; temp=p->next;; p->next=temp->next; free(temp); N个圆可以最多把平面分成多少部分？ 设n个圆最多可以把平面分成S(n)个部分。 则可得： S(1)=2； S(2)=4； ... 前n-1个圆最多将平面分成S(n-1)个部分，此时，对于第n个圆来说，它与先前的n-1个圆最多有2(n-1)个交点，即此第n 个圆最多被这2(n-1)个交点分成2(n-1)条圆弧段。由于每增加一个圆弧段，便可将原来的某个区域分为两个区域（此处 最好看图分析）。因此，第n个圆使平面增加了2(n-1)个区域。因此可得递推关系式： S(n)=S(n-1)+2(n-1), 其中n大于等于2。 由此递推关系式得到： S(n)=S(1)+2*1+2*2+...+2*(n-1)=2+n*(n-1)=n^2-n+2； 即n个圆最多可以把平面分成(n^2-n+2)个部分。

有n个人，其中超过半数是好人，剩下的是坏人好人只说真话，坏人可能说真话也可能说假话这n个人互相都知道对方是好人还是坏人 现在要你从这n个人当中找出一个好人来，只能通过以下方式：每次挑出两个人，让这两个人互相说出对方的身份，你根具两个人的话进行判断。 问通过何种方法才能最快的找出所有人的身份(最坏的情况下) 我们从题意中可知，两人的相互指证中，如果有一个人给指证为坏人，那么两人之中至少有一个是坏人；如果两个都给指证为好人，那么这两人都是好人或者都是坏人。我们的策略是：第一个情况，两人都抛弃，因为少两个坏人或者同时减少一个好任何一个坏人不改变剩下的人之中超过半数是好人这个性质。第二个情况，两个人留下，不过一个人到一边，就是把它们分开。下一次只考虑其中一边的人。这样子每次都少至少一半的人(如果出现第一个情况那么淘汰的更快，只出现第二个情况就淘汰最慢)，最坏的情况是到最后是两个好人一个坏人。具体一点，大写是好人，小写是坏人，他们是，ABCDEFGH和abcd，(好人多，当然考虑的人群中如果好人多一个是最容易找到的)，指证情况是(最坏的情况)，A-B，C-D，E-F，G-H，a-b，c-d，他们都说对方是好人，那么就留下每一对的前面一个人，所以剩下ACEG和ac，那么这次的指证情况是(最坏的情况)，A-C，E-G，a-c，那就剩下AEa，所以说最坏的情况下最后一定会蜕化到两个好人一个坏人的情况。这个时候就很容易找到哪个是好人。这个算法淘汰的次数是O(logn)。指证次数为(两人相互指正为两次)O(n). 我们不妨设想，如果不要求一定是两两出来相互指证的话，那么什么办法会比这个算法更好呢？

Suppose we have an array a1,a2, ... ,an,b1,b2, ... ,bn How to change this array to a1,b1,a2,b2, ..., an,bn in O(n) time with using O(1) space. 本来以为这道题很容易,后来发现自己做的时间是O(n^2), OMG~~, 有人说可以到O(nlogn), ??? 我的想法是这样，原来两列数： 1, 3, 5, 7, 9, 11, 13 2, 4, 6, 8, 10, 12, 14 第1步： 1, 2, 5, 7, 9, 11, 13 3, 4, 6, 8, 10, 12, 14 第2步： 1, 2, 3, 7, 9, 11, 13 5, 4, 6, 8, 10, 12, 14 第3步： 1, 2, 3, 4, 9, 11, 13 5, 7, 6, 8, 10, 12, 14 第4步： 1, 2, 3, 4, 5, 11, 13 7, 9, 6, 8, 10, 12, 14 第5步： 1, 2, 3, 4, 5, 6, 13 7, 9, 11, 8, 10, 12, 14 第6步： 1, 2, 3, 4, 5, 6, 7 9, 11, 13, 8, 10, 12, 14 这样一来，第6步之后，上一列完全符合，下一列演化为原来数组的类似状态，前一半奇数后一半偶数。本来以为这个算法是2O(n)。后来发现疏忽了一个地方，那就是下一列一直都要保证前面奇数的有序，(例如第6步)所以还要把下一列的奇数往前挪，但第5步却不必移动。现在看来，这个问题也没有交代很清楚。因为数组和链表在操作方面有很大不同，如果是数组，就不免有挪动位置的额外操作，而链表则可以避免。这样，如果是链表的话，按照这个方法，是可以在O(n)时间内解决的。这个问题在http://discuss.techinterview.org/default.asp?interview.11.482833.2有讨论，据说是一个完美洗牌问题。 但把这个问题反过来(a1,b1,a2,b2, ..., an,bn 变成a1,a2, ... ,an,b1,b2, ... ,bn)却是容易。解法是，2nd位置的和3th的互换，4th位置的和5th的互换，如此类推，直到an。下一轮就是从3th位置开始，这样一轮一轮直到作到完成。把这个容易问题的解法倒过来使用，也能解决开始提出的问题。不过时间是，1+2+...+n/2，也是O(n^2)。这个解决办法似乎表现不是很满意。

可信计算VII:拜占庭将军问题 2006年06月21日 http://www.capt.cn/n447957/n447984/n447995/4682.html 前进中的可信计算（Ⅵ）：拜占庭将军问题 闵应骅 一个可信的计算机系统必须容忍一个或多个部件的失效。失效的部件可能送出相互矛盾的信息给系统的其他部件。这正是目前网络安全要对付的情况，如银行交易安全、存款安全。美国2001/9/11遭恐怖袭击之后，大家普遍认识到银行的异地备份非常重要。纽约的一家银行可以在东京、巴黎、苏黎世设置异地备份。当某些点受到攻击甚至破坏以后，可以保证账目仍然不错，得以复原和恢复。从技术的角度讲，这是一个很困难的问题。因为被攻击的系统不但可能不作为，而且可能进行破坏。国家的安全就更不必说了。对付这类故障的问题被抽象地表达为拜占庭(Byzantine)将军问题。 拜占庭(Byzantine)将军问题 拜占庭帝国就是5～15世纪的东罗马帝国，拜占庭即现在土耳其的伊斯坦布尔。我们可以想象，拜占庭军队有许多分支，驻扎在敌人城外，每一分支由各自的将军指挥。将军们只能靠通讯员进行通讯。在观察了敌人以后，忠诚的将军们必须制订一个统一的行动计划。然而，这些将军中有叛徒，他们不希望忠诚的将军们能达成一致，因而影响统一行动计划的制订与传播。问题是：将军们必须有一个算法，使所有忠诚的将军们能够达成一致，而且少数几个叛徒不能使忠诚的将军们做出错误的计划。 解决拜占庭将军问题的算法必须保证： A．所有忠诚的将军必须基于相同的行动计划做出决策。 忠诚的将军按算法的要求行动，而叛徒则按他们自己的意志行动。算法要保证不管叛徒怎么做，条件A都能得到保证。忠诚的将军们不但要能达成一致，而且要同意一个合理的计划。这就要求条件B。 B．少数叛徒不能使忠诚的将军做出错误的计划。 这一条是很难做到的，因为“错误的计划”很难形式地加以定义。 我们考虑将军们怎么达成一致。设有n个将军，v(i)表示第i个将军送出的信息。每个将军用相同的方法把v(1),…,v(n)按某一种逻辑方式组合起来，形成一个行动计划。要满足条件A，将军们就必须用同样的方法来组合这些信息。而条件B要求使用的方法是健壮的。考虑最简单的情况，如果决定只有进攻和撤退两种可能，v(t)就是将军认为选择那一种行动最好，而最后的决定则基于多数表决。少数叛徒只有在忠诚的将军们几乎随机地（每一种选择的概率都是1/2）做出决策时才能影响决策，但既然每一种选择的概率都是1/2，那就不管怎么决策都不能说是坏的。 如果把第i个将军的信息v(i)送给其他将军。由于条件A要求每一个忠诚的将军得到v(1),…,v(n)相同的值，而叛徒将军可以给不同的将军送不同的值。为了使条件A得到满足，下面两条必须成立。 1．每一个忠诚的将军得到v(1),…,v(n)相同的值。 这就意味着忠诚的将军并不一定使用第i个将军送来的信息作为v(i)。因为第i个将军可能是叛徒。但这又可能使忠诚的将军送来的信息也被修改，因为忠诚的将军并不知道第i个将军是忠诚的，还是叛徒。如果要满足条件B，这是不能允许的。例如，我们不能因为少数叛徒说“撤退”，忠诚的将军说“进攻”，而做出“撤退”的决定。因此，要求 2．对每一个 i，如果第i个将军是忠诚的，其他忠诚的将军必须以他送出的值作为v(i). 我们可以重写条件1如下。 1’。 对每一个 i，不论第i个将军是忠诚的，或是叛徒，任何两个忠诚的将军使用相同的值v(i). 条件1’和2都只牵涉到第i个将军怎么送一个值v(i)给其他的将军。因此，我们可以用司令送命令给副官的方式叙述如下： 拜占庭将军问题：一个司令要送一个命令给他的n-1个副官，使得 IC1。所有忠诚的副官遵守同一个命令。 IC2。假如司令是忠诚的，则每一个忠诚的副官遵守他送出的该命令。 条件IC1和IC2称为交互一致性条件。注意，如果司令是忠诚的，IC1可以从IC2推出来。但是，司令并不一定是忠诚的。 这个问题比过去的容错更困难。因为过去的容错都是针对那样一些软硬件故障，其故障效果是固定的。而拜占庭故障却假定故障机是鲜活的，它可以做坏事。 拜占庭将军问题的可解性 （1）叛徒数大于或等于1/3，拜占庭问题不可解 如果有三位将军，一位副官是叛徒，如图1所示。当司令发进攻命令时，副官2可能告诉副官1，他收到的是“撤退”的命令。这时副官1收到一个“进攻”的命令，一个“撤退”的命令，而无所适从。 如果司令是叛徒，如图2所示。他告诉副官1“进攻”，告诉副官2“撤退”。当副官2告诉副官1，他收到“撤退”命令时，副官1由于收到了司令“进攻”的命令，而无法与副官2保持一致。 正由于上述原因，在三模冗余系统中，如果允许一机有拜占庭故障，即叛徒数等于1/3，因而，拜占庭问题不可解。也就是说，三模冗余对付不了拜占庭故障。三模冗余只能容故障-冻结(fail-frost)那类的故障,就是说，元件故障后，它就冻结在某一个状态不动了。对付这类故障，用三模冗余比较有效。 (2) 用口头信息，如果叛徒数少于1/3，拜占庭问题可解 注意，这里说“少于1/3”表明，要对付一个叛徒，至少要用四模冗余。在四模中有一个叛徒，叛徒数是少于1/3的。所谓口头信息，是指它满足三个条件：① 传送正确，② 接收者知道是谁发的。③ 沉默（不发信息）可以被检测。拜占庭问题可解是指：所有忠诚的副官遵循同一命令。若司令是忠诚的，则所有忠诚副官遵循其命令。我们可以给出一个多项式复杂性的算法来解这一问题。算法的中心思想很简单，就是司令把命令发给每一副官，各副官又将收到的司令的命令转告给其他副官，递归下去，最后用多数表决。如图3所示。如果司令是忠诚的，他送一个命令v给所有副官。若副官3是叛徒，当他转告给副官2时命令可能变成x。但副官2收到{v, v, x}，多数表决以后仍为v，忠诚的副官可达成一致。如果司令是叛徒，如图4所示。他发给副官们的命令可能互不相同，为x, y, z。当副官们互相转告司令发来的信息时，他们会发现，他们收到的都是{x,y,z}，因而也取得了一致。 （3）用书写信息，如果至少有2/3的将军是忠诚的，拜占庭问题可解 所谓书写信息，是指带签名的信息，即可认证的信息。它是在口头信息的基础上，增加两个条件：① 忠诚司令的签名不能伪造，内容修改可被检测。② 任何人都可以识别司令的签名，叛徒可以伪造叛徒司令的签名。一种已经给出的算法是接收者收到信息后，签上自己的名字后再发给别人。由于书写信息的保密性，可以证明，用书写信息，如果至少有2/3的将军是忠诚的，拜占庭问题可解。 如图5所示。如果司令是叛徒，他送“进攻”命令给副官1，并带有他的签名0，送“撤退”命令给副官2，也带签名0。副官们转送时也带了签名。于是副官1收到{“进攻”：0，“撤退”：0,2}，说明司令发给自己的命令是“进攻”，而发给副官2的命令是“撤退”，司令对我们发出了不同的命令。对副官2也同样。 拜占庭将军问题的形式描述 考虑网络N，包含n个处理器，或叫游戏者，记为1,2,…,n，设n≥4。每一个处理器是一个交互的、概率的多项式时间图灵机。设网络N是完全的以私人通道连接，即每对处理器皆可互相通信而不能被其他处理器读取。该网络是同步的，即有统一的时钟。在d和d+1个脉冲间送出的信息将在d+1个脉冲时收到。 游戏者i称为是好的，如果它遵循协议，即正确执行其程序，在适当的时间在适当的地点写入返回的值。i称为是坏的，如果它破坏了该协议。如果坏的游戏者被敌手选用和控制，则更一般的故障行为可能发生。敌手是一个算法，在一个网络中发作，腐化一定比例的游戏者。 定义：设A是一个概率算法，r为常数。A称为是一个r-敌手，如果A可以在任何n游戏者的、运行任何协议P的网络上发作，并且满足： (1) A可以读取非私人通道上的任何通信链路。 (2) A可腐化任何t个游戏者。当A腐化i时，A可以读取i的所有数据，并夺取i输出的执行写控制。 (3) 动态性：A可以在P的任何步骤上腐化游戏者。 (4) 急促性：A读第d周期内通过非私人通道传送的信息。第d周期私人通道信息在第d周期送给坏游戏者。基于这些信息，A在第d周期腐化其他的游戏者（少于t个）。而且在第d周期把d周期信息送给新被腐化者。这一过程继续到腐化t个游戏者。在第d+1个脉冲之前，A不需要选择在第d周期由坏游戏者送给好游戏者的信息。 (5) A可以即时完成无限步的计算 有文章给出了拜占庭一致性算法，不要求亲信伙伴和预处理。给定私人通信链路，可望在常数时间内达成一致，如果同步网络故障机；异步网络，故障机。如果不能保证私人通信，可以用密码得到在容错和敌手有限计算能力的运行时间两方面最优的算法。在这种情况下，对异步网络也能容n/3个故障。 可信计算中的拜占庭将军问题 可信计算中必须考虑人为的故障，特别是人为恶意的攻击。这是保证计算安全性的基本出发点，在今天的网络环境下有非常重要的现实意义。拜占庭将军问题不过是保持并行计算中数据一致性问题的一个抽象表达。一种抽象表达往往能把本质问题从繁琐的工程实现中提取出来，对于基础研究极其重要。工程师们常常被繁琐的工程任务所左右，在保证安全的要求下要考虑的问题非常多，而忽略了提纲挈领的功夫。 在可信计算领域，过去考虑的故障-冻结模式，假定部件故障以后就“死”去了，不再工作了。现在我们必须考虑故障-活动模式，即部件故障以后，它可能仍然活动，甚至进行系统所有者所不希望它做的事情。这正是电子对抗中要着力研究的问题。 并行计算中有两个基本问题：一个是控制的同步性；一个是数据的一致性。不论是并行的处理器，还是并行的线程，总需要保持某种程度上的同步，以期达到各个计算部件之间的协同与合作。尽管这种同步可以是紧耦合，也可以是松散的耦合。另一方面，各计算部件之间的数据一致性也至关重要。例如银行系统在为用户存取款服务时，人名的查找必须和存取款数量相对应，否则就错了。而这两件事可能由不同的计算部件或不同的时刻完成。而这种一致性常常能被故障，特别是恶意攻击所破坏。敌人的攻击也常常是利用这一点。拜占庭将军问题只把数据简化为二值的0和1。当然，多版本的一致性不单是“进攻”和“撤退”这样简单的信息，但原理是一样的。 为了保持多版本的一致性，系统需要一定的时间。在这段时间内，系统还没来得及达成一致，系统可能有可攻击的脆弱之处。这段时间表现为故障潜伏期，即敌人的攻击不一定马上生效，系统在某一时机来到时就可能做出错误的响应。 解拜占庭将军问题的算法给我们提供数据一致性的思路和算法。而在该算法中就有各位将军的同步问题。这些问题都为计算可信性的提高以启发。要解决拜占庭将军问题需要四模冗余，硬件开销是很大的。所以，现在银行的异地备份并不都是四模冗余。这就看你的系统要求有多高的安全性，相对于那些投资，孰轻孰重。 从拜占庭将军问题解法可以看出，签名和认证对保证数据安全有节省硬件的效果。这些技术将在后文详细介绍。