【文章內(nèi)容簡介】 個pop 系列。因?yàn)榭梢杂腥缦碌膒ush 和pop 序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，這樣得到的pop 序列就是1。但序列2 就不可能是push 序列5 的pop 序列。ANSWERThis seems interesting. However, a quite straightforward and promising way is to actually build the stack and check whether the pop action can be achieved.int isPopSeries(int push[], int pop[], int n) { stackint helper。 int i1=0, i2=0。 while (i2 n) { while (() || () != pop[i2]) { if (i1n) (push[i1++])。 else return 0。 while (!() amp。amp。 () == pop[i2]) { ()。 i2++。 } } } return 1。} 到n 的正數(shù)中1 出現(xiàn)的次數(shù)題目：輸入一個整數(shù)n，求從1 到n 這n 個整數(shù)的十進(jìn)制表示中1 出現(xiàn)的次數(shù)。例如輸入12，從1 到12 這些整數(shù)中包含1 的數(shù)字有1，10，11 和12，1 一共出現(xiàn)了5 次。分析：這是一道廣為流傳的google 面試題。ANSWERThis is plicated... I hate it...Suppose we have N=ABCDEFG.if G1, of 1’s in the units digits is ABCDEF, else ABCDEF+1if F1, of 1’s in the digit of tens is (ABCDE)*10, else if F==1: (ABCDE)*10+G+1, else (ABCDE+1)*10if E1, of 1’s in 3rd digit is (ABCD)*100, else if E==1: (ABCD)*100+FG+1, else (ABCD+1)*100… so on.if A=1, of 1 in this digit is BCDEFG+1, else it’s 1*1000000。so to fast access the digits and helper numbers, we need to build the fast access table of prefixes and suffixes.int countOf1s(int n) { int prefix[10], suffix[10], digits[10]。 //10 is enough for 32bit integers int i=0。 int base = 1。 while (base n) { suffix[i] = n % base。 digit[i] = (n % (base * 10)) suffix[i]。 prefix[i] = (n suffix[i] digit[i]*base)/10。 i++, base*=10。 } int count = 0。 base = 1。 for (int j=0。 ji。 j++) { if (digit[j] 1) count += prefix。 else if (digit[j]==1) count += prefix + suffix + 1。 else count += prefix+base。 base *= 10。 } return count。}：一類似于蜂窩的結(jié)構(gòu)的圖，進(jìn)行搜索最短路徑（要求5 分鐘）ANSWERNot clear problem. Skipped. Seems a Dijkstra could do.int dij32.有兩個序列a,b，大小都為n,序列元素的值任意整數(shù)，無序；要求：通過交換a,b 中的元素，使[序列a 元素的和]與[序列b 元素的和]之間的差最小。例如:var a=[100,99,98,1,2, 3]。var b=[1, 2, 3, 4,5,40]。ANSWERIf only one swap can be taken, it is a O(n^2) searching problem, which can be reduced to O(nlogn) by sorting the arrays and doing binary search.If any times of swaps can be performed, this is a double binatorial problem.In the book beauty of codes, a similar problem splits an array to halves as even as possible. It is possible to take binary search, when SUM of the array is not too high. Else this is a quite time consuming brute force problem. I cannot figure out a reasonable solution.33.實(shí)現(xiàn)一個挺高級的字符匹配算法：給一串很長字符串，要求找到符合要求的字符串，例如目的串：1231******3***2 ,12*****3 這些都要找出來其實(shí)就是類似一些和諧系統(tǒng)。ANSWERNot a clear problem. Seems a bitset can do.34.實(shí)現(xiàn)一個隊(duì)列。隊(duì)列的應(yīng)用場景為：一個生產(chǎn)者線程將int 類型的數(shù)入列，一個消費(fèi)者線程將int 類型的數(shù)出列ANSWERI don’t know multithread programming at all....35.求一個矩陣中最大的二維矩陣(元素和最大).如:1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3要求:(1)寫出算法。(2)分析時間復(fù)雜度。(3)用C 寫出關(guān)鍵代碼ANSWERThis is the traditional problem in Programming Pearls. However, the best result is too plicated to achieve. So lets do the suboptimal one. O(n^3) solution.1) We have know that the similar problem for 1 dim array can be done in O(n) time. However, this cannot be done in both directions in the same time. We can only calculate the accumulations for all the sublist from i to j, (0=i=jn) for each array in one dimension, which takes O(n^2) time. Then in the other dimension, do the tradtional greedy search.3) To achieve O(n^2) for accumulation for each column, accumulate 0 to i (i=0,n1) first, then calcuate the result by acc(i, j) = acc(0, j)acc(0,i1)//acc[i*n+j] = acc(i,j)void accumulate(int a[], int n, int acc[]) { int i=0。 acc[i] = a[i]。 for (i=1。in。 i++) { acc[i] = acc[i1]+a[i]。 } for (i=1。 in。 i++) { for (j=i。 jn。 j++) { acc[i*n+j] = acc[j] acc[i1]。 } }}第36 題40 題（有些題目搜集于CSDN 上的網(wǎng)友，已標(biāo)明）：：longzuo谷歌筆試：n 支隊(duì)伍比賽，分別編號為0，1，2。n1，已知它們之間的實(shí)力對比關(guān)系，存儲在一個二維數(shù)組w[n][n]中，w[i][j] 的值代表編號為i，j 的隊(duì)伍中更強(qiáng)的一支。所以w[i][j]=i 或者j，現(xiàn)在給出它們的出場順序，并存儲在數(shù)組order[n]中，比如order[n] = {4,3,5,8,1......}，那么第一輪比賽就是4 對3， 5 對8。.......勝者晉級，敗者淘汰，同一輪淘汰的所有隊(duì)伍排名不再細(xì)分，即可以隨便排，下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4 對5,直至出現(xiàn)第一名編程實(shí)現(xiàn)，給出二維數(shù)組w，一維數(shù)組order 和用于輸出比賽名次的數(shù)組result[n]，求出result。ANSWERThis question is like nocopying merge, or in place matrix rotation.* Nocopying merge: merge order to result, then merge the first half from order, and so on.* in place matrix rotation: rotate 01, 23, .. , 2k/2k+1 to 02...2k, 1,3,...2k+1...The two approaches are both plicated. However, notice one special feature that the losers’ order doesn’t matter. Thus a halfway merge is much simpler and easier:void knockOut(int **w, int order[], int result[], int n) { int round = n。 memcpy(result, order, n*sizeof(int))。 while (round1) { int i,j。 for (i=0,j=0。 iround。 i+=2) { int win= (i==round1) ? i : w[i][i+1]。 swap(result, j, win)。 j++。 } }}37.有n 個長為m+1 的字符串，如果某個字符串的最后m 個字符與某個字符串的前m 個字符匹配，則兩個字符串可以聯(lián)接，問這n 個字符串最多可以連成一個多長的字符串，如果出現(xiàn)循環(huán)，則返回錯誤。ANSWERThis is identical to the problem to find the longest acylic path in a directed graph. If there is a cycle, return false.Firstly, build the graph. Then search the graph for the longest path.define MAX_NUM 201int inDegree[MAX_NUM]。int longestConcat(char ** strs, int m, int n) { int graph[MAX_NUM][MAX_NUM]。 int prefixHash[MAX_NUM]。 int suffixHash[MAX_NUM]。 int i,j。 for (i=0。 in。 i++) { calcHash(strs[i], prefixHash[i], suffixHash[i])。 graph[i][0] = 0。 } memset(inDegree, 0, sizeof(int)*n)。 for (i=0。 in。 i++) { for (j=0。 jn。 j++) { if (suffixHash[i]==prefixHash[j] amp。amp。 strncmp(strs[i]+1, strs[j], m) == 0) { if (i==j) return 0。 // there is a self loop, return false. graph[i][0] ++。 graph[i][graph[i*n]] = j。 inDegree[j] ++。 } } } return longestPath(graph, n)。}/*** 1. do topological sort, record index[i] in topological order.* 2. for all 0indegree vertexes, set all path length to 1, do relaxation in to