蚂蚁金服四面总结

第一面

本来我是想找个php或go的位置的,结果猎头把我推到蚂蚁金服的搜索推荐部门。

第一面在环球金融中心九楼现场面试的,问的问题不算特别难,大部分记不清了,只记住一些印象比较深的问题。

请说说c++是怎么实现多态的

是利用虚函数表来实现的,每个虚函数类的内存开头都有一个虚函数表,里面存储了虚函数指针地址,当用父类指针调用派生类函数的时候,会去虚函数表里寻找函数指针然后调用

gdb调试你知道的参数有哪些,代表啥意思

我表示gdb用的不多,只知道-bt是打印调用栈,平时直接用IDE调试。

跳跃表结构

我理解跳跃表就是索引的索引,一个单链表查找数据需遍历,遍历的时间复杂度是O(N),为了减少时间复杂度,所以在这个单链表上简历索引,逐步缩小查找范围,但是当数据太多的时候,单层索引可能不够用,所以会弄很多层索引,也就是索引的索引。这种结构理解起来不复杂,但是写起来还是挺麻烦的。

new和malloc的区别

malloc就是单纯的分配内存,但是new还会调用构造函数。我曾经做过内存池,就是重载new和delete,分配内存的时候,从一个deque里面取,delete的时候,把内存放回deque,这样可以避免重复的申请内存。

简述全文索引工作过程

全文检索分3部分吧,1是文章抓取,2分词,归一化根据term建立倒排索引。3是搜索的时候对搜索语句进行分词,归一化处理,然后在每个term里抓出文章id,计算相关度并排序输出。

你觉得全文检索的核心是什么

当然是分词了。分词的难点在NLP。低层次的分词就是一个字典查找。但是复杂的,还有结合搜索上下文,用户信息,当前的时间,地点,以及社会热点等综合理解。现在机器学习比较火,我理解的机器学习就是一个黑盒,根据训练,找出各个维度数值的系数,然后打分。

说说你对分词的理解

分词就是把一个句子拆成词,我个人认为主要分两类,1是字典比对,就是前后两个游标,他们框出的字组成的词拿去字典比对,是词的话就摘出来,当然有按拆分最细分的,有按当个词最长原则分的。2是统计分词,就是N-Gram分词,按固定的长度把句子拆成词,然后统计每个词出现的频率,如果出现频率高可能他是个独立的词,否则就不是。这两种方法各有利弊,词典法主要是简单,速度快。缺点是无法识别词典以外的词。统计法就相反了。

分布式原理

分布式主要有两点

  1. 分布存储,就是数据根据一定的映射规则分散到不同的机器或虚拟节点

  2. 主从存储,每个机器或节点会有一个master,一个或多个slaver.在设计数据的增改删的时候,是master节点来操作的。当涉及读的时候,只从slaver读或master和slaver随机。

    分布存储是因为数据规模比较打,单机或单节点无法承载所有的数据。所以需要把数据分散。分散规则有多种,比如es是取模,比如redis是crc16,还有memcache集群的一致性hash。

    主从主要是保证可靠性的,因为机器或节点可能挂掉,挂掉要保证整个系统可用,而且数据不丢。所以需要有备份。但是多备份涉及到数据一致性问题,所以一般都是1主多从。当主节点挂了,会选举一个新的主节点。为了实现节点的监控,所以可能还需要一个监控系统,比如zookeeper或sentinel。选举协议paxos或raft.在选举的时候,为了防止集群分裂,所以只有半数以上的集群才会选举。

怎么实现geo搜索,比如你周围的商家

把地图化成小格子,每个格子建立倒排索引。在查找的时候,根据当前位置和距离半径算出符合条件的格子,然后遍历每个格子进行筛选。我在微博的时候,我们存储用户位置的时候,用了geohash来筛选附近的用户。

说说你对搜索引擎的认识

搜索引擎我觉得应该分两步吧,一个是索引,一个搜索。当数据录取的时候,对他进行过滤,同义词转换,归一化处理,进行分词,然后根据分词进行倒排索引。查询的时候,对查询语句也要进行上述操作,然后去对应的倒排索引找出文档id,然后合并啊,排序什么的。现代的搜索引擎应该不算是单纯的全文检索工具了,还有一些个性化的内容,比如根据你的年龄,地域,上下文进行相关的推荐。所以搜索引擎=全文检索+推荐

说说根据倒排索引多个term的ANDOR的查找过程

我当时在纸上花了一个倒排索引的图,然后对着图讲解,图大概如下 倒排索引

首先讲指针移到第一位,获得1-2-3

如果不等,找出最大的那个;比如图中1-2-3,的termN的3,剩下的节点一直往下移,直到值大于等于当前最大值,这时都 停到3,把3摘出来,

所有指针下移一步,如图中5-4-4,这时最大的是5,那么term2移到5停止,termN移到5停止,5摘出来,所有节点下移一位

这时term2没有了,寻找停止。

上述是and,or类似,只是判断条件不在于相同,而是满足一个即可

你之前做过哪些与搜索相关的东西

