L家 index设计题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

L家 index设计题

L家 index设计题# JobHunting - 待字闺中

s*m2015-03-21 07:03

1 楼

Given a large number of records (with increasing but not necessarily
consecutive sequence number), design a indexing scheme
factorial digits sum。比如input为10，因为10！= 3628800，就应该返回sum的值 =
3+6+2+8

l*n2015-03-21 07:03

2 楼

第一题能说的具体一点吗？不是很明白是什么意思啊？
第二题不就是array相乘嘛，贴个代码练习一下：（跑了几个test case，应该是对的）
public int factorialDigitsSum(int n){
int sum = 0;
int[] pre = intToArray(n);
for(int i=n-1; i>=2; i--){
int[] curr = intToArray(i);
pre = multiply(pre, curr);
}
for(int i=0; isum += pre[i];
}
return sum;
}
private int[] intToArray(int n){
int size = 0;
int copy = n;
while(copy!=0){size++; copy /= 10;}
int[] arr = new int[size];
copy = n;
for(int i=0; iarr[i] = copy%10;
copy /= 10;
}
return arr;
}
private int[] multiply(int[] pre, int[] curr){
int[] result = new int[pre.length + curr.length];
int carry = 0;
for(int i=0; ifor(int j=0; jresult[i+j] += pre[i]*curr[j] + carry;
carry = result[i+j]/10;
result[i+j] %= 10;
}
if(carry != 0){
result[i+curr.length] += carry;
carry = 0;
}
}
return result;
}

s*s2015-03-21 07:03

3 楼

第一题没idea啊，求大牛指点

l*s2015-03-21 07:03

4 楼

第一题是要构造BST么？

s*s2015-03-21 07:03

5 楼

database自带的index功能本身就是BST，这是要考如何实现database里面的index么

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

: 第一题是要构造BST么？

l*s2015-03-21 07:03

6 楼

大概是这个目的，要是要求平衡的，就是被黑了。

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

: database自带的index功能本身就是BST，这是要考如何实现database里面的index么

k*i2015-03-21 07:03

7 楼

第一题没说清楚，这种题都要问支持什么操作的。如果只是一个O(1)的look up，用
hashtable就行，如果是要支持ordered iteration，用B+-tree

g*e2015-03-21 07:03

8 楼

第一题是online streaming系统
具体参考kafka
说btree的都fail了

=

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

: Given a large number of records (with increasing but not necessarily
: consecutive sequence number), design a indexing scheme
: factorial digits sum。比如input为10，因为10！= 3628800，就应该返回sum的值 =
: 3+6+2+8

m*r2015-03-21 07:03

9 楼

求大牛给详细一点的解释
没太明白

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

: 第一题是online streaming系统
: 具体参考kafka
: 说btree的都fail了
:
: =

s*s2015-03-21 07:03

10 楼

是不是大约这个意思，问的不是数据库里面如何做index而是kafka内部如何做index
0.8中增加了逻辑offset，那么就需要做逻辑offset和物理地址间的转化
简单的方法，直接用hashmap，cache所有offset，问题就是这样空间耗费比较大
所以kafka的方式，是分段索引，用offset通过二分查找中index中找出段的起始地址，
然后再去file里面遍历找出精确的地址，时间换空间的设计
1. LogSegment.translateOffset
首先是从index文件中找到近似的物理地址
前面说了，index中从效率考虑并不会为每个offset建立索引entry，只会分段建立
offset索引，所以从index中直接可以找到精确物理地址的概率不大，但是可以找到最
接近的那个物理地址
如果你觉得index的粒度比较粗，可以直接给出开始查找的startingFilePosition
所以精确的物理地址需要到MessageSet文件里面去继续找

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

: 第一题是online streaming系统
: 具体参考kafka
: 说btree的都fail了
:
: =