f*l
发帖数: 161 | 1 一次面试碰到的
1） 两个sorted大数组，只有某几个小区域有重复的值(那个区域不详)，如何找到那些
重复的值。比如数组A,B 有1M， 但是A[4-10]与B[10000-1010]有部分重复的值
对于这个零星的区域，没有想出办法
2） 一个长的list，通常操作（添加和删除）都发生在相距较远的节点间，不如一个在
位置10， 一个在位置10000. 如果设计去保证thread safe
一种想法是：使用lock根据区域，然后使用global lock处理区域间的处理。但是如何
维护区域是一个问题。
3）一个数据集有很多对象，如果更新两个对象A,B 保证thread safe，但是不使用
global lock。
一种想法是： lock_a, lock_b, unlock_b, unlock_a.但是会有死锁如果有人反过来调
用。改进的是比较A,B,决定锁的顺序 | s*****u
发帖数: 151 | 2 3的想法不可靠好像。2个事务t1,t2分别更新AB和BC, t1获取A，T2获取B以后就锁了。
lock free做法是搞一个对象的版本号。 | l*n
发帖数: 529 | 3 http://stackoverflow.com/a/4601106/2073130
二分，在A中间找个数，然后在B里面搜，搜没搜到都把B切成了两半，A也是两半。然后
左边对左边，右边对右边，递归之。
【在 f*l 的大作中提到】
: 一次面试碰到的
: 1） 两个sorted大数组，只有某几个小区域有重复的值(那个区域不详)，如何找到那些
: 重复的值。比如数组A,B 有1M， 但是A[4-10]与B[10000-1010]有部分重复的值
: 对于这个零星的区域，没有想出办法
: 2） 一个长的list，通常操作（添加和删除）都发生在相距较远的节点间，不如一个在
: 位置10， 一个在位置10000. 如果设计去保证thread safe
: 一种想法是：使用lock根据区域，然后使用global lock处理区域间的处理。但是如何
: 维护区域是一个问题。
: 3）一个数据集有很多对象，如果更新两个对象A,B 保证thread safe，但是不使用
: global lock。
| f*l
发帖数: 161 | 4 这个应该没事啊，t1可以等到t2释放B继续
【在 s*****u 的大作中提到】
: 3的想法不可靠好像。2个事务t1,t2分别更新AB和BC, t1获取A，T2获取B以后就锁了。
: lock free做法是搞一个对象的版本号。
| f*l
发帖数: 161 | 5 这个条件只有几个很小的区域有重复似乎没有用到。
【在 l*n 的大作中提到】
: http://stackoverflow.com/a/4601106/2073130
: 二分，在A中间找个数，然后在B里面搜，搜没搜到都把B切成了两半，A也是两半。然后
: 左边对左边，右边对右边，递归之。
|
|
