s*******m
发帖数: 228 | 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*****n
发帖数: 246 | 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; i
sum += 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; i
arr[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; i
for(int j=0; j
result[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*****s
发帖数: 94 | |
l******s
发帖数: 3045 | |
s*****s
发帖数: 94 | 5 database自带的index功能本身就是BST， 这是要考如何实现database里面的index么
【在 l******s 的大作中提到】
: 第一题是要构造BST么？
|
l******s
发帖数: 3045 | 6 大概是这个目的，要是要求平衡的，就是被黑了。
【在 s*****s 的大作中提到】
: database自带的index功能本身就是BST， 这是要考如何实现database里面的index么
|
k****i
发帖数: 128 | 7 第一题没说清楚，这种题都要问支持什么操作的。如果只是一个O(1)的look up，用
hashtable就行，如果是要支持ordered iteration，用B+-tree |
g*********e
发帖数: 14401 | 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*********r
发帖数: 19 | 9 求大牛给详细一点的解释
没太明白
【在 g*********e 的大作中提到】
: 第一题是online streaming系统
: 具体参考kafka
: 说btree的都fail了
:
: =
|
s*****s
发帖数: 94 | 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了
:
: =
|
