C 語言面試筆記

規格

Explain lvalue and rvalue.

Ans

lvalue 在 C 中指的是 object type 和 incomplete type 的表示式，不包含 void。
在 C 裡面只有區分 lvalue 與 non-lvalue，沒有定義 rvalue。

C99 [6.3.2.1] An lvalue is an expression with an object type or an incomplete type other than void;

Object in C - 一種資料表示法，在執行期間資料儲存的區域，其內容可以用來表示數值。

C99 [3.14]：region of data storage in the execution environment, the contents of which can represent values

Incomplete type : 已宣告但未給予記憶體空間的 type ，因尚未有空間，故非 object type。
- example: struct example *ptr;、int a[]
型別可分為三， object type 、 function type 、 incomplete type 。

C99[6.2.5] Types are partitioned into object types (types that fully describe objects), function types (types that describe functions), and incomplete types (types that describe objects but lack information needed to determine their sizes).

練習：

int a = 10;
int *E = &a;
++(*E);  // a = a + 1
++(a++); // error

ref: [Note] 你所不知道的 C 語言：開發工具和規格標準篇
ref: 參考來源

Explain “struct” and “union” ?

Ans

struct 稱為結構體，可以包含數個不同資料型態的變數，所有變數佔用不同的內存。
union 稱為聯合體，也可以包涵不同資料型態的變數，但是所有變數佔用相同內存。

Alignment of struct
What is the difference between Declaration and Definition?

Ans

C11 [6.7] Declarations
Declaration
A declaration specifies the interpretation and attributes of a set of identifiers.
Definition
A definition of an identifier is a declaration for that identifier that:
for an object, causes storage to be reserved for that object;
for a function, includes the function body;
for an enumeration constant or typedef name, is the (only) declaration of the identifier.

對 variable 來說，declaration 僅是標示了 variable 的名稱和特性，definition 才會真正分配對應的儲存空間。
對 function 來說，definition 會包含 body { }，而 declaration 不會。
此外，相同 variable 可以多次 declaration，但是 definition 只能有一次。

ref: C extern keyword

inline

What is the difference between “Inline Function” and “Macro” ?

Ans

// Macro是在預處理時直接單純的文字替換，inline function是在compile階段時，直接取代function。
// 比較下面兩個例子：
// inline寫法：
inline int square(int x) {
    return x * x;
}
output: SQUARE(3 + 2) → (3 + 2) * (3 + 2) = 25
// Macro寫法：
#define SQUARE(x) (x * x)
output: SQUARE(3 + 2) → 3 + 2 * 3 + 2 = 11

Const

What is “const” ? and what is the meaning of:
1. const int a;
2. int const a;
3. const int *a;
4. int * const a;
5. int const * a const;

Ans

const 代表只可讀不可改。
1. 一個常數型整數
2. 同 1，一個常數型整數
3. 一個指向常數型整數的指標 (整型數不可修改，但指標可以)
4. 一個指向整數的常數型指標 (指標指向的整數可以修改，但指標不可修改)
5. 一個指向常數型整數的常數型指標 (指標指向的整數不可修改，同時指標也不可修改)

Volatile

什麼是 volatile?
- 一個參數既可以是const還可以是volatile嗎？解釋為什麼。
- 一個指針可以是volatile 嗎？解釋為什麼。
- 下面的函數有什麼錯誤：

int square(volatile int *ptr)
{
    return *ptr * *ptr;
}

Ans

volatile 用於提示編譯器某個變數會被意想不到的改變，如外部硬體或是其他的實行緒，因此不可對該變數進行優化，需要重新自記憶體存取該變數的值。

可以，因為 const 表示變數不可被程式更改，但 volatile 則是表示變數會被外部硬體更改，兩者並不衝突。
可以，因為當一個指標指向被宣告為 volitile 的變數時，該指標也需要為 volatile ，否則 compiler 會忘記該變數為 volatile 而進行優化。
ptr 指向的整數值可能會在執行時被外部硬體更改，導致 square 輸出的結果錯誤。

