Terark面试

该公司主推数据库产品,所以招聘需求为算法岗。
面试过程中学到了很多(因为被虐很惨)。

简单谈一下对数据库的认识

  • 数据库分为关系型和非关系型数据库
  • 数据库是按照数据结构来组织、存储和管理数据的仓库
  • 数据按照一定格式存放,数据大都持久化在磁盘
  • 数据的共享性高、冗余度低,容易扩充

map

有一个坐标(x,y)(data)带了一个数据实现一个稀疏矩阵,现有两种存储方式供选择:

1
2
map<pair<x,y>, data>
map<x,map<y, data>>

据此计算出两者的时间复杂度。

(x,y)(data)所实现的稀疏矩阵

一维

对于一维map,因为在索引data的时候可以直接查找x并判断y是否相等即可。
若存在条件 x>y,则时间复杂度为 O(x);
若存在条件 x<y,则时间复杂度为 O(y);

二维

对于二维map,在索引data的时候,需要先找出x,再找出y,
所以时间复杂度应该为O(n²)

总结

在数据足够多的情况下,一维的时间复杂度总是要比二维的时间复杂度小。

map实现通讯录(国外)的存储方式

通讯录面对国外用户,首先想到的应该是大小写字母和排序问题。

1
2
3
// 例:Jack Davied
// 排序问题需要map中的一个
map<"JACK DAVIED", "Jack Davied">

重载比较运算符进行排序