C/C++ 常見試題

Pointer

9 min readSep 18, 2019

Call by Value, Call by Address, Call by Reference (C++獨有)
http://wp.mlab.tw/?p=176

你所不知道的C語言：指標篇
https://hackmd.io/@sysprog/HyBPr9WGl?type=view

放在函數裡的指標，若是沒有以*p去做處理，而是以p直接去寫入的話，會因為進入函數另外指向的指標而失效，因此要以指標的指標來做處理。

C/C++ — 常見 C 語言觀念題目總整理（適合考試和面試）
https://mropengate.blogspot.com/2017/08/cc-c.html

int a; // 一個整型數
int *a; // 一個指向整數的指標
int **a; // 一個指向指標的指標，它指向的指標是指向一個整型數
int a[10]; // 一個有10個整數型的陣列
int *a[10]; // 一個有10個指標的陣列，該指標是指向一個整數型的
int (*a)[10]; // 一個指向有10個整數型陣列的指標
int (*a)(int); // 一個指向函數的指標，該函數有一個整數型參數並返回一個整數
int (*a[10])(int); // 一個有10個指標的陣列，該指標指向一個函數，該函數有一個整數型參數並返回一個整數//秘訣是由後往前念

Compare 印出1

int B = 2;void func(int *p){p = &B;}int main(){
     int A = 1, C = 3;
     int *ptrA = &A;
     func(ptrA);
     printf("%d\n", *ptrA);
     return 0;
}

Compare 印出2

int B = 2;void func(int **p){ *p = &B; }int main(){
     int A = 1, C = 3;
     int *ptrA = &A;
     func(&ptrA);
     printf("%d\n", *ptrA);
     return 0;
}

Explain this declairation.

void **(*d) (int &, char **(*)(char *, char **));
--------------------------------------------------------------------
+ d is a pointer to a function that takes two parameters:
    + a reference to an int and
    + a pointer to a function that takes two parameters:
        + a pointer to a char and
        + a pointer to a pointer to a char
    + and returns a pointer to a pointer to a char
+ and returns a pointer to a pointer to void

[C] 透過函式記憶體配置 — malloc()malloc in another function
http://lee.logdown.com/posts/98518/c-through-the-function-malloc-memory-configuration