ref: Why is volatile needed in C?
ref: Why is a point-to-volatile pointer, like "volatile int * p", useful?

Static

C 中 static 關鍵字的作用

Ans

1. static 出現在變數前，且該變數宣告於函式中 (C/C++)：
局部變數加上 static 修飾後便不會因為離開可視範圍而消失。
2. static 出現在變數前，且該變數不是宣告於函式中(C/C++)：
讓變數只限定在該檔案內，而不是整個程式中（解決編譯時連結多個檔案造成相同變數名衝突）。
3. static 出現在類別的成員變數前 (C++ only)：
表示該變數不屬於某個類別實例，他屬於這個類別，所有以此類別生成出來的實例都共用這個變數。
4. static 出現在類別的成員函式之前 (C++ only)：
表示該函式不屬於某個類別實例，他屬於這個類別，所有以此類別生成出來的實例都共用這個函式（即便我們沒有產生實例出來，我們也隨時可以取用這個函式）（同 python 的 @static method）。

extern

What is extern?

Ans

extern 可放在變數或是函數前，提示編譯器該變數或是參數的定義在其他檔案。
ref: C extern keyword
ref: 面试挖坑题（6）之c语言extern

以下 extern 的使用方式正確嗎？
- 在一個 A.c 中定義 char a[6];
- 在另一個 B.c 宣告 extern char *a;

Ans

不正確，因為 B.c 中 extern char *a; 宣告的是一個 pointer to char，與 A.c 中實際定義的 char array 型態不同。

Pointer

Re-write void(*(*papf)[3])(char *);

typedef_______;
pf (*papf)[3];

Ans

papf is a pointer to array of "pointer to function return void"
papf is a pointer to array of "pf"
pf is a pointer to function return void
--> typedef void(*pf)(char *);

請問a陣列的每個值為何?

int a[5]={1,2,3,4,5};
int *p=a;
*(p++)+=123;
*(++p)+=123;

Ans

int a[5]={1,2,3,4,5};
int *p=a; // p is the pointer to the a[5]
*(p++)+=123; // -> *p += 123; p+=1;-> a[0] = 124; p = a + 1;
*(++p)+=123; // -> p+=1; !p+=123;-> a[2] = 126; p = a + 2;

用 C 語言表示：
- 一個整型數（An integer）
- 一個指向整型數的指標（A pointer to an integer）
- 一個指向指標的的指標，它指向的指標是指向一個整型數（A pointer to a pointer to an integer）
- 一個有10個整型數的陣列（An array of 10 integers）
- 一個有10個指標的陣列，該指標是指向一個整型數的（An array of 10 pointers to integers）
- 一個指向有10個整型數陣列的指標（A pointer to an array of 10 integers）
- 一個指向函數的指標，該函數有一個整型參數並返回一個整型數（A pointer to a function that takes an integer as an argument and returns an integer）
- 一個有10個指標的陣列，該指標指向一個函數，該函數有一個整型參數並返回一個整型數（ An array of ten pointers to functions that take an integer argument and return an integer ）

Ans

int a;//1
int *a;//2
int **a;//3
int a[10];//4
int* a[10];//5
int a[10];//
int *b = a;//6
int (*func)(int);//7
int (*func[10])(int);//8

int a[10]; int *b[10]; int (*c)[10];分別代表什麼意思？
- 承上，a++, b++, c++ 那些會造成編譯錯誤？

Ans

int a[10]; // an array of 10 integers
int *b[10]; // an array of 10 pointers to integer
int (*c)[10]; // a pointer to an array of 10 integers

a++, b++ 會發生錯誤，因為 a 與 b 為陣列的開頭位置，不可被更改。

Bitwise Operation

write a code
- set the specific bit
- clear the specific bit
- inverse the specific bit (0->1; 1->0)

Ans

#define SET(num, i) num |= 1<<i
#define CLEAR(num, i) num &= ~(1<<i)
#define INVERSE(num, i) num ^= 1<<i

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

