Soundhound Onsite面经



  • SoundHound是一个音乐识别软件,目前支持Android、IOS、Symbian、Windows Phone平台,当用户听到喜爱的乐曲,但并不知道歌名时,可以使用SoundHound查找,只需要将手机麦克风尽可能对准声源或哼唱,对于大部分歌曲,SoundHound都能在10秒内获取来自midomi歌名。

    第一轮:
    用两个stack实现queue,实现enqueue()和dequeue()两个方法,leetcode原题,但是是generic(顺带问了generic的好处,检查是在run time还是compile time)。我的方法是enqueue()的时候直接push到stack1里,dequeue()从stack2中pop,这种解法enqueue是O(1)复杂度,dequeue()是O(n)复杂度(因为要将stack1里的元素换到stack2)。

    0_1469484009052_soundhound.png

    面试官的follow up就是能不能dequeue保证O(1)的复杂度,enqueue无所谓。要保证dequeue是O(1)就要保证stack2中一直有元素,所以使用wait()和notify(),当stack2中没有元素了就notify stack1,将元素置换过来。

    然后还问了如何使这个数据结构线程安全,最简单的方法是给这两个method都加synchronized。面试官问这种方法有什么缺点,我的答案是这样效率很低,一种改进是两个方法用不同的锁,这样两个方法可以分别被访问。

    还考了一些Java基础,比如JVM是干嘛的,有什么好处之类的。

    第二轮:
    CTO面,受宠若惊。
    问如何给新闻页面关联一些内容相关的wiki pages。

    我的答案是首先要对wiki pages做一些预处理,比如给每个页面提取key words,然后建立索引map<key word, list of pages that contain is key word>。对于一个新闻页面,我们可以使用TF-IDF等方法提取key words,然后对每个key word在索引map中查找,找到相关的wiki pages,然后对这些相关的wiki pages排序,找到top10关联。

    然后面了一道算法题subset, 说了递归算法,然后让写了非递归算法。

    第三轮:
    给一个数字,用binary search找到误差范围小于0.01的平方根。
    MapReduce,计算word count。
    什么情况下用MapReduce,这个问题我答得很烂。

    第四轮:
    设计SQL数据库表。
    然后写SQL queries。
    如何预测美国大选谁会赢。我说我会用twitter API获取twitter数据,用候选人的名字过滤一下数据,然后做sentiment analysis分类看是支持还是反对,最后统计做出预测。

    本文作者:Marie

    更多精彩内容,欢迎访问官网 Click Here
    或关注 “论码农的自我修养” 微信公众号:bit_tiger
    0_1469484219361_bittiger qr code.jpg


登录后回复
 

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