軟體/韌體工程師面試重點與考題- 程式語言(C/C++/C#/JAVA),資料結構,演算法,以及OS作業系統..等題目(筆試考題)

目錄:
面試須知與應答技巧
資料結構 / 變數儲存與記憶體
關於多處理序(Process)與多執行緒(multi-thread) 在Linux / Windows
基本演算法
轉自ptt: [重要] 發文前務必閱讀:C/C++常見問題十三誡
擬真試題1/擬真試題2/擬真試題3/擬真試題4
直接列出考古題1(精華完整48題含解答)
直接列出考古題2(精華完整34題含解答)
深度討論考古題1(DEMO完整10題含解答) 選擇使用C,C++,C#或JAVA
深度討論考古題2(DEMO完整10題含解答) 選擇使用C,C++,C#或JAVA

基本演算法

Divide and conquer作法:

將問題先切分成小問題後再解決,再將結果合併求出原始問題的答案。
優點:
– 將困難的問題簡化為容易實作的方式,例如河內塔(Tower of Hanoii)問題。
– 提升程式效率,例如歸併排序(Merge Sort)讓排序速度提升。
– 能夠平行處理,例如MapReduce也是Divide and conquer的一種。
不適合的情況:
– Divide and conquer是利用遞迴的方式來實作,所以當不適合使用遞迴的時候也就不適合使用Divide and conquer

-> 二元搜索法(Binary Search):

又稱折半搜索,搜索演算法的一種,可使用Divide and Conquer或直接使用迴圈來實作,搜索的目標資料必須是已經排序過的(以小到大排序為例)。其概念是每次挑選中間位置的資料來比對,若該資料小於目標值,則縮小範圍為左半部,反之亦然;因此使用這個方法每次比對後都可以濾掉一半的資料,以增快搜索速度。

Divide and Conquer方法:

Dynamic Programming

中文譯作動態規劃,動態規劃類似Divide and Conquer,一個問題的答案來相依於子問題,常用來解決最佳解的問題。與Divide and Conquer不同的地方在於,動態規劃多使用了memoization的機制,將處理過的子問題答案記錄下來,避免重複計算,因此在子問題重疊的時候應該使用動態規劃;Divide and Conquer通常使用遞迴(Top-Down)來處理,轉成迭代法(Bottom-up)來解並不容易,故使用動態規劃則可以解決重覆計算並保留遞迴思考的優點。

費波那西數列(Fibonacci)

費波那西數列(Fibonacci),又稱費氏數列、黃金分割數列等很多譯名,由西方的數學家費波那西使用兔子問題來描述這個數列
使用數學式來表達的話如下:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

使用Divide and Conquer的寫法如下: O(2^n)
每次都必須recusive計算出數值

動態規劃寫法如下: O(n)
透過array方式將計算過的數值儲存起來, 避免重複計算!

最大子序列(Maximum Subarray)

最大子序列(Maximum Subarray或稱作Maximum Subsequence)為在一個具有正負數陣列當中,找出一段連續的元素總和最大,這個問題又分為一定要取值或可不取。實作方法有很多種,這裡說明四種實作方法,分別為暴力法、改良式暴力法、Divide and Conquer和Kadane’s演算法(Dynamic Programming),其中Kadane’s實作取值和可不取值兩種版本,其他為一定要取值版本。 (參考)


暴力法 O(n^3)
最簡單直覺的想就是將所有可能的開始和結束範圍都算過一遍即可,[0] ~ [0]、[0] ~ [1] … [0] ~ [N] … [N] ~ [N]的總和找出最大。

改良式暴力法 O(n^2)
然而在上面暴力法計算,[0] ~ [N]的總和時,其實過程中[0] ~ [0]、[0] ~ [1] … [0] ~ [N]的總和也已經同時計算了,所以只需計算[0] ~ [N]、[1] ~ [N] … [N] ~ [N]即可。

Divide and Conquer O(nlog n)
如下圖所示,Divide and Conquer的基本概念是,將數列分成兩塊,各自回報最大的值,如藍色部分;然而這是最大子序列不只會出現在左邊或右邊,也有可能出現橫跨兩邊的紅色區域,所以還要再找出紅色區域的最大值。由於紅色區域表示的是橫跨兩邊,所以只要考慮包含中點的情況,如圖紅色元素與綠色區域,最後最大子序列的值即為紅色區域或藍色區域的最大值。

Kadane’s演算法 O(n)
Kadane’s演算法為Dynamic Programming(動態規劃)方式,概念上其實是很直覺的思考,如下圖所示,當計算前四個元素的時候,前面總和是1、3和6,很明顯列入計算是有幫助的,故我們會納入計算,但是到了第五個元素的時候,前面總和變成-1,若列入計算會拉低分數,故我們不列入計算;由以上簡單的範例可知,當連續總和是正的時候,可以繼續列入計算,當為負的時候,則不列入計算,也就是重新重0開始。不過也因為這樣的演算法特性,原始版本無法是一定要取值的版本,必須做額外的處理。

34 thoughts on “軟體/韌體工程師面試重點與考題- 程式語言(C/C++/C#/JAVA),資料結構,演算法,以及OS作業系統..等題目(筆試考題)

  1. 昭哥

    發現一個小bug
    7.write a function that can calculate 1*2+2*3+…..+(n-1)*n
    int nc(int n)
    {
    int sum = 0;
    for(int i = 2; i <= n; i++){
    sum = sum + n*(n-1); <= 這裡錯了 是 sum = sum + i*(i-1); 才對
    }
    return sum;
    }

  2. R.C.

    板主您好,對於這題的解答請問是否應修正為以下這樣,如有錯誤,請不吝賜教:

    1.2 32-bit machine用C語言對位址 0x00005000 的第三個bit設成0,第五個bit設成1。
    #define BIT3 (0x0004)
    #define BIT5 (0x0010)

    unsigned int a=0x00005000;
    void clear_bit3(void) { a &= ~BIT3;}
    void set_bit5(void) { a |= BIT5;}

  3. 1

    在第三題時做strcmp函式那題中,如果兩個參數char a[] 和 b[] 是使用如下宣告: char a[4] = “1234”,這樣的話就不一定會有’\0’在array的最後面,請問這樣的話該如何處理?

    1. 易春木 Post author

      本題是要比較字串, 所以基本上字串結尾必須要有一個「\0」字元作為結尾
      如果不是字串的話, 則不適用strcmp

      若要比較array不是比較字串的話, 也就是說沒有「\0」字元作為結尾
      改寫為

      但其實已經偏離題目的基本設定, 共勉之

  4. Pingback: 工作面試心得(QNAP、緯穎、正文、 工研院、啟碁、全景、智易、CHTTL) – Cinnating

  5. 易春木 Post author

    感謝Cha****支持, 已發送邀請函!
    感謝Ron****支持, 已發送邀請函!
    感謝Eri****支持, 已發送邀請函!
    感謝Sym****支持, 已發送邀請函!
    感謝But****支持, 已發送邀請函!
    感謝1qa****支持, 已發送邀請函!
    感謝Chl*** 支持, 已發送邀請函!
    感謝P51****支持, 已發送邀請函!
    感謝Vin****支持, 已發送邀請函!
    感謝Chu** 支持, 已發送邀請函!
    感謝Dcp*** 支持, 已發送邀請函!
    感謝Pet** 支持, 已發送邀請函!
    感謝Lbj****支持, 已發送邀請函!
    感謝Fre** 支持, 已發送邀請函!
    感謝Pai.** 支持, 已發送邀請函!
    感謝Can** 支持, 已發送邀請函!
    感謝Car****支持, 已發送邀請函!
    感謝Lin****支持, 已發送邀請函!
    感謝Cy6****支持, 已發送邀請函!
    感謝Mrd****支持, 已發送邀請函!
    感謝Jim****支持, 已發送邀請函!
    感謝11*****支持, 已發送邀請函!
    感謝lin****支持, 已發送邀請函!
    感謝leb****支持, 已發送邀請函!
    感謝siu****支持, 已發送邀請函!
    感謝kek****支持, 已發送邀請函!
    感謝all****支持, 已發送邀請函!
    感謝j_a****支持, 已發送邀請函!
    感謝tiz****支持, 已發送邀請函!
    感謝w7****支持, 已發送邀請函!
    感謝rs****支持, 已發送邀請函!

    謝謝熱烈支持, 小編會持續加入更多程式設計的面試重點!
    任何問題或考題都歡迎討論研究, 祝大家求職順利!!

發表迴響

Copy Protected by Chetan's WP-Copyprotect.