Christian Craig

為了2015 summer internship, 我投了好幾十家公司(老婆也幫我投了不少XD)。

今天進行第一場，希望不是最後一場的電話面試。

到了快五點，信箱就收到了一個coderpad link for interview。

這是一個共同文字編輯的網頁，可以選c++/Java/... or plain text。

接著Dropbox工程師就打電話來了，相當準時，五點開始面試。

一共有兩位工程師。一開始大家先自我介紹，講一下自己的經歷。

聊一下之後就開始進入正題，進行technical interview寫程式題目。

我遇到的程式題目就是大家在網路上提到的高頻題：

統計一個網站在過去5分鐘內的訪客數量

有兩個functions: void hit()和long getHits()

詳細可以看http://www.mitbbs.com/article_t/JobHunting/32549839.html

由於對這題有些實作概念不太懂，所以我先用口頭描述我大概的演算法

特別提到關鍵字circular buffer和time stamp

實際寫時找一個我覺得比較合理的答案抄抄：

class HitsCounter {

private:

    vector<int> hitcnt; // stores the hit for each second

    long long total;    // always keeps the current hit count

    long long last;     // the time of last hit

    int size;          // size of hitcnt array, for this question set to 

300

public:

    HitsCounter(int secondCnt) {

        // in this case, secondCnt shoule be 300

        hitcnt = vector<int>(secondCnt, 0);

        total = 0;

        size = secondCnt;

    }

    long long getHit() {

        // total always stores the current hit count

        return total;

    }

    void hit(long long cur) {

        // suppose the unit of time() is second

        // long long cur = time();

        // if cur > last, some previous value need to be reset to 0

        // also, if t - last > size, we've set 0 for entire queue, no need 

to continue

        for (int t = last + 1; t <= cur && t - last <= size; t++) {

            // update total, and reset the specific count to 0

            total -= hitcnt[t % size];

            hitcnt[t % size] = 0;

        }

        // update hitcnt, total and last for this hit

        hitcnt[cur % size]++;

        total++;

        last = cur;

    }

};

整個面試時間是一小時，從下午五點到六點。大概剩20分鐘時，我寫得差不多了，但是因為是臨時看這段code，中間有些地方不太確定，所以一直修修改改。面試官要我把code講解一遍，有些地方因為不太懂，我講的不好，面試官也人很好的提示我。他似乎覺得我做得還不錯(?)，不知道是不是客套，我覺得自己基本上是搞砸了。最後十分鐘，他問我有沒有什麼問題，我就把預先準備的問題拿出來問：(a) intern要做什麼project啊？ (b) 我想做document tracking difference, or image difference讓dropbox功能更強大，請問具體有什麼挑戰，如何完成？

就這樣結束了第一次在美國的面試，好緊張!!面試完終於鬆了一口氣嚕:)

其實這次我比較認真準備的是另外一題高頻題：

pattern matching：

Given a pattern and a string input - find if the string follows the same 

pattern and return 0 or 1.

Examples:

1) Pattern : "abab", input: "redblueredblue" should return 1.

2) Pattern: "aaaa", input: "asdasdasdasd" should return 1.

3) Pattern: "aabb", input: "xyzabcxzyabc" should return 0.

細節可以參考http://www.capacode.com/?p=447

我自己用C++寫的程式碼如下：

#include <iostream>

#include <string>

#include <map>

using namespace std;

static bool isMatched(string pattern, string input);

static bool isMatchedRecur(string& pattern, int startPattern,

                           string& input, int startInput, map<char, string>& defition);

int main(int argc, const char * argv[]) {

    // insert code here...

    cout << "Hello, World!\n";

    bool result = isMatched("aba", "aba");

    if(result)  cout << "Matched\n";

    else        cout << "Unmatched\n";

    return 0;

}

/**

 * Check whether input matches pattern with the current definition

 * @param pattern

 * @param startPattern

 * @param input

 * @param startInput

 * @param defition

 * @return

 */

static bool isMatchedRecur(string& pattern, int startPattern,

    string& input, int startInput, map<char, string>& defition) {

    bool finishedPattern = startPattern >= pattern.length();

    bool finishedInput = startInput >= input.length();

    if(finishedInput && finishedPattern) {return true;}

    else if (finishedInput ^ finishedPattern) {return false;}

    char nextPatternChar = pattern[startPattern];

    //if the next character in pattern is already defined, check its definition as prefix of the input

    if(defition.find(nextPatternChar)!=defition.end()) {

        string charDef = defition[nextPatternChar];

        if(startInput + charDef.length() - 1 >= input.length()) {return false;}

        for (int i = 0; i < charDef.length(); i++) {

            if (charDef[i] != input[startInput + i]) {return false;}

        }

        return isMatchedRecur(pattern, startPattern + 1, input,

               startInput+int(charDef.length()), defition);

    } else {

        string builder = string();

        int j = 0;

        //try all possible definition of the current character in the pattern

        for (int i = startInput; i < input.length(); i++) {

            builder.insert(builder.begin()+j, input[i]);

            string newDef = builder;

            //make sure the definition is distinct

            for(auto it = defition.begin();it !=defition.end();it++){

                if(it->second == newDef){continue;}

            }

            defition.insert(pair<char, string>(nextPatternChar, newDef));

            bool isMatch = isMatchedRecur(pattern, startPattern + 1,

                    input, startInput + int(newDef.length()), defition);

            if(isMatch) {return true;}

            defition.erase(nextPatternChar);

            j++;

        }

        return false;

    }

}

static bool isMatched(string pattern, string input){

    map<char, string> dict;

    return isMatchedRecur(pattern, 0, input, 0, dict);

}