【正文】 和諧系統(tǒng)。ANSWERNot a clear problem. Seems a bitset can do.34.實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的應(yīng)用場景為：一個(gè)生產(chǎn)者線程將int 類型的數(shù)入列，一個(gè)消費(fèi)者線程將int 類型的數(shù)出列ANSWERI don’t know multithread programming at all....35.求一個(gè)矩陣中最大的二維矩陣(元素和最大).如:1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3要求:(1)寫出算法。(2)分析時(shí)間復(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)系，存儲在一個(gè)二維數(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 個(gè)長為m+1 的字符串，如果某個(gè)字符串的最后m 個(gè)字符與某個(gè)字符串的前m 個(gè)字符匹配，則兩個(gè)字符串可以聯(lián)接，問這n 個(gè)字符串最多可以連成一個(gè)多長的字符串，如果出現(xiàn)循環(huán)，則返回錯(cuò)誤。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 topological order to find single source shortest path.*/int visit[MAX_NUM]。int parent[MAX_NUM]。// 1 path weight, so 0 is enough.define MAX_PATH 0 int d[MAX_NUM]。int longestPath(int graph[], int n) {memset(visit, 0, n*sizeof(int))。if (topSort(graph) == 0) return 1。 //topological sort failed, there is cycle.int min = 0。for (int i=0。 in。 i++) {if (inDegree[i] != 0) continue。memset(parent, 1, n*sizeof(int))。memset(d, MAX_PATH, n*sizeof(int))。d[i] = 0。for (int j=0。 jn。 j++) {for (int k=1。 k=graph[top[j]][0]。 k++) {if (d[top[j]] 1 d[graph[top[j]][k]]) { // relax with path weight 1d[graph[top[j]][k]] = d[top[j]] 1。parent[graph[top[j]][k]] = top[j]。if (d[graph[top[j]][k]] min) min = d[graph[top[j]][k]]。} }}}return min。}int top[MAX_NUM]。int finished[MAX_NUM]。int t = 0。int topSort(int graph[]){memset(visit, 0, n*sizeof(int))。memset(finished, 0, n*sizeof(int))。for (int i=0。 in。 i++) {if (topdfs(graph, i) == 0) return 0。}return 1。}int topdfs(int graph[], int s) {if (visited[s] != 0) return 1。for (int i=1。 i=graph[s][0]。 i++) {if (visited[graph[s][i]]!=0 amp。amp。 finished[graph[s][i]]==0) {return 0。 //gray node, a back edge。}if (visited[graph[s][i]] == 0) {visited[graph[s][i]] = 1。dfs(graph, graph[s][i])。} }finished[s] = 1。top[t++] = s。return 1。}Time plexity analysis:Hash calculation: O(nm)Graph construction: O(n*n)Toplogical sort: as dfs, O(V+E)All source longest path: O(kE), k is 0indegree vetexes number, E is edge number.As a total, it’s a O(n*n+n*m) solution.A very good problem. But I really doubt it as a solvein20min interview question.38.百度面試：（只能比較，不能稱重）從一堆小球中找出其中唯一一個(gè)較輕的，使用x 次天平，最多可以從y 個(gè)小球中找出較輕的那個(gè)，求y 與x 的關(guān)系式。ANSWER:x=1, y=3: if a=b, c is the lighter, else the lighter is the lighter...do this recursively. so y=3^x。，大到?jīng)]有存儲器可以將其存儲下來，而且只輸入一次，如何從這個(gè)輸入流中隨機(jī)取得m 個(gè)記錄。ANSWERThat is, keep total number count N. If N=m, just keep it.For Nm, generate a random number R=rand(N) in [0, N), replace a[R] with new number if R falls in [0, m). 字符串，如何從中去除重復(fù)的，優(yōu)化時(shí)間空間復(fù)雜度ANSWER1. Use hash map if there is enough memory.2. If there is no enough memory, use hash to put urls to bins, and do it until we can fit the bin into memory.39.網(wǎng)易有道筆試：(1).求一個(gè)二叉樹中任意兩個(gè)節(jié)點(diǎn)間的最大距離，兩個(gè)節(jié)點(diǎn)的距離的定義是這兩個(gè)節(jié)點(diǎn)間邊的個(gè)數(shù)，比如某個(gè)孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1，和相鄰兄弟節(jié)點(diǎn)間的距離是2，優(yōu)化時(shí)間空間復(fù)雜度。ANSWERHave done this.(2).求一個(gè)有向連通圖的割點(diǎn)，割點(diǎn)的定義是，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，有向圖不再連通，描述算法。ANSWERDo dfs, record low[i] as the lowest vertex that can be reached from i and i’s successor nodes. For each edge i, if low[i] = i and i is not a leaf in dfs tree, then i is a cut