大神面試紀錄 Hardware Interview

1. 序
2. 面試題目
1. 2.1. 結論

序

本篇文章記錄身邊大神去面試時所遇到的神祕問題，對於現在大三的我只能旁觀，雖然在計算機組織這一類的硬體課程修完不久，但是看到這些問題，還真的不知所措。

面試的時候，可以帶上會協助您的小夥伴們一起面試，這一點相當地奇特，面試不再是單打獨鬥。當然，小夥伴有事也沒有關係，將可以使用線上 call out。

也是這些原因，才有機會參與這些問題的討論。

面試題目

以下附錄僅為討論，不代表正確答案。

面試採用漸進式，由高階至低階開始追問，同時也會問到 Hardware Algorithm。

用 C/C++ 寫一個九九乘法表

這邊就不多加以描述，通常採用兩層迴圈的寫法和一個 printf

1
2
3

for(int i = 1; i <= 9; i++)
    for(int j = 1; j <= 9; j++)
        printf("%d x %d = %d\n", i, j, i * j);

printf(format, arg) 怎麼實作的？

請準備 stdio.h 開始查閱，不過當下要想出來還真的挺難的，不過在 linux 下，stdin, stderr, stdout 都是一個檔案形式，這是在呼叫 printf後會去導入的目標所在。但如何解決 arg，要查閱一下 va_start 怎麼運作的，若上網搜尋得到。

printflink

#include <libioP.h>
#include <stdarg.h>
#include <stdio.h>
#undef printf
/* Write formatted output to stdout from the format string FORMAT.  */
/* VARARGS1 */
int
__printf (const char *format, ...)
{
  va_list arg;
  int done;
  va_start (arg, format);
  done = vfprintf (stdout, format, arg);
  va_end (arg);
  return done;
}
#undef _IO_printf
ldbl_strong_alias (__printf, printf);
/* This is for libg++.  */
ldbl_strong_alias (__printf, _IO_printf);

多變數到底是如何在這裡實作的，這一點要去考量 va_start，他會將參數位置丟入 va_list arg 中，但是如果參數個數或者是型態不符合 format，則運行的時候指針會指到錯誤的地方而噴出 RE，嘗試所及就到這裡了。

CPU 怎麼實作這些？

CPU 的 pipeline 的五個階段和實作，IF, ID, EX, MEM, WB
擷取指令、指定解析、執行運算、寫入記憶體、寫回暫存器。
然後如何 pipeline，如果有類型的不同的時候，pipeline 會猜測到底要不要 branch，如果真的要 branch，要將 branch 之後的指令清掉 … 計組忘得一乾二淨。

實作一個 n bits 加法器 adder，在平行的情況下，最多能多快。

一般而言，要在 n 個 clock 後才能得到，這麼做就太慢了，之前上課有提到 carry lookahead adder, carry saved adder, … 等，這些雖然能在比一般時間更快得到是否要進位，但問題是要怎麼知道加完之後的結果！

所以通常是切塊，然後賭前一塊到底會不會進位過來，把兩個答案都先算出，最後再利用 selector 去選擇正確的那個結果。

如果單純是要得到是否會 overflow，最快可以在 O(log n) 時間內得到，採用分治的方式去考慮進位問題。

分治算法看起來很接近線段樹的做法，藉由上一步，把兩種可能的答案都先算出，我們已經在 O(log n) 時間內把線段樹建出，接著對每一個元素做前綴的區間查詢，全部并行可以在 O(log n) 時間內完成，然後調用 selector 決定我們的答案。

太多平行，平行處理的效能分析和處理資料的優先順序，很少在 ACM 使用，只好在此刻 yy 了。
給很多區間 [l, r]，接著詢問某個點 x 被多少區間覆蓋。

線段樹處理，搭配區間的懶操作，直接對區間 [l, r] 所有元素 + 1 即可，在 O(n log n) 時間內建表，然後單點查詢 A[x] 的值為何，這種做法可以動態支持。
給一般圖進行匹配，假設不使用標準的帶花樹算法，使用自己的算法，請問誤差為多少。

貪婪策略：
每次對一個鄰居最少的點，找到其鄰居 (他的鄰居也最少) 進行匹配，然後把這些點都拿掉，繼續遞迴匹配。

至於誤差－只能想辦法找到一個反例，來確定誤差一定大於某個值，要詳細證明什麼的，大概可以順便報一篇論文了。

一群人在思考反例，想了很久都沒有結果，最後由天祥大神找到一個誤差有 20% 的反例，詳細如上圖所述，如果一開始拿到 AD 或者是 HI，則會把匹配數最多拿到 4 個，事實上為 5 個。

結論

相當可怕，學得都忘得一乾二淨，無法精準回答。

Morris' Blog

大神面試紀錄 Hardware Interview

contents

序

面試題目

結論