一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 829|回复: 5
收起左侧

Pocket Gems 第一轮电面

[复制链接] |试试Instant~ |关注本帖
ycsung 发表于 2015-2-11 06:22:21 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Pocket Gems - 猎头 - 技术电面 |Pass

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
跟大家一样 第一轮是以下两题 很顺利的通过了拿到第二轮

. visit 1point3acres.com for more.1. Implement strStr(), LeetCode原题. more info on 1point3acres.com
    Takes two strings as parameters, returns index of the first occurrence of the second string in the first string. from: 1point3acres.com/bbs

. Waral 鍗氬鏈夋洿澶氭枃绔,
我用bruce force解, O(m*n). m是length of first string, n是length of second string..1point3acres缃
进阶解法如KMP可以参考 http://www.csie.ntnu.edu.tw/~u91029/StringMatching.html
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2. K frequently occurring numbers
    Given a unsorted list of  N integers, write a program to find k most repeating integers.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    follow up是给你sorted number但是是非常长的stream

我用hashmap去计算所有的integer出现的frequency. 再用min heap去得到top k frequency. 最后输出对应的integer
O(k + (n-k)logk) = O(nlogk)
这篇文章提供了6种解法 http://www.geeksforgeeks.org/k-l ... ements-in-an-array/


评分

3

查看全部评分

 楼主| ycsung 发表于 2015-2-11 08:32:21 | 显示全部楼层
follow up就是用min heap. 他有提供我has.next(), next() func可供調用. 用while(has.next()) { if tmp == next(): count++, else: minheap(...); count = 0; tmp = next()}

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

tonywen2014 发表于 2015-2-11 07:42:58 | 显示全部楼层
follow up的话楼主是怎么做的?因为很大的数据量要用到distrubuted solution吗?mapreduce什么的
回复 支持 反对

使用道具 举报

ppcheng 发表于 2015-2-19 13:41:50 | 显示全部楼层
ycsung 发表于 2015-2-11 08:32
follow up就是用min heap. 他有提供我has.next(), next() func可供調用. 用while(has.next()) { if tmp ==  ...

nice,good point
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-3-10 21:45:32 | 显示全部楼层
我不知道为啥没人说,可能是只有我看到这个题目脑子一片空白吧。
楼主你给的链接是k largest(or smallest) elements in an array. from: 1point3acres.com/bbs
应该跟K frequently occurring numbers不一样吧……
还有别的链接么?
回复 支持 反对

使用道具 举报

Frankhappens 发表于 2015-3-11 12:25:37 | 显示全部楼层
对于第二题,lz很有想法。但是如果输入流要求是进来一个处理一个,并且能够有实时信息怎么办?例如给木每次更新后的largest Kth?总不能每次都重新heapify一下吧?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-1-23 06:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表