Interview prepare

1.準備投影片有系統的自我介紹3分鐘
2.人格特質內容：

• 你寫過最大的程式專案是什麼？中間最難的部份是哪裡？你如何克服這個難題？
• 你有什麼合作經驗？中間遇到什麼困難，並如何解決？
• 在你過去工作經驗或求學過程中，你認為最大的成就/果是?為什麼?
• 在你過去工作經驗或求學過程中，你認為最大的困難/挑戰是?為什麼?
• 你的職涯規劃是什麼？

3.準備問公司的問題：

• 幾點上下班、假日需要輪班on call …
• 有沒有新進員工的職業培訓？
• 部門的管理方式如何、部門的風氣？

技術問題:

OS、計組:
1.Interrupt、DMA、Process & Thread、Multi-thread、Mutex & Semaphore、Spin lock、Sync相關各類問題、volatile、Pipeline、virtual memory、fork、priority inversion.

---

Process & Thread:

process為OS分配系統資源(memory)的單位，thread為OS分配CPU time的單位

Process:

• 在 disk 上叫 program， load進memory 開始執行後就變成 process
• 有自己的address space =>code section, data section(放已初始化global, static data), bss section(未初始化的global, static data 在bss區預留位置)、stack、heap
• context switch 成本高需要: OS需要換Pagetable、LDT、TSS (cpu register、pc)

thread:

• LWP(light weight process)
• 共享process的code section, data section 所以當有share data時候就要注意synchronization問題
• thread有自己的program counter, cpu register, stack
• 好處減少context switch overhead

linux是用一個task struct來描述一個process or thread

stackoverflow how kernel-separate-threads from-processes

x86怎麼幫助處理context switch

• GDT global descripter table
  • 存所有 process 的 LDT 跟 TSS (task state segment) 的位置
  • 存kernel data 跟 kernel text 的位置(用來描述kernel data segment位置及kernel code的位置)
• LDT local descripter table
  • 每個 process 都有 LDT
  • 存 text 跟 data segment 的位置

TSS(task state segment) structure，x86 一個特別的structure用來記錄現在task的一些register及資訊
General-purpose register fields
State of the EAX, ECX, EDX, EBX, ESP, EBP, ESI, and EDI registers prior to
the task switch.
Segment selector fields
Segment selectors stored in the ES, CS, SS, DS, FS, and GS registers prior to
the task switch.

---

Mutex & Semaphore、Spin lock、Sync相關各類問題:

lock 可以如何實作？spinlock、mutex、semaphore 的差異和實作？考慮 single-core single-thread、single-core multi-thread、multi-core multi-thread 不同情況呢？
atomic 是什麼？可以怎麼實作？

race condition問題:
2個thread同時進入到critical section操作share data

e.g.,原本預期，Thread 1 先做完 i++ 之後Thread再做 i++:

因為沒有保護好share data 結果:

• 1-CPU 2-thread:
  做了 context switch，取的值皆放在 memory，shared data 沒有同步好
  
• 2-CPU:
  多核也需要解決單核的問題
  

解決方法:

• 必須使用 lock 機制來保護share data，而 lock 本身需要是 atomic oeration

spinlock: busy waiting(non-sleep)

volitale int lock=0;
void spinlock(void){
    while(lock==1)
    {};
    lock=1;
}

• UP (unicore processor):
  • spin lock 完全不存在，因為如果只有一個CPU跑到spin_lock()時候，去檢查目前的lock被鎖住(代表你是去preempt別人，這其實不會發生，因為 spin_lock要先preempt_disable，不允許preemption)，然後執行spin，則就會一直spin耗掉CPU time，無法讓出CPU給別的thread用來解開lock
  • 在單核CPU情況下就只有把kernel preemption關掉(preempt_disable)

#define __LOCK(lock) \
  do { preempt_disable(); __acquire(lock); (void)(lock); } while (0)

#define _spin_lock(lock)			__LOCK(lock)

• SMP (symmetric-multi-processors)
  • 進入一個non-stop for loop，先把preempt_disable關掉
  • do_raw_trylock()，如果拿到就break跳出迴圈，
  • 如果沒有拿到lock就把preempt_enable繼續spin
  • 在沒有拿到lock時候，進入while loop，OS會將CPU放到low power state

    for(;;){
      preempt_disable()
      if(do_raw_trylock(lock))
          break;
      preempt_enable()
      
      while(!raw_can_lock(lock)&&(lock)->break_lock)
          arch_relax(&lock->raw_lock)
    }
    (lock)->break_lock=0;

spinlock 使用原則:

• lock的是data，而不是code
• lock 的資料太長就不建議使用 spin lock，不要讓 CPU 空轉太久
• 不要recursive 使用spin lock(會重複lock e.g., lock A 又lock A 會卡住，造成死結)
• 使用spin lock進入到出來critical section時間應小於2個context switch時間，如果大於就沒好處，代表其他CPU會空轉太久無法做其他事，就不應該使用spin lock
• 在preemptive kernel情況下，使用spin lock要先preempt_disable()
• 但是spin lock並沒有保證說不可以有interrupt，在進入critical seciton時候有可能會被interrupt，去執行ISR，執行完再回來執行下一道指令，但是要考慮ISR會不會操作critical section的share data，如果ISR會操作此share data，最好作法是將local interrupt關掉 local_irq_disable()，不可以關掉全部的interrupt
• 可以用在interrupt handler但是要關掉local interrupt

semaphore: 它是一個整數值與一對P、V函式的組合，當行程要進入critical section之前先呼叫P，若權狀值>0則讓行程進入critical section，權狀值-1，當行程離開critical section時候則呼叫V釋放權狀，權狀值+1，並且喚醒正在等待的行程，在linux則是用down()、up()組合

• 較複雜，少人用
• sleeping lock，也是用atomic operation實作出來的
• 沒有disable kernel preemption
• 把自己設為 idle去sleep，然後call scheduler讓出CPU可以去做其他事
• 適合拿到lock進入critical section會比較長的時間
• 如果小於兩個 context switch 的時間就使用 spin lock
• 只能用在process context，不可以用在interrupt context，如果在interrupt context睡覺，則其它interrupt打不進來，OS反應就會不好，e.g.,移動滑鼠，但是鼠標不動~QQ
• hold semaphore 可以去睡覺，因為沒有關閉preemption，其他人還是可以往下走
• hold semaphore 可以 hold spin lock，但是hold spinlock之後不可以再hold semaphore，這樣等於拿到spinlock後可以去睡覺

Linux 的權狀都是mutex

