P*****f
发帖数: 2272 | 1 baseline的解法就是dp了.O(MN)
当然在实际中可以根据输入先算一些hash值,提高amortized performance
one. |
|
o*******7
发帖数: 13 | 2 O(n)还是有希望的。虽然每个element移动最坏情况下确实要O(n)步，但是如果设计巧
妙的话，有可能并不是每一个
element都需要O(n)，这样amortize下来，也许最后能平均成O(1). 最后也许O(n)就能
解决...
但是具体怎么做还没想到。 |
|
n******n
发帖数: 49 | 3 对的就是挨个网里塞，但是hash_set c++中insert/lookup amortized下来都是o(1),普
通set是红黑树实现，o(lgn),所以普通set慢一点。
set |
|
j**l
发帖数: 2911 | 4 不管是原始名题O(1)求栈最小(或最大)
还是变体题O(1)求队列最小(或最大)
还是这道滑动窗口题，
思路都是空间换时间，核心都是用空间维持一个序列，因为最大的可能会被删除，原来
小的会变为最大。可以用辅助栈，可以给元素增加链域，也可以这道题那样单独用一个
链表(其实也是一个辅助队列，一个特殊的双端操作的队列)
所谓O(1)都是amortized分析，也就是看每个元素出入辅助空间的次数
单次操作当然有可能是O(k)的 |
|
d*****t
发帖数: 41 | 5 这个可以把给定的n个单词先放到hash table里。
然后从文章开始，每扫一个单词到hash table里找，如果在就把单词和位置放到queue
里，一直到这n个单词都在queue里（有的单词可能出现多次），记下此时cover
distance。这之后每次往queue里加单词的时候，如果检查queue的前端，如果是同一个
单词，就pop。每次pop之后从queue前往后扫描一直扫到queue里只出现一次的元素，把
前面的删除，确保queue里不会所有的单词都出现2遍，同时更新cover distance,一直
到扫完text
貌似用这种方法是，amortized O（n）,但是更新queue导致不能保证O（n）
呼唤更好的办法~ |
|
|
c***r
发帖数: 46 | 7 An alternative method. 先找数组中存在的最小的大于1的值。 把这个减一即可。
Amortized O(n), in place. Don't destory input values.
Think about this way first.
1) For all in input:
If value <= 1, value = LargePositive
2) Construct a min-heap. Output the root.
In fact, step 1) is not necessary. You just need to modify your comparator
function so that all values <=1 are treated as max. |
|
|
i**********e
发帖数: 1145 | 9 恩，说得对，的确不能保证保持原有顺序。
那这样呢，假设三个 index 为 lo, mid, hi，并且同时满足以下条件：
A[i] < 0, All i < lo
A[j] == 0, i <= j < mid
A[k] > 0, mid <= k < hi
当 A[hi] 与 A[mid] 交换了之后，就把 A[mid+1] 到 A[hi-1] 往上移一步， 再把原
来的 A[hi] 插入 A[mid+1] 的位置就好。这样能保证原有顺序。
至于最坏情况的复杂度呢，是否 O(N^2) 还有待验证。也有可能 amortized O(N) run
time.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
Z**********4
发帖数: 528 | 10 前两个问题MIT的那本算法书上都有
第一个问题貌似在讲amortized analysis中有
第二个问题就看hash表那一章 |
|
j********x
发帖数: 2330 | 11 Effect of different data structures
The designer of the priority queue should take into account what sort of
access pattern the priority queue will be subject to, and what computational
resources are most important to the designer. The designer can then use
various specialized types of heaps:
There are a number of specialized heap data structures that either supply
additional operations or outperform the above approaches. The binary heap
uses O(log n) time for both operations, but allows peeking... 阅读全帖 |
|
N*****8
发帖数: 253 | 12 "平摊分析"amortized analysis?
能给一个数学的推算公式吗？ |
|
i**********e
发帖数: 1145 | 13 来自主题: JobHunting版 - 上一道题吧 我想到一个办法，利用双链表来表达字符串，每个字符中间有一个数字（首先全都初始
化为 0 ）。
然后一次从头到尾扫描，注意以下这两个条件：
- 每次看到数字左边和右边个别是 ‘（’和‘）’就删掉左边和右边的 node，然后把
数字本身 + 2.
- 另外，如果左边也是个数字，就两个数字加起来进行合并。
直到以上两个条件不符合为止，就继续看下一个 node。
这个似乎要花费 O(n) 空间，但应该是 amortized O(n) 时间. |
|
h********e
发帖数: 1972 | 14 来自主题: JobHunting版 - 问一道老题 仔细想啊-0- 。。。别重复找,每次min，max都是list的第一个元素，不需要扫一遍list。。找过的都扔掉了。。amortize下来肯定O(1).就两个指针，永远不回头的。不可能搞出n^2的复杂度。
应该叫skiplist。。不过这里的用法跟skiplist的本意应该不一样。反正很简单，就是个array里面每个元素都有可能有一个指针指向下一个要去的地方。这样就有O(1) access, which is better than linked list. |
|
S******t
发帖数: 151 | 15 No, delete() is still amortized O(1) |
|
z*********8
发帖数: 2070 | 16 经典教材<算法导论>上面就有这章 amortized analysis
现在听说过了吧 |
|
h********g
发帖数: 155 | 17 你应该把目光集中到累积分析上面，不要只注重一个操作所需的时间，而是所有操作所
需的时间的和。对单个操作来讲当然是O（N），但是如果把它们求和就还是O（N），因
为你从后向前操作，永远不用回头，所以操作的时间累积不会超过O（N）。
你也可以试着搜索amortized analysis，看看相关几个问题的经典分析。记得Cormen的
算法书上也有专门一章讲这个的。
(1 |
|
f***n
发帖数: 117 | 18 我明白你的意思，但我觉得加起来是O(N*k1), k1是正数的个数。
想一个简单的worst case，所有正数在一边负数在一边，每一个正数都需要从一边挪到
另一边，而且只能一个位置一个位置的挪，这本身就是O(k1^2)，对吧？ amortize后不
会是O(N)啊 |
|
v****c
发帖数: 29 | 19 next_permutation 的amortized cost 是 O(1) |
|
v****c
发帖数: 29 | 20 这个就是O(log n + m)，虽然worst case每一步都是log n
但是你算算看amortized cost，多出来的那部分被log n absorb掉了 |
|
|
w****x
发帖数: 2483 | 22 挑了一些比较主要的章节, 分先后顺序, 不知道合不合理
Chapter 5: Probability analyze and Randomized Algorithms (Along with
Appendix C1, C2, C3)
Chapter 6: Heap sort
Chapter 7: Quick sort
Chapter 11: Hash Tables
Chapter 12: Binary search trees
Chapter 14.3: Interval tree
Chapter 32: String matching
Chapter 22: Elementary Graph Algorithm
Chapter 24.3: Dijkstra algorithm
Chapter 4: Recurrences
Chapter 9: Medians and order stastics
Chapter 15: Dynamic Programming
Chapter 16: Greedy Algorithm
Chapter 17: Amortized analysis
Ch... 阅读全帖 |
|
w****x
发帖数: 2483 | 23
我根据我个人需求整理了一下比较重要的几章:
Chapter 5: Probability analyze and Randomized Algorithms (Along with
Appendix C1, C2, C3)
Chapter 6: Heap sort
Chapter 7: Quick sort
Chapter 11: Hash Tables
Chapter 12: Binary search trees
Chapter 14.3: Interval tree
Chapter 32: String matching
Chapter 22: Elementary Graph Algorithm
Chapter 24.3: Dijkstra algorithm
Chapter 4: Recurrences
Chapter 9: Medians and order stastics
Chapter 15: Dynamic Programming
Chapter 16: Greedy Algorithm
Chapter 17: Amortized analysis
Chapter... 阅读全帖 |
|
c*****t
发帖数: 93 | 24 问了一下以前project的biggest challenge
coding题没做好。他先问了怎么用stack来实现queue。我说用两个stack来做
然后他说amortized time complexity是多少。我说insert, remove都是O(1)
然后他问worst case time complexity for remove是多少，这个我以为他是让我算每
个case中最差的那个remove是多少，我说可能是n/2吧，或者是sqrt(n)，我说不不太清
楚。没想到他其实是让我求每个case中，remove总共需要的时间，答案是O(3n)。在这
个问题上纠结时间挺长的
总之这块根本准备的时候没看过。没想到会问这么细。而且面试官是俄国人，口音很重
，也有一定问题。
祝同学们都面试好运！ |
|
|
l*****a
发帖数: 14598 | 26 for n-1 times, u need O(1), for 1 times ,u need O(n)
1) remove a node in a list ,given the head.
2) ArrayList/Vector.add(); |
|
|
O******i
发帖数: 269 | 28 还有用两个栈实现一个队列，从每个元素的角度看，O(1) |
|
e****e
发帖数: 418 | 29 two stack实现一个queue, 我能理解，从一个stack倒到另一个stack时是O(n),以后的
pop都是O(1). 你给的两个例子能详细说说是怎么for n-1 times, u need O(1), for 1
times ,u need O(n)?谢谢。 |
|
|
d******e
发帖数: 164 | 31 第一题是给head和ptr to the node to be removed 吧？ |
|
w****x
发帖数: 2483 | 32
可能指的是amortized的复杂度是O(n^2)，毕竟当前的max size很大的限制了计算量，
感觉有可能是O(n^2),但是数学功底有限，不知道怎么证明 |
|
|
l*****a
发帖数: 14598 | 34 两个指针一起向前走，为什么还要amortized |
|
p*****p
发帖数: 379 | 35 The array is not sorted so not possible to get that in linear time
qsort can do that in amortized O(n) but not worst case |
|
d*s
发帖数: 699 | 36 universal hashing，按我的理解，是在每次create instance的时候用随机的hash
function, 一旦instantiated之后就不变了，也就是说你的table只要存在就用同样的
hash function访问，但你想攻击我的系统，我只要做一个新的table出来，然后把原来
的数据全部copy过来就行了。这个cost amortized之后就忽略不计了 |
|
o****d
发帖数: 2835 | 37 yes, O(1) should be amortized time cost, including hashtable.
O( |
|
s*****c
发帖数: 122 | 38 "每次碰到index比现在array的size大的话，我就double，所以应该是一个o(logn)的
效率"
-- amortized complexity of vector doubling should be o(1) |
|
a***r
发帖数: 93 | 39
My implementation is based on BinaryHeap,insert's worst-case cost is O(logN)
Fibonacci Heap's insert amortized cost is O(1)
which C++ document are you referring to? |
|
l*****a
发帖数: 14598 | 40 转载一个牛人的经验.
发信人: wwwyhx (wwwyhx), 信区: JobHunting
标 题: Re: 看来还是要看算法导论啊
发信站: BBS 未名空间站 (Sun Nov 18 23:33:22 2012, 美东)
我根据我个人需求整理了一下比较重要的几章:
Chapter 5: Probability analyze and Randomized Algorithms (Along with
Appendix C1, C2, C3)
Chapter 6: Heap sort
Chapter 7: Quick sort
Chapter 11: Hash Tables
Chapter 12: Binary search trees
Chapter 14.3: Interval tree
Chapter 32: String matching
Chapter 22: Elementary Graph Algorithm
Chapter 24.3: Dijkstra algorithm
Chapter 4: Recurrences
Chapter 9: Medians and... 阅读全帖 |
|
t*q
发帖数: 104 | 41 Amortized O(1)
有可能存很多数，如果序列是一直递减的 |
|
b***e
发帖数: 1419 | 42 Imagine there's a hanoi stack. Each time you get a new number i, it pop all
the numbers from the top that are less than i, until the top of the stack
is greater than i. Now push i in the stack. This way, any time you have
the max at the bottom of the stack. The maintenance of the stack is
amortized to be O(1) per number, because each number is in once and out once. |
|
f*********m
发帖数: 726 | 43 能避免用这个12个月的数据数组吗？
我觉得每秒都需要更新吧，至少每秒要删掉超过12个月的数据。
Max和Min value的数据需要两个变量，同时还要记录这两个变量在12个月数据数组中的
位置，若他们中的任何一个被dsicard了，就的扫描整个数组，找到新的Max和Min
value的，对吧？平均来说 amortized time可能还是O（1）。
或者用两个stack，分别装每个时刻的Max和Min value，Max和Min value被从12个月的
数组discard后就从stack pop掉。 |
|
l********n
发帖数: 54 | 44 我对楼主TreeMap或者MinHeap & MaxHeap的方案有点疑问。
按我的理解，MaxHeap应该记录Max值的。如果在future的stream price大于heap top的
值，那么更新top.但假设t1的值是20, (t2, 15), (t3, 19),然后t3后的值都小于19。
那么在t1 expire后，max of t3就丢失了。
我能想的用minHeap & maxHeap的情况是用 linked list + heap。linked list 按照时
间顺序insert,当list head expire时候delete。每次insert & delete都fix heap. 不
知道楼主是不是这个意思。
我想到一中方案使用deque.
find max:
(1) 当stream data中一个值v来的时候，不断pop_back queue中所有比v小的。
(2) query max的时候，check queue front的data是否expire, 如果expire pop_front
到12 months内的data,那就是max。有点leetco... 阅读全帖 |
|
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... 阅读全帖 |
|
a**********e
发帖数: 36 | 46 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****y
发帖数: 581 | 47 我查了这个Amortized Time worst case可以是o(n)， 如果要resize arraylist
的话 |
|
|
d**********u
发帖数: 3371 | 49 比如我觉得union find也比较适合这个题目啊 amortize o(1) 不过还是得先用size排序 |
|
d**********u
发帖数: 3371 | 50 比如我觉得union find也比较适合这个题目啊 amortize o(1) 不过还是得先用size排序 |
|
