# CPP 面試筆記
# Ref
[C++ Interview Questions](https://hackr.io/blog/cpp-interview-questions?fbclid=IwAR0GluAmoeBIvnMmqhxBMvb0bElUBSa63eTsy5dwd9ret2_ejgvbhnNBfnQ)
[常見 C 語言觀念題目總整理（適合考試和面試）](https://mropengate.blogspot.com/2017/08/cc-c.html)

## 1. 繼承

class E {
public:
    E(){cout<<"E";}
    ~E() {cout<<"~E";}
};

class D {
public:
    E *e;
    D(){cout<<"D"; e = new E;}
    ~D() {cout<<"~D"; delete e;}
};

class A {
public:
    A(){cout<<"A";}
    ~A() {cout<<"~A";}
};

class B : public A {
public:
    B(){cout<<"B";}
    ~B() {cout<<"~B";}
};

class C : public B {
public:
    D d;
    C(){cout<<"C";}
    ~C() {cout<<"~C";}
};

int main(){
    C c;
}

Output: ABDEC\~C\~D\~E\~B\~A
priority: 繼承 > member var(pointer不會init) > constructor

## 2. Coding Problem

char* func(){
    char a[10] = "123";
    return &a[0];
}

int main(void)
{
    char* a = func();
    cout<<a[0];
}

Function裡面的變數會被存在stack裡，Function 結束時就會被release掉，
Sol1: 在main allocate 變數
Sol2: dynamic allocte 會在heap，用完要記得delete掉

char* func(){
    char* a;
    a = new char[10];
    return a;
}

## 3. Abstract Class

class Base // abstract class
{
   int x;
public:
    virtual void fun() = 0;  //Pure Virtual Function 
    int getX() { return x; }
};

// This class inherits from Base and implements fun()
class Derived: public Base
{
    int y;
public:
    void fun() { cout << "fun() called"; }
};

需要在繼承的時候implement function，不然會compile error
Abstract Class 不能單獨宣告

## 4. Static
1. global static
life : process runtime
scope : whole process
global variable for the file

2. local static
life : process runtime
scope : in function
Ex:

void f(){
    static int a = 0;
    cout << a++;
}

int main(){
    f();
    f();
    f();
}

Output: 012

3. static member variable/function

class A{
    static int a;
    static int get(){
       return a;
    }
}

int A::a = 0;

同一個 class 的 objects 會 share 同一個 static member variable,
由於 static member variable 在程式執行時就會被 create, 因此需要另外初始化
=> 同理, 可以藉由 static member function 來 access static member variable

4. static function

static void function(); // in header file

只有該 file 才看的到此 function
若多個 cpp 會 include 同一個 header file, 如果該 function 沒有 define 成 static, 在 create symbol 時,當要整合成執行檔， link 就會出問題

## 5. STL
vector, map(紅黑樹), unordered_map(hash), set(紅黑樹), unordered_set(hash)
### [Vector](https://mropengate.blogspot.com/2015/07/cc-vector-stl.html)

## 6. sprintf/strcat/strcpy

void func(){
    char a[5];
    sprinf(a,"123456");
}

risk : 填的值超過 char array size, 會有 buffer overflow risk
sol : 改用 snprintf/strncat/strncpy -> 需 input size n

## 7. polymorphism 多型
static v.s dynamic
- static : compile time polymorphism
function overloading : 同一個 function 名稱, 有不同的 parameter
operator overloading : 讓運算子(符號)有不同的意義。讓我們可以自己定義Operator的功能，讓程式可以更精簡
- dynamic : run time polymorphism
Allows us to override a function of parent class in child class
virtual function : 當你用在derived class object使用pointer或reference時，你可以call virtual function for that object 並執行該derived class的function。

## 8. static binding v.s. dynamic binding

- static binding ，compiler 會在 compile-time 時就把函式定義與函式呼叫連結起來, 由於呼叫函式的所有資訊都已經提前先知道了，所以在程式真正執行起來會比較快一些
e.g. function overload
int a(int)
int a(int,int)
- dynamic binding ，這樣的連接會一直延遲至 run-time 才會發生，因此也可稱為 late binding。在 C++ 中，dynamic binding 主要可以透過 virtual 來達成 e.g. virtual

## 9. oop 封裝 (encapsulation) 、繼承 (inheritance) 及多型 (polymorphism)
- 繼承 : 目的是讓 derived class 可以擁有 base class 的成員 (member), 且其子物件的的型別也會是富物件的型別
- 多型 : 同一個名字的 function 可以有不同的用途,可以在父類別定義並且子類別的物件都可以用同一個function來對於不同的物件做不同的事情
- 封裝 : 把 data 隱藏在 class 裡面, 讓外部不能隨意存取(private),若想讓子類別的物件存取則可以用(protected),其餘則在public可以讓程式任意存取, 以確保class的安全性,不該被動到的變數不會被輕易碰到

## 10. virtual function

class base { 
public: 
	void fun_1() { cout << "base-1\n"; } 
	virtual void fun_2() { cout << "base-2\n"; } 
	virtual void fun_3() { cout << "base-3\n"; } 
	virtual void fun_4() { cout << "base-4\n"; } 
}; 

class derived : public base { 
public: 
	void fun_1() { cout << "derived-1\n"; } 
	void fun_2() { cout << "derived-2\n"; } 
	void fun_4(int x) { cout << "derived-4\n"; } 
}; 

int main() 
{ 
	base* p; 
	derived obj1; 
	p = &obj1; 

	// Early binding because fun1() is non-virtual 
	// in base 
	p->fun_1();

	// Late binding (RTP) 
	p->fun_2(); //rewrited by derived class

	// Late binding (RTP) 
	p->fun_3(); //not rewrited by derived class

	// Late binding (RTP) 
	p->fun_4(); //Not the same function of fun_4(int x)
}

## 11. design pattern
可以看[這本](https://legacy.cs.indiana.edu/classes/c212-dgerman/spr2015/griffin/a.pdf)，常見的有 singleton, factory, decorator...，design pattern 固然重要，但 designe pattern 的發明往往是根據語言的限制而創建的，可以參考但不用完全參照。

## Storage class in C++?
Storage class in C++ specifically resemble life or even the scope of symbols, including the variables, functions, etc. Some of the storage class names in C++ include mutable, auto, static, extern, register, etc.

## volatile
volatile關鍵字可以用來提醒編譯器它後面所定義的變量隨時有可能改變，因此編譯後的程序每次需要存儲或讀取這個變量的時候，都會直接從變量地址中讀取數據。
編譯器優化的時候 看到上下文 可能沒有對這個記憶體位址的值做更動 編譯器編譯的時候 就不會從新從記憶體mov 新資料到暫存器中
被更動的可能有 像是共用share memory的時候，或是DMA在搬資料的時候，或是中斷程式。
"Volatile" is a function that helps in declaring that the particular variable is volatile and thereby directs the compiler to change the variable externally- this way, the compiler optimization on the variable reference can be avoided.

## C vs C++
[Ref](https://www.freecodecamp.org/news/c-vs-cpp-whats-the-difference/)
### C
- procedural oriented language
- emphasis is on functions

### C++
- procedural language
- Object Oriented
- diving a program into objects.
- Everything is organized and divided into smaller groups of related parts or objects

## Stack vs. Heap
### Stack
靜態記憶體配 置用來儲存 Value Types (Primitives)的地方，其特性是 LIFO （後進先出），用來儲存物件的 stack 與 run-time 的 call stack 運作原理是一樣的，run-time 的 stack frame 包含了：
Parameters：函數的參數
Return address：回傳位址，當function執行完，從哪行code繼續執行
Local variables：區域變數
一但 function 執行完畢，系統會自動回收空間，不需要擔心 Memory Leak 在這裡發生。
### Heap
動態記憶體配置
用來儲存 Reference Types，new 一個物件即是存在 Heap 裡面，由於是動態配置記憶體空間，其存活時間不規律不可預測的，即使已經執行完動態配置的 function ，物件仍可能存在 Heap 中，這邊會因程式語言有沒有 GC 功能而有所不同：
需要release memory

## STL
### Unorder Set vs. Set and Unorder Map vs. Map
C++ STL 中 map 裡面的存放資料是有序(排序)的，map 對應的資料結構是紅黑樹(red-black tree)，紅黑樹是一種自平衡的二元搜尋樹，在紅黑樹上做搜尋的時間複雜度為O(logN) unordered_map 裡面的存放資料是無序的，unordered_map 對應雜湊表(hash table)，雜湊表的特點就是搜尋效率高，利用鍵值與雜湊函數(hash function)計算出雜湊值而快速的查找到對應的元素，時間複雜度為常數級別O(1)， 而額外空間複雜度則要高出許多。unordered_map 與 map 的使用方法基本上一樣，都是 key/value 之間的映射，只是他們內部採用的資料結構不一樣。所以對於需要高效率查詢的情況可以使用 unordered_map 容器。而如果對記憶體消耗比較敏感或者資料存放要求排序的話則可以用 map 容器。

## Hashing
[Link](https://blog.kennycoder.io/2020/02/18/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95%E7%AD%86%E8%A8%98-Hashing-%E9%9B%9C%E6%B9%8A%E5%8E%9F%E7%90%86%E4%BB%8B%E7%B4%B9/)
是一種資料儲存與擷取之技術，當要存取 Data X 之前，必須先經過 Hashing Function 計算求出 Hashing Address (or Home Address)，再到 Hash Table 中對應的 Bucket 中存取 Data X，而 Hash Table 結構是由 B 個 buckets 組成，每個 bucket 有 S 個 Slots，每個 Slot 可存一筆 Data

=> Hash Table 大小 = B * S 筆

再沒有 Collision 情況下，Search X 之 time 為: O (1)，與資料量 n 無關

### 何謂 Collision (碰撞)？
不同的 Data，例如 (x,y)，經過 Hashing function 計算後得出相同的 Hashing Address 稱之，也就是 H (x) = H (y)。

### 何謂 Overflow (溢位)？
當 Collision 發生後，且對應的 Bucket 已滿，則稱為 Overflow

### Overflow 處理方法 (重要)
#### Linear Probing (線性探測)
當 H (x) 發生 overflow 的時候，則探測 (H (x)+i)% B，B 為 Bucket 數，i = 1,2,3,…,B-1，直到有 Bucket 可存 or Table 全滿為止

優點：

- 簡單、易於實施
- 保證 Table 空間可以充分利用
缺點：

- 容易發生 Primary Clustering 現象，造成 Search/Insert/Delete X 等時間大幅增加之問題

- Primary Clustering 意思：具有相同 Hashing Address 之 Data 容易占用相鄰的 Buckets 存放，形成群聚現象

#### Chaining or Link List (鏈結串列)
具有相同的 Hashing Address 的 Data 均置入同一個 Bucket 去，而 Bucket 內之 Data 彼此透過 Link List 結構串連在一起，而這種情況就作 Closed Address Mode。

其他的 Overflow 處理方法是 Open Address Mode。

分析：

最差之 Search Time in chain 是 O (n)，但如果串列裡面結構改用 AVL Tree、R-B Tree 之結構去作，則改善時間為 O (logn)

#### Rehashing (再雜湊)
提供一系列的 Hashing Function H1~Hm，當 H1 發生 Overflow，則改用 H2，以此類推，直到找到 Bucket 可存，或 Hashing Function 用完為止。

## C++ virtual 用法
[Link](https://shengyu7697.github.io/cpp-virtual/)

virtual function:可以讓子類別在繼承父類別後,可以call到子類別內部的function 並且實作不同繼承的class可能有不同的function的實作

pure virtual function:父類別宣告一個 =0的function 並且在子類別一定要被實做出來，且有pure virutal function 的 clss 稱為abstract class 不能獨立宣告一個object(因為裡面沒有實作完整)

class Animal {
public:
    virtual void eat() {
        cout << "I eat food\n";
    }
    virtual void drink() =0; //pure virtual function -> must implemented in the derived classes
                             // the class derived is call abstract class, it can't define a object
};

class Dog : public Animal {
public:
    void eat() override {
        cout << "I eat meat\n";
    }

    void drink() override {
        cout << "I drink water\n";
    }
};

class Cat : public Animal {
public:
    virtual void eat() override {
        cout << "I eat fish\n";
    }
    void drink() override {
        cout << "I drink water\n";
    }
};

## C++ pointer 注意
一個pointer可以給三種值
- 一個指標
- 一個新的記憶體位置
- 一個變數的位置

int * getAddressA(){
    int *p=new int;
    *p=100;
    return p;
}
int * getAddressB(){ //比較少用到
    return new int;
}
int * getAddressC(){
    int p=50;
    return &p;
} ///這個會fail 因為當function執行結束後 p的記憶體就被收回了 ((function的變數放在stack中

用完的memory 可以delte掉

## malloc() vs new
1. new calls constructors, while malloc() does not. In fact primitive data types (char, int, float.. etc) can also be **initialized with new**.

## CCT
- 給你一個 binary search tree 再給你一個數字範圍假設數字1到10，要怎麼有效率的把這個bst 的數字加起來
- 假設你遇到一個需求，就像電動中要學習技能一樣，學習一個技能之前可能要有其他技能才能學習這個技能，舉例：學習游泳前要先學會換氣2級，學會滑水3級，你會用什麼資料型態來表達技能
- Follow up: 設計一個function輸入技能，回傳學到這個技能需要的技能點數，舉上面的例子學習游泳總共就需要6點，因為要5點先學會之前的技能加上1點學游泳的技能。
- 給你一個二維矩陣，如何向右或向左翻轉90度
- 假設給你100塊，可以分成3、5、10塊，共有幾種組合