mutex: 與semaphore最大不同是，ownership的概念，每次只允許一個行程進入critical section，並且須由該行程離開critical section 釋放lock，就是握有lock的人要自己解開lock，無法靠其他人來解開，這樣就不會像semaphore有第二個人不小心釋放lock而忘了鎖

• count for 1的semaphomre
• 大部分的 linux 實做都是使用 mutex
  

Mutex產生的問題: priority inversion

priority inversion:

範例:

當具備中度優先權的 task (簡稱 M) 搶先 (preempt) 一個原本享有 resource 的低優先權的 task (簡稱 L)，而該 resouce 又是一個高優先權的 task (簡稱 H) 所等待。問題就在於 H 與 L 共享 resource，當 L 被 preempt 時，就該放下 resource，這是合理的行為，而原本 H 就在等待 resource 的釋放，因為隨後就會使用到。但問題是，這段 latency 中，M 把這個規則打破，先行 preempt 了 L，也就把 L 的 resource 給「搶走」，這下有趣的事情就發生了。原本 L 與 H 具備相對高低的優先權差異，但因為 M 的介入，造成延遲，如果 M 一類的 task 相當多，或者 M 本身是 non-RT task，這樣的過程可能就讓 H 發生超出 deadline 的情況，更可能逆轉 L 與 H 的執行順序。更甚者，當 H 發生崩潰的情況，因為 watchdog 的效應，很可能 H 因此甚失其原本的高優先權

可以分成以下2種情況:

• Bounded priority inversion
  高優先權的process/thread等待進入critical section，該critical section目前由低優先權的process/thread佔用中。因此只要低優先權的process/thread離開該critical section後高優先權的process/thread便可繼續執行
• Unbounded priority inversion
  高優先權的process/thread等待進入critical section，該critical section目前由低優先權的process/thread佔用中
  不幸的是，當低優先權process/thread還在critical section執行的時候，被切換到中優先權的process/thread由於高優先權的process/thread被block，而低優先權的process/thread一定會被中優先權的process/thread搶走執行權。最壞的狀況就是之後就只剩中優先權的process/thread被執行
  • 看來可以解Unbounded priority inversion，bounded priority inversion應該還是本質無法解掉?

解法:
1.Priority inheritance
當高優先權的process/thread要進入critical section發現該section已被低優先權的process/thread佔用時，系統暫時將該低優先權的process/thread調整到高優先權直到該低優先權的process/thread離開critical section

2.Priority ceiling
當低優先權的process/thread進入critical section就將優先權調至最高

主題分享: 淺談 Semaphore 與 Mutex youtube
priority-inversion
Jserv priority inversion
priority-inversion

Deadlock:

1. deadlock 與 shared data 有關，重點在於需要的 resource 拿一半，另一半遲遲等不到
2. 例如下面2個threads，Thread1、Thread2都需要A、B兩個resource，2個thread都有做好race condition但還是會deadlock
   

• deadlock預防:
  要資源需要照一定順序
  Do not double lock，不要重複 lock 某資源
  解 lock 順序: A, B, C -> C, B, A

• deadlock處理:
  1.不處理
  2.用銀行家演算法

livelock:

Concurrency in The Linux Kernel
kernel-hacking locking

---

Buddy system、Slab allocator是在幹麻?怎麼做?

Node, Zone and Pages
在NUMA架構下，每個處理器會管理一個memory node，每個node上會有三個區域分成ZONE_DMA、ZONE_NORMAL、ZONE_HIGH，每個區域都會切成4KB大小的page frame來給使用者

buddy system : Linux kernel管理實體記憶體的機制，為了避免外部碎裂問題，

• 提供O(1)的時間來分配連續的記憶體
• 但會有internal fragmentation問題
• 適合大的連續記憶體

slab allocator:

• 解決 internal fragmentation，kernel 裡面的資料結構常常小於 4k(one page)，所以需要額外的資料結構來記載小的記憶體空間配置，並將他們放在一起。

• kmalloc(): 要求 physical 與 logical 都連續的記憶體
• vmalloc(): 要求 logical 連續的記憶體，但physical不一定連續
  Vivian

user mode與kernel mode的差別 ? trap 是什麼？簡單解釋 system call 流程
user-and-kernel-mode

在基於x86保護模式的基礎下, 使用者的程式相對於核心的程式而言是比較不可靠的,也就是說屬於Ring 3的程式並不能存取屬於Ring0的記憶體空間,並且屬於Ring3的程式也無法直接去執行屬於Ring0 的程式碼範圍.

x86結構中有四種級別Ring 0 ~ Ring 3
Ring 0最高，有著OS Kernal
Ring 3最低，也就是user mode，通常Application都在此層執行
Ring 1及Ring 2供驅動程式使用，很少用到

---

virtual memory:

虛擬記憶體是電腦系統記憶體管理的一種技術。它讓每個program擁有連續的可用的記憶體（一個連續完整的位址空間），是可以讓多個 processes 共享實體記憶體，採用demanding page技術，當process執行時只需要載入目前所需要的page就好，

• 每個linux用task_struct來描述一個process，透過task_struct->mm->mmap可以找到vm_area_struct，linux用利用VMA(virtual memory area)來描述每個segment特性，大小

how kernel manages your memory

---

I/O運作方式：

Interrupt:
流程:
1.OS收到中斷後會先存取目前process state
2.去查詢interrupt vector(中斷向量表)，看是發生哪種中斷，並找到對應的ISR位址
3.跳到ISR執行(會將device controller buffer資料搬到memory)
4.執行完後，將控制權交給kernel，通知在等I/O的process已經完成
5.之後再恢復中斷之前process的執行or由scheduler挑選下一個工作

__interrupt double isr(double r) //不能有參數
{
 double area = PI*r*r ;
 printf("%f\n",area) ; //改成printk
 return area ; // 不能有return 
}
ISR不能有返回值(不知道給誰)
ISR不能傳遞參數(不知道誰呼叫)
pintf改printk
ISR應短而高效

詳細版:

• CPU 可以由兩種方式中斷執行，Exception and Interrupt
• Exception
  • 通常和 CPU 同步 (Synchronous Exception)
    • Exception 發生的原因通常來自於執行某一道程式
    • Trap、Set break point、decode error、memory access fault
• Interrupt
  • 通常來自於外界
  • Asynchronous Exception
• CPU 把目前指令做完之後，把一些狀態存到 memory 去
• 根據 CPU 去問 PIC 的 number 來判斷到底是哪一個 Line 進來
• 根據 Line 的數字和 offset 算出正確的 Vector
• 這個 Vector 擺的就是指向某個 interrupt handler 的第一行程式的指標
  • Vector table 會是一堆 jump 到不同的 address (Interrupt Vector)
  • 這個 vector table 以 x86 來看前面一部份是給 exception 用的，之後就是給 interrupt 用的，這個 vector table 放在 memory 裡面

