x*****p
发帖数: 1707 | 1 平面上有随机2000个点，其中1000蓝点，1000红点。但任何三点都不同线。
要求寻找一种最优化的算法，生成1000条互不相交的连接蓝点和红点的线段。换句话说
，让任何蓝点去连接任何红点，但各不相交。 |
|
e****e
发帖数: 1885 | 2 如果这个问题是一维的求线段的most overlapping segment，sweeping line应该就能
搞定了，需要nlog(n)的时间。但是现在是二维，我有点想不清楚 |
|
|
b*******8
发帖数: 37364 | 4 貌似可以简化一下，第一个左端点入Stack，记下坐标；当某个右端点来了造成Stack空
了，那么此右端点减去前面那个坐标，就是此条合起来大线段的长度。
covered = 0;
stack = 0;
for (i = 1; i < list.length; i++) {
//if (stack > 0) {
// covered += list[i] - list[i-1];
//}
if (list[i] is a starting point) {
if (stack == 0) left = list[i];
stack++;
} else { // if list[i] is an ending point
stack--;
if (stack == 0) covered += list[i] - left;
}
} |
|
g***s
发帖数: 3811 | 5 当年同事去google面试的题目。
给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
（i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
的液体容量最大
(容器不能倾斜)。
大家先做做 |
|
p*****r
发帖数: 1883 | 6 这是曾经MSRA中国的面试题，参看《编程之美》，解法是用DP，或者是线段树 segment tree |
|
d*******l
发帖数: 338 | 7 有这么复杂？线段树非常强大，但用在这题上不是很顺吧。我在前面的post里提到一个
简单的O(n)的做法，我觉得好像是没错的。再写一次：
minE = -INF
maxS = INF
foreach (s, e)
minE = max(minE, s+1)
maxS = min(maxS, e-1)
if(minE > maxS)
return (maxS, minE)
return (maxS, maxS+1）
segment tree |
|
f*****w
发帖数: 2602 | 8 只能想出NlogN的 先按照线段左端的点排序 然后走一遍
不知道怎么样还能更好的没有 |
|
d*******l
发帖数: 338 | 9 如果要统计两两overlap的总对数，那用线段树应该能O(nlogn)出来。如果要输出所有
，那只能O(n^2)了 |
|
g**********y
发帖数: 14569 | 10 {1, 5, 9, 8} 是有效解的话，就明白了。
就是说，任何一个点都不能在以前点形成的线段上。比如 {1, 9, 5}就违规了。
这个题还有点tricky。 |
|
g**********y
发帖数: 14569 | 11 算了，不想了，你把所有线段退化成点，那就等同于货郎担问题了。这个找出简单解来
就牛大了。 |
|
b*******h
发帖数: 53 | 12 1. 一个array当中，每个element都是一个带一种颜色的小球。有20种颜色的选择。排
序，将相同颜色的小球放在一起。 要求linear time and in-place.
in-place, 我的理解就是不能再用一个array装重新的排序的小球。
2.如何判断两个矩形overlap. 用最少的判断条件。
这道题是一道经典题吧，隐约好像以前见过。
自己给出的方案： 分别判断两边有没有overlap，就是x方向和y方向的线段有没有重叠
的部分，如果两个方向都有的话，两个矩形overlap。
不知道有没有其他方法。 |
|
s*****n
发帖数: 5488 | 13 1. C++ faq
2. 线段hashtable,然后对每个bucket 操作找。
3.DFS
4.
节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
回答更多的题目，但是保证正确才是最重要的。
复杂度。
比如(3,5)和(4,6)之间的叫"a", 那就表示为
,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是 |
|
P**********c
发帖数: 3417 | 14 题目要求是给你一串structure, 比如放到一个array里。每个array element是一条线
段，里面包括起始点的横纵坐标，终止点的横纵坐标，和线段的名字。 |
|
g*****k
发帖数: 623 | 15 第3题错了，
第1：并不一定是其他线段的终点
第2：component没有propogate,也就是没有进行set union
第3题，不太明白，4 billion的数一个一个读进内存，还能只读原文件32次？
请问这是如何做到的?
较，如果相等则标记已访问过，并且标上component的值，这个也是O(n^2)吧。回来也
没想出有什么错误。
她属于0～2^31还是后面，这样数范围，如果数完发现左半边缺数，下次数的时候就只
看左边，继续分成两半。总共需要读原文件32次。不能用careercup那个做法。面试的
人似乎认为我的思路是对的， |
|
d*******l
发帖数: 338 | 16 题目的意思应该是要求连通分量，也就是所有能连到一起的线段都被放到一块输出 |
|
k*j
发帖数: 153 | 17 想问下第三题有结论了没？线段求component的那题。
节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
回答更多的题目，但是保证正确才是最重要的。
复杂度。
比如(3,5)和(4,6)之间的叫"a", 那就表示为
,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是 |
|
k*j
发帖数: 153 | 18 想问下第三题有结论了没？线段求component的那题。
节还是很重要的，必须多写多练才行。类似copy constructure, assignment operator
哪些地方应该用const, 哪些地方为什么用reference，不要搞混了. 本来以为自己这些
都是知道的，没想到现场一步一步的写，还是出了很多小错，当时就感觉给面试官印象
不好了。写程序的时候要先想一想，以前写过看过什么类似的程序，需要注意什么问题
。不要急着下笔。有的面试官问题问题很多，频率很快。很容易让你自己很心急，希望
回答更多的题目，但是保证正确才是最重要的。
复杂度。
比如(3,5)和(4,6)之间的叫"a", 那就表示为
,6,"a")和(4,6,8,2,"b")是连在一起的, 又比如c和d是连在一起的，那打出来应该是 |
|
k*j
发帖数: 153 | 19 Given a two dimensional graph with points on it, find a line which passes
the most number of points.
这是在cracking coding interview书里（10.6）的一题。书里是用hash的方法。
public int hashCode(){
int s1= (int)(slope*1000);
int in = (int)(intercept*1000);
return s1 | in;
}
但我一直不明白，如果是x = x1,也就是slope = infinite的情况，如何求这个
hashcode呢？因为infite是inf, 乘上1000 ＝ ？ |
|
|
b*******8
发帖数: 37364 | 21 对斜率无穷的竖线，大不了专门扫一次特殊处理，O（N)时间。 |
|
P**********c
发帖数: 3417 | 22 斜率无穷的直线，书上没有把slope存成无穷，初始值是多少就是多少, Java里应该是
默认为0。你要是用C++写的话，可以在Line的constructor里面的else{}部分把slope设
成0就没问题了. |
|
l***i
发帖数: 1309 | 23 You have at most (n choose 2)=n^2 lines for each pair of points. Represent
each line as A*x+B*y=C.
Now sort the triples for all lines. Lines coincide will have same (A,B,C) so
count them. This is O(n^2logn). If you have a magic hash function, you can
get O(n^2) assume you map each distinct triple to a unique bucket. |
|
k*j
发帖数: 153 | 24 面了2轮电话。应该挂了。
第一轮电话面试，老印。已知每天的股票价格，计算何时买卖获益最大。这是个老题，
O(n)。
然后他扩展了一下，问如果可以多次买进卖出。如何maximize收益最大。
我先用DP，他说可以用recursive call。要我编程念给他听。然后说如何加速，我说建
一个table, O(n^2)。他说再怎么加速，我没答出来，他自己说应该是greedy 解法，O(
n).
第二轮，g docs 编程。是一个ABC面的。两个线段数组，求common区间
A［1，5］［10，15］
B [3,12]
return [3,5],[10,12]
这题有好几种情况要考虑。我没写好。
总结：
我是网上申请的。感觉他们家就只考算法，而且大部分都是如何加速到O(n)的题。没有
设计之类的问题。另外我发现glassdoor上的有关P家的题目很多，而且重复出的概率很
大，建议大家去做一下。Good luck。 |
|
s****j
发帖数: 67 | 25 周一onsite，昨天回来，坐飞机累得半死。。。
说说面试感受吧，具体题目不便透露，见谅
面试这东西，在我看来，三分实力，三分临场发挥和表现，还有四分是运气。运气当然
包括了很多方面，最容易理解的就是面试题目是不是对你胃口，不过其实这不是运气最
大的体现。运气最重要的是，你要赶上合适的时机。比如有的公司正好近期slow down
了，甚至freeze了，那你实力和表现再好，恐怕也少有机会。所以，如果你内部有认识
的人，打探一下这方面的情况也是有必要的。
关于面试的题目，虽然我这次还是处女面，但见也算见了不少了。我觉得，正常的面试
题目，大概可以分成这么几类：
1 考察基本功，和代码质量。比如一个二分，我觉得要五分钟、bugfree地写完。
2 需要应变和思考一下的题目。比如著名的min函数stack，这种题目说实话如果之前没
见过，能在面试时间内想出来，那就很牛逼了。
3 标准或者纯的算法题。会写dfs，bfs，基本就没问题了。普遍来说，算法方面公认的
比较有难度的会考到的也就dp了，而且应该也是简单的dp。其实dp这东西，做过10几20
道题以后，或者把背包问题相关的搞清楚，应付面试... 阅读全帖 |
|
s***h
发帖数: 662 | 26 来自主题: JobHunting版 - 一个dp题 有一条线段上有点1, 2, 3, ...n, 均匀分布, 每两个之间间隔为1,从一点出发
到另一点需要花费时间t = 1.
假定你从某点s出发, 需要遍历所有的点. 每点i都有一个时间ti与之相关,必须在
ti之前到达点i.
如何在最短时间里面遍历所有的点, 并且满足ti的限制? 提示(可以使用S(i,j,x)表示遍历点i->j, 满足ti,且终止在点x(x = i or j).)
这个好像可以写成
OPT = min(S(1,n,1), S(1,n,n))
S(1,n,n) = min{((S(1,i,i) + (n-i)) > tn) ? inf : keep the value, or
((S(1,i,1) + n) > tn) ? inf: keep the value}
...
但是从1出发就trivial了.出发点不是1, 这个解没有用. 如果i!=1, S(i,j,x)怎么表示呢? 如果写成
S(i,j,j) = min{((S(i,k,k) + (j-k)) > tj) ? inf : keep the value, or
... 阅读全帖 |
|
f*******t
发帖数: 7549 | 27 我以前写过一个程序，用linked list存interval，按起始位置排序，各线段不重叠。
要往里插入新的节点相当不好写对，有多种情况和边界条件。
interval tree概念是不复杂，面试中基本没可能写出来。 |
|
f*******t
发帖数: 7549 | 28 我以前写过一个程序，用linked list存interval，按起始位置排序，各线段不重叠。
要往里插入新的节点相当不好写对，有多种情况和边界条件。
interval tree概念是不复杂，面试中基本没可能写出来。 |
|
x*****o
发帖数: 23 | 29 “给你 n 个数字 a1,a2...an,表示坐标上面(i,ai)个点,i=1..n(i,ai)到(i,0)共 n 个
线段,从中挑两条,和 x 轴一起构成一个容器,让容器能装的液体容量最大(容器不能倾
斜)。”
应该是可以O(N)吧？ |
|
j****u
发帖数: 11 | 30 给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
（i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
的液体容量最大 (容器不能倾斜)。 (非maximum rectangle in histogram)
之前版上讨论过,貌似没讨论出来强于O(n^2)的解... |
|
j****u
发帖数: 11 | 31 给你n个数字a1,a2...an，表示坐标上面（i，ai）个点，i＝１.. n
（i，ai）到（i，０）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装
的液体容量最大 (容器不能倾斜)。 (非maximum rectangle in histogram)
之前版上讨论过,貌似没讨论出来强于O(n^2)的解... |
|
|
s******t
发帖数: 169 | 33 离散化+线段树可以做，或者离散化+树状数组，对于每个pair，直接插入，时间为log(
n)，总共为nlog(n)。然后查询的时候，每次查询log(n)
wwwyhx说的本质上就是离散化吧，如果我没理解错的话。本质上相当于把一个相当大的
区间离散成较小的区间，比如说有一个对是(1,100000)另一个是(2,300000)，真用一个
300000的数组去存就不太划算了，其实把几个点排下序然后离散化，4个点就可以 |
|
d****o
发帖数: 1055 | 34 来自主题: JobHunting版 - 一道面试题 把每一个线段表示出来不行吗？ |
|
m******d
发帖数: 25 | 35 第一题可以这么做：先计算一下最左L和最右R两条线包围出的面积。假定L比R短，那么
从左边开始，找到第一条比L高的线段L'。计算L'和R包围的面积，看看是不是更大。L
和L'包围出的面积不可能比L和R包围的面积大，所以不用考虑。下一步，L'变成新的L
，重新开始。O(n)。 |
|
i***h
发帖数: 12655 | 36 如果N=2的话,
连线上任意一点的移动距离都是一样的, 就是线段长度, 对不对?
题： |
|
|
b***m
发帖数: 5987 | 38
纯属个人意见：
航空公司订票系统的核心应该是航段信息管理，具体展开说，就是以许多城市为点构成
的有向图，以及连接这许多点的线段（也即航班）。有向图在数据库中可以表现为一条
条与日期有关的记录，而航班的核心应该是舱位管理（每个舱位对应不同的价位，分别
售出多少，根据季节选择超售的比例）。航空公司一般只允许预订未来365天的机票，
大概就是因为这样可以维护一个合理数量的“未来数据库”。在这样的抽象基础上，我
觉得后面的设计相对就清晰和容易一些了。
大家都可以说说自己的看法，我觉得设计题没有必然的正确答案，合理性、易理解性、
可扩展性应该是最重要的。 |
|
f****e
发帖数: 34 | 39 来自主题: JobHunting版 - G/F面经 第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
个过程不到30分钟。
fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
个问题该怎么回答，另外还要我要好好练习英语口语。
2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
穿线二叉树的，另外一个题目是copy a link list with a random ptr，相信大家都见
过这个题目。
3. 9月底的时候google安排10月11号onsite... 阅读全帖 |
|
l***m
发帖数: 339 | 40 来自主题: JobHunting版 - G/F面经 先按照线段起点排序，然后用bst，所以代码不太长的。（nlogn） |
|
c*****r
发帖数: 214 | 41 来自主题: JobHunting版 - G/F面经 cong!
现在从国内直接过来人的太多了，这条路比当年考T考G读phd的那批人真是平坦太多了
第一次写面经。。也不知道该侧重哪方面，就记录一下流水账吧。
1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
个过程不到30分钟。
fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
个问题该怎么回答，另外还要我要好好练习英语口语。
2. fb电面完后马上google电话面试，早上7点半从美国总部打过来的，不过是用的中文
。面试题目就2道，都是比较常见的题目，在google docs里面写代码。一个题目是关于
穿线二叉树的，另外一个题目是copy a link list with a random... 阅读全帖 |
|
l*****a
发帖数: 559 | 42 来自主题: JobHunting版 - G/F面经 二爷看明白了讲讲。
p1027的第二行有句话看不懂。
"If p is on sweep line z, then q = p."
p是a和b的交点，再加一个endpoint q，岂不是三条线段相交了，和假设不符啊。 |
|
w****x
发帖数: 2483 | 43 来自主题: JobHunting版 - G/F面经
晕， 我连怎么判断线段相交都写不出来 |
|
l***i
发帖数: 1309 | 44 大公司可能好一点，人太多了可以装南郭先生，小公司，比如1000人以下的可能就不好
混了。
我觉得还是像楼上说的推一推，把基本算法都搞搞熟再去吧。不然就出个n个线段相交
的题我就直接挂了。 |
|
w****x
发帖数: 2483 | 45 第一题不需要build interval tree那么麻烦吧， 把所有结点部分启始还是结束混在一
起排序， 然后扫描一遍， n=0, 遇到开始端点 n++, 遇到结束端点 n--, 遇到开始端
点的时候如果n > 0设置那个开始端点对应的线段conflict flag为true |
|
|
g***j
发帖数: 1275 | 47 感觉自己这块很弱，网上资料很乱，请问大家有什么好的资料推荐学习一下吗？特别是
你看过的，觉得很好的，谢谢。 |
|
m******s
发帖数: 165 | 48 greedy
事实上，假设最多overlap的地方被k条线段覆盖，则k个x轴必须且足够。
4. |
|
O******i
发帖数: 269 | 49 面官后来反馈说，the best O(1) solution I know so far is to use a trie
真的能用trie达到O(1)么？如何实现？
*******************************************************************
给定一个大整数N,比如N = 100, 有如下的初始有序序列位于[0, N - 1]之间
[0 1] [4 5 6] [9 10 11] [20] [50] [90] [95 96] [98 99]
请设计一个数据结构保存这个初始序列，然后写一个函数，接受一个input参数x, 满足
0 <= x <= N - 1
1) 假如x在该结构中不存在，出错处理
2) 假如x在该结构中存在，返回x之后第一个不存在的数，并把该数写入结构中
例如
x = 8, 出错，初始序列中没有8
x = 5, 返回7， 序列变为
[0 1] [4 5 6 7] [9 10 11] [20] [50] [90] [95 96] [98 99]
x = 4, 返回8, 序列变为
[0 1] [4... 阅读全帖 |
|
O******i
发帖数: 269 | 50 能给具体的方法么？
感觉我的Bitmap(bit vector)解法，只能保证最坏情形(也就是几乎所有的数都插入数
据结构中)的空间复杂度比普通Hash表更小，但查找下一个数还是O(N), 或许他想要二
分查找的O(logN), 或者还有更巧妙的空间换时间达到O(1), 类似那个栈O(1)找最小元
素？
可能线段或者区间的方法更好，这样连续区段，只需要保存两个端点就可以了，能够省
很多空间，类似合并区间题的思路。 |
|
