2014年2月19日 星期三

面試 Interview 考題 test part 1

1.

物件導向的三大特性

  1. 封裝
    將程式碼包裝成為Class以提供特定功能的一種過程。好處:程式碼共用
  2. 繼承
    Class可透過Inheritance(繼承)來擴充(或修改)內容。
  3. 多型
    在執行階段,定義可供用戶端程式碼交換使用,具有不同功能名稱完全相同之方法或屬性的Class。


2.

Overload和Override的區別。Overloaded的方法是否可以改變 
返回值的類型? 

Overload發生在同一類別裡,Override發生在繼承關係間。 
Overload為靜態連結,Override為動態連結。 
可改變返回值的型態,前提是參數也要變,參數相同傳回值不同是
不被允
許的。 

3.

write your own strcmp
int ownstrcmp(char a[], char b[])
{
   int i = 0;

   while( a[i] == b[i] )  
   {

      if( a[i] == '\0' ) 
        return 0;
      ++i;
   }

   return  ( a[i] < b[i]) ? 1 : -1;
}

4.

what is different between mutex and semaphore?

Mutex是一把鑰匙,一個人拿了就可進入一個房間,出來的時候把鑰匙交給隊列的第一個。一般的用法是用於串行化對critical section代碼的訪問,保證這段代碼不會被並行的運行。
(A mutex is really a semaphore with value 1.)

Semaphore是一件可以容納N人的房間,如果人不滿就可以進去,如果人滿了,就要等待有人出來。對於N=1的情況,稱為binary semaphore。一般的用法是,用於限制對於某一資源的同時訪問。

5.

Compare array and list

std::array is just a class version of the classic C array. That means its size is fixed at compile time and it will be allocated as a single chunk (e.g. taking space on the stack). The advantage it has is slightly better performance because there is no indirection between the object and the arrayed data.
std::vector is a small class containing pointers into the heap. (So when you allocate astd::vector, it always calls new.) They are slightly slower to access because those pointers have to be chased to get to the arrayed data... But in exchange for that, they can be resized and they only take a trivial amount of stack space no matter how large they are.

6.

Compare stack and queue

佇列(Queue)是用先進先出的方式處理物件的集合,例如到銀行排隊,先排的人先處理;
堆疊(Stack )後進先出的集合,例如玩撲克牌排遊戲時,發牌時是從整疊的最上一張拿取。

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);
}
return sum;
}

8. 

Explain Static and volatile


Static:

(1) 修飾檔案中的global variable:

使這個變數只有在本檔案中才可以被使用,相同專案中的其他檔案看不到它的存在。

補:放在function前也有一樣的作用。

(2) 修飾function中的local variable:

此變數一旦經過初始化就會一直存在直到程式結束,跳出function時它也會保持當下的值,

ex. 可用來計算同一個function被呼叫的次數。

只會被初始化一次,並且只有進入function中才看得到這個變數 !!

(3) 修飾class中的member variable和function:

variable:會使同一個class的所有實體共用同一個member variable,

或者說這個member variable在同一個class的所有實體擁有相同的值。

一樣只會初始化一次,甚至不需要實體就可呼叫。

function:static member function不屬於任何一個實體,也是不需要實體就可呼叫,

但它只能操作static member variables而已。

他們都透過 :: 運算子來呼叫,表示屬於某一個class但不屬於任何實體。 ex. A::x

也可以透過實體用 . 運算子呼叫,但觀念上比較不好!


Volatile:

被volatile修飾的變數代表它的值有可能因為編譯器不知道的因素修改,

所以告訴編譯器不要對它涉及的地方做最佳化,

並在每次操作它的時候都去讀取該變數實體位址上最新的值,

而不是讀取CPU暫存器上的值,

一般的變數可能因為剛剛讀取過而放在CPU暫存器上使動作變快。

例子:

(1) 硬體暫存器,如狀態暫存器。

(2) 多執行緒所共用的全域變數。

(3) 中斷服務函式 (Interrupt Service Rountie,ISR)所使用的全域變數。

囧~ 我只能了解多執行緒的情況,其他兩個例子都沒概念。

陷阱:

假設有個函數

int square(volatile int *ptr) {

return *ptr * *ptr;

}

則編譯器可能會把它解讀成下列code

int square(volatile int *ptr) {

int a,b;

a = *ptr;

b = *ptr;

return a * b;

}

實際上產生的可能不是平方值,所以改成下列方式才不會出錯

int square(volatile int *ptr) {

int a;

a = *ptr;

return a * a;

}


C/C++ 的volatile
C/C++中的volatile使用時機?

.不知各位對volatile(揮發性的)這個字陌不陌生? 我相信大家在一些程式或多或少都看
過這個字眼, 但是究竟要在何種場合用它呢?
.當然一定是有需要, C/C++才會有這個保留字, 否則只是增加programmer的困擾而已
.有2兩個場合(I/O & multithread program), 供各位參考!
.請大家check自己的程式中(尤其是第2個場合), 若有的話請記得加上volatile

