a***g 发帖数: 234 | 1 1. Given 2 sorted arrays A and B, find the kth element in the merged array A
U B
Time complexity requirement: log(k)
2. Least Recently Used (LRU) Cache: discards the least recently used items
first
How do you design and implement such a cache class?
1) find or search the item quickly
2) when there is a cache miss and cache is full, u want to replace the
least recently used item quickly |
r****o 发帖数: 1950 | 2 第一题两个sorted array是不是可以不一样长?
第二题可以用min heap实现吗?
A
【在 a***g 的大作中提到】 : 1. Given 2 sorted arrays A and B, find the kth element in the merged array A : U B : Time complexity requirement: log(k) : 2. Least Recently Used (LRU) Cache: discards the least recently used items : first : How do you design and implement such a cache class? : 1) find or search the item quickly : 2) when there is a cache miss and cache is full, u want to replace the : least recently used item quickly
|
a***g 发帖数: 234 | 3 可以不一样长
min heap不能find the item quickly
【在 r****o 的大作中提到】 : 第一题两个sorted array是不是可以不一样长? : 第二题可以用min heap实现吗? : : A
|
r****o 发帖数: 1950 | 4 min heap直接返回top不就可以了吗?
【在 a***g 的大作中提到】 : 可以不一样长 : min heap不能find the item quickly
|
a***g 发帖数: 234 | 5 top is the minimal, you also need to access to any other item quickly
【在 r****o 的大作中提到】 : min heap直接返回top不就可以了吗?
|
m****u 发帖数: 3915 | |
c**a 发帖数: 316 | 7 log(k)?
log(N) 可以实现吧。 log(k) 不可能吧。
第一题。
第二题, 2个binary tree, 再加一个 stack 不久行了。
A
【在 a***g 的大作中提到】 : 1. Given 2 sorted arrays A and B, find the kth element in the merged array A : U B : Time complexity requirement: log(k) : 2. Least Recently Used (LRU) Cache: discards the least recently used items : first : How do you design and implement such a cache class? : 1) find or search the item quickly : 2) when there is a cache miss and cache is full, u want to replace the : least recently used item quickly
|
h****r 发帖数: 2056 | 8 log(k)可能,
把问题退化为find k th element from a[0,k-1] and b[0,k-1],一下子就查找长度从N
退化到k级别(2k)。
比较a[k/2]和b[k/2],如果a[k/2]小,那么 the element一定在a[k/2,k]和 b[0, k/2
]中,反之则在a[0, k/2]和b[k/2,k]中,重复这个步骤继续二分法比较下去即可。
【在 c**a 的大作中提到】 : log(k)? : log(N) 可以实现吧。 log(k) 不可能吧。 : 第一题。 : 第二题, 2个binary tree, 再加一个 stack 不久行了。 : : A
|
r****o 发帖数: 1950 | 9 请问你能不能再推广到更general的case,
1)一个array 长度>k,另一个array长度
2)两个array长度都k
从N
/2
【在 h****r 的大作中提到】 : log(k)可能, : 把问题退化为find k th element from a[0,k-1] and b[0,k-1],一下子就查找长度从N : 退化到k级别(2k)。 : 比较a[k/2]和b[k/2],如果a[k/2]小,那么 the element一定在a[k/2,k]和 b[0, k/2 : ]中,反之则在a[0, k/2]和b[k/2,k]中,重复这个步骤继续二分法比较下去即可。
|
r****o 发帖数: 1950 | 10 能不能说说第二题为什么用binary tree和stack?
【在 c**a 的大作中提到】 : log(k)? : log(N) 可以实现吧。 log(k) 不可能吧。 : 第一题。 : 第二题, 2个binary tree, 再加一个 stack 不久行了。 : : A
|
|
|
h****r 发帖数: 2056 | 11 这两个都还不到search 2k data的程度。
【在 r****o 的大作中提到】 : 请问你能不能再推广到更general的case, : 1)一个array 长度>k,另一个array长度: 2)两个array长度都k : : 从N : /2
|
r****o 发帖数: 1950 | 12 题目是要log(k)的复杂度啊。
【在 h****r 的大作中提到】 : 这两个都还不到search 2k data的程度。
|
b******v 发帖数: 1493 | 13 第1题:假设A,B的size分别为A, B,不失一般性,假设A <= B
(1)先假设k <= A
则merge后的第k个元素只可能在A和B的前k个元素里面,并且是这2k个元素的median
在两个size为k的sorted array中找median是网上的老题,复杂性log(k)
(2)如果k > A
如果A+B-k+1 <= A (i.e. k >=B+1 ),则可以考虑A和B的后A+B-k+1个元素找median
O(log(A+B-k+1)) <= O(log(k+k-k)) = O(log(k))
(3) 如果 A < k <= B
这个等我吃完饭继续想
A
【在 a***g 的大作中提到】 : 1. Given 2 sorted arrays A and B, find the kth element in the merged array A : U B : Time complexity requirement: log(k) : 2. Least Recently Used (LRU) Cache: discards the least recently used items : first : How do you design and implement such a cache class? : 1) find or search the item quickly : 2) when there is a cache miss and cache is full, u want to replace the : least recently used item quickly
|
s*********t 发帖数: 1663 | 14 find(a[0,k],b[0,k]):
if a(k/2)==b(k/2): OK!
elif a(k/2)>b(k/2): find( a[0,k/2], b[k/2, k] )
else find(a[k/2,k],b[0,k/2])
A
【在 a***g 的大作中提到】 : 1. Given 2 sorted arrays A and B, find the kth element in the merged array A : U B : Time complexity requirement: log(k) : 2. Least Recently Used (LRU) Cache: discards the least recently used items : first : How do you design and implement such a cache class? : 1) find or search the item quickly : 2) when there is a cache miss and cache is full, u want to replace the : least recently used item quickly
|
b******v 发帖数: 1493 | 15 如果A < k <= B
则取array B的median,用binary search找出它在A中的位置,
由此可以找出它在整个(A+B)个数中的位置k0,
(a)如果k = k0,则程序结束
(b)如果k < k0,则可以扔掉B的后一半和A的后半段
(c)如果k > k0, 则可以扔掉B的前一半和A的前半段
这样问题转化为两个size为A'和B/2的sorted array的情形
使用递归可以解决
【在 b******v 的大作中提到】 : 第1题:假设A,B的size分别为A, B,不失一般性,假设A <= B : (1)先假设k <= A : 则merge后的第k个元素只可能在A和B的前k个元素里面,并且是这2k个元素的median : 在两个size为k的sorted array中找median是网上的老题,复杂性log(k) : (2)如果k > A : 如果A+B-k+1 <= A (i.e. k >=B+1 ),则可以考虑A和B的后A+B-k+1个元素找median : O(log(A+B-k+1)) <= O(log(k+k-k)) = O(log(k)) : (3) 如果 A < k <= B : 这个等我吃完饭继续想 :
|
r****o 发帖数: 1950 | 16 你说的第2)和第3)种情况有什么区别?
【在 b******v 的大作中提到】 : 第1题:假设A,B的size分别为A, B,不失一般性,假设A <= B : (1)先假设k <= A : 则merge后的第k个元素只可能在A和B的前k个元素里面,并且是这2k个元素的median : 在两个size为k的sorted array中找median是网上的老题,复杂性log(k) : (2)如果k > A : 如果A+B-k+1 <= A (i.e. k >=B+1 ),则可以考虑A和B的后A+B-k+1个元素找median : O(log(A+B-k+1)) <= O(log(k+k-k)) = O(log(k)) : (3) 如果 A < k <= B : 这个等我吃完饭继续想 :
|
b******v 发帖数: 1493 | 17 例如A=100, B=300, k=350
这属于第(2)种情况(k>=B),只需考虑A的后50和B的后50取median
但是如果k=200(A
【在 r****o 的大作中提到】 : 你说的第2)和第3)种情况有什么区别?
|
r****o 发帖数: 1950 | 18 how about A=70, B=80, k=100?
【在 b******v 的大作中提到】 : 例如A=100, B=300, k=350 : 这属于第(2)种情况(k>=B),只需考虑A的后50和B的后50取median : 但是如果k=200(A
|
b******v 发帖数: 1493 | 19 情况(2)
三种情形分别为
(1) k <=A
(2) k >=B
(3) A
【在 r****o 的大作中提到】 : how about A=70, B=80, k=100?
|
y**i 发帖数: 1112 | 20 如果所有的A都比B小,那么kth元素将是B的250th元素,那你这个情况不是漏选了?(B
的后50是从251th-300th)
【在 b******v 的大作中提到】 : 例如A=100, B=300, k=350 : 这属于第(2)种情况(k>=B),只需考虑A的后50和B的后50取median : 但是如果k=200(A
|
|
|
b******v 发帖数: 1493 | 21 good point我再想想
(B
【在 y**i 的大作中提到】 : 如果所有的A都比B小,那么kth元素将是B的250th元素,那你这个情况不是漏选了?(B : 的后50是从251th-300th)
|
b******v 发帖数: 1493 | 22 我把前文修改了,三种情况的边界应该是
(1) k<=A
(2) k>B
(3) A
对于我前面举的那个例子,应该考虑A+B-k+1=51个元素,而不是50个元素
(B
【在 y**i 的大作中提到】 : 如果所有的A都比B小,那么kth元素将是B的250th元素,那你这个情况不是漏选了?(B : 的后50是从251th-300th)
|
h**6 发帖数: 4160 | 23 总结一下:
1若k<=min(A,B),则A B各取k
2若k>min(A,B),A+B>2k-1,则A全取,B取2k-A
3若k>min(A,B),A+B<2k-1,则令m=A+B-k+1,此时A+B>2m-1,转化为2
4若k>min(A,B),A+B=2k-1, 则A、B都全取
注意:
第1、2、3三种情况共取2k个数,需要求出左中位数,而不是中间两数的平均值
第4种情况共取(2k-1)个数,则需要求出中位数
有没有人介绍一下第二题的解法啊? |
x******3 发帖数: 245 | 24 第二题可以用balanced search tree, 比如RBT
在每个节点中保存以下信息
1) cache tag -> 查找O(lgn)
2) 以本节点为根的子树中最小recent used值 ->查找LRU O(lgn) |
f****e 发帖数: 30 | 25 when u visit a cache, LRU value should be modified. Then how can you change
the min LRU value in subtree within lg(n) complexity
【在 x******3 的大作中提到】 : 第二题可以用balanced search tree, 比如RBT : 在每个节点中保存以下信息 : 1) cache tag -> 查找O(lgn) : 2) 以本节点为根的子树中最小recent used值 ->查找LRU O(lgn)
|
s******a 发帖数: 103 | 26 Can I use a hashtable and a min heap for the second problem?
A
【在 a***g 的大作中提到】 : 1. Given 2 sorted arrays A and B, find the kth element in the merged array A : U B : Time complexity requirement: log(k) : 2. Least Recently Used (LRU) Cache: discards the least recently used items : first : How do you design and implement such a cache class? : 1) find or search the item quickly : 2) when there is a cache miss and cache is full, u want to replace the : least recently used item quickly
|
H*****L 发帖数: 5705 | 27 这个方法和2K里找MEDIAN思路相同但实现比较简洁
从N
/2
【在 h****r 的大作中提到】 : log(k)可能, : 把问题退化为find k th element from a[0,k-1] and b[0,k-1],一下子就查找长度从N : 退化到k级别(2k)。 : 比较a[k/2]和b[k/2],如果a[k/2]小,那么 the element一定在a[k/2,k]和 b[0, k/2 : ]中,反之则在a[0, k/2]和b[k/2,k]中,重复这个步骤继续二分法比较下去即可。
|
x******3 发帖数: 245 | 28 first find the search cache line, update its LRU value
then just walk up the tree to update each LRU value along its way towards to
root
since updating LRU value only needs to check itself and the new LRU value,
its complexity is just lgn
change
【在 f****e 的大作中提到】 : when u visit a cache, LRU value should be modified. Then how can you change : the min LRU value in subtree within lg(n) complexity
|
i********s 发帖数: 133 | 29 the code for the 1st problem. assume A[0] <= B[0].
int findK(int *A, int *B,
unsigned int sizeA, unsigned int sizeB,
unsigned k)
{
if (sizeA == 0)
{
if (k < sizeB)
return B[k-1];
else
throw std::exception();
}
if (sizeB == 0)
{
if (k
return A[k-1];
else
throw std::exception();
}
unsigned int index1, index2;
index1 = std::min(k-1, sizeA-1);
index2 = 0;
|
i********s 发帖数: 133 | 30 for question 2, I still it should use a min-priority queue. |
|
|
h*******x 发帖数: 12808 | 31 可以
是找到第k个元素,不是找到等于k的元素,你想难了。
【在 c**a 的大作中提到】 : log(k)? : log(N) 可以实现吧。 log(k) 不可能吧。 : 第一题。 : 第二题, 2个binary tree, 再加一个 stack 不久行了。 : : A
|
S******a 发帖数: 862 | 32 其实,k>min(A,B)时,把A,B后面补正无穷,补足到A,B都是k长度。
不用真改变数组的size,override []即可。
【在 h**6 的大作中提到】 : 总结一下: : 1若k<=min(A,B),则A B各取k : 2若k>min(A,B),A+B>2k-1,则A全取,B取2k-A : 3若k>min(A,B),A+B<2k-1,则令m=A+B-k+1,此时A+B>2m-1,转化为2 : 4若k>min(A,B),A+B=2k-1, 则A、B都全取 : 注意: : 第1、2、3三种情况共取2k个数,需要求出左中位数,而不是中间两数的平均值 : 第4种情况共取(2k-1)个数,则需要求出中位数 : 有没有人介绍一下第二题的解法啊?
|