面試題目二 - hjwu

由於已經遲繳了，因此看到Codility 題目只要求正確性後我對時間/ 空間複雜度也就不太在意了。

總共是3 題兩小時，下面列出我理解後的內容與解答，但程式碼 ... Frank乾一杯dark light hacker solarized kimbieAboutTimelineTagsCategoriesSeriesdark light hacker solarized kimbieAbout TimelineThispagelooksbestwithJavaScriptenabled面試題目二📅 Aug20,2020  · ☕ 2 minread 2017年獵頭幫我介紹的面試考題。

當時信上寫Before2017-10-30結果我發現時已經是2017-10-31凌晨了…😅由於已經遲繳了，因此看到Codility題目只要求正確性後我對時間/空間複雜度也就不太在意了。

總共是3題兩小時，下面列出我理解後的內容與解答，但程式碼可能跟我交付的有差。

😩第一題給定一字串S(只有數字與英文字母)，找出最長子字串滿足內容沒有數字且至少有一大寫字母。

如果存在回傳該子字串長度，否則回傳-1看著倒數計時的數字，我還是有點緊張。

所以我直接暴力這題1 2 3 4 5 6 7 8 9 10 intSolution(stringS) { if(string.IsNullOrWhiteSpace(S))return-1; varlongestSub=S.Split(newchar{'0','1','2','3','4','5','6','7','8','9'}) .Where(s=>s.Any(c=>char.IsUpper(c))) .OrderByDescending(s=>s.Length) .FirstOrDefault(); returnlongestSub==null?-1:longestSub.Length; } 等醒來後才想到也可以不用Linq這樣寫1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 intSolution(stringS) { intans=-1; intsum=0; boolhasUpper=false; foreach(charcinS) { if(Char.IsDigit(c)) { if(hasUpper)ans=Math.Max(ans,sum); sum=0; hasUpper=false; continue; } hasUpper|=Char.IsUpper(c); sum++; } if(hasUpper)ans=Math.Max(ans,sum); returnans; } 第二題給定POP,DUP,+,-跟數字組成的字串算出結果。

請依下表計算答案，若答案為負或是無法計算請回傳-1。

指令意思POPPOPDUPDUPLICATE+ADD-Subtract數字PUSH例如給45DUP2+8-POP答案為5。

指令結果4454,5DUP4,5,524,5,5,2+4,5,784,5,7,8-4,5,1POP4,5這題基本上用Stack加暴力法就解決了。

雖然題目很長，但卻很簡單。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 intSolution(stringS) { string[]ops=S.Split(''); object[]o=newobject[ops.Length]; for(inti=0;istack=newStack(); try { foreach(objectopino) { if(opisint)stack.Push((int)op); else { if(op.ToString()=="POP")stack.Pop(); elseif(op.ToString()=="DUP")stack.Push(stack.Peek()); elseif(op.ToString()=="+")stack.Push(stack.Pop()+stack.Pop()); elseif(op.ToString()=="-")stack.Push(stack.Pop()-stack.Pop()); elsereturn-1; } } intans=stack.Pop(); returnans<0?-1:ans; } catch { return-1; } } 第三題給定一非負整數，試將其位數重排，回傳有效相異整數個數。

例：123回傳6,223回傳3,120回傳4,100回傳1這題基本上就是數學題。

但我稍微卡了一下，一直打結在錯排問題(Derangement)上，浪費了一些時間。

另外由於題目數字範圍，我一度想把階乘的函數直接寫死。

😏1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 intSolution(intN) { int[]counts=newint[10]; while(N>0) { counts[N%10]++; N/=10; } intproduct=1; for(inti=1;i<10;i++)product*=GetFactorial(counts[i]); intdigitCount=counts.Sum(); intans=GetFactorial(digitCount)/(GetFactorial(counts[0])*product); if(counts[0]>0)ans-=GetFactorial(digitCount-1)/(GetFactorial(counts[0]-1)*product); returnans; } intGetFactorial(intn) { if(n==0)return1; elsereturnn*GetFactorial(n-1); } 結論沒看到三題的分數，不知道是不是因為逾期所以拿到缺考。

另外不知道是不是祖先保佑，我覺得Codility給的這三題比LeetCode跟ProjectEuler都簡單很多。

😬WRITTENBYFR4NKMath/BackendRD面試題目一面試題目三What'sonthisPage 第一題第二題第三題結論