l*********y
发帖数: 142 | 1 以前面过的，好像板上没有。贡献的同时也想请教如何解答，应该看那方面的资料。
谢谢。
1）
一个数据库，有很多人的资料，如名字，年龄，性别，工资等等。
数据库要支持单项和多项查询，单项比如输入名字，要显示其余的信息。
多项比如要年龄 > 30，工资 > 1000 的所有人。
从速度考虑，请问应该如何设计系统。 另外多项查询的复杂度是多少？
2）
如何设计一个 short link 生成器? 我主要谈了两方面，
1.算法。
2.多线程 ：如何避免同一个url产生多个不同的short link的情况。 |
f*******t
发帖数: 7549 | 2 第一个对new grad来说有点太难了吧
第二题用hash应该就可以了 |
c****p
发帖数: 6474 | 3 算法得当的话，相同link不会产生不同的短link吧？
我觉得需要解决的是怎么处理collision。。。。
【在 l*********y 的大作中提到】
: 以前面过的，好像板上没有。贡献的同时也想请教如何解答，应该看那方面的资料。
: 谢谢。
: 1）
: 一个数据库，有很多人的资料，如名字，年龄，性别，工资等等。
: 数据库要支持单项和多项查询，单项比如输入名字，要显示其余的信息。
: 多项比如要年龄 > 30，工资 > 1000 的所有人。
: 从速度考虑，请问应该如何设计系统。 另外多项查询的复杂度是多少？
: 2）
: 如何设计一个 short link 生成器? 我主要谈了两方面，
: 1.算法。
|
l*********y
发帖数: 142 | 4 我当时谈的是如果两个人同时要产生同一个url的 short link，怎么处理。
我说要在hashtable上加lock。现在想想当时真的是昏了头，这个是不是在shortlink
产生的算法处加lock就行了。
for example.
short_link function(long_link)
{
if (map[long_link] != null) {
return map[long_link];
} else {
lock();
short_link = generate(long_link);
map[long_link] = short_link;
map[short_link] = long_link;
unlock();
}
}
【在 c****p 的大作中提到】
: 算法得当的话，相同link不会产生不同的短link吧？
: 我觉得需要解决的是怎么处理collision。。。。
|
g*********e
发帖数: 14401 | 5
如果这样浪费空间的话，那干脆用一个锁对应一段index？比如1-10用锁1， 11-20用锁
2. 因为大多数时间里锁是空的。hash够均匀的话不太会排队。
【在 l*********y 的大作中提到】
: 我当时谈的是如果两个人同时要产生同一个url的 short link，怎么处理。
: 我说要在hashtable上加lock。现在想想当时真的是昏了头，这个是不是在shortlink
: 产生的算法处加lock就行了。
: for example.
: short_link function(long_link)
: {
: if (map[long_link] != null) {
: return map[long_link];
: } else {
: lock();
|
z*********8
发帖数: 2070 | 6 第一题B+ tree可以吧
【在 f*******t 的大作中提到】
: 第一个对new grad来说有点太难了吧
: 第二题用hash应该就可以了
|
l*********y
发帖数: 142 | 7 应该是的，能详细谈谈吗？
多谢！
【在 z*********8 的大作中提到】
: 第一题B+ tree可以吧
|
l*********y
发帖数: 142 | 8 这个我也说了，面试官又往 lock-free 的算法上说了下。我没太说好。
【在 g*********e 的大作中提到】
:
: 如果这样浪费空间的话，那干脆用一个锁对应一段index？比如1-10用锁1， 11-20用锁
: 2. 因为大多数时间里锁是空的。hash够均匀的话不太会排队。
|
n**4
发帖数: 719 | 9 2) 一个思路是不是可以考虑无损压缩？因为长url的空间应该只被用了一小部分吧。一
一对应的short url就不用考虑collision了
另外，长url里应该有很多common word，比如域名，目录名等，是不是可以用trie |
l*********y
发帖数: 142 | 10 第一题应该是b+ tree，请问有什么资料可以看吗？
网上有很多简单介绍b+ tree的资料，但是没和这道题结合起来。
【在 l*********y 的大作中提到】
: 以前面过的，好像板上没有。贡献的同时也想请教如何解答，应该看那方面的资料。
: 谢谢。
: 1）
: 一个数据库，有很多人的资料，如名字，年龄，性别，工资等等。
: 数据库要支持单项和多项查询，单项比如输入名字，要显示其余的信息。
: 多项比如要年龄 > 30，工资 > 1000 的所有人。
: 从速度考虑，请问应该如何设计系统。 另外多项查询的复杂度是多少？
: 2）
: 如何设计一个 short link 生成器? 我主要谈了两方面，
: 1.算法。
|
|
|
q****x
发帖数: 7404 | 11 这不就是DB的设计吗？
【在 l*********y 的大作中提到】
: 以前面过的，好像板上没有。贡献的同时也想请教如何解答，应该看那方面的资料。
: 谢谢。
: 1）
: 一个数据库，有很多人的资料，如名字，年龄，性别，工资等等。
: 数据库要支持单项和多项查询，单项比如输入名字，要显示其余的信息。
: 多项比如要年龄 > 30，工资 > 1000 的所有人。
: 从速度考虑，请问应该如何设计系统。 另外多项查询的复杂度是多少？
: 2）
: 如何设计一个 short link 生成器? 我主要谈了两方面，
: 1.算法。
|
f**********r
发帖数: 2137 | 12 1) b+ tree for hierarchical indexing, to avoid disk operations
【在 l*********y 的大作中提到】
: 以前面过的，好像板上没有。贡献的同时也想请教如何解答，应该看那方面的资料。
: 谢谢。
: 1）
: 一个数据库，有很多人的资料，如名字，年龄，性别，工资等等。
: 数据库要支持单项和多项查询，单项比如输入名字，要显示其余的信息。
: 多项比如要年龄 > 30，工资 > 1000 的所有人。
: 从速度考虑，请问应该如何设计系统。 另外多项查询的复杂度是多少？
: 2）
: 如何设计一个 short link 生成器? 我主要谈了两方面，
: 1.算法。
|
k*********6
发帖数: 738 | 13 1st: you can find it in standard database text book, such as the one from
Rague. |
k*******r
发帖数: 355 | 14 第2题我的naive想法， 就基于next permutation就可以了吧。
一直保持一个加锁的全局string变量。given a url,如果这个ur在hash表中已存在，则直接返回其hash表中的shortlink， 否则把这个全局string变量变成其next
permuatation,作为此url的short link存入hash表。
如果要lock-free,那就让每个线程保持一个彼此不重叠的全局string变量。比如一个线程规定其全局string变量是 a开头的6位数，另一个线程是b开头的6位数... |
w********m
发帖数: 1137 | 15 Create index idxFirstname, idxLastname by Hashtable
Complexity O(n ^ 2);
Create index idxAge, inxSalaray by B+ tree;
Complexity O(n log n); |