Review (Traps):

1.當執行到fork指令時，編譯器會把此指令轉譯成2道machine code:MOV EAX 0x02,INT 0x80，當CPU指到INT 0x80時候產生exception
2.CPU跳去INT 80 system call的handler
3.再根據EAX 0x02查syscall table 對應的handler, 執行0x02對應的service routine (fork)

linux syscall detail:

• IDTR : CPU 的一個 register 其功能是指向 interrupt descriptor table (exception table) 由硬體做，計算 syscall handler 的位置。

在linux 會初始化一個system call的進入點

set_system_gate (0x80, &system_call)

Top Half and Bottom Half

Top half:

• interrupt service routine 把 interrupt 關掉，然後把封包 DMA 搬到 main memory 裡面
• 至於後續封包是屬於誰的就給 daemon program (kernel thread) 來處理
• 會先處理跟 Hardware 有關或是 time critical 的會先做，不是的會留到 Bottom Half 再做

Bottom half:

Softirq:

• 傾向於效能，一些很重要的需要緊急處理的
• 靜態註冊 32 bottom half，編譯進入kernel
• 都是在interrupt context下，兩個相同的 softirq 可以在兩個 CPU 上面同時執行 bottom half，但是兩個 Top half 不能同時執行
• interrupt enable 且不能 sleep

Tasklet

• 基於易用性，一般都是寫這個
• 基於Softirq，Tasklet 是 Softirq 的其中一個程式，這個程式會去檢查另外一個 Table，任何人都可以來註冊 Tasklet
• 所有的 Tasklet share 同一個 Softirq
• 兩個相同的 tasklet 是不能在不同的 CPU 上同時執行，不同的 tasklet 才可以
• 好處使可以動態註冊

Workqueue:

• workqueue 運行在 process context (kernel thread在執行)
• 就是上述提到的最簡單的做法 (用daemon program來做)

---

DMA:
電腦的ISA　DMA controller它會負責I/O device與memory之間的資料傳輸，不需要透過CPU介入
，這樣可以提高CPU的利用率，要初始化資料傳輸時，driver一起設定DMA通道的位址和計數暫存器，以及資料傳輸的方向，讀取或寫入。然後指示DMA硬體開始這個傳輸動作。當傳輸結束的時候，裝置就會以中斷的方式通知中央處理器

how-does-a-dma-controller-work

---

write back、write through差別?

快取寫入的機制 (write hit):
為了要保持主記憶體與快取資料一致性問題，通常有2個機制:

write through:

• 當CPU將資料寫入快取時候也同時寫回主記憶體，優點:操作簡單，缺點就是耗時
• 可用write buffer改善，就是CPU將資料寫入快取時候也同時寫入write buffer，等到write buffer滿了它會將資料寫回主記憶體

write back:

• 則是當寫入發生時，資料只寫入快取，當區塊要被置換出去時候，則將有被修改過的區塊寫回主記憶體
• 優點:寫入的速度快 缺點:一旦系統斷電則資料將會遺失

寫入失誤 (write miss):
當發生write miss時候處理方式有2種處理方式:
write allocate: 在快取中配置一個區塊，並將資料從主記憶體搬到快取區塊中，再寫入配置區塊中
NO write allocate (write around): 更新在記憶體中該區塊需被寫入部分，而不在快取中配置此區塊

通常write through會用no write allocate機制，write back會用write allocate機制

Pipeline hazard 是什麼？cache 是什麼？什麼時機會用到 cache？Pipeline IPC是多少?怎麼算?

Pipeline IPC為何?

解答:
1.在沒有pipeline情形下，每一道指令必須執行完IF、ID、EX、MEM、WB這幾個階段之後才執行下一個指令
2.如果有pipeline則可將指令分為5個階段IF、ID、EX、MEM、WB來執行，藉由指令重疊，每個階段會執行不同指令，因此可以增加整體的throughput

IPC計算:
假設pipeline為5個stage，有N道指令要執行，IPC為何?
ans:
1.當1個指令會在第5個cycle執行完畢，之後每一個cycle會執行完一道指令，所以後面

$N-1$個指令會花費

$N-1$個cycyle，因此總過會花費

$5+N-1=N-4$個cycles，IPC(instruction per cycyle)為

${\displaystyle \frac{N}{N-4}}$，當N趨近於很大時候，IPC=1
2.如果沒有pipeline情形，則N個指令必須要花費5N個cycles時間，IPC(instruction per cycyle)為

${\displaystyle \frac{N}{5N}}$ =

${\displaystyle \frac{1}{5}}$，IPC為

${\displaystyle \frac{1}{5}}$

結論: 在有pipeline情況下相當於每個cycyle就會執行一道指令，而在沒有pipeline情況下則每個cycyle只會執行

${\displaystyle \frac{1}{5}}$道指令

Pipeline hazard

pipeline stage: IF ID EX ME WB
pipeline hazard: 主要是因為pipeline無法順利在下一個cycle執行下一個指令

• structural hazard:只有單一記憶體，而不是分成instruction memory與data memory，就會造成同一週期，同時有2個指令對記憶體做存取，例如在第4個cycle時候load要將data存入memory，而這時要從memory擷取另一個指令出來
  • A structural hazard occurs when a part of the processor's hardware is needed by two or more instructions at the same time

• data hazard:主要是例如:第一個指令對

  $r1\mathrm{做}\mathrm{寫}\mathrm{入}\mathrm{動}\mathrm{作}\mathrm{外}，\mathrm{下}\mathrm{個}\mathrm{指}\mathrm{令}\mathrm{則}\mathrm{是}\mathrm{對}$r1做讀取的動作，但是在cycle 5的時候才會將
  $r1\mathrm{值}\mathrm{寫}\mathrm{入}，\mathrm{造}\mathrm{成}sub\mathrm{指}\mathrm{令}\mathrm{與}and\mathrm{指}\mathrm{令}\mathrm{讀}\mathrm{到}$r1的值並非最新的
  

• control hazard:就是如果當beq需要在第3個階段才能知道分支會不會發生，add及lw指令已經進入pipeline，這時候就發生了control hazard
  

解決hazard的方法:

• structural hazard:增加記憶體，將instruction memory與data memory分開
• data hazard:
  • software(compiler):Inerst NOP、Instruction reordering
  • hardware : Forwarding、stall+forwarding(lw,sw)
