c*****t
发帖数: 1879 | 1 Assuming this "set" is randomly ordered and no constraint on the algorithm.
a. O (n). Has to spend O (n) time to scan. Sorting 3 numbers is O (1).
So overall O (n).
b. O (nlogn). Getting k largest numbers from n is O (n). But sorting
these numbers using comparison only is O (nlogn). So overall O (nlogn).
c. O (n). Finding these k numbers would take O (n) time. Sorting these
numbers should take O ( log n * log log n ) < O ( log^2 n) < O ( n).
So overall is O (n).
of
(a
for
al |
|
z****c
发帖数: 602 | 2 One idea to solve 1:
Add horizontal intervals and vertical intervals into two interval trees. (
nlogn)
Add the top edge and bottom edge coordinate of cards into an array, sort it.
then you have 2n coodinates and 2n-1 intervals.(nlogn)
Do the same to left and right edge. (nlogn)
All horizontal interval and vertical interval will divide plane into (2n-1)(
2n-1) sub regions.
for each sub region, query two interval trees and find intersection in the
results. You can use a map to find the intersectio... 阅读全帖 |
|
m******t
发帖数: 635 | 3 这个人是真牛，没他的话，就没有V8了，没有node.js了，javascript也就还在前端打
酱油
同样的GOOG内部的两个家伙搞Unladen Swallow，号称要将cpython加速5倍以上，结果
悲剧，Facebook那几个PHP改进好像评价也不高，和v8比基本就是玩票的。
如果用算法复杂度来评价人牛的程度的话，普通级是O(n^2)，小牛级O(nlogn)，中牛级
O(n)，大牛级O(logn)，巨牛级O(1)。这家伙至少是O(logn)的，那几个折腾Python和
PHP优化的估计是O(nlogn)。
几个动态语言发明者比如Perl, Python, Ruby之类的应该有O(n)，javascript的发明者
再次些O(nlogn)。搞笑一把，如果要啃类似V8这种硬骨头的活，至少需要O(n)级别才可
能成功，小牛级别的基本都是炮灰。 |
|
l*******s
发帖数: 1258 | 4 说实话，我觉得这个没有必要上cluster和hadoop，有点太复杂了。
简单的方案反而更适合。
这不是个machine learning问题，而是个merge sorting问题。有可能我理解的不透彻
，纠正我。
从n个点中，找出top m个跟给定点距离最近的点。这就是个多路归并加堆排序啊。
单线程思路：
建一个Heap,size为m，然后就遍历数据集，把一个个点扔到Heap里排序，等遍历完了，
Heap里面的就是你要的KNN。复杂度为 O(nlogn)
多线程思路：
把数据集分成若干份，比如10份，把每份按照单线程思路进行堆排序，然后你会得到10
个size为m的heap，然后就是10路merge sorting。复杂度为O(nlogn/10) = O(nlogn)
具体实现：
python我不知道。Java里面直接用PriorityQueue这个class即可。
当然了，你要是足够自信，干脆自己实现一个heap，主要是heapify那块少难点。
多线程部分，python我也不大清楚。java的话，就用现成的线程池好了，省得你自己去
实现， java.util.concurrent... 阅读全帖 |
|
发帖数: 1 | 5 当然是做梦
美元收缩全球泡沫都在破裂
[在 nlogn (nlogn) 的大作中提到：]
:你是说涨回去是做梦？
:<br>: 大过节的别做梦了
:<br>: [在 CatchGodLine (捆仙绳) 的大作中提到：]
:<br>: :走着瞧
:<br> |
|
m*****f
发帖数: 1243 | 6 经典题稍微变化下题目太多了， 比如LIS现在是O(nlogn)了， 问LCS怎么O(nlogn)，
也很容易考到
能,
怎么 |
|
k***e
发帖数: 556 | 7 I just doubt whether step 4 can be done in nlogn
it is true that the key are sorted. however, the idx corresponds to the key
has no order. Thus you may need to take linear time to find the
corresponding min idx.
I thought I get the nlogn and later found it is wrong ... |
|
h*******x
发帖数: 12808 | 8 第一题，排序一下，是nlogn，然后用n次找两个数和为T-n3的算法，但是这样是n^2啊
？谁知道nlogn的啊
up
elements
O( |
|
f***n
发帖数: 117 | 9 对，我这个肯定是n^2
我知道有nlogn但我实在是想不起来，很久很久没做类似的东西，知道有nlogn也写不出
来 :(
我主要是运气好 |
|
l******o
发帖数: 144 | 10 比如n个数unsorted，有n！种可能，难道find a target value需要
log(n!)=nlogn的时间么？显然O(n)就可以了。
n^2*log(n^2)-n^2-n*(n*logn-n)=n^2*logn
我没有看出来多少种possibility和需要多少复杂度有什么关系。不要把sort的分析方
法硬套在这里。
n^2 numbers put in n rows, each row sorted,
you have altogether (n^2)!/[(n!)^n] possibilities,
is it Log >= nlogn ??? I think Sterling's formula
should easily confirm this? |
|
e**********6
发帖数: 78 | 11 有一个解不知道对不对。。。
首先排序
i=0,j=length of array;
x=sum-array[i]-array[j]
find x between i and j using binary search
然后如果第一次二分查找判断出array[middle=(i+j)/2]比x小，且没找到x，下一次就i
++（因为需要更大的值）；反之则j--。
重复以上步骤。
排序nlogn，从i++或者j--遍历是n，然后每次遍历会进行二分查找为logn。结果就是O(
nlogn) |
|
u**s
发帖数: 50 | 12 This method looks like O(nlogn).
However, when you code it, you will notice that dedup is a little bit
annoying.
If you create a bitmap/boolean for n^2 and init to false, then this is
already n^2. Of course, you can use other hashtable to solve this, but just
looks ugly.
If you ignore this issue, then you can say this is O(nlogn) ... |
|
y*********e
发帖数: 518 | 13 O(nlogn):
qsort 和 mergesort 都可以达到O(nlogn)，但是 qsort 的常数因子比 mergesort 低
很多。所以，一般情况下 qsort 会更快。
O(n^2):
虽然 qsort 的最坏情况是 O(n^2)，但是要达到这个最坏情况不容易。对于实现的较好
randomized qsort，达到这个最坏情况的几率接近于 1 / n^logn。这个数值是非常低
的。
stable vs unstable:
通常 qsort 的实现是 unstable的，mergesort 的实现是 stable 的。
还有一点，qsort 一般是 inplace 的，mergesort 一般的实现不是 inplace 的。
random access:
qsort 要求可以对排序对象进行 random access。对于排序主内存中的 array 就很实
用。但是，遇到排序的对象不支持 random access，那么 qosrt 就不行了。比如排序
linked list，或者做磁盘文件排序。。利用这一点，可以很容易的用 mergesort 实现
并发排序。 |
|
x*****p
发帖数: 1707 | 14 来自主题: JobHunting版 - 再问一道题 1. Find max and min in O(n) time
2. Use binary search to find some x (may not be in the file), such that the
number of integers <= x is the same or 1 difference as the number of
integers >x. It takes O(nlogn) time.
3. Find the closes integer to x in the file. It takes O(n) time.
Totally O(nlogn), and the space required is O(1). |
|
b*****n
发帖数: 221 | 15 我说得不是很精确.对每一个元素,找前面的不重叠的元素需要nLogN时间.另外, 这道题还需要重新排序,也需要NLogN时间. |
|
K******g
发帖数: 1870 | 16 不明白
你把这个值传下去干吗呢？每次搜索左子树最大值的时候，走的都是不同路径（从左子
树一直向右，找到最右的一个leaf就返回），你保存这个值有什么意义呢
如果不保存，需要把每个节点遍历一边， O(n),对每个节点，需要搜索左右子树的最值，O（nlogn)。
所以最终的复杂度是O(n+nlogn)
你保存的话，复杂度又是多少？ |
|
A*********r
发帖数: 564 | 17 解法很简洁，有点greedy的意思。
时间复杂度有点困惑，貌似应该是 总元素个数*NlogN ：每一次只刨去一个元素，刨去之后N个数排序需要O（NlogN）。 |
|
j********x
发帖数: 2330 | 18 I think paul's algorithm has an interesting complexity.
That is, in each iteration, a number if removed and will not be considered
again. So we have exactly sum_i{N_i} iterations, or use N to denote this
number.
Then in each iteration, we need to find the min and max value. This is
actually O(n), where n is the number of arrays.
Overall, we have a O(nN) complexity.
We can improve it by combining two strategies. Remember the problem of find
the minimum window in a longer string that contains all ... 阅读全帖 |
|
l*****a
发帖数: 14598 | 19 I remember that,the answer there is really not clear.
step 1) sort by height O(nlogn)
step 2) find the longest increase sequence O(nlogn) by weight
there is tricky in step 2).
but LIS should be a common issue
one |
|
g***s
发帖数: 3811 | 20 sum(i)表示到第i个元素的和。O(n)可以做。
用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
那么这个p=5 sum(5)=10,sum(4）=8不行
然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
小于等
于max(a[])
所以，负责度是O(nlogn + n log max(a[])
对于DP，因为
dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。
所以是 O(NKLogN)
另外，空间复杂度可以用O(n)因为任何dp函数，k都只和dp[k-1]相关。所以，用两个长
度为n
的array就可以了。（另外还要一个sum（i）的数组，那么空间是3×n） |
|
h***n
发帖数: 276 | 21 1) sort currsum array O(nlogn)
2) for each currsum[i], binary search the nearest number to currsum[i]+t (lo
gn) for each
to sum up O(nlogn) |
|
a**********k
发帖数: 1953 | 22 sort based on ht first, O(nlogn),
then find the longest increasing subsequence on the sorted array,
which has a well-known O(nlogn) alg. |
|
a**********k
发帖数: 1953 | 23 sort based on ht first, O(nlogn),
then find the longest increasing subsequence (based on wt) on the sorted
array,
which has a well-known O(nlogn) alg. |
|
b********h
发帖数: 119 | 24 一共N个interval，每个interval花费logN的时间，那总时间当然是NlogN了。
所有conflic是O（N）跟这个算法是NlogN好像不矛盾吧。
这道题有个很强的限制条件就是每个schedule自身不冲突，这样，任何一个interval，
它最多跟另一个schedule的所有interval冲突，而且，这个interval之后的那个
interval，最多就只能跟另一个schedule的最后一个interval冲突。楼上讨论出来的O
（N）算法就是基于这个条件的。 |
|
A**y
发帖数: 62 | 25
把所有数穿起来排序，保留左右信息，一旦碰到重复的就合并range,O(NlogN)
用一个buffer先排序合并再和前面的合并 ?
reservior sampling
如果两正一负，对每一个负数取绝对值，然后在所有正数里找和等于此数的两个
同理对两负一正的情况
分正负 O(N), 找数 O(N)*O(NlogN+N), 总共O(N^2 logN)
有没有更多信息？多边形怎么表示？ |
|
s*******d
发帖数: 4135 | 26 在一个数组中寻找三个数，使得它们的和为0
这题是不是可以这么做：
step1: sort them all O(nlogn)
step2: pick the first element, then in the remaining elements, find two of
them that sum is equals to 0- first element O(n), apply this to all the
other elements O(n2)
total is O(n2) + O(nlogn) = O(n2) |
|
b*******8
发帖数: 37364 | 27 先按开始时间排序nlogn，再扫一遍碰见重叠就完成了。O(nlogn)，如果已经排序好了
那就是O(n)。 |
|
c******e
发帖数: 73 | 28 could sort based on the end date of each person o(nlogN) and then scan one
time O(n) from the end first people to get the result.
It will be nLogn to sort the data. Not sure the way for for O(n) |
|
o*****e
发帖数: 99 | 29 search "interval tree"
O(nlogn) to setup tree.
should be O(logn) to gather the total length.
so result should be o(nlogn) |
|
d*******l
发帖数: 338 | 30 嗯，不过需要先排序所以还是O(nlogn)。上面讨论的区间树我有点记不清具体内容了，
但感觉如果建树再对每个区间查找所有overlap的区间，应该也不会好于O(nlogn)了吧
。不知有没有本质上更好的办法
nlgn)了 |
|
g**********y
发帖数: 14569 | 31 如果数都不连续，这个解法是O(n^2), 即使把Hashtable排序，也是O(nlogn)。如果O(
nlogn), 可能直接排序，然后数更直接。
O(n)的算法，有吗？
我看careercup上的讨论，没人给出O(n)的。 |
|
g**********y
发帖数: 14569 | 32 如果数都不连续，这个解法是O(n^2), 即使把Hashtable排序，也是O(nlogn)。如果O(
nlogn), 可能直接排序，然后数更直接。
O(n)的算法，有吗？
我看careercup上的讨论，没人给出O(n)的。 |
|
d***n
发帖数: 65 | 33 |a-b| + |b-c| + |c-a| = (Max(abc)-Min(abc))*2对n=3成立
用这个思路，一般情况还是需要O(n)的时间来计算差和。
先对每个array排序时间O(klogk), k是array平均长度。
然后根据每个array最小的数对所有array排序时间O(nlogn)。
scan的时候要维持所有array按当前数的大小排序，每scan一个数需要logn时间调整排序（binary search or heap），计算新的差和O(n), scan完所有的数需要O(nk)个操作。
最终时间是O(nklogk + n^2klogn) = O(nk(logk+nlogn))。
不知有没有更快的方法。 |
|
l***i
发帖数: 1309 | 34 This one is a bit strange. Since sorting gives O(nlogn) trivially.
Use partition with randomization will give O(n) in expected time. If you use
O(n) time algorithm to find median and do partition, then it is worst case
O(nlogn).
hashing is a bit cheating in my opinion. If you are allowed hashing, then
you can solve the problem with one element appear once and the other
elements can appear any number of two or more times. This defeats the
purpose of other elements appear exactly 3 times.
1 |
|
d*******l
发帖数: 338 | 35 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
的满足条件的窗口。
对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
这样总的时间复杂度可以达到nlogn。空间复杂度O(n)。 |
|
d*******l
发帖数: 338 | 36 上面火鸡给的是求整个里面最长连续sequence的方法，O(n)复杂度。
按我理解这题目应该是求最大的这样的窗口，满足窗口中的元素重排之后能形成一个序
列。上面我说的nlogn的方法就是用二分法枚举窗口的长度l，然后检查是否存在长为l
的满足条件的窗口。
对于每个l，我觉得可以用O(n)的时间检查出是否存在长为l的满足条件的窗口。
先考虑最左边的l个数，把他们放进hashtable中，并记录占用的bucket的数目，每次窗
口移动就是把一个新的数放进hashtable，并把最右边那个删除。这个过程中要维护占
用bucket的数目。对于一个长为l的窗口，如果里面的元素占用了l个不同bucket，且这
个窗口中的最大值最小值满足max-min+1=l。那这个窗口的元素经过重排就能形成序列
。窗口的最大最小值可以用队列来维护，或者用rmq的办法预处理一遍也可以。
这样总的时间复杂度可以达到nlogn。空间复杂度O(n)。 |
|
S**I
发帖数: 15689 | 37 ☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Fri May 27 14:30:18 2011, 美东) 提到:
A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bian... 阅读全帖 |
|
r*******g
发帖数: 1335 | 38 我觉得O(nlogn)已经够好了，对于原题，这个版讨论了很多，一个叫shyx(可能记错了)
的id给了个链接上面有O(n)的解答，还用到了素数的东西。
但是这个版面很多人给的O(n)的解答其实不是O(n)，我当时还专门比较过，结果发现基
于分治法的O(nlogn)实际运行起来更快，原因是他们把查找链的过程不算做开销，实际
上这个开销对大的输入是很大的。这个链就是需要交换的位置，一个链的意思就是说上
面的元素依次交换。O(n)的办法无非就是找到这样的多个链。 |
|
b******g
发帖数: 1721 | 39 那我就抛砖引玉了,针对3个数的。
1. 两个for-loops得到任意2个数的和，存在一个临时数组,tmp1. O(n^2)
2. sort (tmp1). O(nlogn)如果merge sort.
3. 再扫一遍原来数组，对于每个元素，a, search（-a) 在sorted tmp1. O(nlogn)
所以，O（n^2).
自我感觉，我们必须对所以pair的数进行判断，所以这就是最优化的算法。 |
|
k***t
发帖数: 276 | 40 可能是些初级问题：Binary Radix Sort 是O(N)还是O(NLogN)?
扫一遍，分两份，N，再对两份分别递归2*F(N/2)。
F(n)=2*F(n/2)+n 不是典型的O(NLogN)吗？
或者说是N*KeyBitLength，对4G个数是32N也等于N*Log(N)=N*Log(4G)=32N。
有何标准说法？
再有，递归时占用的栈空间算空间复杂时如何算？
请教了，谢谢。 |
|
v***a
发帖数: 365 | 41 来自主题: JobHunting版 - 问一道题目 或许可以这样：
构造 Voronoi Diagram, O(NLogN) 可以构造出来
Voronoi 最多有 3N 条边
求每个点最近的点，只需要检查每条 voronoi的边，O(2 * 3N )
求每个点最近的2个点，除了检查每条边，还要检查，离他最近点的所有voronoi的边，
O(? * 3N), ? is constant,
求最近的3个点，还要检查第二近的点的所有边，以及第一近的点的所有voronnoi的边
，可以证明肯定在这些边里，O(? * 3N), ? is also constant.
Anyway, O(NLogN）
请问你面的什么公司？
这种计算几何的题目，估计 G/FB 也不会考的吧，做地图的公司？
如果还有position的话，也想投一下试试，
投了无数公司，现在一个面试都没有……杯具啊 |
|
d****o
发帖数: 1055 | 42 我这个代码是不是O(nlogn)?面试官问我。帮忙看看。
我看crack上面即使最后一个解法也需要O(nlogn)吧。
怎么能O(n)?除非你用多余空间吧。 |
|
r****t
发帖数: 10904 | 43 这个按 master theorem 是 \Theta(nlogn) 说 O(nlogn) 没有错。 |
|
r******6
发帖数: 808 | 44 how to choose between sort first or merge first?
assume same length, first one is O(nlogn) O(nlogn) 2n
second is O(2nlog(2n))
how to compare them without the coefficient of the O?
sorry that can't type Chinese now.... |
|
S**I
发帖数: 15689 | 45 ☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Aug 30 00:32:06 2011, 美东) 提到:
Given an array A of positive integers. Convert it to a sorted array with
minimum cost. The only valid operation are:
1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of element
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Aug 30 00:37:57 2011, 美东) 提到:
my 2 cents:
允许额外花费O(n)空间么。。。
允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
当前计数器值放入新开的等大... 阅读全帖 |
|
i*********7
发帖数: 348 | 46 就是将数组里的负数排在数组的前面，正数排在数组的后面。但不改变原先负数和正数
的排列顺序。
例：input:-5，2，-3,4，-8，-9,1,3，-10
output: -5,-3,-8,-9,-10,2,4,1,3
原本要求是in place, time o(n), space o(1)
我看了版上关于这题目的大部分评论，好像大部分都在热议time o(nlogn) space o(1)
是可行的。
现在我只想求一个time o(nlogn) space o(1)解法的具体思路或者算法。。谢谢。。 |
|
g**u
发帖数: 504 | 47 This divide and conquer can achieve O(nlogn). It seems O(nlogn) is optimal
with the constraints of no extra space and in place. Is there any way to
achieve O(n)? |
|
g**u
发帖数: 504 | 48 这样worst case复杂度就增加了吧
本来第三个数列只要遍历一遍的，现在可能要做很多次binary search.
假设三个数列都是n长度，本来worst case 是3n=O(n),现在worst case是2n+nlogn-=O(
nlogn).
you |
|
h*****g
发帖数: 312 | 49 我看到 一种 nlogn 的解法，但感觉不对。。
Approach:
First Have all the points in an array and sort them according to their X
axis, which would give:
3 -12.2 12.2
1 0.0 0.0
2 10.1 -10.1
4 38.3 38.3
5 79.99 179.99
Then for every point P, calculate the distance from 1 point in the front and
1 point in the back:
For Ex: Point with Id=3 (-12.2, 12.2) does not have 1 point
in the back.
Always store only min distance and the corresponding point Ids
Then Sort the points according to their Y Axis, which would give:
2 10.... 阅读全帖 |
|
z********c
发帖数: 72 | 50 他问我sleep sort复杂度你觉得是o(n)还是o(nlogn)，我说O(n)，他说nlogn，因为进
程调度要用个堆。。然后我跟他argu说那你这个是klogn，k是时间片的个数，然后就吵
。。。
这个题他出出来我觉得是好玩的，因为他说他前两天刚看个blog看到的，问问我有什么
想法。。 |
|
