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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 以前面过的,好像板上没有。贡献的同时也想请教如何解答,应该看那方面的资料。 : 谢谢。 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 算法得当的话,相同link不会产生不同的短link吧? : 我觉得需要解决的是怎么处理collision。。。。
|
g*********e 发帖数: 14401 | 5
如果这样浪费空间的话,那干脆用一个锁对应一段index?比如1-10用锁1, 11-20用锁
2. 因为大多数时间里锁是空的。hash够均匀的话不太会排队。
【在 l*********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我当时谈的是如果两个人同时要产生同一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一个对new grad来说有点太难了吧 : 第二题用hash应该就可以了
|
l*********y 发帖数: 142 | 7 应该是的,能详细谈谈吗?
多谢!
【在 z*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题B+ tree可以吧
|
l*********y 发帖数: 142 | 8 这个我也说了,面试官又往 lock-free 的算法上说了下。我没太说好。
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 如果这样浪费空间的话,那干脆用一个锁对应一段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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 以前面过的,好像板上没有。贡献的同时也想请教如何解答,应该看那方面的资料。 : 谢谢。 : 1) : 一个数据库,有很多人的资料,如名字,年龄,性别,工资等等。 : 数据库要支持单项和多项查询,单项比如输入名字,要显示其余的信息。 : 多项比如要年龄 > 30,工资 > 1000 的所有人。 : 从速度考虑,请问应该如何设计系统。 另外多项查询的复杂度是多少? : 2) : 如何设计一个 short link 生成器? 我主要谈了两方面, : 1.算法。
|
|
|
q****x 发帖数: 7404 | 11 这不就是DB的设计吗?
【在 l*********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 以前面过的,好像板上没有。贡献的同时也想请教如何解答,应该看那方面的资料。 : 谢谢。 : 1) : 一个数据库,有很多人的资料,如名字,年龄,性别,工资等等。 : 数据库要支持单项和多项查询,单项比如输入名字,要显示其余的信息。 : 多项比如要年龄 > 30,工资 > 1000 的所有人。 : 从速度考虑,请问应该如何设计系统。 另外多项查询的复杂度是多少? : 2) : 如何设计一个 short link 生成器? 我主要谈了两方面, : 1.算法。
|
f**********r 发帖数: 2137 | 12 1) b+ tree for hierarchical indexing, to avoid disk operations
【在 l*********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 以前面过的,好像板上没有。贡献的同时也想请教如何解答,应该看那方面的资料。 : 谢谢。 : 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); |