• control hazard:
  • software(compiler):Inerst NOP、delay branch (將總是會執行指令的放到delay slot)
  • hardware:Predict not taken (branch predict table,BHT)、Flush wrong instruction、減少分支延遲移到ID stage

進階管線:

提高指令平行度(instruction level parallelism,ILP)方法
1.增加管線深度(superpipeline)
2.增加電腦內部單元，在每個pipeline stage可以執行多個指令-多重分發(multiple issue)，可以使CPI(cycle per instruction)小於1，

靜態多重分發:

• 由編譯器將包裝指令安插issue slot，並且處理data、control hazard問題
  例如:假設一次可以發2個指令，可以將load store與ALU branch指令分開進入pipeline，並且用loop unrolling讓更多指令可以加入編譯器對指令reordering，減少pipeline stall與減少分支判斷
  ，但也不能展開太多，因為這樣會占用很多的memory空間

• VLIW:IA64

loop unrolling可以減少分支判斷

for ( i = 0; i < 100; ++i )
    sum += a[ i ];

但是這樣會做100次的 i < 100 的判斷，增加branch降低效率，
所以loop unrolling的技巧就是在迴圈內部多做幾次，減少判斷的次數。

for ( i = 0; i < 100; i += 5 ) {
    sum += a[ i ];
    sum += a[ i + 1 ];
    sum += a[ i + 2 ];
    sum += a[ i + 3 ];
    sum += a[ i + 4 ];
}

動態多重分發:

動態多重分發處理器又稱為 超純量(superscalar) 處理器，使用dynamic pipeline scheduling的技術，選擇下一群要執行的指令，並將指令重新排序以避免管線暫停，主要分三單元:
1.指令擷取和分發單元(Instruction fetch and decode unit)
2.多個功能執行單元(multiple functional units)
3.交付單元(commit unit)

當Instruction fetch and decode unit擷取指令後解碼，然後把每個指令送到functional units並且，每個functional units會有個緩衝器reservation station它會儲存運算元與運算子，一旦運算元與functional units準備好後就會將結果計算出來，並且送到commit unit，commit unit會先將結果存起來，等到確定安全時候，再把結果寫回reggister or memory，commit unit內的緩衝器稱為reorder buffer提供運算元(1,2,3..)

• superscalar:現代處理器設計

---

3.有沒有寫過shared memory，大概怎麼寫

Linux IPC 主要可以用在Shared Memory, Message Queue, PIPE, FIFO, Unix Socket

New POSIX 現在都用這個：
shm_open (+ ftruncate) + mmap with MAP_SHARED

shmget-vs-mmap
4.gprof、perf的差別.
gprof: 是以在程式碼前後插入_mcount函式來計算function被呼叫次數
perf: 定期 interrupt CPU，看 CPU 跑在哪裡，看CPU有多少時間花在甚麼地方，並且統計分析

6.API、ABI差別
API:為source code層級的介面

ABI:一個ABI定義了機器碼如何存取資料結構與運算程式，
例如MSVC的目的檔是否連結GCC的目的檔成為一個可執行檔呢?
須滿足以下條件:
變數的記憶體位置擺放、函式呼叫的方式(參數加入堆疊的順序)及返回值如何保持

7.為什麼宣告並初始一個超大陣列會crash，而宣告成static就不會，他們的儲存方式有什麼差別.

ANS:
因為再int main中宣告會造成stack overflow(目前限制是8MB)，
而宣告成static or global則是再data segment.

8.function在進行呼叫的時候OS會作什麼事情，組合語言大概怎麼寫.
會先保存呼叫此main function的old rbp並將目前sp的位址設為rbp，讓它指向此function的activation的開頭，之後開闢空間存放funciton的local variable，設定好register值後在呼叫sub function comp

int comp(int a, int b) {
    return a == b;
}
int main() {
    int a = 1;
    int b = 2;
    comp(a, b); 
}

0x0040050e    55                       push rbp //把main之前的rbp push到stack
|           0x0040050f    4889e5       mov rbp, rsp //將目前stack sp指的位置設為rbp
|           0x00400512    4883ec10     sub rsp, 0x10 //開闢10 bytes空間
|           0x00400516    c745f801000. mov dword [rbp-0x8], 0x1 
|           0x0040051d    c745fc02000. mov dword [rbp-0x4], 0x2
|           0x00400524    8b55fc       mov edx, [rbp-0x4]
|           0x00400527    8b45f8       mov eax, [rbp-0x8]
|           0x0040052a    89d6         mov esi, edx
|           0x0040052c    89c7         mov edi, eax
|           0x0040052e    e8c3ffffff   call sym.comp//呼叫comp函式
|              sym.comp(unk)
|           0x00400533    b800000000   mov eax, 0x0
|           0x00400538    c9           leave
\           0x00400539    c3           ret

9.Edge trigger和 level trigger

10.LMA and VMA

Output section如果被載入記憶體，會存放兩種記憶體位址
VMA: Virtual Memory Address
Runtime 的記憶體位址
LMA: Load Memory Address
load time的記憶體位址
一般來說，VMA = LMA。不同情況有東西要燒到ROM時參考LMA。從ROM載入到記憶體執行的時候參考VMA
可以使用objdump -h看VMA/LMA資訊

linker-script

LMA (Load Memory Address): 表示section被保存在記憶體上的位址
VMA (Virtual Memory Address): 表示程式碼執行時期的位址
STM32 程式開發：以 GNU Toolchain 為例

網路:

1.TCP/UDP差別在哪，用途？Socket程式大概怎麼寫，http？(三向交握那些)

TCP三向交握:

在上面的封包連接模式當中，在建立連線之前都必須要通過三個確認的動作， 所以這種連線方式也就被稱為三向交握(Three-way handshake)。 那麼我們將整個流程依據上面的 A, B, C, D 四個階段來說明一下：
A:封包發起
當用戶端想要對伺服器端連線時，就必須要送出一個要求連線的封包，此時用戶端必須隨機取用一個大於 1024 以上的埠口來做為程式溝通的介面。然後在 TCP 的表頭當中，必須要帶有SYN(希望雙方建立同步處理) 的主動連線(SYN=1)，並且記下發送出連線封包給伺服器端的序號 (Sequence number = 10001)

B:封包接收與確認封包傳送
當伺服器接到這個封包，並且確定要接收這個封包後，就會開始製作一個同時帶有 SYN=1, ACK=1 的封包， 其中那個 acknowledge 的號碼是要給 client 端確認用的，所以該數字會比(A 步驟)裡面的 Sequence 號碼多一號 (ack = 10001+1 = 10002)， 那我們伺服器也必須要確認用戶端確實可以接收我們的封包才行，所以也會發送出一個 Sequence (seq=20001) 給用戶端，並且開始等待用戶端給我們伺服器端的回應喔！

