嵌入式面試中常見的一些編程題目

注：本文只是代碼實現，並沒有深入講解實現原理，大家可以看一下主要會考什麼，然後再具體針對性瞭解原理，也更有利於理解。

眼看26屆秋招接近尾聲，自己雖然很菜，但也在激烈的競爭中拿到了幾個 offer，已經非常滿意了，希望未來持續學習進步。

本文主要總結了嵌入式秋招中問的比較多的編程題目，總的來説，大部分不會涉及到複雜的算法題（我本身非科班，也沒怎麼刷題，秋招期間遇到手撕複雜算法的公司也是成功掛掉了），比較重要的是一些已有函數的實現，主要考察對數據在內存中分佈的掌握，對C語言在嵌入式場景中理解的深度，比如 memcpy() 函數，遇到 dest 和 src 空間重合的問題是怎麼處理的。其次就是各大排序，鏈表，字符串，數組的操作，二叉樹的概念，遍歷等等。

一、鏈表

鏈表的一些基礎操作

1. 鏈表定義

struct Node {
    int data;
    struct Node* next;
}

2. 創建節點

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode == NULL)
        printf("malloc failed!");
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

3. 頭插法插入節點

struct Node* insertAtHead(struct Node* head, int value) {
    struct Node* newNode = createNode(value);
    newNode->next = head;
    return newNode;  // 新的頭結點
}

4. 尾插法插入節點

struct Node* insertAtTail(struct Node* head, int value) {
    struct Node* newNode = createNode(value);
    if(head == NULL) 
        return newNode;
    struct Node* temp = head;
    while(temp->next != NULL) {
        temp = temp->text;
    }
    temp->next = newNode;
    return head;
}

5. 遍歷鏈表

void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

1. 實現鏈表的逆置

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return NULL;
    struct LiseNode* former;
    struct ListNode* latter;
    struct ListNode* mid = head;
    while (mid != NULL) {
        latter = mid->next;
        mid->next = former;
        former = mid;
        mid = latter;                        
    }
}

2. 判斷單鏈表中是否存在環

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    
    while(fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) {
            fast = head;
            while(fast != slow) {
                fast = fast->next;
                slow = slow->next;
        	}
            return slow;
        }
    }
    return NULL;
}

3. 單鏈表相交，如何求交點

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* p = headA;
    struct ListNode* q = headB;
    
    while(q != p) {
        if (p == NULL)
            p = headB;
        else
            p = p->next;
        if (q == NULL)
            q = headA;
        else
            q = q->next
    }
    return q;
}

4. 求有環鏈表第一個入環點

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    
    while(fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) {
            fast = head;
            while(fast != slow) {
                fast = fast->next;
                slow = slow->next;
        	}
            return slow;
        }
    }
    return NULL;
}

5. 寫出鏈表的刪除一個節點的程序

void deleteNode(Node** headRef, int key) {
    Node* temp = *headRef;
    Node* prev = NULL;
	if (temp == NULL) return;
    if (temp->data == key) {
        *headRef = temp->next; // 頭指針後移
        free(temp);            // 釋放原頭節點
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp); 
}

6. 用遞歸算法實現兩個有序鏈表的合併

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    if (pHead1 == NULL) return pHead2;
    if (pHead2 == NULL) return pHead1;
    
    if (pHead1->val > pHead2->val) {
        pHead2->next = Merge(pHead1, pHead2->next);
        return pHead2;
    } else {
        pHead1->next = Merge(pHead1->next, pHead2);
        return pHead1;
    }
}

二、二叉樹

滿二叉樹：除了最後一層，所有的節點都是滿的，並且所有節點都有兩個子節點

完全二叉樹：最後一層可以是單節點，所有節點連續幾種在左邊。

二叉搜索數：BST，左子樹中的所有節點值都小於該節點值。右子樹中的所有節點值都大於該節點值。

平衡二叉樹：AVL，左右子節點的高度不超過1的BST。

// 定義二叉樹節點結構
typedef struct Node {
    int data;               // 存儲節點的數據
    struct Node* left;      // 指向左子節點
    struct Node* right;     // 指向右子節點
} Node;

