T400s要换硬盘，是不是需要一个光驱adaptor? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Hardware - 计算机硬件

T400s要换硬盘，是不是需要一个光驱adaptor?

T400s要换硬盘，是不是需要一个光驱adaptor?# Hardware - 计算机硬件

a*g2011-06-15 07:06

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

h*i2011-06-15 07:06

2 楼

雪儿18岁了，一天吃饭前，妈妈突然拉着她上下打量了一圈，
满意又幸福地说：“雪儿真是遗传我的，和我年轻时一样漂亮！”
我爸爸坐在一边椅子上，本来在看报纸，听这么一说，
抬起头来也打量了我一下，点点头沉着道：
“就是这胸是遗传我的…”我当时就傻了…泪……

s*s2011-06-15 07:06

3 楼

那个1.8的硬盘ms不比SSD便宜，是不是要装光驱位2.5? 哪里买的adaptor?
光驱位能做主盘么？

r*o2011-06-15 07:06

4 楼

第一题两个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*s2011-06-15 07:06

5 楼

T400s的光驱不是超薄的那种？

【在 s******s 的大作中提到】

: 那个1.8的硬盘ms不比SSD便宜，是不是要装光驱位2.5? 哪里买的adaptor?
: 光驱位能做主盘么？

a*g2011-06-15 07:06

6 楼

可以不一样长
min heap不能find the item quickly

【在 r****o 的大作中提到】

: 第一题两个sorted array是不是可以不一样长？
: 第二题可以用min heap实现吗？
:
: A

s*s2011-06-15 07:06

7 楼

不知道。可能是。不能换么？

【在 A*****s 的大作中提到】

: T400s的光驱不是超薄的那种？

r*o2011-06-15 07:06

8 楼

min heap直接返回top不就可以了吗？

【在 a***g 的大作中提到】

: 可以不一样长
: min heap不能find the item quickly

A*s2011-06-15 07:06

9 楼

超薄的是放不了硬盘的
但是不知道T400s是不是超薄光驱

【在 s******s 的大作中提到】

: 不知道。可能是。不能换么？

a*g2011-06-15 07:06

10 楼

top is the minimal, you also need to access to any other item quickly

【在 r****o 的大作中提到】

: min heap直接返回top不就可以了吗？

l*n2011-06-15 07:06

11 楼

thinkpad有光驱的都行吧

m*u2011-06-15 07:06

12 楼

第一题怎么做?

A*s2011-06-15 07:06

13 楼

x300/301就不行，超薄光驱，比2.5寸的硬盘都薄

【在 l*****n 的大作中提到】

: thinkpad有光驱的都行吧

c*a2011-06-15 07:06

14 楼

log(k)?
log(N) 可以实现吧。 log(k) 不可能吧。
第一题。
第二题， 2个binary tree，再加一个 stack 不久行了。

A

【在 a***g 的大作中提到】

p*i2011-06-15 07:06

15 楼

我从ebay买了一个山寨adapter,用起来没问题。
据说可以做主盘，我没有试过。

【在 s******s 的大作中提到】

: 那个1.8的硬盘ms不比SSD便宜，是不是要装光驱位2.5? 哪里买的adaptor?
: 光驱位能做主盘么？

h*r2011-06-15 07:06

16 楼

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

A*s2011-06-15 07:06

17 楼

可以做主盤，我試過的從T41開始就可以

【在 p****i 的大作中提到】

: 我从ebay买了一个山寨adapter,用起来没问题。
: 据说可以做主盘，我没有试过。

r*o2011-06-15 07:06

18 楼

请问你能不能再推广到更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*o2011-06-15 07:06

19 楼

能不能说说第二题为什么用binary tree和stack？

【在 c**a 的大作中提到】

: log(k)?
: log(N) 可以实现吧。 log(k) 不可能吧。
: 第一题。
: 第二题， 2个binary tree，再加一个 stack 不久行了。
:
: A

h*r2011-06-15 07:06

20 楼

这两个都还不到search 2k data的程度。

【在 r****o 的大作中提到】

: 请问你能不能再推广到更general的case,
: 1)一个array 长度>k,另一个array长度: 2)两个array长度都k
:
: 从N
: /2

r*o2011-06-15 07:06

21 楼

题目是要log(k)的复杂度啊。

【在 h****r 的大作中提到】

: 这两个都还不到search 2k data的程度。

b*v2011-06-15 07:06

22 楼

第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 的大作中提到】

s*t2011-06-15 07:06

23 楼

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 的大作中提到】

b*v2011-06-15 07:06

24 楼

如果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*o2011-06-15 07:06

25 楼

你说的第2)和第3)种情况有什么区别?

【在 b******v 的大作中提到】

b*v2011-06-15 07:06

26 楼

例如A=100, B=300, k=350
这属于第(2)种情况(k>=B)，只需考虑A的后50和B的后50取median
但是如果k=200(A
【在 r****o 的大作中提到】

: 你说的第2)和第3)种情况有什么区别?

r*o2011-06-15 07:06

27 楼

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*v2011-06-15 07:06

28 楼

情况(2)
三种情形分别为
(1) k <=A
(2) k >=B
(3) A
【在 r****o 的大作中提到】

: how about A=70, B=80, k=100?

y*i2011-06-15 07:06

29 楼

如果所有的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*v2011-06-15 07:06

30 楼

good point我再想想

（B

【在 y**i 的大作中提到】

: 如果所有的A都比B小，那么kth元素将是B的250th元素，那你这个情况不是漏选了？（B
: 的后50是从251th-300th）

b*v2011-06-15 07:06

31 楼

我把前文修改了，三种情况的边界应该是
(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*62011-06-15 07:06

32 楼

总结一下：
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*32011-06-15 07:06

33 楼

第二题可以用balanced search tree, 比如RBT
在每个节点中保存以下信息
1) cache tag -> 查找O(lgn)
2) 以本节点为根的子树中最小recent used值 ->查找LRU O(lgn)

f*e2011-06-15 07:06

34 楼

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*a2011-06-15 07:06

35 楼

Can I use a hashtable and a min heap for the second problem?

A

【在 a***g 的大作中提到】

H*L2011-06-15 07:06

36 楼

这个方法和2K里找MEDIAN思路相同但实现比较简洁

从N
/2

【在 h****r 的大作中提到】

x*32011-06-15 07:06

37 楼

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*s2011-06-15 07:06

38 楼

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 (kreturn A[k-1];
else
throw std::exception();
}

unsigned int index1, index2;
index1 = std::min(k-1, sizeA-1);
index2 = 0;

i*s2011-06-15 07:06

39 楼

for question 2, I still it should use a min-priority queue.

h*x2011-06-15 07:06

40 楼

可以
是找到第k个元素，不是找到等于k的元素，你想难了。

【在 c**a 的大作中提到】

: log(k)?
: log(N) 可以实现吧。 log(k) 不可能吧。
: 第一题。
: 第二题， 2个binary tree，再加一个 stack 不久行了。
:
: A

S*a2011-06-15 07:06

41 楼

其实，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)个数，则需要求出中位数
: 有没有人介绍一下第二题的解法啊？