Software軟體/韌體系統工程師《面試重點與考題》包含資料結構演算法,OS作業系統..等筆試考古題詳解! 使用程式語言C,C++,C#,JAVA

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

基本演算法

演算法:Algorithm
1.定義:由有限步驟所構成的集合,可以用於解決某一個特定的問題。
2.一個演算法應具備之五個特性(條件)
.輸入:由外界供給演算0或多個輸入資料。
.輸出:至少產生一個輸出。
.明確性:要很明白地知道所做的運算要如何處理。
.有限性:經過一些步驟後必需要執行終止,不會造成無窮迴路。
.有效性:即每一步驟皆能用紙筆完成。
3.影響程式執行時間因素:
.程式所輸入資料量多少有關(使用者)
.使用演算法(algorithm)所須時間的複雜度(程式)
.Compiler的產生機器碼是否最佳化(系統程式)
.指令在電腦中執行的速度(電腦硬體)

Complexity Analysis複雜度分析:

即將新增內容…

Greedy algorithms 貪婪演算法:

即將新增內容…

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開始。不過也因為這樣的演算法特性,原始版本無法是一定要取值的版本,必須做額外的處理。

40 thoughts on “Software軟體/韌體系統工程師《面試重點與考題》包含資料結構演算法,OS作業系統..等筆試考古題詳解! 使用程式語言C,C++,C#,JAVA

  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

    感謝各位支持, 已發送邀請函! (因版面有限,小編暫時不逐一一列出2個月以前的名單, 請見諒)
    2017/12 ~ 2018/01
    感謝dav***支持, 已發送邀請函!
    感謝yo****支持, 已發送邀請函!
    感謝ju****支持, 已發送邀請函!
    感謝ro****支持, 已發送邀請函!
    感謝a09***支持, 已發送邀請函!
    感謝she***支持, 已發送邀請函!
    感謝int***支持, 已發送邀請函!
    感謝s91***支持, 已發送邀請函!
    感謝mar***支持, 已發送邀請函!
    感謝bo*** 支持, 已發送邀請函!
    感謝meg***支持, 已發送邀請函!
    感謝qqq***支持, 已發送邀請函!
    感謝jia***支持, 已發送邀請函!

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

    1. 易春木 Post author

      謝謝提醒, 這部分中英的確造成困擾, 近期會修正, 非常感謝告知喔!若有其他問題歡迎留言告知. It is my pleasure to get your feedback.

      2017/12/27: 已更正囉!

    1. 易春木 Post author

      應該會先處理 Linux process的部分喔, 若擬真試題遇到卡關的問題, 歡迎來信提問或留言喔!

  6. 易春木 Post author

    引用心得推廣 by:

    HC 分享:
    整理面試題目:易春木題庫類 軟韌體工程師面試重點與考題

    mropengate 分享:
    易春木 – 軟體/韌體工程師面試重點與考題- C語言,資料結構,演算法,以及OS作業系統..等題目(筆試考題)

    zmcx16 分享:
    專業知識複習:軟韌體工程師面試- C語言與OS作業系統 常見題目(筆試考題)
    內容很豐富,因為資工的東西真的很多,裡面的內容可以幫你快速複習OS以及C語言相
    關。

    RTZU 分享:
    這個網頁整理了很多面試時會遇到的不管是筆試/面談常常會被問到的問題
    基本上很多考古題和計結資結OS演算法基本概念
    這邊都整理得十分清楚了
    推薦要去面試之前可以靠這邊的筆記惡補一下

發表迴響

Copy Protected by Chetan's WP-Copyprotect.