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 写错了； 应该是Ｏ（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 可以从２个开始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. |
|
|
