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)为第1个区间到第i个区间中的最大不重叠区间个数。
F(i)= Max{F(i-1),1+F(j)},A[j]是1。。。i-1
中结束点t2最接近A[i]的起始点t1并且不要A[i]重叠的区间。 j可以采
用Binarysearchded。
简单DP, 时间复杂度O(nlogn), 空间复杂度O(n)。 |
|
d****n 发帖数: 233 | 47 来自主题: JobHunting版 - F家题请教 这样看来相交可以定义为线段在X轴上的投影相交,并且在Y轴上的投影也相交。 |
|
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)的复杂度。 |
|