IT 討論區（48）最強工種，FG25K，你！敢唔敢成功？

再玩下先

係呢度抄完答案就有interview?

space complexity係O(1)啊
頭兩個for都係純粹traverse the list，最後pop()都唔會clone條list

Sorry，it is O(1) indeed but what about the array being large than the main memory? You make 3 passes over arr. I think one pass is sufficient. The algorithm can be implemented as simple state machine using one-bit input.

太複雜，行數係短，但可讀性低咗，可能我問題，作code巴個寫法我覺得好d, 同埋code4food提出嘅space complexity你係O(n)

Btw,可唔可以用網頁版paste code

It is hard to estimate the space complexity of Haskell code due to lazy evaluation. Haskell only computes data that is necessary. Data not needed can be garbage collected. I can change my code to python of C++ easily using O(1) space. When you do addition, you only need to keep track of one digit at a time You can forget the previous digits. That's why I ask 作code人 if it is possible to process a billion digit using a computer with only 64K. 作code人's solution make 3 passes over the data so it is not possible. However, there are a simple way to change this into a stream processing algorithm.

嚴格黎講係2個，因為最後個while maximum應該得2個iteration，除非唔係
你意思係咁?

def solution(arr):
    for i in range(1, len(arr)):
        if arr[i] == 1:
            arr[i - 1] += 1
        if arr[i-1] == 2:
            arr[i-1] = 0
            arr[i] -= 1
    while arr and arr[-1] == 0:
        arr.pop()
    return arr

另外我唔明array large than the main memory點pass入黎，memory睇黎要惡補

其實返工都用唔著，亦都無人會想同你傾，只不過得閒做下d hackerrank消遺下，本身又唔係讀CS，多少都要pick up下
如果返工D同事會互相challenge，其實好好，一齊進步，可惜無呢支歌仔唱，大家淨係care 交到貨

You stream in the array and stream out the result at the same time. Since you only need to look at the current and the previous digit, you do not need too much memory to store the sliding window.

To handling potentially indefinite number of trailing zeros, you do not output zeros immediately, rather you keep a count of the current block of consecutive zeros. If you see a one in the output, you need to first output all the pending zeros and then reset the count, and then the one

而家fg做QA tester市價係幾多？
唔想頂爛市

我get到你意思係stream既case所以可以用64k電腦，呢到我get到，所以要變一個loop我都明
我睇唔明haskell，stream既話唔係好明最後點樣remove trailing zeros

而家fg做QA tester市價係幾多？
唔想頂爛市

12k

草起D 0我明，但如果太多consecutive 0都係唔work

You defer output a block of zeros until you see the next one. At the end of the output, check to see if it is the special case of all zeros, if so output just one single zero digit and close the output stream.

BTW, counting zero is no longer O(1) but O(log n). You need O(log n) bits to implement a counter.

無野了，係草count of 0，唔係草0

其實都唔使，trailing zeros最多得2個，除非唔係。
多過3個0已經可以output住先

變咗寫code 討論區

好撚毒

Sor囉

你坐咁遠又比人睇實，我地超FREE

其實我都唔後生，返工寫code差不多20年。 還未計由中一讀書開始dup code都有十幾年。

廢老!

中坑
想問下你，30/40歲打後其實係咪真係會變弱，要做management work，然後中年失業