LeetCode 刷題知識總整理
前言這篇用來記錄刷leetcode 的各類主題，以及不同情境下要用的對應解題策略是哪些，也連接到之前所做的筆記跟部落格 Roadmap 這邊是參考 NeetCode 官網的roadmap 按照不同主題進行刷題的 Big-O https://www.bigocheatsheet.com/ Two PointersTwo pointer 如果出現在陣列題目中，代表兩個索引(index)，如果出現在 Linked List題目中，代表兩個不同的指標。但核心目的都是一樣的，透過移動pointer位置來減少溶於計算提高效率。 常見的Two pointer類型： 反向指針: 一個指向頭部一個指向尾部，逐漸向中間靠攏，檢查回文, 兩數之和通常很常用這種類型 快慢指針: 一個指針較快，另一個指針較慢，可以用於檢測Linked List 中是否有環。 某些情況下會搭配 Sliding Windows 來去動態調整子陣列的大小，Ex.右指針擴展Windows，左指針收斂windows。以下整理常見的 Two Pointer 使用時機： $O(N^2)$ 降低成 $O(N)$,題目要求降...
DevOps技能樹知識整理 |【筆記目錄】
前言這裡紀錄 DevOps 面試常見的知識點，主要是參考了這個 github repository: DevOps Exercises 和 ByteByteGo 的 GitHub Repo 所做的筆記整理 可能會花很久時間才能夠全部整理完成~ DevOps GeneralPython Basic Data Types OOP / Class Raise Exceptions Regex Async File Manipulation OS lambda decorator Flask 文章： Python for DevOps |【DevOps技能樹】 Networking TCP/UDP OSI Model CIDR Mac Addr. CSMA/CD NAT DNS ICMP TLS/SSL Handshake Route Table ARP DHCP VLAN SDN Configuration ..etc Linux Basic Commands Filesystem Hierarchy Standard Permi...
NASA HDTN 架構解析：太空 DTN 如何真正運作？
前言：從 DTN 的概念，走向真正可以運作的太空網路在上一篇文章 〈為什麼太空網路需要 DTN？從 TCP/IP 的限制到深空網路〉 中，我整理了太空網路和地面 Internet 之間最根本的差異。 在地球上，我們通常預期來源與目的地之間存在一條可以立即使用的完整路徑。即即便途中偶爾發生遺失封包，TCP 也能透過 ACK、Timeout 與 Retransmission 等一大堆機制處理問題～ 但如果場景在太空中，斷線不一定代表故障。舉例來說，狀況可能是：衛星可能飛出地面站的可視範圍，月球探測車可能進入隕石坑，航天器可能為了節省能源暫時關閉通訊模組。另外，不同節點之間的連線，也可能受到軌道位置、天體遮蔽、天線方向與通訊排程影響 因此，太空網路不能只看 現在有沒有一條可以立刻抵達終點的路？ 還必須進一步考慮： 下一次可以轉送資料的機會是什麼時候？, 在那之前，資料應該先存放在哪一個節點？, 如果通訊窗口突然消失，又該如何恢復傳輸？ 以上就是 Delay/Disruption-Tolerant Networking（DTN） 試圖解決的問題 而我的上一篇文章已經介...
二元樹的垂直走訪 | Hard | LeetCode#987. Vertical Order Traversal of a Binary Tree
題目敘述 題目難度： Hard 題目描述： 這題給定二元樹的 root, 要我們實踐垂直走訪二元樹 這邊題目解釋垂直走訪的定義，每個節點都有位置 (row, col)， 而 left children 的座標相對於 root 會是 (row+1, col-1) 反之 right children 的座標會是 (row+1, col+1) 。 垂直走訪的意思是由上而下，由左而右的方式開始走訪，起點會是最左側的節點，接著會是下一個 column 依序走訪，而在 column 當中最後回傳的走訪順序，同column 需按照節點值大小由小排到大。也會有多個節點存在於相同座標的情況，也一樣依照節點值排序。最終輸出走訪順序。 解法一開始的想法這題一開始想法有點歪掉，原本是想說如果把最左側當成新的root, 橫的進行BFS，然後依序把下一column 丟到queue，但這樣還會需要用複雜的邏輯紀錄每個節點的parents是誰，挺麻煩。 後來換了想法，其實題目給的座標很方便，要是我們有個結構同時存放節點值跟座標的關聯，那就只要迭代最終這個結構，按照 column 順序輸出即可。 所以...
快照陣列 | Medium | LeetCode#1146. Snapshot Array
題目敘述 題目難度： Medium 題目描述： 這題要你實踐一個 class SnapshotArray 要支援以下功能： SnapshotArray(int length) : 根據給定長度參數 length 初始化陣列結構大小，最初每個元素值為0 void set(index, val): 將給定 index 對應值設定成 0 int snap(): 對陣列結構進行快照，並且回傳 snap_id 這邊的 snap_id 會是每次呼叫 snap method 次數扣掉 1 int get(index, snap_id): 回傳給定 snap_id 時間中 index 對應的儲存值 解法一開始的想法一開始先釐清主要目標： 實踐類似陣列的 DS 紀錄每次呼叫 snap 次數 保存特定 snap_id 時刻，陣列結構狀態 這種想法有點偏暴力，我一開始的想法是，透過一個 Hash Table 保存像是 { snap_id: array} 的結構，透過另一個暫存的 latest_array 來記錄當前最新的陣列是哪個， set 就直接更新 latest_a...
為什麼太空網路需要 DTN？從 TCP/IP 的限制到深空網路
前言：在太空中，我們還能順暢地上網嗎？ 前陣子看了 NASA Artemis II 繞月行動的直播，看著火箭升空，算是見證了人類的另一個里程碑。近年不論是 NASA 、商業月球酬載服務（CLPS）、SpaceX Starship 的進展，以及各國對月球與深空任務的投入，都讓太空基礎設施 不再只是科幻概念，而是逐漸走向工程實作的問題。但身為一個工程師，我腦中浮現出一個很實際的問題：「如果我們要在太空發展科技，甚至建立基地，那我們地球上現有的網路架構，搬到太空中還能直接用嗎？」為了解答這個疑惑，我就爬了一些相關論文與技術文件中進行研究。這篇文章，就算是我的學習筆記跟總結～ 直覺上，我們可能會認為：「只要把天線做大、訊號功率推高、多發射幾顆中繼衛星，不就能把地球上的 Internet 延伸到太空了嗎？」但實際上，太空網路面臨的挑戰，絕對不是單純的 頻寬不夠 或 訊號太弱 。 最根本的問題在於：整個網路環境的基本假設，在太空中完全變了。 因為地球上的網際網路，通常假設端到端（end-to-end）的路徑絕大多數時間都是暢通的，封包可以在極短時間內抵達目的地。斷線通常視為「異常狀況」。但...
K 組反轉節點 | Hard | LeetCode#25. Reverse Nodes in k-Group
題目敘述 題目難度: Hard 題目敘述: 題目給定一個 linked list 的 head，請每 k 個節點反轉一次，最後回傳整個 linked list 的 head 這邊的 k 會是正整數，如果 list 長度無法整除 k 則剩餘的節點不反轉然後題目有提醒，你只能變更整的節點，不能夠透過改節點值來完成這題，另外也希望在 O(1) 空間複雜度完成這題 這邊也可以觀察題目的 constraint， 1 <= k <= n <= 5000 解法一開始的想法我的想法其實就是，先找有幾組，然後剩餘湊不滿一組的就不管它。然後每一組會做反轉，因為每 k 個節點會是一組，可能單獨一個用於反轉的函數來處理，然後丟那一組的 head, tail 跟 前一組的尾端。 所以應該會是，迴圈迭代去找每一組的頭跟尾，回圈內呼叫用於反轉list的函數，接著回傳回來的節點應該要是新的 head，這個 head 還要再去跟前一組尾端接起來。 最後回傳新的 list 的頭 我的解法1234567891011121314151617181920212223242526272829303...
使用 SatNOGS 架設衛星地面站的實作與分析
Introduction過去我對一直衛星是如何與地面站通訊這件事充滿興趣，包含，衛星如何被追蹤、地面站如何取得軌道資料(Ex. TLE 還有就是 SDR 接收到的訊號) 如何轉換成可解碼的 IF Frequency等等。 因此我決定以 SatNOGS（Satellite Networked Open Ground Station 作為切入點，架設一個可以自動排程、追蹤、接收衛星信號的完整 ground station 實作過程讓我對衛星任務運作與Ground Segment有具體的理解 SatNOGS 介紹SatNOGS 是一個全球性的衛星地面站網路，使用者可以：(1)架設自己的 Ground Station , (2)加入 SatNOGS 全球 Network , (3)接收並上傳衛星觀測資料 其架構包含： SatNOGS Network： 排程、任務分配、收集結果 SatNOGS Client： 在本地端控制 SDR、rotator、recording SatNOGS DB： 衛星資料庫（頻率、modulation、TLE 等） 官方參考文件 - Build S...
多米諾與三格骨牌鋪磚問題 | Medium | LeetCode#790. Domino and Tromino Tiling
題目敘述 題目難度: medium 題目敘述: 題目給定兩種骨牌，一種會是 2*1 大小的長方形骨牌，另一種會是 L型骨牌。給定整數 n，請回傳用這兩種骨牌撲滿 2*n 大小板子的擺放方式。答案可能會很大，因此回傳時要對 1000000007 取餘數 解法我的解法這題好像也是經典的 dp題目，首先要定義我們要解的 dp[n] 代表的意義，既然我們最後要回傳的是有幾種擺放方式，那 dp 內要存放的就是有幾種擺放方法。 因此對於 dp[n] 代表 2*n 大小的板子可以被兩種骨牌撲滿的方法數 1234567891011121314151617181920class Solution {public: int numTilings(int n) { if(n==1) return 1; if(n==2) return 2; // dp[n]: the number of methods of fill 2*n board using domino and trimino tiles ...
initrd 與 initramfs 差異介紹 | Linux Kernel
Introduction在開機早期，會需要一個暫時的檔案系統，來在開機初期進行初始化跟組態設定，有兩種機制來去使用暫時的檔案系統，分別是 Initrd (Initial RAM Disk) 以及 Initramfs (Initial RAM Filesystem) 。 其中 initrd 會是比較早期的作法，現今大多開機流程都使用 initramfs 居多。 Initrd Initrd（Initial RAM Disk）是一個早期 Linux 開機使用的暫時性 root filesystem。 它的形式是 一個被 gzip 壓縮的 block image，開機時會被放進一個虛擬 RAM Disk（例如 /dev/ram0 ）中，再由 kernel 掛載成初始 root。 它通常包含： = 掛載真正 rootfs 所需的驅動 一個 linuxrc（類似 init 的 early user-space script） 掛載 /proc、/sys 之類的初始化腳本 用 Initrd 開機想要透過 initrd 開機，會需要在 bootloader 階段就被 bootlo...
