Re: [心得] Wearisma 面試心得

[pttworld (批踢踢世界)]

※ 引述《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://www.ptt.cc/bbs/Soft_Job/M.1520071199.A.7F4.html
→ lNishan: )(
→ lNishan: 連這種錯都抓不出來還好意思在前面砲人 ~_~
編輯了一下，再請你看一下了。

→ lNishan: 這樣是對的了 第一題這樣做是最佳解
推 drajan: leetcode上討論區不都有答案了?
→ Uzak: 第2題你忘了排序
maintaining the relative order

在你的英文翻譯是什麼。
※ 編輯: pttworld (111.184.19.168), 03/03/2018 20:17:03
推 Uzak: sorry我看錯，原原po例子剛好有排序我以為要排序
→ Uzak: 沒有仔細看他的題目
推 elements: 推
→ dnabossking: 記得我在code war解過一樣的題目
推 a110605: 推，這樣的思緒解題變得很簡單
→ steven11329: 第一題是遇到"("一定要有")" 配對吧，)( 是invalid
推 cateran: 第二題有c++一行解
→ cateran: fill(remove(nums.begin(),nums.end(),0),nums.end(),0)
推 sorryla: 一行解也只是把很多function塞在一行而已，還不是要解釋
→ sorryla: 每個function在做甚麼給面試官聽