1. I/O, 假設有一程式片斷如下

U8 *pPort;
U8 i, j, k;

pPort = (U8 *)0x800000;

i = *pPort;
j = *pPort;
k = *pPort;

以上的i, j, k很有可能被compiler最佳化而導致產生
i = j = k = *pPort;
的code, 也就是說只從pPort讀取一次, 而產生 i = j = k 的結果, 但是原本的程式的目
的是要從同一個I/O port讀取3次的值給不同的變數, i, j, k的值很可能不同(例如從此
I/O port 讀取溫度), 因此i = j = k的結果不是我們所要的

怎麼辦 => 用volatile, 將
U8 *pPort;
改為
volatile U8 *pPort;

告訴compiler, pPort變數具有揮發性的特性, 所以與它有關的程式碼請不要作最佳化動作. 因而
i = *pPort;
j = *pPort;
k = *pPort;
此三列程式所產生的code, 會真正地從pPort讀取三次, 從而產生正確的結果

2. Global variables in Multithread program
=> 這是在撰寫multithread program時最容易被忽略的一部份
=> 此原因所造成的bug通常相當難解決(因為不穩定)

假設有以下程式片斷, thread 1 & thread 2共用一個global var: gData
thread 1: thread 2:

... ....
int gData; extern int gData;

while (1) int i, j, k;
{
.... for (i = 0; i < 1000; i++)
gData = rand(); {
..... /* A */
} j = gData;
....
.... }

