Christian Craig

一樣很準時的早上11點就接到電話嚕。

對方寄了一個collabedit的連結，預備等下的technical interview。

簡短介紹了一下我的研究之後，就開始做題。

題目是binary tree，由運算子和運算元所構成，算其總和。

// example:  

//     +

//   /   \

//  3     *

//      /   \

//     6     5

//    = 33

// 3 + (6 * 5) = 33

我覺得這題還算簡單，不過一開始腦筋有點打結，

完全寫不出來，

就開始跟他講解我大概會怎麼做的演算法來拖時間XD

我講了一下我忘了怎麼做char轉換成operation，

於是他幫我簡化成運算子只有乘法和加法。

還好後來總算寫出個大概了。

聽起來應該是還算ok，

於是他又出了一個延伸題，要增加unary operation，

例如次方(power)運算。

//    ^2

//      \

//       3

// =  3^2

解題過程中，他也有問我這裡面有什麼assumption，

例如乘加法運算左右子樹是要同時存在，

而unary operation一定只有右子樹。

下面是我的解答：

#include <math.h>

struct node {

    double value;

    char type;

    node* child_left;

    node* child_right;

};

double computeExpression(node* root)

{

    if(root->child_left == NULL && root->child_right == NULL)    return value;    

    if(root->type=='^')         return pow(computeExpression(root->child_right), root->value);

    else if(root->type=='+')    return computeExpression(root->child_left) + computeExpression(root->child_right);

    else                   return computeExpression(root->child_left) * computeExpression(root->child_right);

}

技術面試寫完之後，

又隨便聊了一下，就結束這次的面試。

全程剛好是45分鐘，時間剛剛好。