---
title: 題庫
description: 幫忙搜集面試題庫，貼在這你
---
# 題庫
###### tags: `Interview`
* [C/C++ - 常見 C 語言觀念題目總整理](https://mropengate.blogspot.com/2017/08/cc-c.html)
* [C面試考題](https://hackmd.io/@a110605/By6DscbVM?type=view)
* [變數互換|四種 swap 一次滿足](http://catforcode.com/swap-fuctions/)
* [MTK/MStar/Synology](https://hackmd.io/@86E3gZKuToKwjVavw4Wdpw/BJoOqyo6?type=view)
* [面試](https://hackmd.io/@6zSPCmL1Szq0bq_rOqcO6w/HkkhJ-ah-?type=view)
* [mutex](https://blog.louie.lu/2016/10/22/mutex-semaphore-the-difference-and-linux-kernel/)
* [發哥上機考題目整理](https://hackmd.io/@Rance/SkSJL_5gX?type=view)
* [os整理](https://hackmd.io/UZEomFelQH2QwSi88UpB2g?view#DeadLock-%E5%AE%9A%E7%BE%A9)
## 文彬面群暉的題目
1. 判斷主機使用Big endian還是Little endian
```c=
/// 方法一 : 藉由觀察位址變化
#include <stdio.h>
int main()
{
int a = 0x12345678; // 在記憶體(64bits)中會是 0x0000000012345678
char *ptr = &a;
if (ptr[0] == 0x78)
printf("Little-endian\n");
else
printf("Big-endian\n");
}
---
/// 方法二 : 藉由 指標轉型 與 間接運算子(*) 達成
#include <stdio.h>
int main() {
int i = 1;
char *c = (char *) &i;
if (*c)
printf("LITTLE_ENDIAN\n");
else
printf("BIG_ENDIAN\n");
return 0;
}
```
2. 還有定義Binary search tree的結構跟search add delete方法
* LeetCode 450 : BST delete
4. paging memory
5. 寫 kernel space跟user space程式的差異
6. 資料用linked list或是array儲存的差別
---
## 帥哥諺面群暉的題目
* 白板 : 兩個sort過的linked list merge成一條
* 白板 : In-Order 不要用 recusive
* 白板 : int 1234 reverse (4321)
* Process vs thread
* 解釋為什麼 1:3 分配 virtual memory (kernel : user)
* [U-boot 怎麼加速?](https://blog.csdn.net/liushuimpc/article/details/51830444)
* Copy-On-Write 怎麼做的?
* 你遇過印象深刻的bug?
---
# Recursive
* 小明爬階梯每一步可以跨一階或兩階。請幫我設計一支程式計算從平地爬上一個 N 階的階梯有幾種可能的步法。以三階的階梯為例，共有「 1 階 1 階 1 階；1 階 2 階； 2 階 1 階」三種步法。
* LeetCode 1137
## Key Differences between Recursion and Iteration
* A conditional statement decides the termination of recursion while a control variable’s value decide the termination of the iteration statement (except in the case of a while loop).
* Infinite recursion can lead to system crash whereas, infinite iteration consumes CPU cycles.
* Recursion repeatedly invokes the mechanism, and consequently the overhead, of method calls. This can be expensive in both processor time and memory space while iteration doesn’t.
* Recursion makes code smaller while iteration makes it longer.
---
# String
* 344. Reverse String
* 557. Reverse Words in a String III
# Linked-List
* 兩個Linked-List相加
* 2. Add Two Numbers
* Linked-List反轉
* LeetCode 206: Reverse Linked List
* LeetCode 24: Swap Nodes in Pairs
* insert一個element到一個sorted linked list，判斷兩個linked list是否相交
* LeetCode 21 : Merge Two Sorted Lists
---
# OS
* Thread vs Process
* queue vs stack
* stack vs heap
* static, global, local
* 如何將kernel-space的資料寫到user-space
* Linux的Work queue有哪些
* 甚麼是File System，為什麼要有File System
* Virtual Memory的觀念
* Page Fault
* LRU演算法
* struct vs union
* volatile
> ```volatile``` 為一關鍵字 加在變數的前面
被 ```volatile``` 宣告的變數 將不會使用 **最佳化編譯**
有時一個變數的值改變了 compiler 並不會馬上將他寫入記憶體中
而會先把結果放在CPU暫存器中 等到處理結束之後 才寫入記憶體
若說這個變數是多執行緒的flag 其他的執行緒要透過這個變數來反應
而這個值卻又沒有寫入記憶體 這時便會發生意想不到的結果
又或者是這變數為一個硬體的暫存器 會被硬體所改變
然而compiler 並沒有正確的將值從硬體暫存器取出來
而是將自己暫存的值拿來使用
這種情況 就是要用```volatile``` 來宣告變數 告訴compiler不要自己暫存變數來提升速度
程式永遠都要從記憶體中取得```volatile```宣告的變數，而不是CPU暫存器
如此這個變數有任何的改變 便會馬上反應出來
* lvalue and rvalue
* String 跟 StringBuffer差別
* Synchronization
設計一個作業系統，讓作業系統在操作shared data的時候，不會產生race condition
prevent unsafe concurrency and avoid race condition
solutions:
* **atomic instruction** (單一指令的動作，一次做完。若像i++要拆成3個指令，則可能發生race condition。但只能解決單變數問題，作業系統經常是其他資料結構方式。實作方式通常透過bitwise)
* **locking** (lock & unlock，但這種方式還是要搭配atomic instruction實作，才可避免cpu因interrupt而改變其狀態 (ISR可能執行同一個shared data))
* **spin lock**(spin+lock)，當要對某項變數進行操作時，會先將它整個資料結構lock住，其他process若要使用就只能在外面spin(wait)。spinlock在實作時為避免進入cs的process被搶占資源，會自動關掉kernal preemtion的功能 (spinlock通常用在multi processor 環境)(若lock的cs太長，則建議不使用spin lock，以免process busy wating過久)(進入cs的process還是可以被int，執行完int再回來(前提是沒有reschedule，但不能保證isr部會執行cs裡的變數，所以光靠spin lock不夠))
* **semaphores** 又稱sleeping lock ，process把自己設為idle(而不是spin)，這樣CPU可以去執行其他程式，不會一直busy waiting(等很久時間的話較適用)
>不能hold一個spin lock又hold一個semaphore，因為hold semaphore代表sleep，但反過來，可以hold一個semaphore又hold一個spin lock
* **mutex** special case的semaphore，行為和semaphore很像，但是count數只有1，很容易implement，且較有效率，一般linux kernal較多採用這種方式
[補充1](https://ithelp.ithome.com.tw/articles/10219642)
[補充2](https://welkinchen.pixnet.net/blog/post/47071066-spinlock-%26-mutex-%26-semaphore-%E7%9A%84%E4%BD%9C%E7%94%A8%E5%92%8C%E5%8D%80%E5%88%A5)
* [Concurrency vs Parallelism](https://medium.com/mr-efacani-teatime/concurrency%E8%88%87parallelism%E7%9A%84%E4%B8%8D%E5%90%8C%E4%B9%8B%E8%99%95-1b212a020e30)
* Causes of Concurrency
* interrupt
* softirq and tasklet
* kernel preemption (CPU跑process A，process A進kernel，os在操作process A的工作途中，若A沒有lock任何shared data，他就有可能被中斷執行其他程式。好處是對即時狀態反應很快，linux2.4後support)
* sleeping and synchronization with user-space
* symmetrical multiprocessing
* interrupt-safe
* SMP-safe (linux 1.0後支援)
* preempt-safe
---
* [搭配閱讀](https://hackmd.io/yo8egq8CSYOM3S688dAaMQ?view)
---
# OO
* 繼承、封裝、抽象、多型概念
* 寫個class的架構
---
# Sort
* [Mergesort vs heapsort](https://hackmd.io/@smalleye/B1lZvSboH)
* [book](https://www.epaperpress.com/sortsearch/download/sortsearch.pdf)
* LeetCode 561. Array Partition I
---
# Search
* [各種搜尋演算法](https://magiclen.org/search-algorithm/)
* 做search的話hash table跟sorted list哪個比較快
* [ref](https://stackoverflow.com/questions/876923/which-is-faster-to-find-an-item-in-a-hashtable-or-in-a-sorted-list)
* binary search
* 704. Binary Search
```c=
int binarySearch(int arr, int left, int right, int key){
while (left <= right){
int mid = left + (right - left) / 2;
if(arr[mid] == key)
return mid;
if (arr[mid] > key)
return binarySearch(arr, left, mid - 1, key);
return binarySearch(arr, mid + 1, right, key);
}
return -1;
}
```
* BFS
* DFS
---
# others
* tree (算樹的高度、節點數量)
* DP
* 字串反轉
* 一連續數列，打亂，並被拔掉一數，那要怎麼找到是哪個數被拔掉
* 以 C 實作 strcpy
```c=
int __cdecl strcmp (const char *src, const char *dst)
{
int ret = 0 ;
while(!(ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
{
++src;
++dst;
}
/// src < dst, return < 0
if ( ret < 0 )
ret = -1 ;
/// src < dst, return > 0
else if ( ret > 0 )
ret = 1 ;
/// src == dst, return 0
return( ret );
}
```
* 計算出字串內每個字元出現過幾次
* 找出array中重複的數字
* 寫一個function 此function會allocate一塊記憶體給array Ex. myAllocate( &myArray, n );找子集合元素相加最大值 Ex. {2, -1, 3} 有沒有更快的作法?
* Input: 1, 2, 3, 4, 5 => rotate( input, 2 ) => Output: 3, 4, 5, 1, 2，有沒有更快的作法? 用遞迴怎麼做?
* a++ 和 ++a 差別
```c=
int main(){
int A = 2;
int B = 2;
int C = A++;
int D = ++B;
printf("C=%d D=%d \n",C,D);
return 0;
}
int main()
{
int a = 2;
int b = 2;
a = a+++1;
b = ++b+1;
printf("%d %d\n", a, b); // 3 4
}
/// 輸出結果 C=2, D=3
/// A++：意思是先把A放到C，再執行A=A+1 的動作。
/// 因為A先放到C，所以C的值會是2
/// ++B：意思是先再執行B=B+1，再把B放到D。
/// 因為B會先執行B=B+1的動作，所以D的值會是3
```
* [Bitwise Operation (C)](http://puremonkey2010.blogspot.com/2011/05/c-bitwise-operation.html)
* [以linked List 實作 queue](https://alrightchiu.github.io/SecondRound/queue-introjian-jie-bing-yi-linked-listshi-zuo.html)
* [以array 實作 queue](http://alrightchiu.github.io/SecondRound/queue-yi-arrayshi-zuo-queue.html)
* [hash table(c++)](https://mropengate.blogspot.com/2015/12/cc-map-stl.html)
## 參考資料
Sign in with Wallet
Connect another wallet