作者pttworld (批踢踢世界)
看板Soft_Job
標題Re: [心得] Wearisma 面試心得
時間Sat Mar 3 17:59:56 2018
※ 引述《gocreating (小平)》之銘言：
: 標題: [心得] Wearisma 面試心得
: 時間: Sat Mar 3 16:37:21 2018
:
: 網頁好讀版：https://goo.gl/ZegAep
:
: Technical Task
:
: 題目長這樣：
:
: Given a string with left and right parentheses, how you verify the string is
: valid (balanced)
: Ex. ((())()()()) -> Valid, ()) → Invalid
這個問題僅需一個整數變數出值為0，定義遇到(整數+1，遇到)整數-1，
O(n)掃一遍，在掃的過程中整數為負即為Invalid，最後結果整數不為0即為Invalid
special case是空字串，預設整數為0為Valid，但是要看題目定義，
有些題目可能認為空字串是Invalid，這個case視情況客製。
:
:
: 第二階段面試
:
: 第二階段是純粹的Coding Test，面試官開了一個共同編輯的google docs給我，上面已經
: 列好題目如下：
:
: Given an array A, write a function to move all 0's to the end of it while
: maintaining the relative order of the non-zero elements. For example, A = [0,
: 1, 0, 3, 12], after calling your function, A should be [1, 3, 12, 0, 0].
:
: 乍看下會覺得很簡單，開新的陣列來存不就好了，但是往下一看附帶了2項限制：
:
: Note:
: You must do this in-place without making a copy of the array.
: Minimize the total number of operations.
這個問題僅需使用二個整數變數掃一次O(n)解決。
二個變數都是當作index，一個負責遇到0，一個負責遇到非0
遇到非0就把值copy到0的index，然後0的index + 1
最後跑完把0的index後面位置全部填0
int zero_i = 0, non_zero_i = 0;
while(non_zero_i < length_of_array) {
if(A[non_zero_i] != 0) {
A[zero_i] = A[non_zero_i];
zero_i += 1;
}
non_zero_i += 1;
}
while(zero_i < length_of_array) {
A[zero_i] = 0;
zero_i += 1;
}
學生時期練ACM到800題AC打住，結果工作寫組語，轉行IT也沒考過這類白板。
解題這真的要視行業是否有需要才練，能把心態調整成興趣是最好了。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.184.19.168
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Soft_Job/M.1520071199.A.7F4.html
1F：→ lNishan: )( 03/03 18:06
2F：→ lNishan: 連這種錯都抓不出來還好意思在前面砲人 ~_~ 03/03 18:08
編輯了一下，再請你看一下了。
3F：→ lNishan: 這樣是對的了 第一題這樣做是最佳解 03/03 18:20
4F：推 drajan: leetcode上討論區不都有答案了? 03/03 18:24
5F：→ Uzak: 第2題你忘了排序 03/03 20:08
maintaining the relative order
在你的英文翻譯是什麼。
※ 編輯: pttworld (111.184.19.168), 03/03/2018 20:17:03
6F：推 Uzak: sorry我看錯，原原po例子剛好有排序我以為要排序 03/03 20:21
7F：→ Uzak: 沒有仔細看他的題目 03/03 20:22
8F：推 elements: 推 03/03 20:46
9F：→ dnabossking: 記得我在code war解過一樣的題目 03/03 22:48
10F：推 a110605: 推，這樣的思緒解題變得很簡單 03/04 10:48
11F：→ steven11329: 第一題是遇到"("一定要有")" 配對吧，)( 是invalid 03/05 07:59
12F：推 cateran: 第二題有c++一行解 03/05 08:26
13F：→ cateran: fill(remove(nums.begin(),nums.end(),0),nums.end(),0) 03/05 08:27
14F：推 sorryla: 一行解也只是把很多function塞在一行而已，還不是要解釋 03/06 09:41
15F：→ sorryla: 每個function在做甚麼給面試官聽 03/06 09:41