在thread 2的for loop中, 聰明的compiler看到gData的值, 每次都重新從memory load到register,
實在沒效率, 因此會產生如下的code(注意,tmp也可以更進一步的用register取代):
tmp = gData;
for (i = 0; i < 1000; i++
{
/* A */
j = tmp;
....
}
也就是gData只讀取一次, 這下子問題來了, 說明如下:
.thread 2在執行for loop到j = gData的前一列(A)的時候(假設此時gData=tmp=5), 被切換到thread 1執行
.在thread 1的while loop中透過gData = rand(), 對gData做了修改(假設改為1), 再切換回thread 2執行
.繼續執行 j = gData, 產生j = 5的結果
.但是正確的結果應該是 j = 1
怎麼辦 => 也是用volatile,

在thread 1中, 將
int gData;
改為
volatile int gData;

在thread 2中, 將
extern int gData;
改為
extern volatile int gData;


9.


Explain process and thread

Program:放在二次儲存裝置中,尚沒有被Load到記憶體的一堆Code
         稱之為「程式」。  (也就是還是死的)

Process:已經被Load到記憶體中,任何一行Code隨時會被CPU執行,且其宣告的在記憶體
         的變數的值會隨著需求而不斷變動。
         稱之為「程序」。 (也就是活的Program) => 恐龍本第三章
         一個多工作業系統(Multitasking Operating System)可以同時運行多個Process
         然而一個CPU一次只能做一件事情,但CPU的數量永遠少於運行中的Process數,
         因此每個Process使用的時間需要被排程(Scheduling) => 恐龍本第五章
         又每個Process間在記憶體中,如果擺放的方式不當,就會在記憶體中產生很多
         沒辦法用到的碎片,因此MemoryManagement是一個問題 => 恐龍本第八章
         另外,每個Process所需要的記憶體總合,也可能大於實體記憶體,因此需要另
         外用二次儲存裝置充當虛擬記憶體(Virtual Memory),但是二次儲存裝置的速
         度肯定很慢,因此如何做到對虛擬記憶體最小的依賴,盡量避免Page Fault(電
         腦在主記憶體中找不到資料,而要去二次記憶體找,就稱為Page Fault)
         防止Thrashing的發生(因為Virtual Memory演算法不當,造成幾乎每次存取都要
         依賴二次記憶體,就是Thrashing),以達到效能最佳化,也是個學問 => 第九章

Thread :在同一個Process底下,有許多自己的分身,就是Thread,中文又翻成執行緒。
         以往一個Process一次只能做一件事情,因此要一面輸入文字,一面計算字數,
         這種事情是不可能的。但是有了Thread之後,可以在同一個Process底下,讓輸
         入文字是一個Thread,計算文字又是另外一個Thread,對CPU來說兩個都是類似
         一個Process,因此兩個可以同時做。
         又一個Process底下有數個Thread,而一個Process的Global Variable可以讓
         它的所有Thread共享,也就是所有Thread都可以存取同一個Process的Global
         Variable。而每個Thread自己也有自己的專屬Variable。 => 恐龍本第四章
         但是,如果有兩個Thread要存取同一個Global Variable,有可能發生問題,
         也就是說可能會存取到錯的值(例如兩個Thread同時要對一個Variable做加減,
         最後那個答案可能會是錯的),這就是Synchronization問題 =>恐龍本第六章
         又,每一個Thread之間可能會互搶資源,而造成死結(Deadlock),只要以下四
         個條件都滿足就有死結。(1)這個資源不能同時給兩個人用 (2)有一個人拿了一
         個資源,又想拿別人的資源 (3)如果一個人占了茅坑不拉屎,占用資源很久,仍
         不能趕他走 (4)A等B,B等C,C等D,D又等A 等成一圈。 要解決這種狀況有
         Avoid(預防) 或 避免(Prevent)兩種方式,破除以上四種其中一種即可。
         => 恐龍本第七章


10.

Q:
printf("size of BYTE = %d\n \

size of float = %d\n \
size of unsigned int = %d\n \
size of int = %d\n \
size of double = %d\n \
size of unsigned char = %d\n \
size of char = %d\n" 
,sizeof(BYTE)
,sizeof(float)
,sizeof(unsigned int)
,sizeof(int)
,sizeof(double)
,sizeof(unsigned char)
,sizeof(char));

A:
size of BYTE = 1
size of float = 4
size of unsigned int = 4
size of int = 4
size of double = 8
size of unsigned char = 1
size of char = 1


C語言所定義的資料型別如下
型別符號位元位元長度表示方法數值範圍
整數16或32int-2147483648 ~ 2147483647
8char-128 ~ 127
16short-32768 ~ 32767
32long-2147483648 ~ 2147483647
64long long
16或32unsigned int0 ~ 4294967295
8unsigned char0 ~ 256
16unsigned short0 ~ 65535
32unsigned long0 ~ 4294967295
64unsigned long long
浮點數32float10^-38~10^38
64double10^-308~10^308
字元8char-128 ~ 127







Quiz:
請試著寫出下面代碼的輸出:

view plaincopy to clipboardprint?
#include
#include

int main()
{
char strAry[] = "This is string";
char *aryPtr = strAry;
int *intPtr = (int*)strAry;
printf("\t[Line01] strAry=%s\n", strAry);
printf("\t[Line02] aryPtr=%s\n", aryPtr);
//printf("\t[LineX] *aryPtr=%s\n", *aryPtr); // Segment fault
printf("\t[Line03] sizeof(aryPtr)=%d\n", sizeof(aryPtr));
printf("\t[Line04] sizeof(*aryPtr)=%d\n", sizeof(*aryPtr));
printf("\t[Line05] *aryPtr='%c'\n", *aryPtr);
printf("\t[Line06] *aryPtr+1='%c'\n", *aryPtr+1);
printf("\t[Line07] *(aryPtr+1)='%c'\n", *(aryPtr+1));
printf("\t[Line08] sizeof(intPtr)=%d\n", sizeof(intPtr));
printf("\t[Line09] sizeof(*intPtr)=%d\n", sizeof(*intPtr));
printf("\t[Line10] intPtr=%s\n", intPtr);
//printf("\t[LineX] *intPtr=%s\n", *intPtr); // Segment fault
printf("\t[Line11] *intPtr='%c'\n", *intPtr);
printf("\t[Line12] *intPtr+1='%c'\n", *intPtr+1);
printf("\t[Line13] *(intPtr+1)='%c'\n", *(intPtr+1));
return 0;
}

Sol:

[Line01] strAry=This is string # 字串陣列 char[] ="..." 會自動加上 NULL 到結尾.
[Line02] aryPtr=This is string # 同上, 只是把 aryPtr 指標指向 strAry 的位置. strAry 本身也是個指標.
[Line03] sizeof(aryPtr)=4 # 指標的大小根據系統是 32bit (4byte) 或是 64bit(8bypte) 有所不同.
[Line04] sizeof(*aryPtr)=1 # char 的大小為 1 byte.
[Line05] *aryPtr='T' # 指向字串中第一個字元 'T'
[Line06] *aryPtr+1='U' # char 'T' + 1=char 'U'. -> ASCII 'T'=84. 84+1=85=ASCII 'U'.
[Line07] *(aryPtr+1)='h' # 將 aryPtr 指標移動一個 char 的位置 (1 個 byte 的距離), 即是字串的第二個字元 'h'.
[Line08] sizeof(intPtr)=4 # 同 Line03
[Line09] sizeof(*intPtr)=4 # int 類型的大小為 4 byte.
[Line10] intPtr=This is string # 雖然用 int* 指定 pointer 類型, 但是在 printf 使用 '%s', 故還是打印出字串出來.
[Line11] *intPtr='T' # 指向字串中第一個字元 'T'.
[Line12] *intPtr+1='U' # 同 Line6
[Line13] *(intPtr+1)=' ' # 因為 指標類型為 int, 故移動一個位置為 4 byte, 所以指向第 0+4 =4 位置上的字元, 即字串的第五個字元 (從 0 開始).