我表示,我在微博头条做过app的搜索功能,是用es用的,当用户进行搜索的时候,先根据搜索词,再加上文章发布时间,文章的level,虑重标记等搜出100条数据,然后根据这100个oid去redis里获取他们的转评赞。最后根据es的相关度score,文章热度,转评赞利用一个公式算分排序,缓存并输出。

es的排序策略是怎样的,有哪些问题,怎么改进

es的排序是df-idf以及后来的bm25。就是说一个词在这个文档出现的次数很多,但是在所有的文档出现次数很少,那么就说明这个词与这个文档最相关。但是问题就是关键词堆砌,就是以前seo经常搞的,一个词反复出现。解决方式就是,在计算df的时候,还需要引入文长。另外这种算法对短文比较有利。bm25有一些改进,但是也没有解决。应该加入其它的一些因素比如作者等级,用户转评赞平分等综合排序。

现场写代码,找出转折数字

听说现场写代码,当初还是比较紧张的,但是问题一出,心里就窃喜了,这不就是很简单的二分法吗。当时在纸上写的,半真半伪。大概如下

int bs(int arr[],size_t left,size_t right){
  size_t middle = (left+right)/2;
  if(middle==lefft || middle==right){
        return -1;
  }
  if(arr[middle-1]<arr[middle] && arr[middle]>arr[middle+1]){
    return arr[middle];
  }
  if(arr[middle-1]<arr[middle] && arr[middle]<arr[middle+1]){
    return bs(arr,middle,right);
  }
  if(arr[middle-1]>arr[middle] && arr[middle]>arr[middle+1]){
    return bs(arr,left,middle);
  }
}
int x = bs(arr,0,arr.size());

第一面完了让我回去等通知,我以为没戏了,结果第二天猎头告诉我通过了,让我等待第二面

第二面

第二面是电话面试,据说是交叉面,整个过程大约1小时,最后有个在线写代码环节。

自我介绍

说说你做过的个人觉得最有挑战性的一个案例

美团的猜你喜欢你觉得是怎么实现的?

猜你喜欢,个人觉得有两方面,1个就是我和某人比较相似(比如地域,年龄,口味等),然后他经常点的餐馆或菜品可以推荐给我。2个就是我经常点肯德基,而肯德基与麦当劳,汉堡王很类型,所以可以给我也推推麦当劳汉堡王。

推荐的时候,店铺与店铺,店铺与人,人与餐怎么联系的

店铺有很多的属性,比如位置,价位,辣不辣,品类等,每个属性都是一个维度的向量,然后进行余弦相似度计算,在一定的值以内的就算是相似。店铺与人,人与餐就是我刚刚讲过的。我和某人的属性的余弦相似度很高,那么可以把它喜欢的推荐给我。

你对余弦相似度了解多少?说说它的缺点

余弦相似度就是我们高中学过的向量计算,不过我们那会只有2维,而推荐这个是多维的。他呢计算比较简单,但是每个向量是对等的,实际上的向量不对等,比如猜你喜欢,对于餐品推荐来说,地域和价格的权重肯定比其他属性高。这一点没法体现。还有就是余弦相似度是两两对比,如果对象很多,比如一亿的话,两两对比实在太慢,我在微博的时候,我们微博头条在判断文章重复的时候,用过minhash和simhash,就是采取一个统一尺度,这样可以先根据某文算出相似的范围,然后在这个范围内去对比。

在线写代码,找兄弟词

在线写代码,对方向我邮箱发了一个网址,点开后就是一个在线写代码的网页,我本来想show一把c++的,后来一想c++的宽字符实在是个大坑,所以最后只好用python搞,题目如下

有个文件,里面有很多词,每个词一行。现在给你一个词,你需要找出这个文件里,该词的所有兄弟词,兄弟词的意思就是字相同,位置不同,比如abc的兄弟词就是acb,bac,bca,cab,cba等.

我写的还是比较轻松的

def gen_x_code(words):
    arr = map(lambada word:ord(word),words).sort()
    fingerprint=''.join(arr)
    return fingerprint

def find(given):
  given_fp = gen_x_code(given)
  brothers = []
  with open('words.txt','r') as f:
    while line=f.readline():
      if given_fp == gen_x_code(line.strip()):
        brothers.append(line.strip())
  return brothers

第三面

第三面是电话面,没有涉及技术,只是问了我过去的经历,职业规划什么的,并告诉我,第四面是总监面,他喜欢问算法,让我好好准备

第四面

第四面等了好久,而且是某天晚上九点多突然来电话说是进行面试,那时我已经躺着床上了,只好爬起来面试

自我介绍

介绍一下最难的项目

算法题

abcde,打乱顺序能组成哪些字符串,设计一个算法

我回答用个表格,依次为abcde,从上往下走,用一个set记录走过的格子就可以了。

第四面时间很短,总共不到半小时。

总结

第二天,猎头告诉我第四面没过。蚂蚁金服的面试到此结束了,前后脚经历了将近一个月。

个人的心路历程从第一面有些忐忑,到后面越来越有精神,感觉胜利近在咫尺。到最后被pass。 感觉蚂蚁的面试也不算特别难,最终被pass估计是因为过往经历不够出彩吧。