m****y
发帖数: 28 | 1 如果列之间没有关系，应该不存在快于nlogn的方法了。不难证明。 |
|
w*****e
发帖数: 197 | 2 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? |
|
l******o
发帖数: 144 | 3 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? |
|
l******o
发帖数: 144 | 4 不要死读书。
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? |
|
w*****1
发帖数: 245 | 5 a matrix, with each row sorted, but colms are NOT. find a target value.
find a way better than nlogn?
真的不觉得能再快了!
大家讨论下吧, 不知道这题以前在这里出现过吗? |
|
h********e
发帖数: 1972 | 6 我来贴个答案吧。。动态规划不怎么可取，因为多半是伪多项式的。hashtable 也不好
，怎么说呢，hash都是投机取巧。很多面试摆明了不要你hash的答案。sort吧，挺好。
。重点是然后可以这么做。。
8, 10, 2, 9, 5, 7, 1
排好序是
1 2 5 7 8 9 10
然后用19 减一下是
18 17 14 12 11 10 9
然后干啥。。
用一次merge排序的merge方法。。就能用n的时间找到是否两个序列有相同的东西了。
当然还有些细节。。
这样好歹能拿出个nlog+2n的算法。。还凑合，当然如果考官只要求O(nlogn)就无所谓
了。 |
|
s*i
发帖数: 388 | 7 right, that's my 2nd improvement i gave during the interview. but i don't think we need to explicitly "sort" it, 'coz that's O(nlogn).
assume the file size ranges from 1KB to 1GB, we can use a table of 1M size,
and put the files into this file_size_array, then after this round, check
the md5 for those files fallen into the same slot.
but the interviewer still push me after this stage.....
any more ideas? thanks.... |
|
l*****a
发帖数: 14598 | 8 keep a sorted linked list for the give pairs
for [ai,bi] [ai+1,bi+1]
if (ai>bi+1)||(ai+1>bi)
put both those 2 pairs into the right location of the linked list
(in order)
else
merge them into one pair and put into the right location of the linked
list(you can use binary search for this step)
the final result is the linked list.
I assume that u can get the result with O(nlogn) time complexity |
|
B*****t
发帖数: 335 | 9 子集和，整数划分，装载等问题都是0-1背包问题的变形, 这些都是NPC的，一般情况下
没有
什么多项式的解法可以得到最优解。
lz给出的这类装载问题有很多近似解法，比较popular的是O(NlogN)的。如果要得到最优
解可以用回溯+二分，复杂度O(N^N*logN), 看着N^N比较可怕，不过加入剪枝后运算起来
还是比较快的。 |
|
y*c
发帖数: 904 | 10 1. O(nlogn)
divide and conquer
abcd1234 -> ab12cd34 -> a1b2c3d4
T(n) = O(n) + 2T(n/2) -> O(nlgn)
2 O(n)
This is just like matrix transposition using O(1) space.
If we use row major, the absolute position for a[i][j] is i*n + j. After
transposing, it goes to j* m + i = i'*n + j', which in turn will go to j'* m
+ i' and so on. There is a paper on the proof. |
|
u*l
发帖数: 1943 | 11 问了一个问题，
里面有用到排序的复杂度。
我知道是 nlogn, 居然鬼使神差的一直用logn.....
一紧张就出错阿。 |
|
q*********u
发帖数: 280 | 12 你这个id太牛了。
鬼使神差这个，就恰好会在那种紧张的时候冒出来
问了一个问题，
里面有用到排序的复杂度。
我知道是 nlogn, 居然鬼使神差的一直用logn.....
一紧张就出错阿。 |
|
|
x****n
发帖数: 74 | 14 不才想请教两道很常见的面试题
（1） 给定array a1,a2,...,an,b1,b2,...,bn，将其变成a1,b1,a2,b2,...,an,bn的
形式
知道有个O(n)解，不过水平比较低，理解起来是在有困难，CareerCup上给了一个
O(nlogn)
的解，不过自己尝试总不能对，希望大牛们指教
（2）另外就是也很常见的在rotated 的sorted的数组里找一个元素的题，是用Binary
search实
现的，但是对于有重复元素的数组就会有错，不知道是不是就不能处理这种情况。
多谢了 |
|
h*******e
发帖数: 225 | 15
O(n)的你就别管了，没有必要。
O(nlogn)的思想是分治。把X=a1,a2...an,b1,b2...bn看作四段A1,A2,B1,B2。假设要求
的置换是F(X), 那么F(X)=F(A1,B1),F(A2,B2), 也就是说，把A2和B1交换，然后递归。
Binary
可以证明，有重复元素的时候，基于比较的算法有O(n)的下界。具体怎么证明你可以想
想。 |
|
x***y
发帖数: 633 | 16 I know what the method is about, but it's not correct.
Say a1[]={5, 4, 1} a2[]={4, 3, 1} Then the result would be
5+4 = 9
5+3 = 8
4+4 = 8
4+3 = 7 //but in your method is either is 5+1 or 4+1
I have said that the problem with the approach is that there may be more
than 2 candidates for next pair.......
I know with Young talbe, we can get a O(n^2) solution...But how to get
better, like O(nlogn) is very difficult for me.... |
|
B*****t
发帖数: 335 | 17 This can be solved in time O(nlogn) + extra space O(n) by creating
a max-heap, but I don't think there is an O(n) solution.
they are
\in B}.
is defined
largest |
|
|
i*****r
发帖数: 265 | 19 要是每次取中点的那种就是nlogn啦，说n的都是默认取中点是O(1)的……对于链表明
显不对。dsw好像可以是n的，但是要面试的时候搞出来不容易吧 |
|
j**l
发帖数: 2911 | 20 是Maximum SubArray Sum的变体,这里有几个要求，一个是连续，一个是最长，一个是
和小于等于一个定值T
假定全部元素的总和是S, 定义U = S - T, 那么试着把这个问题转为等价的补问题: 找
首尾两段，长度加起来最短且其和大于等于U，剩下的中间那截自然就是满足题目的最
长子数组。
有三种情况
1) 只有从首开始的一段
2) 只有以尾结束的一段
3) 首尾两段都有，且不相交
对这三种情况取最小就可以解答
由于首尾两端都是固定的，那么算出那么算出a1...ai的和，以及aj...aN的和，都只要
O(N)时间, 所以1), 2)都是O(N)时间可解的
难办的是3), 据说可以处理一下，用binary search的思想在NlogN解决。想了半天未果
，请帮忙解答，谢谢。 |
|
K******g
发帖数: 1870 | 21 A matrix, with each row sorted, but colms are NOT. find a target value. find
a way better than nlogn?
好像以前讨论过，但是没有什么结论，请问有谁知道答案吗？多谢 |
|
h**k
发帖数: 3368 | 22 恩，直接用heap可以实现O(nlogn)
这个和是一个partial order，(x,y)表示A[x]+B[y]，则
从(0,0)开始，把(0,0)存入heap of size n,
输出heap中的最大值，然后把(0,1)和（1，0）放入heap，再输出最大值。
suppose the maximum element in the heap is (i,j)，remove it and insert( i+1,
j) and (i,j+1) into the heap. Count the output number.
有个问题，(i,j)可能会被放入heap两次，解决方法，
给每个(i,j)设一个counter,initial value = 0, every time we want to put (i,j)
into the heap, check the counter's value, if it = 0, just increase it by 1,
otherwise put it into the heap; |
|
h**k
发帖数: 3368 | 23 naive的方法是比较first n elements of A and first n elements of B, 得到n*n的
和，然后merge 找nth个，复杂度是O(n*n)
更好的方法是O(nlogn)
这个和是一个partial order，(x,y)表示A[x]+B[y]，则
(0,0) > (0,1) > (0,2) >...
> > >
(1,0) > (1,1) > (1,2) >...
> > >
(2,0) > (2,1) > (2,2) >...
>
...
从(0,0)开始，把(0,0)存入heap of size n,
输出heap中的最大值，然后把(0,1)和（1，0）放入heap，再输出最大值。
suppose the maximum element in the heap is (i,j)，remove it and insert( i+1,
j) and (i,j+1) into the heap. Count the output number.
有个问题，(i,j)可能会被放入heap |
|
g**********1
发帖数: 1113 | 24 Normally you have n*n matrix with columns and rows are sorted. You can merge
all columns at nlogn complexity. |
|
g**********1
发帖数: 1113 | 25 Normally you have n*n matrix with columns and rows are sorted. You can merge
all columns at nlogn complexity. |
|
X*********n
发帖数: 570 | 26 assume A has n elements and B has m, and n<=m
then we can have n lists
a[0]+b[0]>=a[0]+b[1]>=......>=a[0]+b[m-1]
a[1]+b[0]>=a[1]+b[1]>=......>=a[1]+b[m-1]
.....
a[n-1]+b[0]>=................>=a[n-1]+b[m-1]
then we build a max-heap with the first element of each list with O(n).
delete the max from the heap and insert the next element from the
corresponding list, O(logn)
do it N times
So the complexity is O(Nlogn)
and |
|
b*******7
发帖数: 907 | 27 The time complexity of building a n-element heap should be O(nlogn) because
inserting element needs O(logn). |
|
g*****e
发帖数: 282 | 28 这个思路是divide and conquer，不是binary search。经典的求k largest element的
算法之一，不需要是sorted array。但平均time complexity是nlogn. |
|
|
K******g
发帖数: 1870 | 30 如果，把一个链表慢慢插入生成BST，然后在inorder transverse，不就是排序了吗，
这个好像是O（nlogn+n),请问这个叫什么排序呢。多谢 |
|
z*****o
发帖数: 40 | 31 我觉得 L, U 在不同时候是不同的，否则
否则 s = sum(V) 然后 for i = L to V do x[i] = v * N 就可以了
既然说 L, U, V are parameters of each operation, 我觉得他们就是每次可以不同
，否则为啥叫 parameters.
这个应该有 NlogN 的算法
把 L,U 看作一个线段，对所有的线段端点（2N个）排序，
s=0
从左到有扫描端点
如果遇到一个左端点，s+=线段对应的v
如果遇到一个右端点，s-=线段对应的v
处理完一个端点后，s就是x[这个端点+1]到x[下一个端点]的值 |
|
p******r
发帖数: 2999 | 32 3. sort, O(nlogn)
k-th largest number, O(n)
4. count numbers in range [a0,a1),[a1,a2]...
5. hash |
|
p******r
发帖数: 2999 | 33 sort是通用方法
min-heap需要额外内存，而且O(nlogn)和O(nlogm)差不多 (这题的m非常大)
k-th largest的selection是最快的，O(n)
hash可以包含文件大小的信息吧 |
|
K******g
发帖数: 1870 | 34 一个更简单的办法：
1）排序，从小到大
2）两个指针，p1 points to the first element, and the p2 points to the
largest element.
3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
combination with *p2. Then --p2. repeat.
4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
5) repeat until p1 and p2 meet.
the total complexity will be O(nlogn).
each
m) |
|
g**e
发帖数: 6127 | 35 你这怎么会是nlogn，"*p1 to *(p2-1) can have such a combination with *p2"。要
找出p1至p2-1的全组合， 难道是O(1)?
value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
p1 are such as combination. then ++p1, repeat. |
|
l******c
发帖数: 2555 | 36 when a duplicate is encountered, how to process?
I guess it is an nlogn problem |
|
w******1
发帖数: 520 | 37 SORT没什么本质的作用吧？
如果ARRAY ONE: 3 51 71 9 11
ARRAY TWO: 2 4 16 28 10
怎么着也得都给遍历到了才能出个结果。
可不可以把两个ARRAY 合成一个， 加上来自于哪个ARRAY 的标记。
用二分法互除， 如果可以被除并且不是来自于同一个ARRAY ， 那么就RETURN.
NLOGN |
|
j**l
发帖数: 2911 | 38 来自主题: JobHunting版 - AMZ面经 找k大数
1. 排序, O(nlogn)
2. randomized partition, 类似quick sort, average O(n), worst O(n^2)
3. 5个一组划分，保证worst O(n)，具体代码不太好写。
面试官想要哪种？ |
|
p********7
发帖数: 549 | 39 倒数第二个题可以用hash table，对于不同长度的单词使用不同的table，a ＝ 1；b
＝ 51；c＝ 101；d ＝ 151；这么定义字母，人那还cab ＝ 1 ＋ 51＋101 ＝ 153；
对于三个字母的组合，如果是anagram肯定是同样的值。
如果你想对于每个单词都排序了再做，复杂度太高了，至少都是nLogN
最后一个直接用hash table。 把textfile的词都装到table，然后再find list的词，
如果找到就删除，如果没找到就什么都不干。最后table留下的就是答案。 |
|
f**********w
发帖数: 93 | 40 google intrasort.
If I remember it right, it begins with quicksort, but if it could not finish
in O(nlogn), it switch to heapsort. |
|
f**********w
发帖数: 93 | 41 我的想法是这样的，假设我们已经有了3个array a,b,c,分别代表三个单词在文章中的
位置，注意这三个数组应该是已经排序的，比较a[0], b[0], c[0],找到最大值，假设
是a[0],然后在其他的两个数组里做binary search,记录当前的最小范围，然后对a 循
环，每次都对b,c做binary search,并更新最小范围。效率应该是O(nlogn).也许有线性
的解法，我没想到 |
|
f*********5
发帖数: 576 | 42 来自主题: JobHunting版 - 一道电面题 if u think so,that is fine.
but when we talk about time complexity,we will definitely choose
nlogk ,while not nlogn.
sure,we will use O(k) for extra space while u don't need.
at least we should mention this to the interviewer
50000*16 |
|
|
g******e
发帖数: 247 | 44 来自主题: JobHunting版 - 一道面试题 0-99 个数存在array里，如何找到重复的。 回答建一个array记录下出现的次数，
>1的为重复的。再问如果不能有额外的空间，用何方法？回答用heap,但是用heap作
sort时是O(nlogn), 不够快。提示用一个swap，最后结果会是O(2n)。 这个没回答
出, 请各位指教 |
|
B*****t
发帖数: 335 | 45 先找出两个seq的suffix array，然后在SA上找max window，找max window的过程和
已知中序，后续遍历，重建二叉树的方法很象。 复杂度O(nlogn)
of matching
window is 4. ( |
|
h**k
发帖数: 3368 | 46 Give you two sequences of length N, how to find the max window of matching
patterns. The patterns can be mutated.
For example, seq1 = "ABCDEFG", seq2 = "DBCAPFG", then the max window is 4. (
ABCD from seq1 and DBCA from seq2). 起始位置无需相同。
这个我知道有O(nlogn)的算法，不知道是否有O(n)的算法。 |
|
B*****t
发帖数: 335 | 47 先按stop time对record排序， 然后从0到n-1依次找出包含的当前record的最大
score，用binary search找，同时update maxScore。 O(nlogn)
不用什么优化，169.209 ms on its longest test case |
|
h**6
发帖数: 4160 | 48 这个方法好，我把我的帖子删掉了。
O(nlogn)的复杂度，对于100,000级别的输入来说，应该能在1秒钟之内完成啊。 |
|
b*****n
发帖数: 221 | 49 需要NLogN时间找Value[i-(stop-start+1)] |
|
p********7
发帖数: 549 | 50 问题是用hashtable就不用啊，你看我之前写的那个算法，hashtable，查找的时候用
stop这个关键词，insert的时候把start，stop，value一起作为一个数据结构存了
题还需要重新排序,也需要NLogN时间. |
|
