Christian Craig

第一輪面試完後彷彿看到offer的曙光，

心裡想如果第二輪不是三哥三妹，

應該就可以拿到offer了。

3:15電話準時打來，

是個印度大哥，

我心都涼了一半Orz

硬是跟我瞎聊了履歷上的project，花了5~10分鐘

然後就出了一道完全沒看過的題目....

還好基本題並不算太難，

在面試官糾正了我一些小錯誤之後，

順利寫出來了。

但是follow up的problem B是個殺手題，

雖然我想到了解法，

但是是O(nlogn)，印度大哥要求要O(n)

東想西想了許多辦法，要不是有錯，不然就是還是O(nlogn)。

有點扼腕，還好他人還不壞，並沒有要把我打殘，

最後他要我把O(nlogn)的方法implement完成，

總面試時間超過45分鐘後，又多拖了大約10分鐘。

面完之後我自然是累垮了QQ

希望他能給我過啊~

A. Given N points on a two dimensional plane, find all axis parallel lines that can be formed by joining any two points in the set.

follow up :

1. what’s the number of segment combinations?

struct Point {

int x;

int y;

};

int CountNumOfAxisParallelLines(vector<Point> pts) {

int ans = 0;

for (const auto& p : pts) {

++setx[p.x];

++sety[p.y];

}

for (const auto& s : setx) {

if (setx.count(s.first) >= 2) {

ans += setx.count(s.first) * 

(setx.count(s.first) - 1) / 2;

//++ans;

}

}

for (const auto& s : sety) {

if (sety.count(s.first) >= 2) {

++ans;

}

}

return ans;

}

private:

unordered_map<int, int> setx, sety;

B. Following problem A, find the largest rectangle that does not include any other lines.

      | | |

_____|______ |___________|___

_____|______ |___________|___

      | | Big- |

      | | gest |

      | | grid |

      | | |

_____|______ |___________|___

int CountNumOfAxisParallelLines(vector<Point> pts) {

int ans = 0;

for (const auto& p : pts) {

++setx[p.x];

++sety[p.y];

}

int max_x, min_x;

int mx_seg = 0;

for (const auto& s : setx) {

if (s.first < min_x) {

mx_seg = max(mx_seg, abs(min_x - s.first));

} else if (s.first > max_x) {

mx_seg = max(mx_seg, abs(s.first - max_x));

} else {

mx_seg = max(abs(s.first - max_x), abs(min_x - s.first));

}

}

int pre = 0;

int max_len = 0;

// Ordered map is used.

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

      if (sety.count(*it) >= 2) {

if (it == sety.begin()) {

pre = *it;

} else {

int diff = *it - pre;

pre = *it;

max_len = max(max_len, diff);

}

}

++ans;

}

}

return ans;

}