#include <stdio.h>
#include <stdlib.h>
void getMemory(char** s)
{
    *s = (char*)malloc(sizeof(char));
    printf("s = %p\n", s);
    printf("*s = %p\n", *s);
}
int main()
{
    char* ch = NULL;
    getMemory(&ch);
    printf("&ch = %p\n", &ch);
    printf("ch = %p\n", ch);
    return 0;
}```````````````````````````````````````
s = 0x7fff5d2ebc00
*s = 0x7f943bc000e0
&ch = 0x7fff5d2ebc00
ch = 0x7f943bc000e0

字串String反轉

void swap(char* a, char* b){
    if(a==b)return;
    *a^=*b;
    *b^=*a;
    *a^=*b;
}void reverseString(char* s, int sSize){    
    int i=0,j=sSize-1;
    while(i<j){
        swap(s+i,s+j);
        i++;j--;
    }
    return;
}

Virtual Function & Pure Virtual Function

純虛擬函式、抽象類別（Abstract class）
https://openhome.cc/Gossip/CppGossip/PureVirtualFunction.html

C/C++ 學習筆記 004 — polymorphism(多型) 與 virtual function(虛擬函數)
https://lihan.cc/2013/10/410/

overload v.s. overwrite

過載(overload)和重寫(overide，有的書也叫作“覆蓋”)的區別
https://www.itread01.com/content/1547161401.html

Ｃ＋＋繼承、建構解構、虛擬順序

[問題] 關於 C++ 的繼承與建構解構式
https://www.ptt.cc/bbs/C_and_CPP/M.1387272060.A.921.html
http://codepad.org/r7PfzyAs

Q. 請說明 struct 和 class 的差別？

struct是一種值類型，用於將一組相關的variable組織為一個單一的variable實體。
struct實例在創建時分配在process的stack上，它本身儲存了值，所以在使用時，我們可以將其當作int、char這樣的基本類型對待。

class是Object Oriented的基本概念，是一種自定義數據結構類型，可以藉由該實體去描述它的屬性跟功能，也是一種引用類型。
當new一個class的instance時，會在stack上存放該instance在managed heap中的pointer，而instance的值會保存在managed heap當中。

Q. 請說明在c++/c#中，你分別用何種方式處理race condition的問題?

使用Lock來控制彼此之間的進入條件，mutex或是boost::shared_mutex。

Function pointer

[link_1] [link_2]

使用時機

同時符合
  1. 具有一樣輸入輸出但是動作不同的functions
  2. 這些functions有共同的使用時機及規範
便會考慮用function pointer將這些不同的動作封裝起來。優點在於可以一個function pointer便將可能所需的各式動作，以一致的表示法處理，所以可用簡潔的方式動態地執行，以避免用switch case所帶來的大規模修改。缺點也不少，他對於型態的限制其實很鬆，只要轉型後能匹配的都可以，因此內含的隱式型態轉換是很容易藏 bug 的，使用時如不慎容易被搞。
還有必須確定function pointer所指的func是我們所規範的那個func集合才行，不然不小心invoke一個只是符合輸入輸出，但卻八竿子打不著關係的function也是枉然。舉例：
某 BBS 站，決定使用者按鍵的動作就是利用一個 array of function pointers 預先設定好各個字母所要執行的功能，也就是先指定個別的 function pointer 。
例如：
  KeyFunc keys[MAX_KEYNUM];  // KeyFunc 是一種 function pointer type  
  keys['A'] = &keyFuncA;  // 可不寫 & 
  keys['B'] = &keyFuncB; ...  
這樣子在執行時讀取到一個使用者的按鍵內容，經過檢查為合法按鍵值後，便可以直接進行相關的處理動作。

Function Pointer 即為儲存某一個函式起始memory address的變數，此變數可以提供我們在之後進行呼叫。我們可以藉由function pointer省去繁複的 if/switch。

最前面的int是變數data type(資料型態)，和要指向的函式回傳值型態相同。第一個小括號代表指標變數名稱，第二個小括號代表傳入的parameter資料型態們，且理所當然的type必須與我們要指向的函式傳入值相同。例如三個副函式：

(1) int add(int);
(2) float add2(float);
(3) int add3(int,int);

並且宣告一個函式指標：
int (*pf)(int);

則：
(a.) pf = add;    //正確
(b.) pf = add2;   //錯誤，參數資料型態不匹配
(c.) pf = add3;   //錯誤，引入參數個數不匹配

function pointer 的 pointer operator(*)必須與變數名稱一起被小括號括起來並接參數的小括號。若沒有這個小括號，會變成：int *fptr(int); （Ｘ）

常見範例 [link_1]

#include <stdio.h>

//function宣告 
int doAdd(int, int);
int doMinus(int, int);

int main(void) {
   //宣告 function pointer
   //注意所設定的參數數量與型態
   int (*my_func_ptr)(int, int);

   //function pointer 指向 doAdd
   my_func_ptr = doAdd;
   printf("fp 指向 doAdd => %d\n", (*my_func_ptr)(5, 3));    //結果：8

   //function pointer 指向 doMinus
   my_func_ptr = doMinus;
   printf("fp 指向 doMinus => %d\n", (*my_func_ptr)(5, 3));  //結果：2 

   return 0;
}   //end main


int doAdd(int a, int b) {
   return a + b;
}   //end doAdd

int doMinus(int a, int b) {
   return a - b;
}   //end doMinus

結合typedef

結合typedef
typedef int (*MathMethod)(int, int);
意即把int (*)(int, int)簡化成MathMethod
--------------------------------------------------------------------typedef int (*MathMethod)(int, int); 
int Mul(int a, int b){return a*b;}
int Divide(int a, int b){return a/b;}
int Minus(int a, int b){return a-b;}
int Add(int a, int b){return a+b;}int Calc(int x, int y, MathMethod Opt){
     return Opt(x, y);
} 
 
int main(){
    int a = 8, b = 7;
    printf("a x b = %d\n", Calc(a, b, Mul)); 
    printf("a / b = %d\n", Calc(a, b, Divide));
    printf("a + b = %d\n", Calc(a, b, Add));
    printf("a - b = %d\n", Calc(a, b, Minus));
}

sizeof

sizeof 不是函式，不會在執行時計算變數或型別的值，而是在編譯時，所有的 sizeof 都被具體的值替換。

double f(){
  printf("Come into Double f...\n");
  return 0.0;
}

int main(){
  int var=0;
  int size=sizeof(var++);  //sizeof(var++)在編譯時會直接被替換++不會執行
  printf("var = %d, size = %d\n", var, size);
  size = sizeof(f());
  printf("size = %d\n", size);
  return 0;
}
##output
var = 0, size = 4
size = 8

常見考題

64bitsizeof(string)          = 8
sizeof(char)         = 1
sizeof(p)            = 8
sizeof(short)        = 2
sizeof(int)          = 4
sizeof(long)         = 8
sizeof(long long)    = 8
sizeof(size_t)       = 8
sizeof(double)       = 8
sizeof(long double)  = 1632bitsizeof(string)          = 4
sizeof(char)         = 1
sizeof(p)            = 4  //指標
sizeof(short)        = 2
sizeof(int)          = 4  //怕因環境影響程式,絕大多數64,32的編譯器是一樣大
sizeof(long)         = 4      
sizeof(long long)    = 8
sizeof(size_t)       = 4
sizeof(double)       = 8
sizeof(long double)  = 12    //看作long+double = 4 + 8 =12

Explain “struct” “union” “enum”

struct Employee{
	char name[30]; // 名字
	int age; //年齡
	char gender; // 性別，'M' or 'F'
	double salary; // 薪水
};
struct Employee employee; // 宣告變數employee，記得前面要加structunion Var{ 
	char ch;
	int num1;
	double num2;
};除非特別指定，不然都是由0開始，接下來遞增1，例如以下語法：
enum week{Sunday,Monday,Tuesday,Wednesday,Thursday,Friday,Saturday};
以上從Sunday開始，各個識別字被依序設定為0到6，你也可以指定數值

enum week{Monday=1,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday};

malloc, calloc, memset, realloc[link]

int *dynArr;
int arrLen = 10;
// 配置未初始化的記憶體空間
dynArr = malloc( arrLen * sizeof(int) );
//dynArr = calloc(1000, sizeof(int));if( dynArr == NULL ) {
 fprintf(stderr, "Error: unable to allocate required memory\n");
  return 1;
}
// 將記憶體初始化為 0
memset(dynArr, 0, arrLen * sizeof(int));
int *dynArr2 = realloc(dynArr, sizeof(int) * arrLen * 2);
//若記憶體空間大小是足夠的話，有機會讓dynArr2跟dynArr的記憶體位置相同
//不過如果dynArr後面已經沒空間的話，realloc會另外找新的空間給dynArr2，這時候位置可能就會不同。

volatile

以上的i, j, k很有可能被compiler最佳化而導致產生
i = j = k = *pPort;
的code, 也就是說只從pPort讀取一次, 而產生 i = j = k 的結果, 但是原本的程式的目
的是要從同一個I/O port讀取3次的值給不同的變數, i, j, k的值很可能不同(例如從此
I/O port 讀取溫度), 因此i = j = k的結果不是我們所要的

一個參數可以同時是const也是volatile嗎? 解釋為什麼。
∙是的。舉的例子是"只讀的狀態暫存器"。
它是volatile因為它可能被意想不到地改變。它是const因為程式不應該試圖去修改它。

lvalue vs rvalue [link]

左值讓一段 expression 成為一個有名稱的物件；而右值只是一段 expression 的結果且隨時會蒸發不見。所以像 ++x 是左值而 x++ 卻是右值。可以利用一個簡單的方法來 check 一段 expression 是 lvalue 或 rvalue，就是看看可不可以使用 & 運算元對該 expression 取得他的位置。左值和右值皆可以為 non-const 和 const (用 non-const 似乎較 modifiable 來的直覺)，以下為範例：

string one("cute");
const string two("fluffy");
string three() { return "kittens"; }
const string four() { return "are an essential part of a healthy diet"; }

one; // modifiable lvalue
two; // const lvalue
three(); // modifiable rvalue
four(); // const rvalue[以下待整理]Lvalue: 就是一個運算式後還保留其狀態的一個物件 就是Lvalue; 也
就是說 所有的變數(variables)包含nonmodifiable, const 的變數都是Lvalue. 
這邊一個重點是 const的變數也是Lvalue

Rvalue: 就是一個運算式過後其狀態就不會被保留了, 
也就是一個暫存的數值

另一種說法(非完全正確,  但是可以依此來稍做判斷)
能出現在assignment 運算子(=)的左邊的稱為Lvalue, 而只能出現在右邊的稱為Rvalue

這邊只有說出現在左邊的是Lvalue, 但沒說Lvalue不能出現在右邊, 因此Lvalue在=運算子的左右兩邊都是被允許的, 
而Rvalue是不能出現在左邊的; 這邊有沒有注意到, Lvalue是可以被放到右邊的, 也就是說Lvalue也可以被當作Rvalue, 但是Rvalue就不能被當作是Lvalue

static

當變數有宣告時加上 static 限定時，一但變數生成，它就會一直存在記憶體之中，即使函式執行完畢，變數也不會消失。在一個原始程式文件中宣告全域 static 變數，還表示其可以存取的範圍僅限於該原始程式文件之中，也可以將函式宣告為 static。(C++) 若是在class的function前呼叫，則可以在不初始instance的情況下呼叫函數。C語言static有兩個目的
static storage （靜態存儲）：變數儲存空間為static storage而非function stack，使變數生命週期與程式相同。
internal linkage（內部連結）：限制變數可視範圍於檔案內。（聽說這是後來加的，為了減少保留字的使用所以也用static）
function使用static修飾
一個 static函式表示，其可以呼叫的範圍限於該原始碼文件之中，如果有些函式僅想在該原始程式文件之中使用，則可以宣告為 static，這也可以避免與其他人寫的函式名稱衝突的問題。

記憶體配置

[link]

global:

用來放全域變數、靜態變數(static)等等。

stack:

台灣正體中文稱為堆疊，大陸叫做棧。

區域變數、函式的參數與函式的位址等等，由系統管理，必須在編譯時期為已知。這些變數的回收會發生在它從堆疊pop出去的時候，因為個數、大小什麼的都是已知，所以系統知道怎麼進行配置與回收。

heap:

台灣正體中文稱為堆積，大陸叫做堆。

這裡的記憶體由使用者負責進行回收，配置則是由malloc或是new來負責。使用這裡的記憶體主要是用在編譯時期還不知道大小或個數的變數。例如說，你需要用一個陣列，這個陣列的大小要在執行的時候由使用者的輸入來決定，那你就只能使用動態配置，也就是把這個陣列配置在heap中。

.bss section [link_1]

1. 當 global variable 未被初始化時；
2. 或是 global variable 被初始化成零時。如果（但是確實有這種應用場合）我們不想讓 variable 被放到 .bss section 呢？
做法有二:
1.「傳統做法」，程式設計師只要將 global variable 初始化為「非零」值即可。
2. 利用gcc -fno-zero-initialized-in-bss
如：gcc -fno-zero-initialized-in-bss -O2 -o bss bss.c

Quick Sort

C Language

void quickSort(int* nums, int head, int tail){
    if(head>=tail){return;}
    int comp=nums[head];
    int i=head,j=tail;
    while(i<j){
        while(nums[j]>=comp && i<j){j--;}
        nums[i]=nums[j];
        nums[j]=comp;
        while(nums[i]<=comp && i<j){i++;}
        nums[j]=nums[i];
        nums[i]=comp;
    }
    quickSort(nums,head,i-1);
    quickSort(nums,j+1,tail);
}

C++

void quickSort(vector<int>& nums, int start, int end){
    if(start>=end)return;
    int left=start+1, right=end;
    while(left<right){
        if(nums[left]<=nums[start])left++;
        else if(nums[right]>nums[start])right--;
        else std::swap(nums[left],nums[right--]);
    }
    if(nums[left]>nums[start])left--;
    std:swap(nums[left],nums[start]);
    quickSort(nums,left+1,end);
    quickSort(nums,start,left-1);
}

typedef

typedef 保留字可以為資料型態建立別名，使程式更易閱讀理解。

typedef struct structNameee {
 char name[16];
 int age;
 struct structNameee *ptr;
} PERSON;int main(void) {
    PERSON person1 = {"Amy", 20 };
    person1.age = 21;
}

綜合考題

Q1. 請試著寫出下面代碼的輸出:

#include 
#includeint main() 
{ 
    char strAry[] = “This is string”; 
    char *aryPtr = strAry; 
    int *intPtr = (int*)strAry;    printf(“\t[Line01] strAry=%s\n”, strAry); //This is string
    printf(“\t[Line02] aryPtr=%s\n”, aryPtr); //This is string
  //printf(“\t[LineX] *aryPtr=%s\n”, *aryPtr); // Segment fault 
    printf(“\t[Line03] sizeof(aryPtr)=%d\n”, sizeof(aryPtr)); //4
    printf(“\t[Line04] sizeof(*aryPtr)=%d\n”, sizeof(*aryPtr)); //1
    printf(“\t[Line05] *aryPtr=’%c’\n”, *aryPtr); //'T'
    printf(“\t[Line06] *aryPtr+1=’%c’\n”, *aryPtr+1); //'U'
    printf(“\t[Line07] *(aryPtr+1)=’%c’\n”, *(aryPtr+1)); //'h'
    printf(“\t[Line08] sizeof(intPtr)=%d\n”, sizeof(intPtr)); //4
    printf(“\t[Line09] sizeof(*intPtr)=%d\n”, sizeof(*intPtr)); //4
    printf(“\t[Line10] intPtr=%s\n”, intPtr); //This is string
  //printf(“\t[LineX] *intPtr=%s\n”, *intPtr); // Segment fault 
    printf(“\t[Line11] *intPtr=’%c’\n”, *intPtr); //'T'
    printf(“\t[Line12] *intPtr+1=’%c’\n”, *intPtr+1); //'U'
    printf(“\t[Line13] *(intPtr+1)=’%c’\n”, *(intPtr+1)); //' '
return 0; 
}

Ans.

[Line01] strAry=This is string # 字串陣列 char[] =”…” 會自動加上 NULL 到結尾.
[Line02] aryPtr=This is string # 同上, 只是把 aryPtr 指標指向 strAry 的位置. strAry 本身也是個指標.
[Line03] sizeof(aryPtr)=4 # 指標的大小根據系統是 32bit (4byte) 或是 64bit(8bypte) 有所不同.
[Line04] sizeof(*aryPtr)=1 # char 的大小為 1 byte.
[Line05] *aryPtr=’T’ # 指向字串中第一個字元 ‘T’
[Line06] *aryPtr+1=’U’ # char ‘T’ + 1=char ‘U’. -> ASCII ‘T’=84. 84+1=85=ASCII ‘U’.
[Line07] *(aryPtr+1)=’h’ # 將 aryPtr 指標移動一個 char 的位置 (1 個 byte 的距離), 即是字串的第二個字元 ‘h’.
[Line08] sizeof(intPtr)=4 # 同 Line03
[Line09] sizeof(*intPtr)=4 # int 類型的大小為 4 byte.
[Line10] intPtr=This is string # 雖然用 int* 指定 pointer 類型, 但是在 printf 使用 ‘%s’, 故還是打印出字串出來.
[Line11] *intPtr=’T’ # 指向字串中第一個字元 ‘T’.
[Line12] *intPtr+1=’U’ # 同 Line6
[Line13] *(intPtr+1)=’ ‘ # 因為 指標類型為 int, 故移動一個位置為 4 byte, 所以指向第 0+4 =4 位置上的字元, 即字串的第五個字元 (從 0 開始).

Q2. 輸出為何

for(unsigned int i=10; i>=0; --i){ cout << i << endl; }

Ans. 無限迴圈，因為unsigned int為非負數

Q3. 指標考題

char s[]="0113256";
char *p=s;
printf("%c",*p++);
printf("%c",*(p++));
printf("%c",(*p)++);
printf("%c",*++p);
printf("%c",*(++p));
printf("%c",++*p);
printf("%c",++(*p));
printf("\n%s",s);

Ans.

char s[]="0113256";
char *p=s;
printf("%c",*p++); //先取值再把p指標位移
//印0值不變再指到s[1]
printf("%c",*(p++));//等同*p++
//印1值不變再指到s[2]
printf("%c",(*p)++);//先取值再把值+1
//印1值變2一樣指到s[2]
printf("%c",*++p); //p指標位移再取值
//指到s[3]後取值
printf("%c",*(++p));//等同*++p
//指到s[4]後取值
printf("%c",++*p); //*p的值+1後取值
//s[4]值+1後取值
printf("%c",++(*p));//同++*p
//再一次s[4]值+1後取值
printf("\n%s",s);//關鍵在於p和++碰在一起就是位移-> 0113234
-> 0123456

Q4. 陣列指標考題

int main(){
    int a[] ={1,2,3,4,5,6,7,9};
    int *ptr = (int*) (&a+1);
    printf("%d\n", &a);
    printf("%d\n", &a+1);
    printf("%d\n", ptr);
    printf("%d\n", *(ptr));
    printf("%d\n", ptr-1);
    printf("%d\n", *(ptr-1));
    printf("%d\n", ptr-2);
    printf("%d\n", *(ptr-2));
    printf("%d\n", *a);
    printf("%d\n", *a+7);
    printf("%d\n", *(a+7));
}

Ans.

int main(){
    int a[] ={1,2,3,4,5,6,7,9};
    int *ptr = (int*) (&a+1);
    printf("%d\n", &a);         //26410768
    printf("%d\n", &a+1);       //26410800 若以&a後面接+1會直接多個長度
    printf("%d\n", ptr);        //26410800
    printf("%d\n", *(ptr));     //0 -> the one next to a[]
    printf("%d\n", ptr-1);      //26410796
    printf("%d\n", *(ptr-1));   //9 -> a[8-1]
    printf("%d\n", ptr-2);      //26410792
    printf("%d\n", *(ptr-2));   //7 -> a[8-2]
    printf("%d\n", *a);         //1 -> a[0]
    printf("%d\n", *a+7);       //8 -> a[0]+7
    printf("%d\n", *(a+7));     //9 -> a[0+7]
}

Q5. 陣列指標型態考題

int arr[] = {10,20,30,40,50};
int *ptr1 = arr;
int *ptr2 = arr+5;
printf("%d\n", (ptr2-ptr1));               //5
printf("%d\n", (char*)ptr2 - (char*)ptr1); //20

Q6. 多重陣列考題

char *str[ ][2] =
  {"professor","Justin","teacher","Momor","student","Caterpillar"};char str2[3][10] = {"professor", "Justin", "etc"};printf("%s\n", str[1][1]); //Momor
printf("%c\n",str2[1][1]); //u

Q6–1. 多重陣列考題

int main()
{
    double data[3][5] = {{1,3,4,5,10},{7,8,9,10,11},{2,12,6,15,14}};    cout<<*(data+1)[1]<<endl;   // 2  = data[2][0]
    cout<<*((data+1)[1])<<endl; // 2  = data[2][0]
    cout<<(*(data+1))[1]<<endl; // 8  = data[1][1]return 0;
}

Q7. Union考題

union AA
{
  char a[2];
  int s;
};int main(){
  AA aa = { 0 };
  aa.a[0] = 12;
  aa.a[1] = 1;
  printf("%x\n", aa.s);           //10c
  printf("%d\n", sizeof(aa));     //4
  getchar();
  return 0;
}

Q7.1. Union考題

union StateMachine {
    char character;
    int number;
    char *str;     //32-bits: 4     64-bits: 8
};int main(void) {
    union StateMachine machine;
    machine.number = 1;    printf("sizeof: %lu\n", sizeof(machine));
    printf("number: %d\n", machine.number);
    return 0;
}

Q8. 巨集考題

#define XPROC(X) X*X
int main()
{
  int n = XPROC(2+3);
  cout << n << endl;             //2+3*2+3 = 11
}

Q9. Bit處理

unsign long v1 = 0x00001111;
unsign long v2 = 0x00001202;
unsign long v;
v = v1 & (~v2);    //我有你沒有的bit -> 0x00000111
v = v1 | v2;//v= 0x00001313

程式實作：

Q1. 在一個數值中計算幾個bit為1

while(x){
    x&=(x-1);
    cnt++;
}

Q2. 將一個數值的奇偶bit互換

x=(x&0xaaaaaaaa)>>1|(x&0x55555555)<<1;

Q3. 將一個字串reverse

void swap(char* a, char* b){
    if(a==b)return;
    *a^=*b;
    *b^=*a;
    *a^=*b;
}void reverseString(char* s, int sSize){    
    int i=0,j=sSize-1;
    while(i<j){
        swap(s+i,s+j);
        i++;j--;
    }
    return;
}

Q4. bit清除後三碼

x&=(~0)<<3;

Q5. Sorted Liked List

Insertion

struct Node{
 int val;
 struct Node* next;
}void insert(struct Node** head, int x){
    //node to be inserted
    struct Node* tmp=(struct Node*)malloc(sizeof(struct Node));
    tmp->val=x;
    tmp->next=NULL;
    //for initialize
    if(NULL==*head){
        *head=tmp;
        return;
    }
    //dummy for insert easily
    struct Node* dummy=(struct Node*)malloc(sizeof(struct Node));
    dummy->val=0;
    dummy->next=*head;
    //variable fast for traversal
    struct Node* fast=dummy;
    while(NULL!=fast&&NULL!=fast->next){
        if(x>fast->next->val){
            fast=fast->next;
        }
        else{
            tmp->next=fast->next;
            fast->next=tmp;
            *head=dummy->next;
            return;
        }
    }
    //if x is the maximum value
    fast->next=tmp;
    
    return;
}

Deletetion

struct Node{
 int val;
 struct Node* next;
}void delete(struct Node** head, int x){
    //dummy for insert easily
    struct Node* dummy=(struct Node*)malloc(sizeof(struct Node));
    dummy->val=0;
    dummy->next=*head;
    //variable fast for traversal
    struct Node* fast=dummy;
    while(NULL!=fast&&NULL!=fast->next){
        if(x==fast->next->val){
            fast=fast->next;
            struct Node* tmp=fast->next;
            fast->next-fast->next->next;
            free(tmp);
        }
    }
    
    return;
}

Q6. Quick Sort

void quickSort(int* nums, int head, int tail){
    if(head>=tail){return;}
    int comp=nums[head];
    int i=head,j=tail;
    while(i<j){
        while(nums[j]>=comp && i<j){j--;}
        nums[i]=nums[j];
        nums[j]=comp;
        while(nums[i]<=comp && i<j){i++;}
        nums[j]=nums[i];
        nums[i]=comp;
    }
    quickSort(nums,head,i-1);
    quickSort(nums,j+1,tail);
}int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize=numsSize;
    if(1>=numsSize){return nums;}
    
    int* tobe = (int*)malloc(numsSize*sizeof(int));
    memcpy(tobe,nums,numsSize*sizeof(int));
    
    quickSort(tobe,0,numsSize-1);
    
    return tobe;
}

Q7. Merge Sort

void Merge(std::vector<int> &Array, int front, int mid, int end){
  // 利用 std::vector 的constructor, 
  // 把array[front]~array[mid]放進 LeftSub[]
  // 把array[mid+1]~array[end]放進 RightSub[]
  std::vector<int> LeftSub(Array.begin()+front,Array.begin()+mid+1),
                  RightSub(Array.begin()+mid+1,Array.begin()+end+1);

  LeftSub.insert(LeftSub.end(), Max);
               // 在LeftSub[]尾端加入值為 Max 的元素
  RightSub.insert(RightSub.end(), Max);
               // 在RightSub[]尾端加入值為 Max 的元素

  int idxLeft = 0, idxRight = 0;
  for (int i = front; i <= end; i++) {
        if (LeftSub[idxLeft] <= RightSub[idxRight] ) {
            Array[i] = LeftSub[idxLeft];
            idxLeft++;
        }
        else{
            Array[i] = RightSub[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(std::vector<int> &array, int front, int end){
                                  // front與end為矩陣範圍
  if (front < end) {              // 表示目前的矩陣範圍是有效的
    int mid = (front+end)/2;      // mid即是將矩陣對半分的index
    MergeSort(array, front, mid); // 繼續divide矩陣的前半段subarray
    MergeSort(array, mid+1, end); // 繼續divide矩陣的後半段subarray
    Merge(array, front, mid, end);// 將兩個subarray做比較, 並合併出排序後的矩陣
  }
}

Q8. Permutation by Swap Function

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> re;
        _permu(nums,0,re);
        return re;
    }
    
private:
    void _permu(vector<int>& nums, int start, vector<vector<int>>& re){
        if(start>=nums.size()){
            re.push_back(nums);
            return;
        }
        
        for(int i=start;i<nums.size();i++){
            swap(nums[start],nums[i]);
            _permu(nums,start+1,re);
            swap(nums[start],nums[i]);
        }
    }
};

Q9. 尋找質數

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;
vector<int> myprime;

int prime[1001]; // value 0 means prime, 1 means multiple
int main(){
    for(int i=2; i<=sqrt(1000); i++){
        for(int j=i*i; j<=1000; j=j+i){
            prime[j] = 1;
        }
    }
    for(int i=2; i<=1000; i++){
        if(prime[i]==0){
            myprime.push_back(i);
            printf("%d ", i);
        }
    }
    return 0;
}

Q10. bitwise 比大小 [link]

int compare(uint32_t a, uint32_t b){
  uint32_t diff = a ^ b; //找到兩者間不一樣的bit裡面最左邊那個
  if (!diff) return 0;
  // 001xxxxx -> 00100000
  diff |= diff >> 1;
  diff |= diff >> 2;
  diff |= diff >> 4;
  diff |= diff >> 8;
  diff |= diff >> 16;
  diff ^= diff >> 1;  //最後針對這個最左邊不一樣的bit看看是a擁有還是b擁有
  return a & diff ? 1 : -1;
}

socket programming

read()跟recv()的差別？ [link]

ssize_t read(int sockfd, void *buf, size_t len);
ssize_t recv(int sockfd, void *buf, size_t len, int flags);sockfd - sd是socket的描述符，即是前個Example的sockfd。
buf - 一個緩衝區，讓Socket能把接收到的資料塞進裡頭。
len - 即是buf的大小。
flags - 相比最基本的read()，recv()的參數中多了這個旗標，flags代表接收的相關細節，通常是設定為0，也存在其他巨集處理一些特殊要求，比如blocking/nonblocking與超額接收等等，這部分細節可參見man-pages。

C/C++ 常見試題

Pointer

字串String反轉

Virtual Function & Pure Virtual Function

overload v.s. overwrite

Ｃ＋＋繼承、建構解構、虛擬順序

Q. 請說明 struct 和 class 的差別？

Q. 請說明在c++/c#中，你分別用何種方式處理race condition的問題?

Function pointer

使用時機

常見範例 [link_1]

結合typedef

sizeof

Explain “struct” “union” “enum”

malloc, calloc, memset, realloc[link]

volatile

lvalue vs rvalue [link]

static

記憶體配置

global:

stack:

heap:

.bss section [link_1]

Quick Sort

typedef

綜合考題

程式實作：

Q1. 在一個數值中計算幾個bit為1

Q2. 將一個數值的奇偶bit互換

Q3. 將一個字串reverse

Q4. bit清除後三碼

Q5. Sorted Liked List

Q6. Quick Sort

Q7. Merge Sort

Q8. Permutation by Swap Function

Q9. 尋找質數

Q10. bitwise 比大小 [link]

socket programming

Written by Yu-Pu Wu