C:回送確認封包
當用戶端收到來自伺服器端的 ACK 數字後 (10002) 就能夠確認之前那個要求封包被正確的收受了， 接下來如果用戶端也同意與伺服器端建立連線時，就會再次的發送一個確認封包 (ACK=1) 給伺服器，亦即是 acknowledge = 20001+1 = 20002 囉。

D:取得最後確認
若一切都順利，在伺服器端收到帶有 ACK=1 且 ack=20002 序號的封包後，就能夠建立起這次的連線了

Ref:
鳥哥網路

TCP/IP:

Application Layer: 定義應用程式如何進入此層的溝通介面，以將資料接收或傳送給應用程式
Presentation Layer: 上面所製作出來的資料格式不一定符合網路傳輸的標準編碼格式的！ 所以，在這個層級當中，主要的動作就是：將來自本地端應用程式的資料格式轉換(或者是重新編碼)成為網路的標準格式
Session Layer: 定義了兩個位址之間的連線通道之連接與掛斷，確定網路服務建立連線的確認
Transport Layer: 定義了發送端與接收端的連線技術(如 TCP, UDP 技術)， 同時包括該技術的封包格式，資料封包的傳送、流程的控制、傳輸過程的偵測檢查與復原重新傳送等等， 以確保各個資料封包可以正確無誤的到達目的端。
Network Layer: IP (Internet Protocol) 就是在這一層定義的。 同時也定義出電腦之間的連線建立、終止與維持等，資料封包的傳輸路徑選擇等等，因此這個層級當中最重要的除了 IP 之外，就是封包能否到達目的地的路由 (route) 概念了
Data-Link Layer: 因為底下是實體的定義，而上層則是軟體封裝的定義。因此第二層又分兩個子層在進行資料的轉換動作。 在偏硬體媒體部分，主要負責的是 MAC 稱這個資料包裹為 MAC 訊框 (frame)， MAC 是網路媒體所能處理的主要資料包裹，這也是最終被實體層編碼成位元串的資料。
至於偏向軟體的部分則是由邏輯連結層 (logical link control, LLC) 所控制，主要在多工處理來自上層的封包資料 (packet) 並轉成 MAC 的格式， 負責的工作包括訊息交換、流量控制、失誤問題的處理等

Physical Layer: 實體層必須定義所使用的媒體設備之電壓與訊號等， 同時還必須瞭解資料訊框轉成位元串的編碼方式，最後連接實體媒體並傳送/接收位元串

---

C/C++:
1.C++: Overloading、Virtual Function、Funtion Pointer、
各種不同scope的Static用法、Stack/heap/.bss架構. C++ static的用法以及作用

2.overriding vs overloading、virtual 和 static

3.virtual跟abstract?

4.物件導向是什麼?

演算法:
1.特別需要熟悉複習的有 Sorting、Linked list各種implementation (e.g. reverse)、stack&heap的實現.
2.是比較各個sorting複雜度和優缺點以及是如何實作，如果遇到連續分次輸入大量的數字，每次輸入一個數字過後都會進行sorting的話，會使用哪種方式？
3.一題股市波動圖的問題，寫出解法的pseudo code，主要想看的也是想法的邏輯性.

Reference:
作業系統設計與實作 (Spring 2018)

MTK 台北手機系統軟體(2021/4)：

1. 畫出cpu架構及memory 說明指令及data如何從memory到cache
2. 如何寫一個benchmark tool來量測cpu效能
3. 怎麼知道你測出來的結果是cpu的效能極限
4. 如何測試bandwidth, latency
5. 如果cpu clock調高100倍，效能會增加100倍嗎？
6. 解說一下task有哪幾個狀態(預期要回答 TASK_RUNNING，TASK_INTERRUPTBLE， TASK_UN_INTERRUPTBLE…)
7. 解說一下spin_lock, mutex, semaphore 並說明什麼場景會用到?

程式題:

RTK

bluetooth

void move_ptr(uint8_t *ptr){
    ptr +=1;
}

int main(){
    uint16_t arr[5]={0x1,0x2,0x3,0x4,0x5};
    uint8_t *p = (uint8_t*)arr;                                                                                                                                                        

    printf("arr:%x arr+2:%x arr[5]:%x\n", *arr, *(arr+2), arr[5]);

    move_ptr(p);// pointer p 沒有改變

    printf("p+1: %d \n", *(p+1));
    printf("after move_ptr: %d \n", *p);

    move_ptr2(&p);
    printf("after move_ptr2: %d \n", *p)
    return 0;
}

int recursive_factorial()

output

$ ./rtk 
arr:1 arr+2:3 arr[5]:cb00
p+1: 0 
after move_ptr: 1 
after move_ptr2: 0 

p initially points to arr, which is uint16_t, meaning

arr[0] = 0x0001 (stored as bytes: 0x01 0x00 in little-endian)

p is a uint8_t *, so it points to the first byte of arr[0].
After move_ptr(&p), p moves to the second byte of arr[0], which is 0x00

In little endian memory layout, arr[0] = 0x0001 is stored as two separate bytes

Address      Value (in hex)
---------    -------------
  p      ->  0x01  (First byte of arr[0])
  p + 1  ->  0x00  (Second byte of arr[0])
  p + 2  ->  0x02  (First byte of arr[1])
  p + 3  ->  0x00  (Second byte of arr[1])

MTK:
2021/4/7更新:
問 union 初始話方式及

  int main(){

      union w{
          int a;
          char c[2];
      }; // this is fine declare in function

      union w u1={512};
>>    union w u2={0,2};// wrong way to initialize
      union w u3={.c={0x1,0x2}};// correct way to initialize other than first member in union
      
      printf("u1:%d, u3.a:0x%x, u3.a:%d ,u3.c[0]:%d, u3.c[1]:%d \n", u1.a , u3.a, u3.a , u3.c[0], u3.c[1]);

      return 0;
  }
-------------------
$ ./uion 
u1:512, u3.a:0x201, u3.a:513 ,u3.c[0]:1, u3.c[1]:2

考記憶體擺放的位址方式，little endian or big endian答案會不同

      char data[8] = {1, 2, 3, 4, 5,  6, 7, 8}; 
    short *a = (short *)&data[0];
    int b = *a; 

    printf("%d\n", b);//little endian -> 513 => 0x201(256*2+1)

    int d = 320;//0x140
    char *ptr;
    ptr = (char *)&d;
    printf("ptr:%d\n", *ptr);//little endian -> 64
    printf("ptr:0x%x\n", *ptr);//little endian -> 0x40

2018/10/31更新:

