一道又證明我是失敗人士的演算法題

前兩天去一家比較大的公司面試。

一開始是兩個人問我，先問我CSS，於是我就崩了。沒錯，在CSS問題上我崩了。。。我要不考慮轉行過柱子。。然後是js問題哈，問我菲波那切數列想考我遞歸，然而我不按套路出牌實現了非遞歸版本，然後就打亂他們的節奏了。一開始說我寫的不對，人肉運行一下發現我寫的是對的。。。。(遞歸+一個緩存結果(類似於underscore的memorize)真么有什麼好考的）。然後問我閉包，我就講詞法作用域了，看他們表情似乎我有不按套路出牌了。後來他們兩個又問了我幾個經典的例子才確定我懂閉包 。。然後就是扯vue，他們用的是react技術棧，我就講了一下vue的一些基本實現原理。。還有一些雜七雜八的小問題。

然後換一個人來面我，問我vue的原理，hold住場面。然後問我ES6熟嗎，然後是非同步方案，一開始就想起一個promise，後來他一提es7我就想起來async了。。於是就下一個人來面我了。

最後這位先問我是蔥大哪個校區的。。。然後談了一些vue的實現原理，談虛擬DOM的時候有點控制不住場面，畢竟剛看到這。接著是性能優化，我就說了一些基本的東西，畢竟這個沒系統掌握過。。最後就是演算法了，有以下這麼幾個問題：

* 平衡二叉樹 (這個真忘了，說明我真的是失敗人士

* 歸併排序(用中文實現還是so easy的

* 快速排序(雖然化學專業的人設是不會快排，但用中文實現快排還是可以的

* 反轉單向鏈表(基礎題，用畫圖的形式實現了

以上是廢話太多的背景介紹。要說的是一道演算法題，雖然時間上它不是最後被問到的。兩個按升序排列的有序序列，求按序合併後的中間值。比如[1,4,8,102,250]和[2,5]，中間值是5（1,2，4,5，8，102,250）。

我一開始沒多想，就當成簡單地合併問題了，雖然可行吧，說了這個方案後面試官提醒我如果數量多的時候有優化方案嗎。然後我就溢出了。

回來查了一下似乎這是leetcode上的題(看來貴前端圈真的水漲船高了，快排已經撐不住場面了)，那就老老實實做一做（看看別人思路）吧。

當時面試官只讓我考慮合併後是奇數個的情況，考慮偶數個其實也是類似的。假設總元素有N個，奇數個的情況就是求合併後的第(N+1)/2個元素，偶數個的情況是求第N/2和N/2+1個元素，通用一點就是求合併後的第K個元素。(計數都是從1開始)。

我們在第一個序列中從前到後按序取m個元素，在第二個序列中取K-m個元素，這樣所選取的元素就是K個。然後我們去比較這兩個子序列的最大值(下面代碼的value1和value2)，如果value1小於value2，說明從第一個序列選取的元素都在合併後的第K個元素之前，所以我們就不用去關心這些元素了，篩選元素範圍縮小的同時K值也要減去被篩去的元素的數量。剩下的就是遞歸的去處理剩餘的未篩選的元素。退出條件是啥，一個是一個序列沒有未被篩選的元素(這個序列所有元素合併後都在第K個元素之前)，一個是K為1，只需比較開始兩個元素。

下面是我按照這個思路實現的代碼：

function findKthValue(arr1,arr2,K,startIndex1=0,startIndex2=0){ntvar rest1 = arr1.length - startIndex1;ntvar rest2 = arr2.length - startIndex2;nt// 保證arr1對應的待處理元素數量小於arr2的ntif(rest1>rest2){nttvar temp = arr1;nttarr1 = arr2;nttarr2 = temp;nntttemp = startIndex1;nttstartIndex1 = startIndex2;nttstartIndex2 = temp;nntttemp = rest1;nttrest1 = rest2;nttrest2 = temp;nt}nntif(rest1 === 0){nttreturn arr2[startIndex2+K-1];nt}nntif(K === 1){nttreturn Math.min(arr1[startIndex1],arr2[startIndex2]);nt}nntvar middle = Math.floor(K/2);ntvar endIndex1 = startIndex1 + middle -1;ntvar endIndex2;nt// var endIndex2 = startIndex2 + middle;ntif(endIndex1>arr1.length-1){nttendIndex1 = arr1.length - 1;nttendIndex2 = startIndex2 + K - (endIndex1 - startIndex1 + 1) -1;nt}else{nttendIndex2 = startIndex2 + K - middle -1;nt}nntvar value1 = arr1[endIndex1];ntvar value2 = arr2[endIndex2];nt// console.log(value1,value2)ntif(value1<value2){nttreturn findKthValue(arr1,arr2,K-(endIndex1-startIndex1+1),endIndex1+1,startIndex2);nt}else if(value1>value2){nttreturn findKthValue(arr1,arr2,K-(endIndex2-startIndex2+1),startIndex1,endIndex2+1);nt}else{nttreturn value1;nt}nnn}nn// 5nvar test1 = [1,3,7,9];nvar test2 = [5];nconsole.log(findKthValue(test1,test2,3));nn// 3nvar test3 = [1,3,5];nvar test4 = [1,2,3,4];nconsole.log(findKthValue(test3,test4,4));nn// 67nvar test5 = [1,4,8,102,250];nvar test6 = [3,55,67,92,107,233];nconsole.log(findKthValue(test5,test6,6));nn// 5nvar test7 = [1,4,8,102,250];nvar test8 = [2,5];nconsole.log(findKthValue(test7,test8,4));n

然而並沒有什麼用。失敗就是失敗 。

於是，作為失敗人士的我TODO 上又多了一件事。反正遲早要做。

推薦閱讀：