前言 背景台大文組學、電資碩，沒有實習經驗 農曆新年後開始投履歷，投了近百封履歷，面試了 22 家公司，職缺皆為 Firmware or Software Engineer，有幸拿到 8 個 offer 在準備的過程中受惠於網路良多，不管是 Dcard or ptt，或是 blog，因此整理了相關資源，希望這篇文章對正在看這篇文章的你有所幫助 面試前的準備與相關資源整理 刷題策略leetcode 用 C & C++ 總共刷了 600 題，medium x 370、hard x 100，每題 2 ~ 3 遍，有用類似 Anki 的工具（Space Repetition）來定期複習之前做過的題目。 weekly contest 通常都只解出三題，第四題 Hard 要看運氣 前 300 題左右都是不會直接看解答，然後把解答背起來以建立各個主題的常見 pattern，以及熟悉 C++ STL、Container 的使用，後 300 題則會自己想出解答（除了 Hard）。

:::info 這裡彙整了網路上蒐集到的 C 語言考古題與其答案和詳解，並依據考題的主題分門別類。 歡迎有心人士繼續增加題庫，或是對於既有的題目提出新的見解與解答（歡迎留言，反白選取文字即可留言）。 新增題目請新增 下方區域，格式請參考現有的題目，並請附上題目的來源。我會定期檢查並將新增的題目歸類。 ::: storage class function

在了解 Markov Chain 的定義及其性質之後，這一節要介紹一種 continuous-time Markovian Chain: Birth-Death Processes。 在 Birth-Death Processes 中，state $n$ 只會跳到 state $n-1$ 或者 state $n+1$（state $0$ 只能跳到 state $1$），$n$ 代表 population in the system。 Transition rate 可表示為: $$\begin{cases} \lambda_n,\ n \to n+1 \newline \mu_n,\ n \to n-1\end{cases}$$ 所謂 Birth 就代表有一個 arrival($\lambda$ 對應的箭頭)，使整個系統的 size 增加 1，而從一個 birth 到下一個 birth 發生的間隔時間為 exponential random variable。

Markov Processes 不管是 discrete($X(t), t = 0,1,2, \cdots$) or continuous parameter time($X(t), t \gt 0$) 的 Stochastic Process，只要滿足以下式子，即可稱為一個 Markov Process： $$P(X(t_n) \le x_n | X(t_1) = x_1, ..., X(t_{n-1}) = x_{n-1}) = P(X(t_n) \le x_n | X(t_{n-1}) = x_{n-1})$$ :::info a Stochastic Process is best defined as a family of random variables, ${X(t), t \in T}$, defined over some index set or parameter space $T$. The set $T$ is sometimes also called the time range, and $X(t)$ denotes the state of the process at time t. :::

CHAPTER 1 - INTRODUCTION CHAPTER 2 - SIMPLE MARKOVIAN QUEUEING MODELS CHAPTER 3 - ADVANCED MARKOVIAN QUEUEING MODELS CHAPTER 4 - NETWORKS, SERIES, AND CYCLIC QUEUES NTUEE 2020 FALL MIDTERM NTUEE 2020 FALL PRACTICE MIDTERM NTUEE 2021 FALL MIDTERM NTUEE Queueing Theory 2022 FALL PRACTICE MIDTERM NTUEE Queueing Theory 2022 FALL HW1 NTUEE Queueing Theory 2022 FALL HW2

和 M/M/1 以及 M/M/c 一樣，由 Steady-state probability distribution 去推導出各個系統變量，像是系統平均人數（$L$）、顧客平均等待時間（$W_q$）等等，不同的地方在於 system capacity，現在系統總容量上限為 $K$，所以$p_n$ 在 $n\gt K$ 時會是 0。 首先我們要先跟據 Balanced Equation 去求出 Steady-state probability distribution。 $$p_n = \begin{cases} \frac{\lambda^n}{n!\mu^n} \cdot p_0,\ when\ 0 \le n \lt c \ \frac{\lambda^n}{c^{n-c}c!\mu^n} \cdot p_0,\ when\ c \le n \le K \ 0,\ when\ n \gt K\end{cases}$$ $p_0$ 一樣用機率總和等於 $1$ 去求解，和 $M/M/c$ 不同的是，此處 $\rho = \frac{\lambda}{c\mu}$ 不需要小於一，因為等比級數是 finite 的，沒有收不收斂的問題。

image source $M/M/1$ 是一個 arrival rate $= \lambda$，service rate $=\mu$，server 數量為 1，system capacity 為 $\infty$ 的 queue。 在 Birth-Death Processes 中我們學到： 分析各種 queue 的第一步就是搞清楚 state transition，畫出各個 state 之間的 arrival & departure(service) rate（如 Figure 2.1），然後運用下面會介紹的 Balanced Equations 求出 steady state probability($p_n$) ，有了 steady state probability($p_n$) 就可以進一步分析 queue 的各種 metrics，像是 average system size $L$，以及 average waiting time $W$ 等等。 所以說，我們要先跟據 Balanced Equation 去求出 Steady-state probability distribution，求解的過程在 Birth-Death Processes 有詳細說明。

名詞定義 idle period: 從系統離開busy state到下一次系統進入busy state為止 busy period: 從系統離開idle state到下一次系統進入idle state為止 busy cycle: 從系統進入busy state 到下一次系統再次進入 busy state 分析 我們關注的分別是上述三個定義的period 其長度的期望值，即：$E(T_{idle}), E(T_{bp}), E(T_{bc})$。