// 創建新節點
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("內存分配失敗！\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 銷燬二叉樹
void destroyTree(Node* root) {
    if (root == NULL) return;
    destroyTree(root->left);   // 遞歸釋放左子樹
    destroyTree(root->right);  // 遞歸釋放右子樹
    free(root);                // 釋放當前節點
}

// 二叉樹深度
int maxDepth(struct TreeNode* root){
    if (root == NULL) return 0;
    int lenLeft = maxDepth(root->left);
    int lenRight = maxDepth(root->right);
    return lenLeft > lenRight ? lenLeft + 1 : lenRight + 1;
}

1. 遍歷

// 中序遍歷：創建一個數組，數組作為傳入參數保存遍歷的結果
/**
 * returnNum: 保存遍歷出的元素
 * returnSize: 保存二叉樹的大小
 */
void inTra(struct TreeNode* root, int *returnNum, int* returnSize)
{
    if(root==NULL) return;
    inTra(root->left, returnNum, returnSize);
    returnNum[(*returnSize)++] = root->val;
    inTra(root->right, returnNum, returnSize);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int *returnNum = (int *)malloc(sizeof(int)*101);
    *returnSize = 0;
    if(root==NULL) return NULL;
    inTra(root,returnNum,returnSize);
    return returnNum;
}

不需要保存的遍歷：

// 前序遍歷：根 -> 左 -> 右
void preorderTraversal(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);  // 訪問根節點
    preorderTraversal(root->left);  // 遍歷左子樹
    preorderTraversal(root->right); // 遍歷右子樹
}

// 中序遍歷：左 -> 根 -> 右
void inorderTraversal(Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);   // 遍歷左子樹
    printf("%d ", root->data);     // 訪問根節點
    inorderTraversal(root->right);  // 遍歷右子樹
}


// 後序遍歷：左 -> 右 -> 根
void postorderTraversal(Node* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);  // 遍歷左子樹
    postorderTraversal(root->right); // 遍歷右子樹
    printf("%d ", root->data);      // 訪問根節點
}

2. 深度

int maxDepth(struct TreeNode* root) {
    // 遞歸結束條件
    if (root == NULL) return 0;

    int l_depth = maxDepth(root->left);
    int r_depth = maxDepth(root->right);

    return (l_depth > r_depth ? l_depth : r_depth) + 1;
}

3. 是否平衡二叉樹

bool isAVL(struct TreeNode* root)
{
	struct TreeNode* left  = root->left;
    struct TreeNode* right = root->right;
    
    int l_dep = maxDepth(left);
    int r_dep = maxDepth(right);
    
    if (l_dep == r_dep) return true;
    else if (l_dep > r_dep) return ((l_dep-r_dep) < 1 ? true : false);
    else return ((r_dep-l_dep) < 1 ? true : false);
}

三、排序查找算法及其改進

我想對於每一個經歷過秋招的小夥伴們來説，十大排序基本都被問過（快速排序、歸併排序、堆排序、冒泡排序、插入排序、選擇排序、希爾排序、桶排序、基數排序）。

1. 快速排序

void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int pivot = arr[right];
    int l = left - 1;
    int r = left;

    for (; r < right; ++r) {
        if (arr[r] < pivot) {
            l++;
            swap(arr[l], arr[r]);
        }
    }
	
    int povitIndex = l + 1;
    swap(arr[povitIndex], arr[right]);    
    quickSort(arr, left, povitIndex - 1);
    quickSort(arr, povitIndex + 1, right);
}

2. 冒泡排序

// 雙重循環，每次循環次數減1.長度為5的數組，第一次循環對比4次
void bubble_sort(int *arr, int n) {
    int flag;
    for (int i = 0; i < n-1; i++) {
        flag = 0;
        for (int j = 0; j < n-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                swap(&arr[j], &arr[j+1]);
                flag = 1;
            }
        }
        if (flag == 0) return;
    }
}

3. 歸併排序

/*
 * 歸併排序的思想：
 * 1. merge函數，傳入一個以m為界限的左右分別排序好的數組，然後把這個數組合並
 * 1.1 首先malloc兩個數組L，R然後填充，然後使用? :填充arr[k++]
 * 2. mergeSort函數遞歸執行，停止條件l>=r;
 */
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> L(arr.begin() + left, arr.begin() + left + n1); // 或 mid + 1
    vector<int> R(arr.begin() + mid + 1, arr.begin() + mid + 1 + n2); // 或 right + 1

    int i = 0, j = 0;
    int k = left;

    while (i < n1 && j < n2) arr[k++] = L[i] < R[j] ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left)/2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid+1, right);
    merge(arr, left, mid, right);
}

4. 堆排序

