【正文】 和諧系統(tǒng)。ANSWERNot a clear problem. Seems a bitset can do.34.實現(xiàn)一個隊列。隊列的應(yīng)用場景為：一個生產(chǎn)者線程將int 類型的數(shù)入列，一個消費者線程將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)友，已標明）：：longzuo谷歌筆試：n 支隊伍比賽，分別編號為0，1，2。n1，已知它們之間的實力對比關(guān)系，存儲在一個二維數(shù)組w[n][n]中，w[i][j] 的值代表編號為i，j 的隊伍中更強的一支。所以w[i][j]=i 或者j，現(xiàn)在給出它們的出場順序，并存儲在數(shù)組order[n]中，比如order[n] = {4,3,5,8,1......}，那么第一輪比賽就是4 對3， 5 對8。.......勝者晉級，敗者淘汰，同一輪淘汰的所有隊伍排名不再細分，即可以隨便排，下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4 對5,直至出現(xiàn)第一名編程實現(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 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.百度面試：（只能比較，不能稱重）從一堆小球中找出其中唯一一個較輕的，使用x 次天平，最多可以從y 個小球中找出較輕的那個，求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)]有存儲器可以將其存儲下來，而且只輸入一次，如何從這個輸入流中隨機取得m 個記錄。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)化時間空間復(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).求一個二叉樹中任意兩個節(jié)點間的最大距離，兩個節(jié)點的距離的定義是這兩個節(jié)點間邊的個數(shù)，比如某個孩子節(jié)點和父節(jié)點間的距離是1，和相鄰兄弟節(jié)點間的距離是2，優(yōu)化時間空間復(fù)雜度。ANSWERHave done this.(2).求一個有向連通圖的割點，割點的定義是，如果除去此節(jié)點和與其相關(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