如圖，$M/M/c$ 因為 server 數量變成 $c$，因此 service rate 會隨著當前系統人數而變動，不過最大就是 $c\mu$（$c$ 個 server 都為 busy 的狀態下）。 和 M/M/1 一樣，由 Steady-state probability distribution 去推導出各個系統變量，像是系統平均人數（$L$）、顧客平均等待時間（$W_q$）等等。 首先我們要先跟據 Balanced Equation 去求出 Steady-state probability distribution。 $$p_n =\begin{cases} \frac{\lambda^n}{n!\mu^n} \cdot p_0,\ when\ 0 \le n \lt c \ \frac{\lambda^n}{c^{n-c}c!\mu^n} \cdot p_0,\ when\ n \ge c\end{cases}$$ $p_0$ 一樣用機率和等於 1 去求解，當 $\rho = \frac{\lambda}{c\mu} \lt 1$ 時等比級數會收斂，有解：

What is Queueing Theory used for? Queueing theory was developed to provide models to predict the behavior of systems that attempt to provide service for randomly arising demands Most real problems do not correspond exactly to a mathematical model, and increasing attention is being paid to complex computational analysis, approximate solutions, sensitivity analyses, and the like. The development of the practice of queueing theory must not be restricted by a lack of closed-form solutions, and problem solvers must be able to put the developed theory to good use. 排隊理論（Queueing Theory），是一套用來分析系統效能的數學工具，可以應用在生活中的很多地方，從電腦 CPU 到疫苗注射站都可以，只要系統具有 Input、Ouput、以及負責處理 Input/Output 的中央處理器，都可以被排隊理論來分析。 想像今天你要規劃在台北市的哪些據點設置疫苗注射站，以及每個注射站要配置多少醫護人員，這樣民眾才可以順利打到疫苗，這時後就可以用排隊理論來分析，就可以預估民眾的等待時間，以及注射站的壅塞狀況等等，最後再搭配預算、人力等限制條件，配合最佳化演算法來做出最佳決策。 Review of Poisson Process

Poisson Process 機率函數推導 :::info The number of occurrences in some time interval to be a Poisson random variable is equivalent to assuming the time between successive occurrences to be an exponentially distributed random variable (If an only if) ::: 首先定義一些機率與其性質： $$\begin{cases} Pr(there's\ an\ arrival\ between\ T\ and\ T + \Delta t) = \lambda * \Delta t + o(\Delta t) \ Pr(more\ than\ one\ arrival\ between\ T\ and\ T + \Delta t) = o(\Delta t) \ \frac{lim_{\Delta t \to 0}\ o(\Delta t)}{\Delta t} = 0 \end{cases}$$ 我們的目標是求出 $P_n(t)$，即是在 $t$ 單位時間內有 $n$ 個 arrival 的機率。

Basic Graph theorem 因為至少必須把從root到given vertex worst case有n個node 的input讀進來（skew BST) recursive DFS handle the first child first(in the adjacency list) non-recursive DFS handle the last child first(in the adjacency list) Time Complexity $lg^{}(2^n) = 1 + lg^{}(n)$

108 False Dijkstra不行用在有negative weight edge的圖，就算圖是DAG也不行，因為在Dijkstra中，不會對已經被extract min掉的vertex再次進行relax，這也就是Dijkstra的正確性需要edge都是正的的原因。 F FT https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

95 $trace(A^{T}A) = trace(AA^{T}) = \sum_{j=1} (A^{T}A){jj} = \sum{j=1} \sum_{i=1}(A){ij} * (A){ij} = \sum_{j=1} \sum_{i=1}(A){ij}^2 = \sum{i=1} \sigma_i^2$ ($A^{T}A$的奇異值平方和) 要找和奇異值的關係用SVD分解：$trace(A^{T}A) = trace(\sum^T \sum) = \sum_{i=1} \sigma_i^2$ 要找和特徵值的關係用Schur分解：$trace(A^{T}A) = trace(UT^*U^UTU^) = trace(T^*T) = \sum_{j=1} \sum_{i=1}(T_{ij})^2 = \sum_{i=1}(T_{ii})^2 + \sum_{i=1, j>i}(T_{ij})^2$ $= \sum_{i=1} \lambda_i^2 + \sum_{i=1, j>i}(T_{ij})^2 >= \sum_{i=1} \lambda_i^2$ 等號成立於A為正規矩陣的時候 https://ccjou.wordpress.com/2010/05/10/矩陣模/ https://ccjou.wordpress.com/2013/10/30/矩陣跡數與特徵值和奇異值的關係/

T/F 四維用人腦不好想像，先想二維：$T(n) = T(n/2) + O(n), T(n) = O(n)$ WTF WTF WTF

99 先化簡成 RREF，才可以看出行向量之間的線性組合關係，非pivot的行，從上往下看，依序是各個pivot行的組成係數 $\begin{bmatrix} 1&0&1&0&1\0&1&1&0&-2\0&0&0&1&1\0&0&0&0&0 \end{bmatrix}$ 上方矩陣是U的 rref，因此可看出第五行向量就是由 $1*a1 + (-2)a2 + 1a4$ 所組成 非方陣