O******i
发帖数: 269 | 1 二爷的意思是用平衡的二叉排序树，比如AVL或者红黑，然后每个节点是一个线段(可以
用两个端点表示)么？ |
|
m******s
发帖数: 165 | 2 插入8时应该merge吧。。。
可以做到O(n)空间O(logn)时间，其中n是当前线段数<=N/2 |
|
w****x
发帖数: 2483 | 3 那个是interval tree, 和常说的segment tree不大一样。
好像只能返回一个相交的线段 |
|
f*******t
发帖数: 7549 | 4 C/C++性能稳定，用于竞赛比较合适。我用Java写了一个线段树的题，算法照搬网上的
解题报告，提交上去就是TLE。
生活中的问题，至少图形学全靠C++，还是用途很多的。 |
|
i******r
发帖数: 793 | 5 我的算法是：
第二题二分匹配，网络流也行
第三天题求矩形并的面积，但是要线段树，否则估计超时
我反正挂了，第三题犯二没提交成功 |
|
n****r
发帖数: 120 | 6 这题对ACMer来说，立马就被秒了，业余选手咋办呢？默背很难吧 |
|
|
r**h
发帖数: 1288 | 8 O(n log n)的方法需要使用线段树
我觉得面试能用O(n^2)就不错了 |
|
b*****n
发帖数: 143 | 9 我的理解是，线段树只能保证新的长方形开始或者结束的时候logn的时间更新，但是计
算每一段x包含的面积的时候，最坏情况下不还是需要O(n)吗？ |
|
r**h
发帖数: 1288 | 10 是啊，都属于线段树的典型应用
根据我搞ACM的同学说，这些属于ACM的水题。。。T T |
|
|
|
c*********m
发帖数: 43 | 13 你能详细说下嘛？没太明白这个思路啥意思，真写代码肯定没法用线段树啦啊，谢谢! |
|
j******i
发帖数: 244 | 14 DP其实只是一种解题思路，把一个问题的最优解表达成最优子问题的解，这样其实就建
立了各个问题和其下子问题之间的依赖关系。你把每个问题想象成一个顶点，依赖关系
想象成顶点之间的有向线段，那么整个问题其实就是对一个DAG从某一个起点的遍历。
用recursion+memoization是更直观的DFS遍历，而将DAG做toposort以后确定了各个顶
点的前后关系，从后往前iterate，计算量是完全一样的，但是写起来比较难理解，不
过节省了stack空间。 |
|
g***9
发帖数: 159 | 15 RT.期待2爷出手.拜谢了~~
另外,好像区间的题目都跟线段树有关系是么? 求指点 |
|
j******i
发帖数: 244 | 16 来自主题: JobHunting版 - G新鲜面经 1.2可以用toposort做吧。每个位置代表一个节点，大于号代表有向线段。整个图肯定
是无环的。做完拓扑排序之后按照节点的排序顺序从大到小填数就行了，O(n)复杂度。 |
|
l*n
发帖数: 529 | 17 两个都是million级别的话，要么指望有nlogn的解法，要么就只能map reduce了。
如果点和球分布均匀的话，可以考虑用interval sorting的办法，然后x、y、z三个维
度上都和代表球的线段有重合才计算该点是否真的在球内。
, |
|
n*****f
发帖数: 17 | 18 把每条线段拆成进、出两个事件，排序后扫一遍。维护一个可以删点的大顶堆，遇到进
事件就insert，遇到出事件就delete，每两个事件之间堆的top就是这个时段的最大值。
对于delete操作，一种偷懒的做法是先不删它，每次取top的时候判断一下top元素是否
已经被删掉了，如果是就pop。这种方法是不会降低worst case的复杂度的。正规的方
法，也就是要删中间节点，就需要多维护每个节点的编号，以及每个编号的位置，每次
堆sink和swim都需要做相应的修改。删除时把最后一个结点移到被删的节点位置，然后
sink或swim。 |
|
n*****f
发帖数: 17 | 19 把每条线段拆成进、出两个事件，排序后扫一遍。维护一个可以删点的大顶堆，遇到进
事件就insert，遇到出事件就delete，每两个事件之间堆的top就是这个时段的最大值。
对于delete操作，一种偷懒的做法是先不删它，每次取top的时候判断一下top元素是否
已经被删掉了，如果是就pop。这种方法是不会降低worst case的复杂度的。正规的方
法，也就是要删中间节点，就需要多维护每个节点的编号，以及每个编号的位置，每次
堆sink和swim都需要做相应的修改。删除时把最后一个结点移到被删的节点位置，然后
sink或swim。 |
|
C******w
发帖数: 23 | 20 10月17日，第一轮电面：
第一题：上海的电话isTree(vector >& edges); (离散化+dfs判环
判联通)
第二题，
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
y2)
inclusive, and there is an infinite stream of such 2 types of
operations which have to supported. How would you store the values for
efficient updates and retrievals ? （二维线... 阅读全帖 |
|
n****e
发帖数: 678 | 21 楼主能说说第一轮店面的第二题吗？
能展开说说如何用二维线段树来做吗？ |
|
C******w
发帖数: 23 | 22 10月17日，第一轮电面：
第一题：上海的电话isTree(vector >& edges); (离散化+dfs判环
判联通)
第二题，
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
y2)
inclusive, and there is an infinite stream of such 2 types of
operations which have to supported. How would you store the values for
efficient updates and retrievals ? （二维线... 阅读全帖 |
|
n****e
发帖数: 678 | 23 楼主能说说第一轮店面的第二题吗？
能展开说说如何用二维线段树来做吗？ |
|
b*****c
发帖数: 1103 | 24 segment tree就行了，就是线段树。
n个插入最多有2n个点，这个树最大是6n个点吗 |
|
b*****c
发帖数: 1103 | 25 online算法就不能线段树。
直接上stl::map 直接就是排序的。
代码晚点写。 |
|
b*****c
发帖数: 1103 | 26 segment tree就行了，就是线段树。
n个插入最多有2n个点，这个树最大是6n个点吗 |
|
b*****c
发帖数: 1103 | 27 online算法就不能线段树。
直接上stl::map 直接就是排序的。
代码晚点写。 |
|
b********6
发帖数: 97 | 28 背景：本科生物，统计master + 9个月工作经验
结果: offer: amazon, facebook, linkedin, google
Withdraw了ebay的onsite，别的好多电面都fail或者没有消息
电面：
Amazon两个：面得太早，具体想不起来了，code题不多。问怎么从某种格式的log file
里抓出想要的信息，简单的regular expression 和perl scripts, 问一些如果server
有问题怎么trouble shooting的开放问题。
Linkedin 两个：
1 binary tree level order traversal, leetcode原题
2 pow(x,2) leetcode原题
3 判断一个string表示的数字是否valid，类似leetcode Valid Number原题，一些具体
要求要和面试官讨论后确定
4 permutation I and II leetcode原题
Facebook一个：
1 reverse linkedlist (这个我无话可说)
2 decide whether tw... 阅读全帖 |
|
n*****f
发帖数: 17 | 29 恭喜LZ！！！
题目不错，写些思路，如果有问题或者更好的思路，欢迎各位大牛指点
facebook
2. 先比较两个字符串的长度。如果相等，正向和反向分别求最长公共前缀，之和大于
等于串长-1就是similar；如果长度相差1，正向和反向分别求最长公共前缀，之和大于
等于短串的长度就是similar；否则不是similar。前两种情况可以合并一下，更简单，
O(n)
google
1. 维护两个指针从两头向中间扫
2. 每个function_name记录call的次数和总的duration time
3. parent -> child建边，入度为0的点是root，从root出发BFS或DFS
4. 同上
5. 同上
twitter
2. trie
ebay
1. 先git log找到相应时间段的commits，再用git diff找出时间段前后两次修改了哪
些file
3. ac自动机
walmartlab
1. 先看最大值能否正数，找最大的三个正数或绝对值最大的两负一正；如果不行，看
数组里有没有0；还不行就找绝对值最小的三个数
2. ^(https?:\/\/)?([\da-z\.... 阅读全帖 |
|
p*****3
发帖数: 488 | 30 啥skyline, area of overlapped rectangles, 判断二维线段相交，从上往下看color
啥的，都是一类问题 |
|
T*******e
发帖数: 4928 | 31 你好像没看懂题，把简单的BST想成线段树了。
lz答得是对的。 |
|
s******t
发帖数: 229 | 32 二维线段树，建树O(x*y),query O(logn)
如果是rotate rectangle 或者坐标是double什么的，我就不知道了 |
|
f******h
发帖数: 45 | 33 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
i*********e
发帖数: 9 | 34 Google(summer intern)
1.给你一个two dimensional array, array的元素是0 或者1。问能不能找到一个矩形
，矩形的4个角都是1.
leetcode里面有类似的题，我给了类似的答案，复杂度是O(n^3)，感觉面试官不是很满
意。不知道有没有复杂度更少的算法。
2.有高矮不一的一群人，随机排列。排完之后每个人记下比自己前面比自己高的人的数
目。之后把队打乱，
跟据高度和比自己高的人的数目还原原来的队列。
我给了一个O(n^2)的算法，在算法群里讨论之后有牛牛说用线段树可以实现O(nlogn)的
算法。
Bloomberg:
1. 给一个数组： 6， 3， 10， 5， 16， 8， 4， 2， 1
找出这个数组的顺序。写一个程序，input是数组里的一个数，Output是从这个数开始
的整个数组。
2. 实现一个BFS算法。
3. 一个数组，里面有成对出现的数，也有单个的数，把单个的数找出来（leetcode原
题）。
4. 一个公司有好多员工，员工之间的关系储存为（employee ID, manager ID) 这样的
pair。要求写一... 阅读全帖 |
|
|
|
f***s
发帖数: 112 | 37 感谢国人大哥给积极反馈
题目如下，一个m,n 矩阵 每一行升序排列，每一列同样升序排列。
要求找到一个数字是否在矩阵中，注意并不保证每一行头元素高于上一行末元素。
1 2 3
2 3 4
3 4 5
简单解 O(min(m,n)*log(max(m,n)))
我后来想的进一步思路，在正对角线上二分都找到i，i+1的线段，从传递性知道 i上面
包括
i的长方形能都小于所求，i+1下面包括i+1都大于所求。譬如找2， 现在正对角线找到
1， 3， 问题转化为在 1 2 ， 2 3 找 最差情况每次排除一半搜索空间。 |
|
|
|
|
d***j
发帖数: 593 | 41 基本sweep line的做法。 好好看看clsr上里面找任意两个线段是否相交的算法， 稍微
修改就ok了。没记错的话这是其中一个习题。 |
|
s*********1
发帖数: 16 | 42 非牛说说自己的看法。
这道题应该是一个很典型的动态规划应用题。
因为老鼠和洞都在一维直线上，
不妨把问题极简化为：
老鼠是N个不同的整数，取值范围是0到正无穷（把直线处理成射线，或者0到某个定值
，处理成线段）
洞也是M个不同的整数，取值也是0到正无穷。
现在就是，从M个数种取N个值，跟N个老鼠的数一一匹配，然后把匹配以后每对数（一
个老鼠一个洞）的差的绝对值相加，求最小值。
那么我们以N个老鼠，每只老鼠为一轮loop做动态规划。
假设第一只老鼠坐标2，那么他找到坐标为3的洞为最小距离。
好，我们认定第一轮结果，然后，我们把第二只老鼠再带进来，假设第二只老鼠坐标为
5，而他找到最近的洞为坐标6.那么这次结果没有冲突，进入下一轮。但是，如果第二
只老鼠坐标为3，那么冲突产生。所以要重排。
以此类推产生动态规划。
这是个最简单的线性动态规划了吧？
这题还有个捷径，就是最左端坐标的老鼠找的洞不会影响最右端老鼠找的洞（因为距离
最远），所以可以从两端向中间进行动态规划。
好好把动态规划看看，然后有队列和散列表有基本知识，就能做出这道题了。 |
|
g*******h
发帖数: 31 | 43 第二题的标准做法其实应该是线段树, 上班时间是1..T
把所有人的工作时间段插进去O(nlogT)
查询时间是O(logT) |
|
y****2
发帖数: 1017 | 44 来自主题: JobHunting版 - F家题请教 dp O(n2)或者O(n3)都可以做
注意这道题，线段的2个端点都在单位圆上。 我们只要对端点排序。 然后，只要x1
dp[i][j] = max(1+dp[start+1][end-1] +dp[end+1][j]
for start in range(i+1, j) ) |
|
z***e
发帖数: 58 | 45 来自主题: JobHunting版 - F家题请教 LIS 问题，先按照min(p1,p2) 排序，where p1 p2表示线段端点的极坐标的那个角度。
然后就是就是经典的LIS问题了，dp[k] = max(dp[j] + 1) where j < k && seg[k].p2
> seg[j].p2 if seg[k].p1 and seg[j].p1 are selected to sort.复杂度O(n2) |
|
d****n
发帖数: 233 | 46 来自主题: JobHunting版 - F家题请教 longway2008 was on right track at the beginning:
首先把(x,y)坐标转换成极坐标, 每个点用一个角度t来表示就可以了。每个线段就可
以表示成(t1, t2),
这样一来， 我们可以得到n个区间。将这些区间按t2排序,得到新的数组A。
问题变成从A中找最大的非重叠区间。
设F(i)为第１个区间到第ｉ个区间中的最大不重叠区间个数。
Ｆ（ｉ）＝ Ｍａｘ｛Ｆ（ｉ－１），１＋Ｆ（ｊ）｝，Ａ［ｊ］是１。。。ｉ－１
中结束点ｔ２最接近Ａ［ｉ］的起始点ｔ１并且不要Ａ［ｉ］重叠的区间。 ｊ可以采
用Ｂｉｎａｒｙｓｅａｒｃｈｄｅｄ。
简单ＤＰ， 时间复杂度Ｏ（ｎｌｏｇｎ）， 空间复杂度Ｏ（ｎ）。 |
|
d****n
发帖数: 233 | 47 来自主题: JobHunting版 - F家题请教 这样看来相交可以定义为线段在X轴上的投影相交，并且在Ｙ轴上的投影也相交。 |
|
e********2
发帖数: 495 | 48 来自主题: JobHunting版 - F家题请教 我们学校的DP练习题：对所有线段的2个端点分别排序，然后找两个排好续的最大公共
子序列LCS. O(N^2) |
|
w***w
发帖数: 84 | 49 DP 其实就是递归。 设c(i,j)是从i-th cut 到j-th cut的线段的最小cost, 就有递归
式，c(i,j) = min_{i
不能直接递归去解，否则会指数爆炸。DP 的trick就是递归过程中记住所有见过的解，
每次递归先去查解是否已存在。或者是通常看到的递推的自底而上的填表式的解法。
至于Huffman编码，假设题目是切出要求长度的一些木块但并不限定order的话，这样你
可以把长度看成是概率 （设木板总长是1)，那么这里的cost定义就等价于平均码字长
度, 因为每一小段contribute的cost就是把它切出来需要的cut数。 |
|
o***c
发帖数: 32 | 50 明显不对，ex: 3 5 1 4 2
应该是使用点树，线段树或树状数组做才能保证O(nlogn)的复杂度。 |
|
