K******g
发帖数: 1870 | 1 construct a new BST, 不是要求nlogn 么？那就根本不对了，人家要求O(m+n) |
|
i*****r
发帖数: 265 | 2 要是要求balanced的话我只会nlogn的，不知道n的复杂度怎么搞。 |
|
s*******a
发帖数: 42 | 3 对的就是，quicksort的变种，时间复杂度nlogn |
|
w*****e
发帖数: 197 | 4 这个算法有问题 5的倍数恐怕不能简单变成1
比如2x10和2x15得到的尾数应该是不一样的
但是用这个算法得到的结果是一样的
我觉得这个问题恐怕没有logN的算法 NlogN倒是有一个
,
= |
|
m*****f
发帖数: 1243 | 5 I think the basic idea is sort the range number first by nlogn, then use
binary search to find the two range ends in the sorted list, so you don't
have to check the whole list
just O(logn) + O(matched) |
|
x***y
发帖数: 633 | 6 1. Sort the lower boundary, and the upper boundary separately (O(nlogn)),
from the smallest lower boundary min_low (6 in your e.g), and assume upp is
the upper boundary corresponding(10 in e.g) to lower boundary, set old_upp
to min_low;
2. find position of upp in the array of lower boundary, and in the lower
boundary for all the values less than upp, if the largest corresponding
upper bound is bigger than upp, set old_upp to upp and set upp to the
largest corresponding upper bound, and do step |
|
l***i
发帖数: 1309 | 7 For your second problem, why not dump the smallest numbers to A and the rest
to B(swap max in A with min in B), then sort A, B separately to get O(nlogn
). Heap sort can do this since you do not have O(n) extra storage. |
|
g*******y
发帖数: 1930 | 8 分冶可以做到nlogn的in place merge
简单说就是在B中binary 搜索A的median的位置，然后交换两段，然后分冶
不过肯定不是最优了，不过我觉得对于面试的要求也许还行。
(m+n) |
|
|
m******9
发帖数: 968 | 10 先用scan的方法，比如用2 pointer都从A B的左端开始scan，将smaller numbers都
swap到A
中，然后再sort B，例如用heap sort， quick sort
整体上是O(nlgn)
rest
O(nlogn |
|
g*******y
发帖数: 1930 | 11 来自主题: JobHunting版 - 问个面试题 你怎么做到这个的？
我现在还只能想到 k*nlogn 的优化。。。 |
|
g*******y
发帖数: 1930 | 12 我就直接说做过，看过solution是一篇paper，让他换题。
或者写个自己能想到的nlogn算法 |
|
|
G**********s
发帖数: 70 | 14 divide & conquer
切一半，swap一次。。重复做
T(n) = 2T(n/2) + O(n) hence . T(n) < O(nlogn) |
|
c*********n
发帖数: 1057 | 15 interview的时候说出nlogn的就可以了吧 |
|
r****o
发帖数: 1950 | 16 我没想出比较好的办法。
有谁做出来了非2^n情况的O(nlogn)的算法吗？ |
|
l***i
发帖数: 1309 | 17 Divide and conquer can give you nlogn. But I don't know if O(n) is possible. |
|
r**u
发帖数: 1567 | 18 so what? 你能把你O(nlogn)算法具体写出来，给个例子么？dude，不要想当然。 |
|
k***e
发帖数: 556 | 19 i already answered that: the const before n^2 and nlogn is very important
space的 |
|
l*******r
发帖数: 511 | 20 你算算看，n^2和nlogn是有交点的，交点前当然要用n^2了，然后还有不同的系数 |
|
j**w
发帖数: 382 | 21 O(nlogn) might have a HUGE constant, say, 10^6 * n * log n + 10^10, or very
hard to implement correctly for all possible input data. |
|
w*********l
发帖数: 1337 | 22 这两个有交点不代表an^2+bn+c跟nlogn有交点啊 |
|
w**********8
发帖数: 121 | 23 刚刚完成amazon的第2轮电话面试，感觉不是很好。主要是讨论算法。我的一个最大问
题就是没有多向他确认。第一个题目是从两个log 文件里面找到相同的ip地址。我先用
hashtable做，他主要纠缠最坏情况的空间使用，然后mergesort优化。我一直默认不能
sort，结果他最后给我说要sort。时间复杂度就变成O（nlogn）。我应该先问问他是不
是可以sort。
第2个题目简单的unix命令题目。grep搞定
第3个题目是一个web系统设计题目。主要考虑性能，cache等。
不知道能不能拿到onsite。担心中。。。 |
|
|
r**u
发帖数: 1567 | 25 nice，学习了。这真是个经典问题，如果面试时候能提到O(nlogn)算法都能加分不少吧. |
|
s*****i
发帖数: 355 | 26 看过当然知道，我的意思是如果没看过，很难靠自己想出O(nlogn)的算法 |
|
B*****t
发帖数: 335 | 27 二分+hash， 最坏的情况下复杂度O(nlogn), n is the length of the large string.
string
complex |
|
g*******y
发帖数: 1930 | 28 来自主题: JobHunting版 - 问个算法题 这题不错。krone有不错的解法，能做到平均性能nlogn |
|
U********o
发帖数: 132 | 29 来自主题: JobHunting版 - 问个算法题 ss
这题不错。krone有不错的解法，能做到平均性能nlogn |
|
l***i
发帖数: 1309 | 30 sort and merge already achieves O(nlogn), so there is no point to post new
solution unless you have O(n) time and O(1) space. |
|
|
s********f
发帖数: 510 | 32 1 知道range可以用bitmap，不知道range如果spaceO(1)最快也就是nlogn了吧？
2 第一次取样就是是头10个，第二次就是两个10的取样各50%几率再取样，
第三次就是已有的10个有2/3的几率被取，新的10个有1/3的几率被取，再取样。
第n次就是以后的按(n-1)/n的几率，新的按1/n的几率取。
45 |
|
h*******x
发帖数: 12808 | 33 可是人间排序才是（nlogn）啊。。
是都
点费
流，
样。 |
|
t********1
发帖数: 266 | 34 I mean O(nlogn) ...
numbers,
at: |
|
b***u
发帖数: 12010 | 35 第一题用programming pearl中的in space heap sort吧，空间1时间nlogn
45 |
|
|
z*******e
发帖数: 122 | 37 对于第3个题目，找包含所有点的最小圆的半径，我觉得可以先找到一个convex hall
包含所有的点（在CLRS上有nlogn的算法）,然后求这个convex hall的外接圆。 |
|
B*****t
发帖数: 335 | 38 there is a paper on how to do it in O(N) without extra space. But need some
mathematical results from number theory.
Maybe I am wrong, not very clear.
but it can be done in O(NlogN) |
|
s**********r
发帖数: 141 | 39 I saw there's a long discussion on the following problem (I modified the
description a bit).
"给一个整数数组a[0...n]，找出一个size k(1
distance中，使得其min distance 最大化 (max-mindist)."
It bothered me for a while (Simply I am not a DP fan). I consider it as a
binary search problem:
0. Sort the array in ascending order. O(nlogn)
1. If you claim the max-mindist is w, I can verify it in O(n).
2. Note that '0 <= w <= (a[n]-a[0])', you can try possible w's using
binary search.
3. Time comple |
|
|
l***i
发帖数: 1309 | 41 krone's solution is incorrect.
To get worst case O(nlogn) you need to get the exact median of the array in
linear time, then use it as pivot. |
|
s******t
发帖数: 2374 | 42 如果 start和end都sort的话
那么，在每个单位时间里，比如一分钟，只需要比较当前这一分钟里面的start和那些
end有先后关系。
t1 t2 t3 t4 t5...
====|=======|========|=======|===
|____e1___|
|___e2___|
|__e3__|
|__e4_|
这样，排序时nlogn
比较在worse情况下 等于：分钟数*n*n |
|
l******o
发帖数: 144 | 43 假定坐标是整数, 那么dy/dx是个分数, 约分. 然后两个分数相等仅当分子分母的绝对
值相等. 这里用绝对值是因为两个点可能在另一边.
此外, 不是O(N^2), 每个点作为圆心, 然后比较其他N个角度的话怎么说也要O(NlogN),
此后每个点重复一遍, 所以是O(N^2 logN)的.
比如说N个值, 不排序, O(N)怎么找重复的? 排序怎么说也要O(N logN).
别说什么hashtable, hashtable你只能说一般情况下是O(1), 最坏情况还是O(N), 所以
不能用O(1)来分析算法复杂度的.
浮点数也可以比较啊，只是需要有精度的取舍，规定一下比到小数点后哪一位。
真怕浮点数的话，这里没必要用浮点代表吧，比如角度等于2/27的用2.27表示不就行了。
算法，又不是算术。 |
|
h****r
发帖数: 2056 | 44 你这两点都错了吧。
1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。
), |
|
l******o
发帖数: 144 | 45 这么问你吧, N个数, 你怎么在O(N)的时间里找到重复的?
用hashset的那个方法忽略, 理由已经说过了.
你这两点都错了吧。
1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这
个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。
), |
|
l******o
发帖数: 144 | 46 此外你那个对称矩阵, 只不过是把复杂度降低一半而已, 没有从阶上得到降低.
这么问你吧, N个数, 你怎么在O(N)的时间里找到重复的?
用hashset的那个方法忽略, 理由已经说过了.
你这两点都错了吧。
1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这
个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。
), |
|
h****r
发帖数: 2056 | 47 呵呵，这个问题是越辩越明了。
计算出上半矩阵来，需要O(N^2)。
列出矩阵里每行里出现的重复角度需要排序，这个是O(NlogN)，N行即为O(N^2logN)。
所以复杂度是O(N^2) + O(N^2logN)，也就是O(N^2logN)。
-
loop |
|
r******g
发帖数: 58 | 48 在careercup上面看到的。觉得还蛮有意思。
不知道有没有 nlogn 的解法。
大家讨论一下吧。
Given an array of 'n' random integers. Given an integer 1<=n. Find the k
numbers such that the minimum difference of all the possible pairs of k
numbers is maximum (maximum among other minimum differences for various
possible selections of k numbers ). |
|
a***9
发帖数: 364 | 49 是不是这样：
1. sort 这 n个数，记结果为a_1,...,a_n （O(nlogn));
2. 记 D(i,j) （i= 1 to n, j= 1 to min(i,k)) 为必须包括第i个数的前i个数中
取j个使得两两最小差值最大的那个差值，方程为：
D(i,j) = max{min(D(s, j-1), a_i-a_s) (j-1<= s <= i-1)}
算这个D(i,j)直接做是O(n)，但可以加速, 因为(a_i-a_s)值关于s是non-increasing的，
而D(s,j-1)值关于s是non-decreasing的,所以可以做binary search:
search (int start, int end,int i, int j) {
if (start >= end) return;
mid = (start+end)/2
if D(mid,j-1) > a_i - a_mid
then search (start, mid, i, j)
else search (mid, end, i,j)
}
所以第二步最后复杂度O(n |
|
w*****1
发帖数: 245 | 50 a matrix, with each row sorted, but colms are NOT. find a target value.
find a way better than nlogn?
真的不觉得能再快了!
大家讨论下吧, 不知道这题以前在这里出现过吗? |
|
