Soundhound电面总结:一次循循善诱的面试经历



  • 0_1469474964544_经11.jpg

    这次面试先从简历上的一个project开始,面试官挑了一个他感兴趣的project,让我简单介绍一下(一个文本处理的project,处理一些商品的title,title的格式是String)。

    但是面试官其实并不在意我的project做了什么,反而以这个project为背景开始出题了!
    面试官问,假如有一个title stream,源源不断地输入商品title,如何能够实时的找出最popular(出现次数最多)的十个商品title呢?

    既然要求实时处理,我们肯定不能全存储下来再进行排序。我的思路是使用一个map存储title和它出现次数的映射,随着stream的输入不断更新这个map。即输入是一个title,以这个title为key在map中查找,将对应的值加1。如果我们要求的是top-k most popular title,我们可以维护一个大小为k的min heap(最小堆),这个heap里存的就是k个最popular的title和它的出现次数。每次我们更新map的时候我们一下检查heap.peek(),因为是最小堆,heap.peek()返回的是最小值,即第k most popular title。如果我们更新的出现次数大于这个值,我们用新的值来替换heap中的值。

    面试官对这个答案表示赞同,然后顺手问了heap的实现(heapify)和时间复杂度,问的非常详细,插入删除查找都要会。

    然后面试官又继续问了这样一个问题,假如每个title都和一个timestamp相对应,如何能够查找对应时间区间的title,比如[timestamp1,timestamp2]之间出现的title?我的答案是我会以timestamp为key存在数据库中,并且对这个key建立索引来提高查询速度。

    面试官接着问,title是由很多words构成的,如何能够查找某个word对应的title呢?我的回答是首先要将title分词,然后以每个词为key存在数据库中,key对应的value是一个list,这个list里存包含这个词的title ID。这样当我们查找某一个词的时候就可以迅速地找到对应的title了。

    0_1469475105350_经13.jpg

    之后面试官问了两道算法题,一道是给一个integer array找max difference, 有两个constraints,第一个是这两个数可以连续也可以不连续,第二个是小的数要在大的数之前出现。

    还有一道是leetcode原题One Edit Distance。

    所有图片来源于网络

    本文作者:Marie
    欢迎关注 “论码农的自我修养” 微信公众号:bit_tiger
    0_1469475221602_bittiger qr code.jpg


登录后回复
 

与 BitTiger Community 的连接断开,我们正在尝试重连,请耐心等待