---
# System prepended metadata

title: Databricks OA

---

# Databricks OA

:::info
規定：
開鏡頭、share螢幕
身份驗證（準備passport）
只開一個browser
不能用其他device
可用白紙
:::

### 第一題almostSubstring

給兩個string: t, s
s長度為3
計算t 中可以找到幾個 t<sub>i</sub> t<sub>i+2</sub> t<sub>i+4</sub> 與 s 相等
ex:
t = "azcabcab"
s = "acb"
return 2 (i = 0 & i = 3)

### 第二題sumOfString

給兩個數字string，將兩個digit數字相加後相接，回傳string
ex:
"99" + "99" = "1818"
"11" + "9" = "110"

### 第三題allignMemoryAllocation

給一個memory 由 0, 1組成的array
對這個memory作操作，給另一個array 含有多個 query
每個memory block的size是8，（每個block 從 index 0, 8, 16, ... 開始）
第一種query為 alloc X, X為integer，須找到leftmost的block含有連續X數量的0，將他們都改成1 ，alloc 成功回傳index, alloc失敗回傳 -1
第二種query為 erase ID, 將目標位置的1改成0, ID 為alloc的區塊的ID，第一個alloc成功 ID = 1, 第二個alloc成功 ID = 2，erase成功的話 return erase 的 unit 的數量，不成功則return -1
最後答案 return 每個 query 回傳值組成的array

### 第四題 spltTowerintoPairs

給一個array是towers的高度
你可以增加或減少每個tower的高度 by 2
回傳 至少幾次增加或減少可以使得towers兩兩高度相等
ex: 
input: [1, 4, 3, 2] 
output: 2 (高度1 + 2, 與3配對 ; 高度 4 - 2 與2配對)
無解 return -1