s********i
发帖数: 145 | 1 背景：C++，本科数学，研究生改CS，偏Graphics方向
电面一轮，上来随便聊几句项目，然后问了一个C++基础，什么是pure virtual
function。之后做题，2维平面的一堆点，假设有一个在坐标原点的viewport,任给
range(eg: 30度), 问什么角度viewport可包含最多的点。我说先把点转成极坐标，然
后sort by angle, 然后再按点search。他问我search什么复杂度？我说binary search
, nlogn。他说可以做到linear，我想了一会没想到怎么做，他说那你写吧。然后就开
是写代码，发现边界的时候不太好处理，基本写废了，就差没拍桌子了...折腾时间差
不多了，人说就这样吧，有啥问题不？我问他linear的算法是啥,他说window sweep.
感觉不是很好，以为绝对挂了，结果recruiter打电话说表现很好，来onsite吧...于是
约了几周后onsite。
onsite一共5轮，3轮考基础+算法，1轮考test, 1轮考design。中午有个日本人带着吃
了个汉堡，随便聊了几句。每轮过后会留出几分钟让你问问题。比较遗憾的是3轮算法
考我的都是三哥，其他两轮是白人，面试的那个大楼基本没看到国人...
先说3轮3哥面的。感觉3哥给我的题比网上某些大牛onsite拿到的题容易很多，看来G可
能会根据背景按方抓药...所以Onsite如果感觉题目不是很难可能不是啥好事，可能狗
觉得你背景比较一般（虽然也是事实）。可能因为我有数学背景，3哥问了一些和数学
相关的非编程的题目。比如1.给一个光线的入射角和平面法向，怎么求反射光方向; 2.
给一堆采集自某物体表面的3维点，怎么求物体表面在某点法向; 3.估计在某个固定的
level, 多少张图像可以铺满整个Google earch, 怎么压缩存储等。编程的题目 1.
quadtree intersection, 跟本版某牛面经里一模一样，就不重复了。2. transpose an
image。 3. 假设有一个计数器，每秒会产生一个整数（比如，某页面一秒内的访问次
数）， 假设已经有函数 getTimer() 返回当前时间，设计数据结构可以实现
getCountLastMin()，也就是最近的一分钟内时间的访问量；以及insert(int n)， 即
当前生成整数n。
3哥的题目感觉不是很难，数学题基本都秒掉了，编程题思路经过事后确认都是对的，
第二题实现的时候有点bug。感觉知道怎么做跟写出bug free的代码还是两码事，练的
还是不够。3哥的这几轮整体感觉不错，使我一度错觉以为有戏...
考test的那轮给了一道题，给定一个文件名，可能很长很长，网页上有一个定长的
window(如50个字符)，怎么显示可以给用户最多的信息。前一半时间在讨论怎么实现，
各种思路。然后实现一个简单版本，最后写unit tests. 以为平时在公司也常写unit
tests，虽然没有特别准备，感觉也不是十分狼狈。这轮感觉中等吧。
考design那轮比较悲催。interviewer是web出身，我web经验基本为0。假设有一个显示
消息list的网页（如mitbbs的某版面）他给了我一堆api,对应网页的各种功能，问怎么
扩充API实现新功能：可以给消息加标签。这轮感觉答得比较被动，跟interviewer也不
是很来电，不是很好。
两周后收到消息说挂了，小失落了一下下。总结：
1. G电面比较水。
2. 感觉G很看中学历，没记错的话，3个三哥都是phd出身。
3. 题目不是非常难,低于leetcode的平均水平，甚至感觉低于其他G面经的题目水平，
不知什么原因。
4. 除了算法，一定要准备test和design.这个应该比算法好准备，但是像我这样没准备
就上阵，基本不会有啥好结果。
5. G水确实深，看版上那么多大牛都挂了，我也基本do my best了，但还是够不着他家
的bar。
6. 3个3哥感觉级别不是很高，其他两个感觉是senior，特别是最后考design的那个，
所以那两轮可能相对更重要，但是不幸表现不佳。 | p*****2
发帖数: 21240 | 2 5. G水确实深，看版上那么多大牛都挂了，我也基本do my best了，但还是够不着他家
的bar。
其实是看运气。下次可能就拿offer了。 | A*****i
发帖数: 3587 | 3 面试确实看运气……不要太把拒当回事，有时候不是你表现的不够好，而是你们不来电 | j******2
发帖数: 362 | 4 请问lz什么时候电面的？什么时候onsite的？
search
【在 s********i 的大作中提到】
: 背景：C++，本科数学，研究生改CS，偏Graphics方向
: 电面一轮，上来随便聊几句项目，然后问了一个C++基础，什么是pure virtual
: function。之后做题，2维平面的一堆点，假设有一个在坐标原点的viewport,任给
: range(eg: 30度), 问什么角度viewport可包含最多的点。我说先把点转成极坐标，然
: 后sort by angle, 然后再按点search。他问我search什么复杂度？我说binary search
: , nlogn。他说可以做到linear，我想了一会没想到怎么做，他说那你写吧。然后就开
: 是写代码，发现边界的时候不太好处理，基本写废了，就差没拍桌子了...折腾时间差
: 不多了，人说就这样吧，有啥问题不？我问他linear的算法是啥,他说window sweep.
: 感觉不是很好，以为绝对挂了，结果recruiter打电话说表现很好，来onsite吧...于是
: 约了几周后onsite。
| c******3
发帖数: 60 | 5 bless! 下次说不定你就有offer了
search
【在 s********i 的大作中提到】
: 背景：C++，本科数学，研究生改CS，偏Graphics方向
: 电面一轮，上来随便聊几句项目，然后问了一个C++基础，什么是pure virtual
: function。之后做题，2维平面的一堆点，假设有一个在坐标原点的viewport,任给
: range(eg: 30度), 问什么角度viewport可包含最多的点。我说先把点转成极坐标，然
: 后sort by angle, 然后再按点search。他问我search什么复杂度？我说binary search
: , nlogn。他说可以做到linear，我想了一会没想到怎么做，他说那你写吧。然后就开
: 是写代码，发现边界的时候不太好处理，基本写废了，就差没拍桌子了...折腾时间差
: 不多了，人说就这样吧，有啥问题不？我问他linear的算法是啥,他说window sweep.
: 感觉不是很好，以为绝对挂了，结果recruiter打电话说表现很好，来onsite吧...于是
: 约了几周后onsite。
| P*******b
发帖数: 1001 | 6 没有明白binary search nlogn怎么回事
search
【在 s********i 的大作中提到】
: 背景：C++，本科数学，研究生改CS，偏Graphics方向
: 电面一轮，上来随便聊几句项目，然后问了一个C++基础，什么是pure virtual
: function。之后做题，2维平面的一堆点，假设有一个在坐标原点的viewport,任给
: range(eg: 30度), 问什么角度viewport可包含最多的点。我说先把点转成极坐标，然
: 后sort by angle, 然后再按点search。他问我search什么复杂度？我说binary search
: , nlogn。他说可以做到linear，我想了一会没想到怎么做，他说那你写吧。然后就开
: 是写代码，发现边界的时候不太好处理，基本写废了，就差没拍桌子了...折腾时间差
: 不多了，人说就这样吧，有啥问题不？我问他linear的算法是啥,他说window sweep.
: 感觉不是很好，以为绝对挂了，结果recruiter打电话说表现很好，来onsite吧...于是
: 约了几周后onsite。
| w****a
发帖数: 710 | | s********i
发帖数: 145 | 8 多谢各位的鼓励。
电面是1月上旬，店面2月上旬。
那个电面题我是做错了。其实就是一个sorted array, 找两个index，在对应的两个数
差小于给定的angle前提下，之间包含的数最多。有点像搜索某字符串给定条件的最长
子串。trick一点的地方就是，如果一个角度是0，另外一个是359，他们之间的夹角是1
而不是359. | x*****0
发帖数: 452 | | g*****o
发帖数: 1637 | 10 m
search
【在 s********i 的大作中提到】
: 背景：C++，本科数学，研究生改CS，偏Graphics方向
: 电面一轮，上来随便聊几句项目，然后问了一个C++基础，什么是pure virtual
: function。之后做题，2维平面的一堆点，假设有一个在坐标原点的viewport,任给
: range(eg: 30度), 问什么角度viewport可包含最多的点。我说先把点转成极坐标，然
: 后sort by angle, 然后再按点search。他问我search什么复杂度？我说binary search
: , nlogn。他说可以做到linear，我想了一会没想到怎么做，他说那你写吧。然后就开
: 是写代码，发现边界的时候不太好处理，基本写废了，就差没拍桌子了...折腾时间差
: 不多了，人说就这样吧，有啥问题不？我问他linear的算法是啥,他说window sweep.
: 感觉不是很好，以为绝对挂了，结果recruiter打电话说表现很好，来onsite吧...于是
: 约了几周后onsite。
| | | r*********n
发帖数: 4553 | 11 array A 里面存sorted angles of all points
从第一个点开始，t = A[0] + 30， 然后在A里面搜索t（binary search），得到index
j，第一个window长度是j-0=j
然后处理第二个点，t = A[1] +20，在A[j+1]...A[end]里面搜索t，得到新的j，新
window长度j-1
如果搜索的时候t>360，那么就要考虑wrap around，我觉得真要写代码，这些boundary
case还是有点麻烦。
是1
【在 s********i 的大作中提到】
: 多谢各位的鼓励。
: 电面是1月上旬，店面2月上旬。
: 那个电面题我是做错了。其实就是一个sorted array, 找两个index，在对应的两个数
: 差小于给定的angle前提下，之间包含的数最多。有点像搜索某字符串给定条件的最长
: 子串。trick一点的地方就是，如果一个角度是0，另外一个是359，他们之间的夹角是1
: 而不是359.
| b******n
发帖数: 4509 | 12 第一个题其实只要知道 viewport 的精度，比如精确到一度，
然后只要用 counting sort 就可以了，复杂度为 n，
后面的程序也非常容易写。
search
2.
an
【在 s********i 的大作中提到】
: 背景：C++，本科数学，研究生改CS，偏Graphics方向
: 电面一轮，上来随便聊几句项目，然后问了一个C++基础，什么是pure virtual
: function。之后做题，2维平面的一堆点，假设有一个在坐标原点的viewport,任给
: range(eg: 30度), 问什么角度viewport可包含最多的点。我说先把点转成极坐标，然
: 后sort by angle, 然后再按点search。他问我search什么复杂度？我说binary search
: , nlogn。他说可以做到linear，我想了一会没想到怎么做，他说那你写吧。然后就开
: 是写代码，发现边界的时候不太好处理，基本写废了，就差没拍桌子了...折腾时间差
: 不多了，人说就这样吧，有啥问题不？我问他linear的算法是啥,他说window sweep.
: 感觉不是很好，以为绝对挂了，结果recruiter打电话说表现很好，来onsite吧...于是
: 约了几周后onsite。
| a***r
发帖数: 93 | 13 Below solution uses counting sort ( thanks bethove ) | A***o
发帖数: 358 | 14 Nice code, thx!
【在 a***r 的大作中提到】
: Below solution uses counting sort ( thanks bethove )
| a***r
发帖数: 93 | 15
我C++写的不多，哪位大牛指教一下，我洗耳恭听。
【在 A***o 的大作中提到】
: Nice code, thx!
| M******7
发帖数: 30 | | z****p
发帖数: 18 | 17 The above discussions are not quite related to the solution of the problem.
Here is my understanding of the problem.
-The question is about "search"; and so O(NlogN) "pre-processing" is not a
problem
-The angles and the query "range" could be any real numbers, not necessarily
integers.
-The expected solution is what LZ mentioned, "window sweep", as the
following:
--consider all the points are on the face of a clock
--to search for the max point number under a range (say 29.9 degree), we
scan the points using two "arms" of the clock, turning clockwise
--the front arm scans the points one by one, according to their angles
--the back arm is "lazy" and only moves when it lags the front arm by more
than the "range" (29.9); when this happens, the front arm stops and waits
for the back arm to catch up
--when the back arm moves, it is very lazy and only moves enough points to
reduce the lag to below "range" again
--the points between the two arms are monitored and the max value occurred
is the solution
--each point is "hit" by the front arm once, and the back arm at most once,
and so the search is O(N) for an arbitrary query range
However, instead of O(N), I can think of an O(logN) solution, as long as pre
-processing is free and there is no dynamic insertion/deletion of points. I
will post the solution later...
search
【在 s********i 的大作中提到】
: 背景：C++，本科数学，研究生改CS，偏Graphics方向
: 电面一轮，上来随便聊几句项目，然后问了一个C++基础，什么是pure virtual
: function。之后做题，2维平面的一堆点，假设有一个在坐标原点的viewport,任给
: range(eg: 30度), 问什么角度viewport可包含最多的点。我说先把点转成极坐标，然
: 后sort by angle, 然后再按点search。他问我search什么复杂度？我说binary search
: , nlogn。他说可以做到linear，我想了一会没想到怎么做，他说那你写吧。然后就开
: 是写代码，发现边界的时候不太好处理，基本写废了，就差没拍桌子了...折腾时间差
: 不多了，人说就这样吧，有啥问题不？我问他linear的算法是啥,他说window sweep.
: 感觉不是很好，以为绝对挂了，结果recruiter打电话说表现很好，来onsite吧...于是
: 约了几周后onsite。
| z****p
发帖数: 18 | 18 Here is the O(log N) solution:
Key observations:
-The solution is "monotonic" in the following sense: if the query "range" is
29.9 and the solution is 100 points, then when the query "range" becomes 30
, the solution is guaranteed to be >= 100.
-We can "pre-compute" the answers to all the possible query "ranges", put
them in a data structure, and look up the data structure when a new query "
range" is asked for.
Solution details: (W.L.O.G., assuming query "range" <= 180 degree)
1. For each PAIR of points, pre-compute (i) the angle "r" between them, and
(ii) the number of points "n" between them,
2. Define a new 2-D coordinate system where x-axis represent angle and y-
axis is represent points
3. Map each pair obtained in step 1 to a "dot" in the new coordinate system
(and so there are N^2 dots in total, sorted by x-axis, i.e., angle)
4. Scan the dots from left to right in terms of x-axis value, namely angle.
For each dot, check if it is a "dominating dot", where a dominating dot is a
dot whose y value is higher than all dots to its left (in other words, a
dot is "dominating" if there is not another dot with smaller "r" but higher
"n").
5. If a dot is not dominating, it can actually been removed from
consideration. Or we can simply record it's nearest dominating neighbor to
the left (in other words, "If I am not a dominating dot, then which
dominating dot has the highest y-value but has a smaller x-value than me?").
6. That's it! Given a query "range", say 29.9, do a binary search in the
space in step 2, find the "rightmost dominating dot to the left of 29.9",
its y-value is the answer.
So the time complexity is O(log(N^2)) which is O(log N).
Additional notes:
-If query "range" can be > 180 degree, we need to build two copies of the
above data structure, one handles cases of <= 180 degree, and the other
handles cases of > 180.
-The above data structure does not support insertion/deletion of points.
-The preprocessing will take O(N^2) time.
search
【在 s********i 的大作中提到】
: 背景：C++，本科数学，研究生改CS，偏Graphics方向
: 电面一轮，上来随便聊几句项目，然后问了一个C++基础，什么是pure virtual
: function。之后做题，2维平面的一堆点，假设有一个在坐标原点的viewport,任给
: range(eg: 30度), 问什么角度viewport可包含最多的点。我说先把点转成极坐标，然
: 后sort by angle, 然后再按点search。他问我search什么复杂度？我说binary search
: , nlogn。他说可以做到linear，我想了一会没想到怎么做，他说那你写吧。然后就开
: 是写代码，发现边界的时候不太好处理，基本写废了，就差没拍桌子了...折腾时间差
: 不多了，人说就这样吧，有啥问题不？我问他linear的算法是啥,他说window sweep.
: 感觉不是很好，以为绝对挂了，结果recruiter打电话说表现很好，来onsite吧...于是
: 约了几周后onsite。
| s********i
发帖数: 145 | 19 Not sure if your algorithm will work, but I kind of feel you are
overshooting.
is
30
and
【在 z****p 的大作中提到】
: Here is the O(log N) solution:
: Key observations:
: -The solution is "monotonic" in the following sense: if the query "range" is
: 29.9 and the solution is 100 points, then when the query "range" becomes 30
: , the solution is guaranteed to be >= 100.
: -We can "pre-compute" the answers to all the possible query "ranges", put
: them in a data structure, and look up the data structure when a new query "
: range" is asked for.
: Solution details: (W.L.O.G., assuming query "range" <= 180 degree)
: 1. For each PAIR of points, pre-compute (i) the angle "r" between them, and
|
|
