r****e
发帖数: 9 | 1 find a Theta(nlgn) algrithm that given a set S of n integers and another
integer x, determines whether or not there exist two elements in S whose sum
is exactly x.
I thought it long time, but still no clue. Thanks a lot. |
|
j*******a
发帖数: 61 | 2 Thanks for all posts. Just want to confirm I understand right, let me repeat
your ideas.
Assume input: 4, -1, 5, 2, 0, -2.
looks for the closest sub array for 3
0 1 2 3 4 5 get sums sort BS for 3
------------------------------------
0 | 4 3 8 10 10 8 n nlgn lgn
1 | -1 4 6 6 4 lgn lgn
2 | 5 7 7 5 lgn lgn
3 | 2 2 0 lgn lgn
4 | 0 -2... 阅读全帖 |
|
g***s
发帖数: 3811 | 3 抛砖引玉一下：
解法一：
这题可以看作是二分图的最大匹配的最小值路径匹配问题。用KM算法可以知道O(N*M)=O
(N^3).
解法二：
分治法。找到两点，把所有点分成两部分，每个部分都用相同多的红点和蓝点。然后对
两部分分治。
如何找到这样的两点（先给一个nlgn的算法）
1. 找x值最小的一个点A（如果有多个x值相同，取y值最小），把它作为其中一点。
2. 把A作为原点。其它所有点对于A（都减去Ax,Ay)，都相当会落入第一和第四象限。
3. 把所有点求tan，排序。
4. 从小到大进行count，一直到找到这么一条边(A->B)。（易知一定存在这么一条边）
f(n) = max{ f(k) + f(n-k) + nlgn } k=1..n-1
f(n) = O(nlgn * n) = O(n^2 * lgn)
改进找B点的算法
3. 建立一最大堆，和一最小堆
4. 轮流从最大堆最小堆来进行查找，直到找到B
f(n) = max { f(k) + f(n-k) + (n + k*lgn)} k = 1..n/2
f(n) = O(n^2)
O(nlgn)感觉很难。 |
|
g****5
发帖数: 1639 | 4 对于无序的数列，O(nlgn)就是平均最快的sort。当然能够达到O(nlgn)的sort算法有很
多。对比其他数量级最快的算法，quick sort比heap sort一般O(nlgn)的系数要小，所
以更快。跟merge sort比，不需要征用O(n)的额外内存，所以空间上更有效。 |
|
x******3
发帖数: 245 | 5 可以用以下算法
1. sort the array // O(nlgn)
2. iterate through the array, for each element x, compute k = y - x, binary
search k in the rest of the array. if
found, return x and k; if not found, repeat step 2 on the subarray without x
// O(nlgn)
总时间复杂度O(nlgn), space O(1)
这道题应该是CLRS上的习题 |
|
r****o
发帖数: 1950 | 6 想了一下，好像可以达到O(nlgn). 假定数组为 a[1]...a[n]。
先排序 O(nlgn)
然后用binary search 找a[i]，过程如下：
对于a[mid],如果a[n]+a[n-1]也比T-a[mid]小，说明a[mid]选值过小，故在右半边继续找a[mid]；如果a[1]+a[2]也比T-a[mid]大，说明a[mid]选值过大，则应在左半边继续找a[mid]，
继续该binary search，一直找到a[mid]，使得a[1]+a[2]<=T-a[mid]<=a[n-1]+a[n]，
然后可以线性查找出i,j，使得a[i]+a[j]=T-a[mid]。
binary search共需O(lgn)步。线性查找O(n)。
总复杂度还是O(nlgn)。
希望大家对我的想法多提意见。 |
|
l*******y
发帖数: 1498 | 7 quick sort时间依赖于pviot，最好情况下才是nlgn，但是有较好的cache behavior.
heap sort 最差情况下是nlgn，但是heap sort 有很多random access，如果数据是从
high latency的设备上读的话会比较慢。
merge sort最差是nlgn，需要额外的空间(上面2个sort都可以in place完成)，也有比较好的cache behavior，还有merge sort更容易parallelize |
|
|
k****n
发帖数: 369 | 9
wrong, can unsorted array merging faster than sorted ones?
I see, I guess you mean kO(nlgn)+kO(n), but actually should be kO(nlgn)+kn(
lgk)
sort k arrays individually, O(nlgn)
divide & conquer, 2n 1st level, 4n 2nd level, ... kn at root,
lgk levels in total O(kn) |
|
h*******l
发帖数: 22 | 10 对静态interval set：（leetcode上的）
排序，nlgn
过一遍， n
动态的（不停有interval 插入）
方法一：
每个新的都插入到正确的位置，lgn
再过一遍，n
结果是n^2 的
方法2：
2.1 假设知道所有end points，比如1--1000000，每个点都是可能的endpoints
根据end point 建segment tree
每个新的插入需要lgn
总共nlgn
2.2 不知道end points
完全动态的segment tree，每次插入需要rebalance （O(1)）
修改union lgn
插入endpoints lgn
总共nlgn
这个就比较复杂了， 感觉面试仅停留于静态的就不错了
|
|
d******v
发帖数: 801 | 11 能会三种写法就不错了，我上次面试给了O(nlgn)O(nlgn)和O(n)的三种方法，面试官说
我们不需要O(n)这种要求太高了，你能就第二个O(nlgn)那种写法优化一下吗？我说再
优化也不会比方法三O(n)好啊，我直接写方法三吧？"不，方法三要求太高了，你看看
方法二怎么优化？"然后就挂了。 |
|
w**********y
发帖数: 1691 | 12 多谢分享.大概做了做..欢迎补充和指正.
- sqrt(i)=?
e^{\pi/4 i} or - e^{\pi/4 i}
- You and me roll a dice,first one gets a six wins. You roll first. what
is the probability of you winning?
P(I win) = P(Y !win and I win) = 6/11
- A stair of n steps. Each time you step up 1 or 2 steps. How many
different ways are there to reach the top? what is the asymptotic limit?
Fibonacci sequence ..limF(n)/F(n-1)==x for n>2, solve x, and F(n) ~ x^{n-1}
- Moment generating function of standard model.
statistic book…
- Write a si... 阅读全帖 |
|
t*******y
发帖数: 637 | 13 第二题应该是6/11吧
能讲讲这个吗? - X1 and X2 are independent random variable with pdf f and g.
what is what is the pdf of X=X1+X2
Jacobian matrix for X1+X2 and X1-X2..
多谢分享.大概做了做..欢迎补充和指正.
- sqrt(i)=?
e^{\pi/4 i} or - e^{\pi/4 i}
- You and me roll a dice,first one gets a six wins. You roll first. what
is the probability of you winning?
P(I win) = P(Y !win and I win) = 5/6*1/6
- A stair of n steps. Each time you step up 1 or 2 steps. How many
different ways are there to reach the top? what is the asymptotic... 阅读全帖 |
|
z***e
发帖数: 5393 | 14 actually don't need to use b-search, you can make decision while sorting.
find a common number, using quick sort, the firt iteration will divide to:
A: array1, array2
B: array1, array2
if (A.array1.size == B.array1.size && A.array2.size == B.array2.size)
recursively do this until the array size is different.
if A == B, the complexity is at most O(nlgn) (quick sort);
otherwise it's smaller.
so the total complexity <=O(nlgn) |
|
H*M
发帖数: 1268 | 15 given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
想不出什么天外飞仙的算法达到O(nlgn)
谁有点idea? |
|
k***e
发帖数: 556 | 16 你这样是n^2
更好的是nlgn 有兴趣你可以wiki一下
你运气不错
因为就在前面有人同样的问题 给出n^2没给出nlgn都被拒 好像是ms吧 |
|
a*u
发帖数: 97 | 17 给一个string建立suffix array，然后sort这些substrings，复杂度是多少？O(nlgn)
or O(n^2lgn)?
比如 String "bananna", size n = 7
suffix array
{
banana
anana
nana
ana
na
a
}
after sorting
{
a
ana
anana
banana
na
nana
}
for a string size n, creating the suffix array is O(n), sorting is supposed
to be O(nlgn), but I somehow feel it is O(n^2lgn), since the comparison
between two substrings are O(n).
Where did I miss? |
|
o********r
发帖数: 79 | 18 我说一个思路。
不过不是nlgn啊，应该还是N^2
1.sort, nlgn
2. assume a<=b<=c, a+b+c = sum;
这样 a<= sum/3;
c>= sum/3; |
|
c********g
发帖数: 13 | 19 我的教授说LIS能优化到O(NlgN),但他说的那段我没听懂，后来知道考试不考也就没细
想了。不过我猜这个也应该能优化到O(NlgN) |
|
m*****g
发帖数: 226 | 20 我的理解，big O 是upper bound
theta O 才是上限和下限
所以O(n+nlgn) = O(nlgn)
对。那个应该是nlgk。这个是我不仔细。 |
|
r****o
发帖数: 1950 | 21 试着答一下。
就顺序比较吧，每个比较k次，复杂度O(kn)
可以排序，或binary search，或用min heap，复杂度分别是O(nlgn),O(nlgn),O(klgn)
先找出第k1大的元素，再找出第k2大的元素，介于这两者之间的元素就是所求的元素。
复杂度O(k2 lgn)
binary search的方法可能不行了，用排序和min heap应该还可以。 |
|
i****d
发帖数: 35 | 22 借助sum数组
sum[i] = SUM{ a[i] | i = 0~i}
1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
i的值。这样遇到相同的就说明sum[i] == sum[j], j
conflit。O(n)
2. 1)还是计算sum[i]。O(n)
2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
index数组了。 O(n)
4) i = 0~n-1, 对于每个i, 在排序好的sum[i]数组中找 sum[j] 正好 <= sum[i]-
k。那么以a[i]为终点的满足条件的subarray最长的长度就是 i-min_index[i]。通过一
个临时变量max记录并更新这个长度，遍历完就可以知道最大长度了。
总体可以到O(nl... 阅读全帖 |
|
m******m
发帖数: 19 | 23
借助sum数组
sum[i] = SUM{ a[i] | i = 0~i}
1. i= 0~n-1，计算sum[i]的同时，利用hash_map，以sum[i]为key，记录下sum[i] 和
i的值。这样遇到相同的就说明sum[i] == sum[j], j
conflit。O(n)
2. 1)还是计算sum[i]。O(n)
2) 排序，排的时候以sum[i]为key，同时带上下标i。第3)步有用。O(nlgn).
3) 遍历排序后的sum[i]。创建数组min_index，min_index[i] 是 比sum[i]小的元
素中的最小的下标。通过一个临时变量记录并更新这个下标，遍历一遍就可以建立min_
index数组了。 O(n)
4) i = 0~n-1, 对于每个i, 在排序好的sum[i]数组中找 sum[j] 正好 <= sum[i]-
k。那么以a[i]为终点的满足条件的subarray最长的长度就是 i-min_index[i]。通过一
... 阅读全帖 |
|
g***s
发帖数: 3811 | 24 ＊步骤２需要改成如果已经参加过一次，取最后一天。否则取两天。
否则，反例 （１，２）（２，４）
* 单步步骤３不能在O（１）时间内完成。但需要证明所有第３步的总时间可以在总时
间O（n）时间内
完成(具体算法也稍微麻烦一些)。
不过，既然排序已经用了O（nlgn），这里单步简单的用O（lgn）也就行了。总时间
反正都是O
（nlgn）.
除非，参加的人数n＞＞总天数。那么，可以找到排序的算法是O（n）。那么这题总时
间复杂度才可能是
O（n） |
|
g***s
发帖数: 3811 | 25 不明白会了O(n)为啥还要找O（nlgn）的？除非你是老师，要教学生。
否则，你就用O（n）的算出来，得到结果你再做一遍无用的排序，这样就把算法拉到
nlgn了。 ：） |
|
m**q
发帖数: 189 | 26 假设每个任务开始结束为start[i], end[i],对应的权值为a[i],
先把数组按start[i]排序，设从i...n的工作中，总的最大权值为f[i],则：
f[i] = max { f[i+1], a[i] + f[k]: k是i之后和i不冲突的第一个元素 }
排序O(nlgn),遍历a[]数组O（n),对每个元素i用二分法找对应的k，O(lgn),
总复杂度为O(nlgn)。
这个方法对不？
O( |
|
m**q
发帖数: 189 | 27 我的思路和你类似，不过我觉得每取完一个元素后要把这个元素排除，
这样才能保证第i个被选择概率和score(i)成比例
最简单的实现是每次把取过的元素swap到数组前面，复杂度应该是O(kn)
一个可能的优化的方法是组织成一个顺序统计树，每个节点不是存它的子树的
子节点数，而是存它的子树的score的和，这样每次生成随机数可以用
O(lgn)找到对应节点，选k个数复杂度为O(klgn)。生成树应该需要O(nlgn)。
总复杂度O(nlgn)，如果k是O(n)的话这个方法更优
求指正
是( |
|
m**q
发帖数: 189 | 28 思路大概是这样的
因为所有矩形的底边都在x轴上，把每个矩形的左上角和右上角的坐标记录到
一个数组中，每个元素是 pair, int start>，每个矩形
在数组中有两个元素，代表左右两条边，start为1表示开始，为0表示结束。
比如，一个矩形的x轴开始坐标为x1，结束坐标为x2，高为y，则在数组中它
对应的两个元素是 <, 1>, <, 0>
可知n个矩阵生成的数组中有2n个元素，然后sort数组，复杂度O(nlgn)
然后用sweepling line algorithm，扫描数组，用一个BST记录当前
overlapping的所有矩形。
遇到矩形的左边时(start==1)，判断边的高度（即当前y值）是否大于BST中
的最大高度，大于则记录两个点，（当前x值，BST中最大高度），
(当前x值，当前y值)。把当前y值放入BST
遇到矩形的右边时(start==0),把当前y值从BST中删除，如果BST有相同值只删除
一个。判断边的高度（即当前y值）是否大于当前BST中的最大高度，大于则
记录两个点，（当前x值，当前y值... 阅读全帖 |
|
s****j
发帖数: 67 | 29 平面最近点对那题，提供一种方法供参考，该方法看似复杂度o(n^2)，但实际使用中几
乎是o(n)（不算nlgn排序的预处理）。主要是利用了三角形两边之差小于第三边的性质
，大大减枝。另外该方法实现简单，比传统o(nlgn)的实现简单很多也直观很多。
代码如下：
#include
#include
#include
#include
#include
using namespace std;
const int maxn=100005;
const double eps=1e-8;
struct Point
{
double x,y,dis;
} p[maxn];
int n;
bool cmpp(const Point &p1,const Point &p2)
{
return p1.dis
}
void solve()
{
sort(p,p+n,cmpp);
double ans=1e18,now;
int i,j;
for (i=0;i阅读全帖 |
|
m**q
发帖数: 189 | 30 第一题可以用部分和的方法，先算出a[0]~a[i] (0<=i
放在数组b[]中，同时把对应的i值记录下来，就是说b数组每个元素是一个
结构，包含a[0]~a[i]的部分和以及对应的i值；然后根据部分和的值sort b数组，
用两个指针指向b数组开头，递增前指针直到前后指针指向的元素的部分和字段的
差值大于或等于MaxSum，然后递增后指针直到两指针指向元素的部分和字段的差
小于或等于MaxSum，在此过程中只要前后指针指向元素的部分和字段差值小于
等于MaxSum时就计算前后指针指向元素的i值字段的差值，并更新最大差值。
算部分和O(n), sort b数组 O(nlgn), 前后指针遍历数组b O(n)，总时间O(nlgn)。 |
|
z****u
发帖数: 104 | 31 先排序，时间 O(nlgn)，空间 O(n) 都可以做到
排序之后，再搜索可能的 pair，从首尾两端扫描，永远不用回头扫，所以时间应该是
O（n）
这样总共的时间是 O(nlgn)，空间 depends，但不会超过 O（n) |
|
m***o
发帖数: 41 | 32 排序o(nlgn)+搜索0(n)= o(nlgn)? 好像不是很优的办法吧
是 |
|
H***e
发帖数: 476 | 33 sigh
"build heap O(n), 他非说是O(nlgn)"
碰到这种真的没有办法勒， 只好跟他详细解释下，什么情况下（元素已知）可以o(n),
然后表示理解他说的nlgn |
|
H***e
发帖数: 476 | 34 有很多题都是这样的吧
比如那个longest increasing sequence问题 nlgn
能当时想出来我觉得都是天才了
可是有些面试官就是要求nlgn |
|
b*****n
发帖数: 482 | 35 my 2 cents:
It seems O(n) is not possible, should be at least O(nlgn). Worst case
scenario, all the numbers belong to their own group, meaning no two numbers
are consecutive. Then each number has to be compared with existing group to
find out whether it belongs to them or has to be in a new group of his own.
Anything based on comparison like this has a low bound of O(nlgn). Of course
, if the storage can be O(Max), then O(n) time can be realized, similar to
the counting algorithm. |
|
a******a
发帖数: 2646 | 36 应该有nlgn 算法
struct person
{ start time
end time
}
读入person
按start time binary排序，是 nlgn
如果重叠，修改
struct, 另
person.start =min
person.end =max
合并成为一个记录。 |
|
m***n
发帖数: 2154 | 37 2个的话，直接hashtable O(N)，先排序，然后再left--> , <---right 操作O(N)+O(
NlgN)
3个的话，直接先排序NlgN, 然后求a+b=-c 对每一个元素做a+b=x操作 N^2
4个的话，也是排序，然后a+b+c=-d ,用前一步算法 N^3
.... |
|
h********o
发帖数: 14 | 38 我做的跟 3sum 是一个复杂度 O(n^2); 做法也跟 3sum差不错。
1.先sort 数组S，O(nlgn);
2. 使用三个下标 i (当前下标) f(头下标) t(尾下标)
i 从0 到 n-1 遍历 // n 是数组长度
对于每一个i， 设置 f = i+1, t = n-1,
计算 sum = S[i] + S[f] + S[t], 如果比之前的sum更接近，更新。
然后，如果sum 比target 小 ， f++， 否则 t--
对于每一个 i ，以上操作循环至 f>= t, 所以每一个 i 要遍历数组一遍
最终， 第2步的复杂度是 O(n^2)>O(nlgn), 所以这个算法复杂度也是O(n^2) |
|
D**********d
发帖数: 849 | 39 来自主题: JobHunting版 - G/F面经 可以先按 x axis 排序(假设升序)，然后查 y 是否有降序的。
总共是 O(nlgn) + O(n) = O(nlgn) |
|
b***u
发帖数: 61 | 40 算法书上讲的
h >= lg(n!)
>=lg((n/e)^n)
=nlg(n) - nlg(e)
=omega(nlgn)
所以对于任何一个基于比较的排序算法run time至少是nlgn |
|
A******g
发帖数: 612 | 41 in place 删除 string里重复的字符。
书上给的算法是3 pointer, O(N^2)
我想，如果先in place quick sort, O(NlgN) 然后用delete duplicates from sorted
array 的方法 O(N)
是不是可以做到O(N+NlgN)呢？ |
|
|
c*********m
发帖数: 43 | 43 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度o(nlgn).
这题什么思路呢？interval tree? nlgn的想法想不到啊。 |
|
D**********d
发帖数: 849 | 44 我想到的是 O(nlgn) 区间合并问题：
1. sort 所有端点 O(nlgn).
2. 扫描所有端点一次 O(n) 左正右负. |
|
s********0
发帖数: 34 | 45 一个数组只有1，0 元素，找出所有连续区间的数目， 满足该区间1的个数>=0的数目。
比如a:[1, 0, 1, 0, 0, 1]
结果为11: (3+4+1+2+1)
[1], [1], [1], =>3
[1, 0], [0, 1], [1, 0], [0, 1], =>4
[1, 0, 1], =>1
[1, 0, 1, 0], [1, 0, 0, 1], =>2
[1, 0, 1, 0, 0, 1] => 1
要求复杂度 nlgn.
O(n^2)的复杂度比较容易想，0置换成-1，然后求前缀和数组sum。
nlgn我是这么想的：
还是0换成-1，还是求前缀数组，然后对每个sum[i]求 前面小于等于它的个数，这步可
以二分。
比如某一步的时候 sum = 0 有1个， sum = 1 有2个， sum =2 有3个，
则sum <= 0: 1个, sum <= 1: 3个, sum <= 2: 6个 这个是单调递增的
维护这个单调队列 可以用树状数组
觉得实现起来有点麻烦，请教有别的方法没？thanks |
|
o******1
发帖数: 1046 | 46 曼哈顿距离跟是不是整数无关，只跟相对位置有关。这类题一般还要假设没有相等的坐
标。
如果是一维的，最优算法是O(N)。因为不需要sort整个数列，只要找到第(N+1)/2个数
（if N is odd），或者找到floor(N+1)和ceiling(N+1)（if N is even）。
但是如果是2维或者更高维的，最优算法应该是O(NlgN)，因为不能事先确定最小距离点
的位置，所以必须把两个或者更多个维度的距离加起来，每个维度的距离的复杂度都是
(NlgN)。
要是面试官跟你说二维问题的复杂度也是O(N)的话，一定是忽悠你了。 |
|
c*****m
发帖数: 1160 | 47 比如说，一段程序，没有调用子函数，有一个循环 for i=1 to 1000，那么复杂度应该
是 O(1)啰；
如果循环是 for i=1 to n, 那么复杂度应该是 O(n)？
现在问题是：在这个循环里（没有子函数）用了一个dict , python里的词典：
for i=1 to n
value=d[key]
这个dict的查询, 不是数组的直接access，应该最快也是sort算法的 O(nlgn)吧？ 那
么这段程序是否成了 O(n*nlgn)? |
|
i**w
发帖数: 71 | 48 背景:fresh physics PhD
还没offer,但年前基本上不会再折腾了。
有重复。基本上都是很标准的题。
简单的题如果人家想问倒你也是很容易的。
面试书recruiter推荐
1) Mark Joshi: "Quant Job Interviews: Questions and Answers". I have
heard very good things about this book.
2) Xinfeng Zhou, "A Practical Guide to Quantitative Finance Interviews"
个人觉得非常有用， 大部分问题都在这两本上。
算法，C++, stochastic calculus 就看比较标准的几本。
- sqrt(i)=?
- You and me roll a dice,first one gets a six wins. You roll first. what
is the probability of you winning?
- A stair of n steps. Each time you st... 阅读全帖 |
|
H*******1
发帖数: 242 | 49 G(V,E) where |V| = n as points, E = {(u,v)| dist(u,v) <= k}
Now what you are looking at are matchings, so just apply Edmonds' algorithm.
O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
improve the algorithm, google or wait till DaNiu post an answer.
For finding the smallest k, there are probably smarter ways, but a 糙快猛
practical solution could be:
Find d = closest pair distance O(nlgn)
Find D = farthest pair distance O(nlgn)
Binary Search on [d, D] O(lg(D-d) * \sqrt(V)... 阅读全帖 |
|
g*******y
发帖数: 1930 | 50 Google » Algorithm
Algo on November 09, 2009 | Question #245697 (Report Dup) | Edit | History
given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
想知道这个是否有可能做到。我怎么觉得做到O(n^2)就没法提高了 |
|
