2016.9.20 搜狗笔试

职位：搜狗输入法研究部大数据处理及分析实习生
时间：90 min
题型：10道选择/填空，1道编程题，1道设计题

有关红黑树
设k<n，以下操作的平均时间复杂度与“把k个未排序数插入已含有n个节点的红黑树里”相当的有（AB）
A. 从含n个元素的已整理好的小顶堆里依次取出前k个最小的
B. 利用快排过程，从n个未排序数里找第k小的
C. 利用容量为k的大顶堆，从n个未排序数字中找最小k个
D. 从长度分别为n和k的两个序列中找最长公共子序列
解析：题干中红黑树插入时间复杂度为O(klogn)
A. O(klogn)
B. O(klogn)
C. O(nlogk)
D. O(nk)

数据挖掘算法基础知识
下面属于维规约常用的线性代数技术有（AC）
A. 主成分分析
B. 离散化
C. 奇异值分解
D. 特征加权
解析：关于机器学习中奇异值分解及应用的详细介绍

以下哪些算法是基于规则的分类器（A）
A. C4.5
B. KNN
C. NB
D. ANN

语法问题
要禁止修改指针p本身，又要禁止修改p指向的内容，则p应该定义为（D）
A. const char const *p
B. char const *p
C. char *const p const
D. const char * const p

设计题
三元组（id1, id2, freq）表示id1和id2的共现次数，id1、id2都在0-65535范围内，但三元组是稀疏的，共有400万左右，因此直接用二维数组存储太浪费空间。设计一个存储方案，平衡空间的消耗和快速查找需求。
（这个结构是静态的，不用考虑插入等操作。）

我回答的是用HashTable，用id1和id2形成键值，freq作为实值。键可由id1<<16+id2或将id1、id2字符画后连接成id1_id2作为键。这样只需要存储有值的三元组，而且可在O(1)时间内取值。