i******e
发帖数: 273 | 1
讨论一下用两种数据结构实现的时间、空间复杂度：
1）priority_queue (max heap)
2) 100个元素的链表数组
- 使用1）和2）的getPackage() 的时间复杂度都是O(1)
- 对于receive()， 使用priority_queue， 插入是O(lgN), 使用链表数组如果维护一
个指向每个priority链表结尾的指针，插入是O(1)操作。
- 使用1）和2）空间复杂度都是O(N)
- 使用2）查找当前最高priority 链表也是O(1)操作。
所以2）比1）更有效？ 这样分析对吗？ |
|
Y********f
发帖数: 410 | 2 除了recursion外只能有O(1)的extra space。有什么好的方法。
我的想法是用iterative方法同时in order访问两个树，比较节点大小，打印小的，然
后找到该节点的下一个节点。但是需要O(lgN)的space。 |
|
i******e
发帖数: 273 | 3 是呀。这不是和producer-consumer model有点类似吗？ 当一个线程遍历了一个结点之
后block自己同时signal另一个线程遍历另一BST的下一个结点然后比较直到两棵树都遍
历完。
如果有parent指针可以实现getNextNode()函数（O(1)操作）， 可以分别对两棵BST分
别扫描， 就不需要线程同步的方法了。
你说用iterative方法需要O(lgN)的space。 为什么？ |
|
y***u
发帖数: 174 | 4 写了一下next successor: O(1) space, O(lgN) time。
Node getNextSuccessor(Node root, Node node){
if(root==null || node == null){
return null;
}
Node pre = null;
while(root!=null && root!=node){
if(root.val > node.val){
// go left
pre = root;
root = root.left;
}else if(root.val < node.val){
// right
root = root.right;
}else{
//found
if(node.right!=null){
... 阅读全帖 |
|
j********g
发帖数: 80 | 5 0 就是个答案阿。 我想关键问题是端点算不算的问题吧，算的话O(lgn)，不算的话就
得O(n)了 |
|
s******n
发帖数: 226 | 6 小想法：
1. 初始K个坐标对 [0, Ni-1]
2. 求第一个数组的media-- M1
3，去找剩下有多少比M1小的 （K*lgn）
4，shrink坐标对，退化成找第k大元素
复杂度应该是K*(logN)^2 (upper bound) |
|
|
d*********g
发帖数: 154 | 8
这个算法的复杂度不一定比用堆好吧？“给定任意一个数，有办法判断该元素是矩阵中
第几大的”，这一步应该是O(n)，n是矩阵的max{长，宽}，然后二分法找到恰好大于k
个数的数是O(lgm)，其中m是矩阵中的最大值减最小值的大小。所以总复杂度是O(n*lgm
)。而用堆的复杂度是O(k*lgn)。不知道我的理解对么？ |
|
|
g***j
发帖数: 1275 | 10 为啥quicksort的空间是lgN, 为啥mergesort的最坏的情况是N? 一般情况是什么？
quicksort, mergesort, heapsort，如何选择用哪个sort？ 我只知道mergesort
stable，那么quicksort和heapsort的差别呢？除了worse case quicksort是n^2
另外，是不是只要涉及到交换的，都不stable? |
|
p*******f
发帖数: 15 | 11 O（n^2）和O(n)是我主动给的。他让提高，我就又给了O（lgn）。 |
|
a********m
发帖数: 15480 | 12 恩。lgn肯定不行。不过m+n能搞定吗？俺咋脚着至少要nlgn （简化成m=n）？ |
|
s*****t
发帖数: 11 | 13 堆排序算法如下
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i = A.size downto 2
3 exchange A[1] with A[i]
4 A.size = A.size - 1
5 MAX-HEAPIFY(A, 1)
算法书上说
1 BUILD-MAX-HEAP(A) 的时间复杂度为 O(N)
5 MAX-HEAPIFY(A, 1) 的时间复杂度为 O(lg N), N 为当时 A 的长度
那么, 整个算法的时间复杂度是
O(N) + O(lg(N-1)) + O(lg(N-2)) + ... O(1)
= O(N + lg(N-1) + lg(N-2) + ... 1)
= O(N + lg(N-1)!)
= O(lgN!)
比快速排序的 O(NlgN) = O(lg(N^N)) 还要快?
迷惑了,求大牛指点. |
|
l*****a
发帖数: 14598 | 14 找最大的 ,考虑一下淘汰赛，n次比较
然后2nd biggest 在被冠军淘汰的那条path上。。lgn-1 |
|
b*****n
发帖数: 482 | 15 应该是0后面跟的都是1，找第一个1的位置。
知道长度的话就是普通二分，不知道长度的话每次往右移2^i，i=0,1,2...，可以做到O
(lgn) |
|
b*****n
发帖数: 482 | 16 这是二分的另一个用法。
比较有意思的题目是，面试官说，我现在脑子里想一个数，你猜猜是多少？我只能告诉
你大了，小了或对了。你要在O(lgn)里找到这个数。 |
|
c********t
发帖数: 5706 | 17 最后一种解法貌似也是lgn的。按n的binary走的，本质与n/2应该一样
pow(double, double)应该怎么做？ |
|
w***o
发帖数: 109 | 18
好像不是Constant time。任然是O（lgn）。而且还可以简化：
public class Solution {
public double pow(double x, int n) {
boolean isNeg = n < 0;
if(n < 0)
n = -n;
double ret = 1.0;
while(n>0) {
if((n&1) >0)
ret *= x;
x *= x;
n >>= 1;
}
return isNeg? 1.0/ret : ret;
}
} |
|
p**o
发帖数: 1012 | 19 If it is O(lgn), you complexity is O(nlgn), but ours is O(n) |
|
u*l
发帖数: 1943 | 20 你的这个计算复杂度是多少？
O(N) or O(Lgn)? |
|
f*****e
发帖数: 2992 | 21 面4.2很简单的:
记每个interval是[Li,Hi]，给定一个interval A=[x1,x2]
找{L1,L2,...,Ln}中小于等于x2的个数，记为n1，
找{H1,H2,...,Hn}中小于等于x1的个数，记为n2。
与A相交的interval个数就是n1-n2
如果对上限和下限排序，然后再二分查找就可以得到n1和n2。
所以是复杂度是O(lgN) |
|
c********t
发帖数: 5706 | 22 是的，cc答案1给的不是最优解。第二个是bottomup，time O(n), space O(lgn). |
|
c********t
发帖数: 5706 | 23 你这样算的时间复杂度不是 O(nlogn)吗？我其实也认为时间是O(nlgn)。但答案说是O(
n^2).
空间不会算，肯定大于O(lgn),为什么你说worst case是O(n)?
n/ |
|
c********t
发帖数: 5706 | 24 同意每一层都要把剩下的算一遍，但O(n^2)还是不对啊
第一层 1次
第二层 2次*2 nodes
。。
最后一层 lgn* （n/2)
加起来应该还是O(nlgn)的吧 |
|
c***s
发帖数: 192 | 25 空间为啥是大于O(lgn)? 一次height和balance不是都只算一条path吗？
对于那个答案为啥说是O(n^2), 我也不是很清楚，
我自己实现的算法是O(n)的，我就没去看它的答案。
O( |
|
c********t
发帖数: 5706 | 26 嗯，你说得对，是O(lgn). 我原来想错了。 |
|
s****0
发帖数: 117 | 27 Did you read the algorithm yet?
the time complexity of the original version is O(n*lgn). The log n comes
from the binary search of the stack. In this case, it is const time. |
|
c********t
发帖数: 5706 | 28 二爷，一直没弄懂一件事情。
我知道treeset add,remove,search都是lg(n).但api里就是没提update. 比如当一个
query avg被update的时候，treeset是不是也能自动作排序调整？然后也是O(lgn)?
treemap一样问题。 |
|
g****y
发帖数: 2810 | 29 A家的面试默剧了，发一个全程，顺便求靠谱ICC？
A家历时2个月，一月初投出简历后就有人联系。然后就开始了约电面了，到3月onsite
一面电话：
一个中国人，显示介绍亚麻，然后自己的组，再是不一定要你进我们组，问题：
1. 先问了C++和Java的区别
2. 数据结构，问到了队列
3. 写一个队列用一定长度的数组循环，空间不够了就返回满了
二面电话：
老美吧，但是听着说话像老中
1. 数据结构， 问到哈希表
2. 二数求和问题，讲讲思路（就是给一串数和一个值，返回能否用这个数列里的2个
数的和得到这个值）
3. 用哈希表写一个上述问题的代码，当然要O(n)了
onsite 4轮：
那天那个hr总要我去西雅图转转，让我多玩玩，后来问我待几天，我说你们订得明天8
点的机票，我玩个屁啊，她就不说话了
一面
老美，估计是打算招我的那个组的+烙印，估计也是那个组的
1. 行为问题
2. 斐波那契数（输入一个数，输出刚好比这个小的斐数）
3. 我先是O(n)，他不满意，要优化。我推了一遍斐波那契的通项公式（将求和写出一
个矩阵变换，第n项就是矩阵的n次方，通过求矩阵的本征值可以得到矩... 阅读全帖 |
|
b********n
发帖数: 29 | 30 花了两个礼拜才做出来。。。各种查资料。。。
数学上面，得到恒定差的次数是p_1+...+p_n, 得到的定差结果是d1^p1*d2^p2...*dn^
pn*(p1+..._pn)!
这个公式可以通过自己手推，把2个等差数列乘起来，你会发现求两次差就可以得到定
值，把3个乘起来，...一直到把n个乘起来，得到的求差次数是一个和式（在这个网页
里面有http://www.mymathforum.com/viewtopic.php?f=40&t=7993）而这个和式正好等于(p1+...+pn)!
下面的问题就在于提高运算效率，有三点
第一点就是如何maintain任何一个区间里的(p1+...+pn)和d1^p1*...*dn^pn. 这个因为
是range query，用segment tree得到，可以得到lg(n)的update和query time.如果每
次query都需要求一遍和的话，需要O(n)时间，如果提前算prefix sum的话，query是O(
1)，可是update v需要O(n)，所以两种方法都会超时，必须同时有O(lgn)的update和
query time... 阅读全帖 |
|
a***r
发帖数: 93 | 31
Complexity
Constant (in the priority_queue). Although notice that push_heap operates
in logarithmic time.
I think it means the time spent inside priority_queue is O(1),if adding in
push_heap, the overall complexity should be O(lgN). |
|
y****n
发帖数: 743 | 32 牛顿迭代的算法要远好于Binary Search的O(lgn)。
贴个Sqrt(double)的算法。
static double Sqrt(double num)
{
double root = 1;
double diff = num - root * root;
double oldDiff = double.MaxValue;
int loop = 0;
while ((loop < 2) || (Math.Abs(diff) < Math.Abs(oldDiff)))
{
root = root + diff / root / 2;
oldDiff = diff;
diff = num - root * root;
loop++;
}
return root;
} |
|
k*******t
发帖数: 144 | 33 有个疑问，如果这个数组是sorted, 是不是可以用binary search？每次看到一个元素
，比较小相邻的两个值，没有相等的话，再根据index和对应的值决定向左或向右。这
样只要O(lgn), 不知这个有没有什么问题？ |
|
r*******e
发帖数: 7583 | 34 到达时间放进order-statistic tree
然后根据出发从早到晚，依次查询到达时间的rank，也就是score
同时每查询一个，就从tree里删掉一个
每次查询和删除都是O(lgn)
间 |
|
j*****s
发帖数: 189 | 35 这个解法我面试的时候说了，但他说不是n*lgn的，你看，你这个依赖于数组中最大和
最小的值，所以，实际上是Lg(max(a)) * n |
|
j*****s
发帖数: 189 | 36 这个解法我面试的时候说了，但他说不是n*lgn的，你看，你这个依赖于数组中最大和
最小的值，所以，实际上是Lg(max(a)) * n |
|
s****A
发帖数: 80 | 37 直觉的意思就是
比如一般看到嵌套循环,就知道大概是n^2
看到从树的root到leaf的操作，大概就是lgn
推导的话就是比较严谨点的，比如heap的heapify操作，先要想到size为n的binary
tree左右两个子树每个size最多不超过2n/3,然后得到T(n)<=T(2n/3)+O(1),用master
theorem得到最后结果
请问面试中大家一般都会按哪种做法？ |
|
s*******s
发帖数: 1031 | 38 我只能做出n lgn 的算法，是不是有比这个更好的？ |
|
p****3
发帖数: 448 | 39 我是这么想的(假设n x n)
左上角肯定是最小值
右下角肯定是最大
那么每个包含的小矩阵也是最小值在左上角
选了[0][0]后有两个小矩阵的左上角是可能的下一个最小值
以此类推最多从n个数中选下一个最小值
最坏情况O(n^2 lgn)
但从n个数中选下一个最小值的情况很少出现(只有一次)
我猜还是O(n^2) |
|
r*******e
发帖数: 7583 | 40 来自主题: JobHunting版 - 两道F的题 你说的操作都没错，不过找出j这个位置最快也需要O(lgn)把
an
6
it' |
|
L***n
发帖数: 311 | 41 divide-n-conquer
时间要求 NlgN
空间要求 lgN |
|
x*********w
发帖数: 533 | 42 order statistic tree
每个node按时间顺序排序，每个node保存子树个数和代表event的时间戳，一个node获
取需要lgn的复杂度。每当一个event arrive, 很快可以知道时间范围。
问题是怎么有效的清除过期节点并保持statistic tree的平衡 |
|
a**********e
发帖数: 36 | 43 I have one question regarding this problem: what does "the last second"
mean? It could mean 1 second before the current time till now, it could also
mean the last second slot (the most recent time round to seconds minus the
second most recent time round to seconds).
The first case (1s before current time till now) is more real time, and in
this case we can use a vector (or deque or any container that can be
dynamically expanded or shrinked with random accesses) to store the time of
incoming req... 阅读全帖 |
|
x*********w
发帖数: 533 | 44 order statistic tree
每个node按时间顺序排序，每个node保存子树个数和代表event的时间戳，一个node获
取需要lgn的复杂度。每当一个event arrive, 很快可以知道时间范围。
问题是怎么有效的清除过期节点并保持statistic tree的平衡 |
|
a**********e
发帖数: 36 | 45 I have one question regarding this problem: what does "the last second"
mean? It could mean 1 second before the current time till now, it could also
mean the last second slot (the most recent time round to seconds minus the
second most recent time round to seconds).
The first case (1s before current time till now) is more real time, and in
this case we can use a vector (or deque or any container that can be
dynamically expanded or shrinked with random accesses) to store the time of
incoming req... 阅读全帖 |
|
c******a
发帖数: 789 | 46 来自主题: JobHunting版 - 问到G家题 你这就O(n)了。楼主那个O(lgN) |
|
c******a
发帖数: 789 | 47 来自主题: JobHunting版 - 问到G家题 哦！明白了，相当于binary search。那的确是lgN
root. |
|
c********e
发帖数: 186 | 48 2D sorted array 就是行sorted，列sorted吗？知道是从top right corner或者bottom
left开始可以。想知道楼主用two binary search是O(lgn)吗？ 请问怎么做呢？ |
|
z****e
发帖数: 54598 | 49 复杂度是(lgn)^2 ＝ n
跟从右上开始是一样的 |
|
s*********n
发帖数: 191 | 50 发个新面经，供各位大神参考，攒人品。顺便吐槽一下自己的悲惨遭遇。
投的位置是general software engineer new grad.
第一轮45分钟电面的期间正好赶上本地挂了场雷暴，可能有信号塔受影响了，期间几天
手机信号时断时续。面试官是个老印，自称打了1个电话没我没接。我解释我这里没收
到。然后HR又打了个来，说老印跟他说我不接电话。然后赶紧开始面。老印口音很重，
加上语音断断续续，很难听懂说什么。第一句话就是“Can I assume you are a
machine learning expert?”因为自己仅仅是个硕士，是有一点相关的灌水paper，所
以估计老印是要阴人，害怕老印下套，解释了下自己只是个new grad master，不是什
么expert.老印还是不依不饶，丢来一个matrix，让求协方差矩阵。这道题就是理论题
，让我算，不是coding题。大致解释下计算流程。
可能信号太差他也听不清楚我说什么。于是他改为问求multi-dimensional gaussian的
参数，然后我解释先求u，再去运算∑，期间和老印基本互相说什么都不知道，只能在... 阅读全帖 |
|
