Try   HackMD

2022-12-06 課堂問答簡記

System Design Course

System design helps us define a solution that meets the business requirements. It is one of the earliest decisions we can make when building a system. Often it is essential to think from a high level as these decisions are very difficult to correct later. It also makes it easier to reason about and manage architectural changes as the system evolves.

Example: Twitter

  • '#' function implementation
    • Explaination: Tag功能，可以自行在貼文中標註此貼文與某個議題相關
    • Criteria:
      • 避免search all data/tweets
        • latency
        • computational cost
      • 不需要"精準搜尋"
    • How:
      • 可以先透過額外紀錄常使用此'#'的userID、region等等資訊，之後當用這個tag進行搜尋時，則直接在這個另外儲存的空間中尋找即可。
  • The index in the database
    • 索引(Index)是一種資料結構，目的為在進行資料庫搜尋、檢索時可以更有效率，例如：無須搜尋整個表(table)。
      • 若表中有n條紀錄(record)，逐條進行比對則需要O(n)的時間。
    • 通常透過使用額外的儲存空間(表)來儲存。
    • 索引會複製原表中部分的欄位，且通常可以連結回原本的完整紀錄，以方便取得其他欄位的資料。
    • 索引也可以事先過濾掉不需要的紀錄，以縮小所需的空間，並提高這種資料結構的效率。
      • e.g., 我們可以在索引中儲存包含"#Linux"這個tag的column以及對應的UserID，將來在搜尋"#Linux"這個tag時，我們便可以快速地取得對應的UserID，而不需要逐條紀錄進行比對。

Search Tree

2-3-4樹

除了葉節點外，每個節點都有2~4個子節點，故名2-3-4樹。實作較為困難，因為其特殊情況很多，所以現今較少使用在 Database 中，取而代之的是「紅黑樹」，因紅黑樹與2-3-4樹為等價的資料結構，所以對於每個2-3-4樹，都存在至少一個資料元素是同樣次序的紅黑樹。

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

紅黑樹

有以下基本五個的特性

  1. 每個節點會是紅色或是黑色
  2. 根節點一定是黑色
  3. 葉節點一定是黑色(葉節點會是 NIL 節點)
  4. 紅色節點的子節點一定都是黑色的
  5. 從任意節點到其所有葉節點，經過的黑色數量是一樣的

利用這些性質保證了從根節點到任意葉節點的路徑，最多相差一半，應其較好時做所以比2-3-4樹常實用

B+Tree

上週的課程筆記已經提及過，可以看這邊 - Link。B+Tree改善了 B Tree 可能會因為資料量太大(這了指的是 Key-Value 的 Value 大小，不是只資料總數)而一個節點能儲存的空間變少的問題，且因為葉節點的串聯達到很方便的範圍搜尋。

Search in Database

(以下皆以 InnoDB 為例)

  • Search by Primary Key
    只需要用搜尋樹的走法找到目標就可以了。

  • Search by Secondary Key (Not Primary Key )
    會有一顆利用 Secondary Key 建出來的樹，LeafNode 除了目標值外，也儲存了 其對應的 Primary Key所以可以再用 Primary Key 建的樹找到目標資料。

Join Table

通常 Join 使用上就是"Select From Where"，若沒有 Where 則就只是將所有狀況列出來而已。所以通常會是由一個 Table 從頭往後走(因為葉節點都串聯，所以可以直接從第一個走到最後一個)，將每個 Data 根據 Where 條件去另外一個 Table 的 Tree 中 Search。

校友經驗分享問答: Tony

  1. Intern 的選擇
    • 在履歷上有加分作用的的的
    • 牌子大的優先
  2. 海外求職眉角
    • 求職方的準備流程不多
    • 缺開出來就投
  3. 畢業後的 Offer
    • 先投 Startup 練面試
      • Startup 的 Hire 流程比較快
      • 快則 2-3 週
    • 也把 Offer 當 Backup
  4. 選 AWS 的原因
    • 目標：想要參與高流量的 back-end 開發
      • AWS CloudWatch Million QPS
    • What's CloudWatch
    • 在開發時會想更多效率上的優化
      • Case： 改一個流程幫公司省了 7 Million USD
  5. AWS 面試流程
    1. Online Assessment (OA)
    2. Visual interview
      • Amazon 注重 Leadership
      • Behavior question
  6. Performance Improvement Plan
    • 參考
    • Tony 澄清：不容易發生
  7. Bloomberg terminal
    • 金融資訊整合系統
      • 股價、新聞消息
    • 參考

學長的 Keynote: 看到缺就投！

QA

  1. 怎麼針對這麼多的公司作 Resume 的修改和面試的準備呢？
    • 【Tony 個人看法】
      • 不太用特別客制
      • 但要在 Resume 上要有亮點
      • 投的量和速度要夠多和快
    • Interview
      • LeetCode
        • 大多會是常見題目
        • 作用是讓面試官看到解題的方法和過程的溝通
      • 個人經歷
        • 要對自己做的東西很理解
          • (經典的 5W1H)
        • 不要被自己做過的事情問倒
      • Behavior question
      • System design
        • e.g., Tiny url, Twitter, High Concurrency Service
  2. Medium 技術寫作經驗加分的程度、一定要 promote 到讓社群或是讓流量很好看嗎？
    • 難被量化、但面試時需要包裝
      • e.g., Github open source contributing, medium 的 view stat
    • 學生時期
      • Final project / 專題的東西可以包裝一下、寫個 README
    • 在 Interview 上有被提到嗎？
      • 基本沒有、但作為自己 profilio 的補充
  3. 昨天收到 Amazon Cloud Support Intern 的 OA，想詢問學長此職位未來面試方面，有沒有準備上的建議？
    • Aws 在台灣只有 support,沒有開發， OA 記得是問答題，不太問技術方面，進去只做一點開發，如果要做 software engineer 不是很推薦
    • 看到職位就投，有沒有資格給 HR 決定
Last changed by 
 
sysprog
System Software Programming
420
Published on HackMD