Ans

int check(int n) {
    while(n > 0) {
        n -= 3;
    }
    if (n == 0) return 1;
    else return 0;
}

Implement swap with bit operations.

Ans

void swap(int *a, int *b) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

reverse a string.

Ans

void swap(char *a, char *b) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}
void reverse(char s[]) {
    int n = strlen(s);
    for (int i = 0; i < n/2; i++) {
        swap(&s[i], &s[n-i-1]);
    }
}

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

Ans

int define2N(int n){
    return (!(n&n-1) && n!=0)
}
// Ex. n = 11000 n-1 = 10111 n&n-1 > 0

Write a GCD function.

Ans

int gcd(int x, int y) {
    int max, min, mod;
    max = x > y ? x : y;
    min = x < y ? x : y;
    do {
        mod = max%min;
        max = min;
        min = mod;
    }while (mod);
    return max;
}

w/o mod()

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
//  若 u 跟 v 都是偶數，則：gcd(u,v)=2×gcd(u/2,v/2)
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
// 若 u 為偶數，v 為奇數，則：gcd(u, v) = gcd(u/2, v)
    while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;
//         gcd(u, v) = gcd(u-v, v)
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

What is the v's value?

unsigned long v1 = 0x 00001111;
unsigned long v2 = 0x 00001202;
unsigned long v;
v = v1&(~v2);
v = v | v2;

用 bitwise operation 實做一個加法器

Ans

void adder(int a, int b, int c) {
    int sum = a ^ b ^ c;
    int carry = 
}

ref: 以 C 語言實作二進位加法 (Binary Addition)

Preprocessor

用預處理指令#define 聲明一個常數，用以表明1年中有多少秒（忽略閏年問題）

Ans

#define SEC_IN_A_YEAR (1 * 365 * 24 * 60 * 60UL)

Note:

#define SEC_IN_A_YEAR (1 * 365 * 24 * 60 * 60)UL 編譯器會報錯，因為根據 C99[6.4.4] 十進位的 integer constant 是由 decimal-constant integer-suffix 所組成的。也就是說，UL 前面需要加上 decimal- conatant。
#define SEC_IN_A_YEAR (1 * 365 * 24 * 60 * 60UL) 中， UL 會先跟 60 結合，並根據 C 語言的算術提升規則，算術後的結果也會是 unsigned long。
在嵌入式系統 16-bit 的環境中，用 int 表示 SEC_IN_A_YEAR 會導致 overflow，因此需要加上 UL。
ref:https://www.796t.com/content/1543929544.html

寫一個“標準”巨集MIN ，這個巨集輸入兩個參數並返回較小的一個。
Write a MARCO to calculate the square of integer a.

Programming

Write a code to reverse the linked list. For example: [0] -> [n], [1]->[n-1],…[n]->[0].

Ans

void helper(List *head, List **tmp) {
    if (!head) return;
    helper(head->next, tmp);
    (*tmp)->next = head;
    *tmp = (*tmp)->next;
}
List *reverse(List *head) {
    List* dummy = (List *)malloc(sizeof(List));
    List *tmp = dummy;
    helper(head, &tmp);
    List *rets = dummy->next;
    free(dummy);
    return rets;
}

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *cur = head, *pre = NULL, *next = NULL;
    while(cur){
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    
    return pre;
}

Write a function to find the middle field of singled-linked list without traverse whole list.
What is the output?

Ans

#include <stdio.h>

int c;

int func(int m, int* n){
    c += 1;
    m += c;
    *n += m;
    return m;
}

int main(void) {
	c = 0;
	int x = 5;
	int y = 7;
	int z;
	x = func(x, &y);
	z = func(x, &y);
	printf("sum of x, y, z, and c = %d", x + y + z + c); // 37
	return 0;
}

保證 n 一定是上面五個數字之一，且不能用if 和 switch case , 請用你認為最快的方法實作main。

extern void func1(void);
extern void func2(void);
extern void func3(void);
extern void func4(void);
extern void func5(void);

