Christian Craig

這次是面試Google 2017的Summer intern

一共兩輪面試，一次45分鐘，兩輪直接背靠背。

下午2:15電話準時打來。

第一輪面試我的是白人小哥。

一上來不廢話，直接開始貼題做題目。

兩題都是Google高頻題小改一下

第一題是Leetcode 281 Zigzag Iterator

class Interleave { 

public: 

  Interleave(const vector<vector<int> >& vv) {

for (const auto & v : vv) {

if (!v.empty()) {

q.emplace(v.size(), v.cbegin());

}

}

  }

  bool hasNext() {

return !q.empty();

  }

  int next() {

const auto len = q.front().first;

const auto it = q.front().second;

q.pop();

if (len > 1) {

q.emplace(len - 1, it + 1);

}

return *it;

  }

private:

queue<pair<int, vector<int>::const_iterator>> q;

}; 

V1 - A1, A2, A3 

V2 - B1, B2 

V3 - C1, C2, C3, C4, C5 

Interleaved order: 

A1, B1, C1, A2, B2, C2, A3, C3, C4, C5 

void main() {

vector<vector<int>> vv;

vv.push_back({1,2,3});

vv.push_back({4});

vv.push_back({5,6,7});

Interleave inter = new Interleave(vv);

if (inter.hasNext()) {

cout << inter.next() << endl;

}

}

==================================================

第二題是Leetcode 340 Longest Substring with At Most K Distinct Characters 的小變種

class LongestDistinctSubstring {

  void add_char(char c) { 

s_ += c;

for (int i = 0; i < s_.size(); ++i) {

if (visited[s_[i]]++ == 0) {

++cnt;

} else {

++st;

}

if (i - st + 1 > len_) {

len_ = i - st + 1;

max_s_ = s_.substr(st, i - st + 1);

}

}

  }

  int length() {

return len_;

  }

  string longest_distinct() {

return max_s_;

  }

private:

array<int, 256> visited = {0};

string s_;

string max_s_;

int st = 0, cnt = 0;

int len_ = 0;

}

abcaaa

length -> 3

longest_distinct -> “abc”

caa -> invalid, abca -> invalid

==============================

Improve quadratic behaviour of add_char:

class LongestDistinctSubstring {

  void add_char(char c) { 

s_ += c;

if (visited[s_.size() - 1] == 0) {

++cnt;

} else {

while (visited[s_.size() - 1] > 1) {

++st;

}

}

len_ = max(len_, i - st + 1);

for (int i = st; i < s_.size(); ++i) {

if (visited[s_[i]]++ == 0) {

++cnt;

} else {

++st;

}

if (i - st + 1 > len_) {

len_ = i - st + 1;

max_s_ = s_.substr(st, i - st + 1);

}

}

  }

  int length() {

return len_;

  }

private:

array<int, 256> visited = {0};

string s_;

string max_s_;

int st = 0, cnt = 0;

int max_cnt = 0;

int len_ = 0;

}

兩題感覺自己做的都還不錯，

面試官反應也很好，

所以面完後信心大增。

兩題面試完後，和小哥稍微哈啦了5分鐘，

準時45分鐘結束。