堆的數組表示：

對於數組中一個位置為i的節點（下標從0開始），

1. 父節點：(i-1)/2
2. 左子節點2i+1
3. 右子節點2i+2

最後一個非葉子節點的下標是n/2 - 1。n是數組長度。

最大堆：每個父節點大於子節點。

最小堆：每個子節點大於父節點。

構建最大堆，排序

/**
 * @brief 堆化函數
 * 
 * 這是堆排序的核心。它將以 i 為根的子樹調整為大頂堆。
 * 假設 i 的左右子樹已經是大頂堆。
 * 
 * @param arr  待排序的數組
 * @param n    數組的大小，也是堆中元素的總數
 * @param i    當前需要堆化的子樹的根節點索引
 */
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;    
    int left = 2 * i + 1; 
    int right = 2 * i + 2; 

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void maxHeap(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
}

void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    maxHeap(arr);
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

使用priority_heap容器適配器實現的堆排列

void heapSortUsingPriorityQueue(std::vector<int>& arr) {
    if (arr.empty()) {
        return;
    }

    // 1. 創建一個最大堆（默認行為）
    // 將數組中的所有元素放入優先隊列
    std::priority_queue<int> max_heap;
    for (int val : arr) {
        max_heap.push(val);
    }

    // 2. 依次取出最大元素，並存回原數組
    // 此時元素是按從大到小的順序被取出的
    int index = 0;
    while (!max_heap.empty()) {
        arr[index] = max_heap.top(); // 獲取最大值
        max_heap.pop();              // 從堆中移除
        index++;
    }

    // 3. 因為得到的是降序序列，需要反轉數組才能得到升序結果
    std::reverse(arr.begin(), arr.end());
}

5. 插入排序

// 從第二個數開始往前插入數，前面部分是排序好的，假如有n=5個數據，第一次插入a[1]，第4次插入a[4]。
// 所以外循環n-1次，從index=1開始。從j = i - 1依次向左比較，直到比較到最低位或者小於key的數。
// 兩個關鍵點，i是需要插入的索引key=arr[i]，i左邊也就是j=i-1是排序好的節點，然後向左比對，當arr[j]<key時，arr[j+1]=key。
void insertSort(vector<int>& arr) {
    for (int i = 0; i < arr.size(); ++i){
        // i=2插入到前面排序好的數組，跟前面的一一比較
        int key = arr[i];
        int j = i-1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

6. 選擇排序

// 選擇排序函數（升序）
// 遍歷數組，第一遍找出最小的放到第一個位置，第二遍從[1]開始，找出最小的，以此類推
void selectionSort(std::vector<int>& arr) {
    int n = arr.size();

    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }

        if (minIndex != i) swap(arr[i], arr[minIndex]);
    }
}

四、數組

二分查找法

int searchInsert(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left)/2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return left;
}

五、字符串

1. 字符串複製

void mucpy(char *s1, char *s2) {
    while(*s1++ = *s2++);
}

2. 字符串翻轉

//C++
std::reverse(s.begin(), s.end());

void swap(char* str, int start, int end) {
    char temp = 0;
    while (start <= end) {
        temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        end--;
        start++;
    }
}

void reverseStr(char* str, int n) {
    int start = 0;
    int end   = n - 1;

    swap(str, start, end);
}

3. 單詞翻轉

// 字符串反轉
// 1. 使用算法實現 #include <algorithm>
std::string s = "hello";
std::reverse(s.begin(), s.end());
// 2. 手動實現
while (left < right) {
    std::swap(s[left++], s[right--]);
}

// 單詞反轉
std::string reverseWords(std::string s) {
    // 1. 分裂單詞，存入字符串數組
    std::stringstream ss; ss.str(s);
    std::vector<std::string> words;
    std::string word;
    while (ss >> word) {
        words.push_back(word);
    }
    
    // 2. 反轉數組
    std::reverse(words.begin(), words.end());
    
    // 2. 合併單詞
    std::string result;
    for (int i = 0; i < words.size(); ++i) {
        if (i != 0) result += " ";
        result += words[i];
    }
    
    return result;
}

#include <stdio.h>
#include <string.h>
 
// 反轉字符串的某一部分 [start, end]
void reverse(char* s, int start, int end) {
    while (start < end) {
        char temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        start++;
        end--;
    }
}
 
