AI & Data Dreamers練功房
寶箱片場規則
ALGO GATES・演算法關卡・高階・3 題

演算法高階・滑動視窗、字首樹與滾動雜湊

atMost 相減數區段、dict 字首樹做路由比對、二分搜尋加滾動雜湊找重複片段。

這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。

  1. 01

    剛好 k 個使用者的事件區段

    困難滑動視窗

    事件串流依時間記錄了每一筆事件的 user_id。分析「多人同時互動」的片段時,要數有幾個連續區段(至少一筆)裡剛好有 k 個不同的 user_id。起點或終點不同就算不同的區段。

    輸入:

    第 1 行:組數 t

    接下來 t 行:k user_id...(以空白分隔),或 GEN k n m seed(由 starter 產生 n 筆事件,user_id 是 u1 到 um)。GEN 開頭的行是大量測資的縮寫:starter 已寫好 gen(),讀進來後跟一般的 list 一樣,不用自己處理。

    輸出:每組一行,剛好有 k 個不同 user_id 的區段數。

    要求:用滑動視窗算「不同 user 數最多 k 個的區段數」,答案=atMost(k) − atMost(k−1),整體 O(n)。不要列舉每個起點往後掃(GEN 的資料有幾千筆)。

    範例輸入:

    2

    2 a b a c

    2 a a

    範例輸出:

    4

    0

    類型對應:LeetCode「Subarrays with K Different Integers」類(情境與敘述為本平台改寫)。

    輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。

    作答登入後可作答
  2. 02

    API 路由最長字首比對

    困難字首樹

    API 閘道依路徑把請求轉給後端服務。路由規則以 / 分段,段可以是固定字串或 *(* 剛好比對一個任意段)。一條規則比對到某個請求,是指規則的每一段依序跟請求路徑開頭的幾段相符(規則 / 沒有任何段,所以比對所有請求)。路徑前後多出來的 / 不影響分段,例如 /api/v1/ 與 /api/v1 一樣。

    有多條規則比對得到時,依序比較:

    1. 段數多的優先
    2. 段數一樣時,從第一段往後逐段比,第一個不同的段是固定字串的那條優先(固定字串勝過 *)

    輸入:

    第 1 行:規則數 r

    接下來 r 行:路由 服務名(不會有兩條規則的分段完全相同)

    下一行:查詢數 q

    接下來 q 行:請求路徑

    輸出:每個查詢一行 請求路徑 服務名(請求路徑照輸入原樣印出);沒有規則比對得到印 請求路徑 404。

    要求:用巢狀 dict 建字首樹,每個節點存子節點與(若有)服務名;查詢時沿著請求的段往下走,每一層同時試固定字串與 * 兩個分支。不要對每個查詢逐條比對所有規則。

    範例輸入:

    3

    /api/v1 v1

    /api/*/jobs jobs

    /api/v1/jobs jobs-v1

    3

    /api/v1/jobs/7

    /api/v9/jobs

    /home

    範例輸出:

    /api/v1/jobs/7 jobs-v1

    /api/v9/jobs jobs

    /home 404

    類型對應:LeetCode「Implement Trie (Prefix Tree)」類(情境與敘述為本平台改寫)。

    輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。

    作答登入後可作答
  3. 03

    事件代碼最長重複片段

    困難滾動雜湊

    每個工作階段的事件被編成一個字母代碼串(例如 L 是登入、V 是瀏覽、C 是加入購物車)。要找出整串中出現至少兩次的最長片段(連續的子字串),兩次出現可以重疊(例如 AAAA 的答案是 AAA)。最長的片段有好幾個時,取「第一次出現的位置」最前面的那個。

    輸入:

    第 1 行:組數 t

    接下來 t 行:一個由大寫英文字母組成的代碼串,或 GEN n seed 字母表(由 starter 產生長度 n 的代碼串,每個字元取自字母表)。GEN 開頭的行是大量測資的縮寫:starter 已寫好 gen(),讀進來後跟一般的 list 一樣,不用自己處理。

    輸出:每組一行 長度 片段;沒有任何重複的字元時印 NONE。

    要求:對長度做二分搜尋(長度 L 有重複,L−1 一定也有),檢查某個長度時用滾動雜湊在 O(n) 內算出所有長度 L 片段的雜湊值;雜湊相同要再比對字串,避免碰撞誤判。不要列舉所有片段兩兩比較。

    範例輸入:

    2

    LVCLVCX

    ABAB

    範例輸出:

    3 LVC

    2 AB

    類型對應:LeetCode「Longest Duplicate Substring」類(情境與敘述為本平台改寫)。

    輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。

    作答登入後可作答