void main(int n)
{
  if n==1 execute func1;
  if n==2 execute func2;
  if n==3 execute func3;
  if n==4 execute func4;
  if n==5 execute func5;
}

寫一個 function 可傳入正整數參數 N，回傳 1 + 2 + 3 +…+N 的和

Find the possible error

Int ival;
Int **p;
Ival = *p;

What is the output?

#include <stdio.h>

int main(void) {
	char *str[] = {
	    {"MediaTekOnlineTesting"},
	    {"WelcomeToHere"},
	    {"Hello"},
	    {"EverydayGenius"},
	    {"HopeEverythingGood"}
	};
	char* m = str[4] + 4;
	char* n = str[1];
	char* p = *(str+2) + 4;
	printf("1. %s\n", *(str+1));
	printf("2. %s\n", (str[3]+8));
	printf("3. %c\n", *m);
	printf("4. %c\n", *(n+3));
	printf("5. %c\n", *p + 1);
	// 1. WelcomeToHere
	// 2. Genius
	// 3. E
	// 4. c
	// 5. p
	return 0;
}

What is the output?


#include <stdio.h>
#define VAR 6

int func(int a){
    int m = 3;
#undefined VAR
#define VAR 10
    m = 4;
#endif
    return m + VAR;
}

int main(void) {
	int i=5;
	printf("%d\n", func(i));
	return 0;
}

計算自訂型態的記憶體大小（不可使用sizeof，也不可有自訂型態變數或其指標)

Ans

T t1[2];
T *p1 = &t1[0];
T *p2 = &t1[1];
printf("size of T: %d byte", (int)p2 - (int)p1);

以單字為單位反轉字串，例如：He is a boy 變成 boy a is He。
給定一個正整數列進行排列，奇數在前偶數在後，奇數由小到大，偶數由大到小。
Write functions isUpper() and toUpper()

bit field

What is the output?

#include <stdbool.h>
#include <stdio.h>
bool is_one(int i) { return i == 1; }
int main() {
    struct { signed int a : 1; } obj = { .a = 1 };
    puts(is_one(obj.a) ? "one" : "not one");
    return 0;
}

Ans

在 struct {int a : 1; } obj = {.a = 1 }; 的地方，原本 int 這個資料型態需要 4 bytes 的空間，即 32 個位元，我們透過 bit field 指定只用其中一個 bit 來存放數值。
但因 a 是 signed integer，依據二補數系統，1 bit 的範圍內只能表示 -1 和 0，於是程式輸出為 not one。
ref: bit-field

OS 相關

Explain “thread” and “process”, and what is the difference ?
What is stack and heap when talking about memory ?
little-endian and big-endian 判斷

Ans

typedef union {
  unsigned long l;
  unsigned char c[4];
} EndianTest;

int main() {
  EndianTest et;
  et.l = 0x12345678;
  printf("本系統位元組順序為：");
  if (et.c[0] == 0x78 && et.c[1] == 0x56 && et.c[2] == 0x34 && et.c[3] == 0x12) {
    printf("Little Endiann\n");
  } else if (et.c[0] == 0x12 && et.c[1] == 0x34 && et.c[2] == 0x56 && et.c[3] == 0x78) {
    printf("Big Endiann\n");
  } else {
    printf("Unknown Endiann\n");
  }
  printf("0x%lX 在記憶體中的儲存順序：\n", et.l);
  for (int i = 0; i < 4; i++) {
    printf("%p : 0x%02X\n", &et.c[i], et.c[i]);
  }
  return 0;
}

semaphore 和 mutex 的差異

Mutex, Semaphore, the difference, and Linux kernel

Consider the following hardware configuration . virtual address=32bit, page size=4kbytes, and a page table entry occupies 4 bytes. how many pages should the os allocate for the pages tables of a 12mbyte process under the following paging mechanisms?

ref: 發哥(聯發科)上機考題目整理
ref: 聯發科 C語言測試題目
ref: 面試 C/C++ 觀念整理