// 反轉字符串中的單詞順序
void reverseWords(char* s) {
    int len = strlen(s);
    if (len <= 1) return;
 
    // 1. 反轉整個字符串
    reverse(s, 0, len - 1);
 
    // 2. 逐個反轉每個單詞
    int wordStart = 0;
    for (int i = 0; i <= len; i++) {
        if (s[i] == ' ' || s[i] == '\0') {
            reverse(s, wordStart, i - 1);
            wordStart = i + 1;
        }
    }
}
 
int main() {
    char str[] = "Hello world";
    printf("Original: \"%s\"\n", str);
 
    reverseWords(str);
    printf("Reversed: \"%s\"\n", str);
 
    return 0;
}

六、圖

圖的幾個概念：

節點（頂點，vertex），邊（edge），有向圖/無向圖（單向邊，雙向邊），帶權圖（邊帶有數值（權重），比如兩個城市之間的舉例，兩個任務之間的時間成本）

圖在算法中的經典應用：最短路徑問題，搜索問題（BFS，DFS）。

想象你在一個迷宮裏，要從起點走到終點，迷宮有很多岔路口，每個岔路口又有多個分支。你可以用兩種策略來探索迷宮：深度優先搜索（DFS）：一條路走到黑，選一條路一直走下去，直到走不通了，再返回上一個岔路口，換另一條路繼續，使用棧或者遞歸。廣度優先搜索（BFS）：層層推進，先走一步看看所有可能，再走第二步……像水波一樣一圈一圈擴散，用隊列實現，適合找最短路徑。

假設一個無向圖

0 -- 1 -- 3
|    |
2 -- 4

用鄰接表表示為：

0 -> 1, 2
1 -> 0, 3, 4
2 -> 0, 4
3 -> 1
4 -> 1, 2

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

// 圖的鄰接表表示
vector<vector<int>> graph = {
    {1, 2},     // 0
    {0, 3, 4},  // 1
    {0, 4},     // 2
    {1},        // 3
    {1, 2}      // 4
};

vector<bool> visited(5, false); // 記錄節點是否被訪問過

// 深度優先搜索（DFS）- 遞歸實現
void dfs(int node) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

// 深度優先搜索（DFS）- 非遞歸（棧）實現
void dfs_stack(int start) {
    fill(visited.begin(), visited.end(), false); // 重置訪問狀態
    stack<int> s;
    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int node = s.top();
        s.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                s.push(neighbor);
            }
        }
    }
}

// 廣度優先搜索（BFS）- 隊列實現
void bfs(int start) {
    fill(visited.begin(), visited.end(), false); // 重置訪問狀態
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    cout << "DFS (遞歸): ";
    dfs(0);
    cout << endl;

    cout << "DFS (棧): ";
    dfs_stack(0);
    cout << endl;

    cout << "BFS (隊列): ";
    bfs(0);
    cout << endl;

    return 0;
}

七、嵌入式常考的函數實現

1. memcpy

void* my_memcpy(const void* dest, const void* src, int n) {
    char* d = (char*)dest;
    char* s = (char*)src;
    
    // 判斷重疊，s在前從後往前拷貝，s在後從前往後拷貝
    if (s < d && s + n < d) {
        for (int i = n - 1; i >= 0; ++i) {
            d[i] = s[i];
        }
    } else {
        for (int i = 0; i < n; ++i) {
            d[i] = s[i];
        }
    }
    
    return dest;
}

2. strcpy

char *my_strcpy(char *dest, char *src) {
    if (dest == NULL || src == NULL) return NULL;
    char *ret = dest;
    while ((*dest++ = *src++) != '\0');
    return ret;
}

3. strncpy

#include <stddef.h>
char *my_strncpy(char *dest, char *src, size_t n) {
    if (dest == NULL || src == NULL) return NULL;
    
    char *ret = dest;
    while (n && (*dest++ = *src++) != '\0') n--;
    
    // n有剩餘
    if (n != 0) {
        while (n--) *dest++ = '\0';
    }
    
    return dest;
}

4. strlen

size_t my_strlen(const char *str) {
    if (str == NULL) return 0;
    size_t len = 0;    
    while (*str++ != '\0') len++;
    return len;
}

5. strcmp

int my_strcmp(const char *s1, const char *s2) {
    if (s1 == NULL || s2 == NULL) return -1;
    while (*s1 && (*s1 == *s2)) {
        s1++;
        s2++;
    }
    return *(unsigned char *)s1 - *(unsigned char *)s2;
}