int var;
int foo(int n){
     n=2*n;
     return n*n;
}
int main(){    
    var++ = foo(++var);
    printf("%d ",var);
    return 0;
}

程式題:
1.不用sizeof計算出struct的大小

struct foo{
    int a;
    float b;
    char c;
};

int main(){

        struct foo arr[2] = {0};
        struct foo *p=arr;
                             /* 要casting 成 char * */
        printf("size:%d \n", (char*)(p+1)-(char *)p);
        printf("sizeof: %d \n",sizeof(struct foo));
        return 0;
}

Ref:
size-of-structure-in-c
c-sizeof-structure

2.每次吃進input並且計算出median

Input
2
3
3
3
Output:
2
2.5
3
3
------------
int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int main(){

    int arr[10000];
    int n=0, val, idx;

    int sum=0;
    while(scanf("%d", &val) != EOF){
        arr[n]=val;
        ++n;

        qsort(arr, n, sizeof(int), cmp);//sort n element

        if(n%2==0){
            idx = n/2;
            printf("%f\n", (float)(arr[idx-1] + arr[idx])/2);
        }else{
            idx = (n+1)/2;
            printf("%d\n", arr[idx - 1]);
        }
    }

    return 0;

發哥最近考題應該都偏向Leetcode，所以2018之前的就當參考

---

選擇題+填充題(Before 2018/1/30)：

#define INC(x) x*=2; x+=1
    for(i=0,j=1;i<5;i++)
        INC(j);
求j =?
答案是33 
Macro展開如下:

 for(i=0,j=1;i<5;i++)
        x*=2; x+=1;
注意forloop只會執行 x*=2會執行5次, x= 2,4,8,16,32
最後再執行x+=1;
j=33

上機考題:

• 用bit operation做swap.

*x=a, *y=b
void xorSwap(int *x, int *y) {
    *x = *x ^ *y; //a^b
    *y = *x ^ *y; //a^(a^b)=
    *x = *x ^ *y;
}
----
用xor並沒有比較快

#define  swap(X, Y)  (X^=Y, Y^=X, X^=Y)
定理：
  反元素 A^A = 0 
  交換性 A^B = B^A
  結合性 (A^B)^C = A^(B^C) 
  單位元 A^0 = A
  
推導：
   A = A ^ B
   B = A ^ B = (A^B) ^ B = A ^ (B^B) = A^0 = A
   A = A ^ B = (A^B) ^ A = (B^A) ^ A = B

• Maximum Subarray.

[-2 1 -3 4 -1 3]
那你就要output連續最大值是 6
subarray為[4 -1 3]

#include <iostream>
#include <vector>
using namespace std;

void max_subarr(vector<int> &nums){
	 int n=nums.size(), sum=0, max_sum=INT_MIN;
	 int tmp_start=0, start=0, end=0;
	 
	 for(int i=0;i<n;i++){
	 	sum += nums[i];
	 	if(sum<=0){ // 記得要<= 0 
	 	   sum=0;
	 	   tmp_start=i+1;
		 }
	 	
	 	if(sum > max_sum){
	 	  max_sum=sum;
	 	  start=tmp_start; //代表之前選的tmp_start不錯 
	 	  end=i; //更新end  
		}	 	
	 }
	 cout<<max_sum<<endl;
	 for(int i=start;i<=end;++i){
	 	cout<<nums[i]<<" ";
	 }	
}


int main(){
	int n=0, val=0;
	vector<int> nums;
	
	while(cin>>n){// 先吃array大小 
		for(int i=0;i<n;++i){
			cin>>val;
			nums.push_back(val);			
		}
		max_subarr(nums);
		nums.clear(); //記得要清除vector的值 
	}	
	return 0;
}

• 給一個 n * m 的 matrix，輸出成 m * n 的matrix. (考用pointer動態宣告2維陣列)

void transpose(int m,int n){	
	int i,j;
		
	int** arr=(int**)malloc(sizeof(int*)*n);//3x2	
	for(i=0;i<n;++i){
		arr[i]=(int*)malloc(sizeof(int)*m);
	}	
	for( i=0;i<m;++i){
		for( j=0;j<n;++j){
			scanf("%d ", &arr[j][i]);//反向讀入arr的值	
		}				
	}		
	for( i=0;i<n;++i){
		for( j=0;j<m;++j){
			printf("%d ", arr[i][j]);//print n x m	
		}
		printf("\n");			
	}
	for(i=0;i<n;++i){//記得要free避免memory leak
		free(arr[i]);
	}
	free(arr);
	
}
int main(){
	int m,n;	
	while(scanf("%d %d",&m, &n)!=EOF){ //不斷地吃測資
		transpose(m,n);
	}	
	return 0;
}

• 給你一個字串，你要判斷這個字串是不是接下來字串們的prefix

測資:
"hello"

"helly"
"hrlly"
"hellollfdh"
考輸出第3組字串

using namespace std;
bool prefix(string  src, string  s1 ){
	if(src.size()<s1.size()){
		for(int i=0;i<src.size();++i){
			if(src[i]!=s1[i])
				return false; 
		}
		return true;
	}else
		return false;		
}
int main(){	
	string s,s1,s3;	
	cin>>s;	
	while(cin>>s1){
		cout<<prefix(s ,s1)<<endl;//暫時先這樣寫~QQ
	}	
	return 0;
}

• 把出現指定prefix的字串刪掉

#include <iostream>

using namespace std;

int main(){
	int n;
	string s,s1;	
	cin>>s;	
	while(cin>>s1){		
		cout<<s1.erase(0,s.size())<<endl;
	}	
	return 0;
}

• 給定一篇 paragraph，將它轉成二進位輸出。

void str_to_binary(string s){	
	int n=s.size();
	string bin;
	for(int i=0;i<n;++i){
		int val= (int)s[i];			
		while(val>0){
			val&1 ? bin.push_back('1') : bin.push_back('0');
			val>>=1;
		}
		reverse(bin.begin(),bin.end());
	}
	cout<< bin <<endl;	
}
int main(){	
    string s1;	
	cin>>s1;
	str_to_binary(s1);	
	//用bitset也可以 
	int x=5;
	string s="hello";	
	cout<<bitset<4>(x)<<endl; 
	cout<<bitset<8>(s[0])<<endl; 	
	return 0;
}

• even odd sort給你一個n，接下來有n個整數，對他們排序使得(1) 偶數在奇數前面 (2) 偶數遞減排序、奇數遞增排序

• 給定一個正整數n，求出第n個質數

#include <iostream>
#include <algorithm>
using namespace std;

bool isprime(int n){	
	for(int i=2;i<=sqrt(n);++i){
		if(n%i==0)
		  return false;
	}
	return true;
} 
int n_prime(int n){
	int num=0;
	for(int i=2;i<INT_MAX;++i){		
	  if(isprime(i)){
	     ++num;
		if(num==n){
		  return i;
		 }				
	   }	
      }	
}

int main(){
	
	int a;	
	while(cin>>a){
		cout<<"n prime: "<<n_prime(a)<<endl;
	}
	
	return 0;
} 

• 找某個數字的所有公因數
  從 1, 2, 3 … n-2, n-1, n 一個一個嘗試能不能整除n，可以整除就是因數

#include <iostream>

using namespace std;

void find_factor(int n){	
	for(int i=1;i<=n;++i){
		if(n%i==0)
			cout<<i<<" ";
	}	
}
int main(){
	int n=0;
	while(cin>>n){
		find_factor(n);
	}	
	return 0;
}

• 給兩個超大A、B兩個數，求sum

void add(int a[100],int b[100],int c[100]){
	int i=0,carry=0;	
	for(i=0;i<100;++i){
		c[i]=a[i]+b[i]+carry;		
		carry=c[i]/10;//先算carry 
		c[i] %=10;//再算		
	}
}
int main(){
    char s[100];
    int a[100],b[100],c[100];
    
    scanf("%s",&s);
	//puts(s);
	add(a,b,c);
}

• 給任意數n，印出寬度為n的diamond

#include <stdio.h> 
int main(){
    int num, i, k, space; 
    printf("Enter number of rows\n");
    scanf("%d", &num);    
    space = num - 1;
    
    //先印出上方菱形 
    for(int i=0;i<num;++i){    	
    	//印出空白 
		for(int j=0; j<space ;++j)
    		printf(" ");    	
    	
		//每次印出 i 個 * 
		for(int j=0;j<=i;j++)
			printf("* ");//這邊*旁邊的要空一格 
		
		printf("\n");
		space--;    	
	}
	space=0;
	for(int i=num;i>0;i--){
		//印出空白 
		for(int j=0; j<space ;++j)
    		 printf(" "); 
    		
    	      //每次印出 i 個 *
		for(int j=0;j<i;j++)
			printf("* ");//這邊*旁邊的要空一格 	
		
		printf("\n");
		space++; 
	}

• 寫出一個function判斷輸入的數是2的次方

    bool isPowerofTwo(int n)
     return (n > 0) && ((n & (n - 1)) == 0);

白板題:

• 任意寫個sort array
• 一題股市波動圖的問題，寫出解法的pseudo code，主要想看的也是想法的邏輯性.
• 是比較各個sorting複雜度和優缺點以及是如何實作，如果遇到連續分次輸入大量的數字，每次輸入一個數字過後都會進行sorting的話，會使用哪種方式？

Synology:

• 給你兩個set A,B. 想輸出A - B要怎麼做？複雜度呢? -> 我講了平衡樹，或是使用hash來做
• 經典算法LCS
• 做一個調色盤( 輸出n 個RGB顏色，然後輸出的顏色越分開越好)
• 給定一個範圍(1~100之類的)，如何實作一個可以輸出n個(<100個)不重複數值的亂數產生器.
• 給定一個數列和一個數字，請寫出partition的程式，左邊小於此數字， 右邊大於等於此數字，要確保所有特殊數列都能通過測試.
• 順時鐘旋轉一張 NxN 的灰階圖片，不可以使用額外的二維陣列.
• Leetcode 98. Validate Binary Search Tree (Medium)
• Product of Array Except Self
• regular expression
• 給你一張圖，寫一個function參數是起點跟終點，找出最短路的長度
• 翻轉字串hello => olleh，翻轉語句hello world! => world hello! 字串使用linked list結構
• 給一個random的數列，其中只有一個數字佔數列的一半以上，請問如何找出這個數字?
• 給1~15的數字序列，最多可以拿5個，至少拿一個，先拿到15的人就贏了，請問必勝方法是什麼?
• 基本上都是leetcode 題目

Qnap:

1. 數字轉英文字串 123 -> one hundred twinty three
2. 給數學試算答案-> (1+2) -> 3
3. 給一串會重複英文字串，拿掉重複的使最後最符合字典排序
4. 題目為給予兩個array中已排序的數字，要你找出現在第一個array但不出現在第二個
   array的數字，並跟你討論空間、時間複雜度，接著要你改變輸出格式 原本輸出為
   數字\n數字\n 改為 數字,數字

Garmin:

• 給一個數學式子的 String 然後四則運算，
• 然後大數，要做加減乘 然後bonus題是除

群聯:

• 1.給你一個sort好的陣列a[20]，然後請你印出0~500的數字，如果數字在a[20]裡面，則不要印出，請你用最少的cpu和memory
• 2.類似上題，function給一個數字b=0,1,2,3,4時，分別印出0 ~ 99,100 ~ 199,200 ~ 299,300 ~ 399,400 ~ 499之中，不在a[20]裡面的數字，也是用最少的CPU跟memory。(我認為不需要用到switch case)
• 1~500不重複且隨機的print出所有數字
• 0~500個數字每次隨機取一個數字出來，但下次在抽出時不可以出現已經抽過的數字
• 找一數中的最左邊1的bit在第幾位，例如0101，最左邊的1在第三位
• 8-bit size的值求最高位元是在第幾個bit，解出來之後主管會問你如何改善
• 給兩個array塞數字，取差距最近的pair，答出來後，會問有沒有更快的方法
  ref: 1.Find_position_of_MSB 2.find-significant-set-bit
  群聯3題
  群聯3題
  群聯面試 韌體工程師

瑞昱:

• 面試流程主要為先用投影片介紹碩論及project，接下來是leetcode白板題
• 介紹物件導向是什麼？介紹物件導向三大特性

封裝(Encapsulation)、繼承(Inheritance)、多型(Polymorphism)

• 用c語言實作strcmp
• 找出一個數字的平方根，精確度在0.01以下
• 白板題考了bitwise operation
• 印出菱形
• 白板題考1-500樂透小程式 樂透小程式
• 找log7方法和利用正方形折出三角形
• 寫一個函式判斷little endian、big endian
• APP1與APP2溝通，共用一塊1.1KB大小Memory，彼此傳輸1K資料，剩下0.1K你會怎麼做

晨星:
最近都考C++ STL

int a[]={6,7,8,9,10}
int *p=a;
*(p++) +=123;
*(++p) +=123; 

HPE:
就是多講些和virtualization有關的東西，面試也有vmware那邊的team的人會看，要能提出你怎麼樣能勝任這個工作，就算沒有直接使用vmware的產品，對於aws或kubernetes或openstack能有點了解會更好

Nvidia:

1. Converts a digital number into a binary string.
2. Describe the differences between C and C++
3. Sort
4. Give a file and grab all the lines that contain the combination of “TEST” and a number

Ref:

• 113研替2017.11.4 聯發科、新思、晨星　很詳細
• 2017 聯發科allen
• 2017 ptt charles面試心得 聯發科/瑞昱/晨星
• 2017 面試（1部)［鴻海/聯詠/瑞昱/晨星
• 116 2017研替聯發科、聯詠、群聯
• 2018聯發、晨星、聯詠、新代、絡達、瑞昱
• Synology_群暉科技 hackmd
• 聯發科ｃ考題 hackmd
• 聯發科&群暉 hackmd
• 普安、Realtek c考題
• 聯發科暑期實習 2017.3.15
• Jserv Bit-wise operations
• 聯發科經典面試題 答案
• 研發 MTK 2016.8 howard
• 建蛋新鮮人求職
• 瑞昱　聯發科實習Andersen's Blog
• realtek-interview
• Ptt 大大OS、計組、網路複習資料
• 群聯考古題

C 考題

聯發科 (before 2018) :

[C test]
1.Explain "#error"
在編譯時，輸出錯誤訊息，警告使用者某些錯誤，並且不會真的進行編譯，在巨集處理階段就會停止
-----------------------
2.Explain "struct" and "union"
struct 為一個資料結構，可以放不同data type 的資料
union  與struct相同差別在於 union 的資料成員共用同一個記憶體
-----------------------
3.Explain "volatile".Can we use "const" and "volatile" in the same variable? Can we use "volatile" in a pointer?
可以的volatile是要告訴編譯器不要對此變數做最佳化

-----------------------
4.unsigned long v1 = 0x00001111;
  unsigned long v1 = 0x00001202;
  unsigned long v;
  v=v1&(~v2)
  v=v|v2  
  ask:the value of v
  
v = v | v2
  = (v1 & (~v2)) | v2
  = ( v1 | v2 ) & ( ~v2 | v2 )//等於0xFFFFFFFF
  = 0x00001313 
-----------------------  
5.int a[5]={1,2,3,4,5}
  int *p = (int*)(&a+1);
  ask:the value of *(a+1) ,(*p-1)?
  
  &a取出a的address
  
-----------------------    
6.write a code
(a) set the specific bit 
static inline void set_bit(*x,int n){*x |=(1<<n)}

(b) clear the specific bit
static inline void clear_bit(*x, int n){*x &=~(1<<n)}

(c) inverse the specific bit (0->1;1->0)
static inline void inverse_bit(*x, int n){*x ^=(1<<n)}


7.Re-write void(*(*papf)[3])(char*)//papf as a pointer to arrary of 3 pointers to a function (pointer to char) returning void
typedef void(*pf)(char*);
pf(*papf)[3];

8.write a code that check the input is a multiple of 3 or not without using division or mod


9.Explain lvalue and rvalue.

Ref:
1.Diagnostics
2.typdef不同用法
3.error-do
4.error-directive-in-c
5.C面試考題

Qualcomm 台北 (2018/11):

int a[5]={1,2,3,4,5};
int i;
  for(i=0;i<5;++i){
   if((char)a[i]=='5')
	printf("%d ", (char)a[i]);//這邊有點忘記~ 大概是這樣
  }
-------------------------------    
    orig=0x128a mask=0x30 val=0x70
    new= orig &  ~mask
    new |= val & mask;
    ask: new
-------------------------------
    int a=2.1 ,b =1.1;
    printf("%d ",a);
    printf("%d ",b);
-------------------------------
    int a[5]={1,2,3,4,5}
    int *p=a;
    *(p++) +=10;
    *(++p) +=20;
    
    for(int i=0;i<5;i++){
        printf("%d ", a[i])
    }
-------------------------------
    float num=1/1+1/2+.....1/10;
    printf(" %.0f",num);
-------------------------------
typedef struct _A{
	char a;
	double b;
}A; 

#pragma pack(push)
#pragma pack(1)
typedef struct _B{
	char a;
	double b;
}B;
#pragma pack(pop)

int main(void) {       
    printf("sizeof A:%d ",sizeof(A));
    printf("sizeof B:%d ",sizeof(B));
    return 0;
}
-------------------------------   
  func(int *a  , int b){      
      *(a++)=b;
  } 
  
  int a[5]={1,2,3,4,5};
  int *p=a;
  
  for(inti=0;i<5;++i){
      func(p ,*p+1);
      p++;
      printf("%d ",a[i]);      
  }   
  

機智問答

Question：
如果兩個人比賽，從1數到100，喊到100的人獲勝，每一次最少喊一個數，最多喊七個數，先攻的人喊到幾時便保證必勝？

Answer：                                                                         
如果自己要喊100，對方必須只能喊99~93，
        自己要喊  92，對方必須只能喊91~85，
        ...........................
        自己要喊  12，對方必須只能喊11~  5，
        自己要喊    4

因此只要先喊到4，則先喊的人必獲勝
往後原則就是喊 [8-對方喊幾次]
喊100除以8餘4的數，喊4 12 20 28 ... 

例如 A喊4
         B喊1次到5
         A喊(8-1=7次)到12
         直到A喊到92時，B不管怎樣都不會贏

Realtek:
( a ) 有九顆看起來一模一樣的球 但是有一顆不一樣重 也不知道它是比較輕還比較重 用一個天秤最少要量幾次可以"確保"找出這顆球?
( b ) 從1數到100 喊到100的人獲勝 每一次最少喊一個數 最多喊七個數 先攻的人喊到幾時便保證必勝?
( c ) 就是FB上有出現過的假錢問題 有個商品賣30元 成本25元 客人用100元紙鈔跟商人買了商品 商人沒錢找所以拿了這張紙鈔去跟隔壁攤販換零錢找給客人後來隔壁攤販跑來說那是假鈔 所以商人又賠了100元給隔壁攤販 試問商人總共虧多少錢?
Realtek 喊數字遊戲
搶數遊戲!
秤球問題

蒙提霍爾問題:

由貝氏定理得知：
如果在不換門的情形下，贏得新車的機率是 1/61/6+1/3=13≈33.3%；
如果在換門的情形下，贏得新車的機率是 1/31/6+1/3=23≈66.7%。
班的答案完全正確，但是直覺上機率 1/2 是怎麼回事？
蒙提霍爾問題
蒙提霍爾問題（一）決勝21點
蒙提霍爾問題-多門

燒繩子問題~