s*******t 发帖数: 248 | 1 for the min-max heap. I don't think it is easy to implement during interview
.
However, maintain a min heap and a max heap will be easier, but the running
time will be nlog(n), since inserting an item into a heap is log(n). I guess
it is more suitable for streaming data. |
|
c******n 发帖数: 4965 | 2 Divide and Conquer 做法要从min point 分开, 这个导致只有平均情况才能 nlog(n
)
吧? 跟qsort 一样
其实那个O(n) time 的stack 做法倒是更natural 一些 |
|
j*****u 发帖数: 1133 | 3 2. hash: time,space O(n)
sort one and binary search: time: O(nlog(n)), const space |
|
k***s 发帖数: 277 | 4 think about the infinite matrix
2^1 3^1 4^1 5^1
2^2 3^2 4^2 5^2
2^3 3^3 ...
then you can find a traverse routing from 2^1 in increasing order.
for each row, store the header
all headers are put into a min heap (# of headers depends on how long the
sequence)
each time to get min element in min heap, add the next element in same row
to heap.
space O(n), time O(nlog(n))
of |
|
g********d 发帖数: 203 | 5 为什么复杂度是NKlog(K)? 我怎么觉得是Nlog(K). |
|
z****o 发帖数: 78 | 6 怎么这个题重现率这么高啊......
我只能做 kLog(n) 或者 nLog(Value_Range)的。 |
|
s*******t 发帖数: 248 | 7 我能想到的是这样:
每行取最大O(n), 是一个sorted array, 取最大O(1), 然后 insert next value to t
he right place O(log(n)). k个所以klog(n). 是这个意思吗?
有人说用heap,但是感觉建个heap就要nlog(n)吧。 |
|
e****e 发帖数: 1885 | 8 如果这个问题是一维的求线段的most overlapping segment,sweeping line应该就能
搞定了,需要nlog(n)的时间。但是现在是二维,我有点想不清楚 |
|
|
b*k 发帖数: 27 | 9 don't need to maintain heaps, just maintain the value of max and min of
i_k has been scanned so for.
Anyway, the sort part takes O(nlog(n)) |
|
c********0 发帖数: 112 | 10 DP 是 n^2
binary search 是 nlog(n) |
|
u*******o 发帖数: 405 | 11 我觉得这道题是在迷惑人(如果我理解对了的话)。实际上跟多边形没多大关系,也不
用建树(建树就要sort, sort就是nlog(n))。这就是一个找max值问题的变形。根据题
,所有poly或者包含,或者不重叠,那么其实你关心的所有poly都是包含given poly的
,所以他们肯定互相包含,不会互不重叠。这样所有的candidate(也就是包含given
poly的所有poly)是单调包含的。
设A>B表示A包含B,那么算法如下
min=null
foreach poly
if poly > given_poly and (min = null or min > poly)
then min = poly
return min
这个算法是O(n)的
多机就把整个集合分成n块,然后每块上面运行上面的算法,最后reduce就可以了。不
过多机永远没法降低时间复杂度的级别。
the
remove |
|
P*******7 发帖数: 55 | 12 This question exists nlog(n) solutions. the O(n2) algorithm is not optimal.
为3
3
- |
|
w********n 发帖数: 13 | 13 1. n个球,n很大 > 1billion, k个颜色, k相对小, 比如10. 要求in space sort最
efficient的做法 白板coding. (hint, k<< n 所以最后算法争取比nlog(n)小)
该题的第二问 k = 1000 实现比nlogn 更efficient的in space的算法
另外 还有elevator设计 不同楼层多个button都按下了 如何处理 多个电梯 如何处理 |
|
w********n 发帖数: 13 | 14 不能计数 只能用少量的临时variable. 另外 这个题目的第二问是k如果是1000, 还是
远小于n, 实现比nlog(n)小的code |
|
b*******8 发帖数: 37364 | 15 题目既然澄清了,那10楼的就毫无疑问最佳了。O(Nlog(sum-max))。 |
|
r*******y 发帖数: 1081 | 16 第三题,先读到 vector 里面去,然后 nlog(n) sort, 然后 O(n)
统计次数?
hashtable 是好,不过设计 hash table不容易吧 |
|
l*****a 发帖数: 559 | 17 or search LIS for a nlog(n) solution |
|
g**u 发帖数: 583 | 18 请问大家一个区间overlap的问题:
比如说 我们有如下的区间:
[1, 5], [2, 6], [3, 7], [8, 10], [9, 11]
如果是判断是否有overlap的话, 可以sort stating point, 然后用类似merge的方法
来确定是否有overlap( O(nlog n) );
如何找到所有的overlap的区间呢?
用brute force就是O(n^2)的解法, 有没有更快的呢?
谢谢 |
|
g**u 发帖数: 583 | 19
恩, 这个很好理解, 谢谢了。
如果要返回所有的overlap的区间的pair的话, 可不可以直接这样:
对按起点排好序之后的区间, 对每个区间, 用binary search寻找在它后面所有与之
overlap的区间。
我们有n个区间, 每个区间寻找overlap的区间是 log n, 排序的复杂度是 nlog n,所
以总的复杂度依然是 o(nlogn).
不用interval tree 也可以做到。
但是如果我们有stream of intervals的话, interval tree估计派上用场了。 |
|
s********x 发帖数: 914 | 20 heapSort is n/2*log(1.5n)+n*log(1.5n)
quickSort is nlog(n)
node |
|
d*******l 发帖数: 338 | 21 我记得POJ上有一道一模一样的题,是典型的线段树/树状数组的题,线段树可以做到
nlogn,树状数组nlog^2n。我应该A掉了,方法就是用线段树维护一个区间内还剩下的
点的个数。 |
|
b***r 发帖数: 4186 | 22 还是要好好准备一下啊,
是个老印,一开始说问几个technical得问题,后来就问了一个
问我说给我99个数字,都不一样,都在1-100中间,怎么找出来漏掉得那个。
我说is it sorted?
No!
想了一下倒是答得很快,说拿5050减去和就可以了。
然后问我如果missing两个怎么办,没有答上来。说sort一下,问我sorting
complexity,我说nlog(n)对方哦了一声
然后就没有了,move on了。需不需要写个感谢信啊 |
|
n*******n 发帖数: 3 | 23 我来试着证明一下本题的时间复杂度是有下限的。而且下限是 O(nlogk), n为所有
integer的个数. 证明如下:
一般常识是sort n个integer最快是O(nlogn). 所以把n个integer分成k组,每组分别
sort,再合起来,不可能比O(nlogn)更快。 n = k * m
分别sort k 个 size 为 m的数组共需时间 k * O(mlogm) = O(nlogm). 所以merge k个
数组的时间不可能小于 O(nlogn)- O(nlogm) = O(nlog(n/m)) = O(nlogk) .
楼上各位已经找到最优解了。 |
|
b******v 发帖数: 1493 | 24 第13题我的想法是这样的,不知道对不对
P(exactly one accept) = N*p*(1-p)^{N-1}
logP = logN + log(p/(1-p)) + Nlog(1-p)
d(logP)/dN = 0 ==> N = 1/log(1/(1-p)) |
|
b******v 发帖数: 1493 | 25 第13题我的想法是这样的,不知道对不对
P(exactly one accept) = N*p*(1-p)^{N-1}
logP = logN + log(p/(1-p)) + Nlog(1-p)
d(logP)/dN = 0 ==> N = 1/log(1/(1-p)) |
|
x****1 发帖数: 118 | 26 这应该是一道大公司面试常见题吧,网上没有找到满意的答案,所以发个贴讨论一下。
题目的意思是:pre-order travesal 一个 BST,将节点值保存在一个数组中。怎样通
过这个数组重建这棵BST。我能想到的最直接的方法就是一个节点一个节点的插入,复
杂度是nlog(n)。这题有没有O(n)解法?
void makeTree(int[] arr)
{
Node root = null;
for(int i = 0; i
insertNode(root, arr[i]);
}
}
void insertNode(Node treeNode, int value)
{
if (treeNode == null)
treeNode = new Node(value);
else if (value < treeNode.value)
insertNode(treeNode.left, value);
else
insertNode(tree... 阅读全帖 |
|
a********1 发帖数: 750 | 27 我想错了,是nlog^2n 当然还是比n^2好
我晚上贴上来吧 |
|
h******3 发帖数: 351 | 28 I understand one of the reasons that the code can be concise is:
whether the string includes repeated pattern. That's why we care about the
factor of N. And the running time is Nlog(N). |
|
D*******e 发帖数: 151 | 29 1. the difference is pair-wise, not just adjacent ones
2. only think of nlog(n)
3. your logic is incorrect
as
array |
|
g*****i 发帖数: 2162 | 30 dp复杂度高
我觉得这题类似paint partition problem,应该用binary search,复杂度是O(nlogn+
nlog(Max(a[i]))) |
|
g*****i 发帖数: 2162 | 31 dp复杂度高
我觉得这题类似paint partition problem,应该用binary search,复杂度是O(nlogn+
nlog(Max(a[i]))) |
|
x********i 发帖数: 10 | 32 面我的是叫做item similarity组的一个principal engineer
人很好,先介绍了半天他们组大概做什么
其实就问了两个问题
第一个是问有两个web browsing的log files,第一个条目是customer ID,问怎样找出
其中的returning customer
我先说可以把这两文件的customer ID读到两个array去,然后sort再比较,这样 time
complexity是O(nlog(n))+O(n)
然后问可不可以O(n),我就说用hash table,然后又问如果内存限制放不下这么大的
hash table怎么办,然后我就说可以把customer ID分成几段,多几个hash table,然
后hash collision用separate chaining解决
然后就问Fibonacci,我先写了个简单的recursive算法,然后问输入大数字会怎样,他
自己说会有memory exception,问不出问题的最大数字是多少,我就说32位系统里内存
的限制和stack/heap分配的比例,时间复杂度O(n^2)
最后就写了non-... 阅读全帖 |
|
x********i 发帖数: 10 | 33 面我的是叫做item similarity组的一个principal engineer
人很好,先介绍了半天他们组大概做什么
其实就问了两个问题
第一个是问有两个web browsing的log files,第一个条目是customer ID,问怎样找出
其中的returning customer
我先说可以把这两文件的customer ID读到两个array去,然后sort再比较,这样 time
complexity是O(nlog(n))+O(n)
然后问可不可以O(n),我就说用hash table,然后又问如果内存限制放不下这么大的
hash table怎么办,然后我就说可以把customer ID分成几段,多几个hash table,然
后hash collision用separate chaining解决
然后就问Fibonacci,我先写了个简单的recursive算法,然后问输入大数字会怎样,他
自己说会有memory exception,问不出问题的最大数字是多少,我就说32位系统里内存
的限制和stack/heap分配的比例,时间复杂度O(n^2)
最后就写了non-... 阅读全帖 |
|
I***A 发帖数: 6 | 34 写错了; 应该是O(Nlog(N));
另外的两个呢, 有没有想法?
|
|
|
|
|
s****a 发帖数: 528 | 38 qsort 的话如何 randomize pivot 呢? |
|
b*****c 发帖数: 1103 | 39 不random , 用mid of 3 or mid of 9 |
|
i**********e 发帖数: 1145 | 40 singly linked list 就可以做到 n log n 了。
用merge sort,in-place merge。
linked list 没有像数组那样可以 random access in O(1),quick sort 不适用。 |
|
|
a*****n 发帖数: 158 | 42 可以从2个开始MERGE啊,就象前几天那个LINK LIST REVERSE一样吧。。。 |
|
|
s*****k 发帖数: 18 | 44 我觉得mergesort应该是O(n2)
T(n) = 2n + 2T(n/2) -> O(n^2) |
|
|
a*******6 发帖数: 520 | 46 不知道问第四题是什么意思?
n<
is
the |
|
s****a 发帖数: 528 | 47 sort the words will cost nLog(n)
search will cost kn, where the k is the average length of the word. |
|
a*******6 发帖数: 520 | 48 不知道问第四题是什么意思?
n<
is
the |
|
s****a 发帖数: 528 | 49 sort the words will cost nLog(n)
search will cost kn, where the k is the average length of the word. |
|
|