一亩三分地论坛

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

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

刚刚结束的pocket gems 二面

[复制链接] |试试Instant~ |关注本帖
kuaileziyou 发表于 2015-3-25 06:32:07 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Pocket Gems - 网上海投 - 在线笔试 |Other

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

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

x
刚刚结束电面。 看名字以为面试官是个白人,打电话发现既不是白人也不是三哥, 所以问题叙述的时候,听得没那么顺利
. Waral 鍗氬鏈夋洿澶氭枃绔,
一共面了3道.1point3acres缃
1. Sort Colors
2. find next node in BST。 问这题之前它又让我写了如何找到BST 最小的element。搞得我以为换题了。
3. find first occurrence in sort array(里面有重复的elements)。 有点bug,他提示了一下子,不过也没让我改。


求onsite啊.1point3acres缃

评分

1

查看全部评分

nathanwong 发表于 2015-3-27 03:47:17 | 显示全部楼层
lz 请问可否说一下sort color 具体要求,因为我看到其他人说 sort color 和leetcode 上的不一样?
回复 支持 1 反对 0

使用道具 举报

liokumo 发表于 2015-3-26 07:17:42 | 显示全部楼层
楼主,第三题是啥意思啊?
回复 支持 反对

使用道具 举报

 楼主| kuaileziyou 发表于 2015-3-26 07:52:29 | 显示全部楼层
liokumo 发表于 2015-3-26 07:17
楼主,第三题是啥意思啊?

不好意思,没叙述清楚。
举个例子

int[] A = [1,2,2,2,3,4,5];
int target = 2;
. visit 1point3acres.com for more.
target 第一次在A里面出现的index 是1, 所以返回1. 如果target不再A里面,返回-1.
面试官要求O(logn)的解法
回复 支持 反对

使用道具 举报

liokumo 发表于 2015-3-26 20:29:28 | 显示全部楼层
kuaileziyou 发表于 2015-3-26 07:52
不好意思,没叙述清楚。
举个例子
-google 1point3acres
谢谢楼主回答,既然是O(lgn),那就是让二分查找吧?
回复 支持 反对

使用道具 举报

 楼主| kuaileziyou 发表于 2015-3-27 03:35:06 | 显示全部楼层
liokumo 发表于 2015-3-26 20:29.鐣欏璁哄潧-涓浜-涓夊垎鍦
谢谢楼主回答,既然是O(lgn),那就是让二分查找吧?

恩对的
回复 支持 反对

使用道具 举报

 楼主| kuaileziyou 发表于 2015-3-27 04:47:33 | 显示全部楼层
nathanwong 发表于 2015-3-27 03:47. From 1point 3acres bbs
lz 请问可否说一下sort color 具体要求,因为我看到其他人说 sort color 和leetcode 上的不一样?

我也看到其他帖子说是给一个arraylist,不过我的面试官给我的是一个array of Color objects. 其它的和leetcode是一模一样的。
回复 支持 反对

使用道具 举报

nathanwong 发表于 2015-3-27 05:22:19 | 显示全部楼层
kuaileziyou 发表于 2015-3-27 04:47
我也看到其他帖子说是给一个arraylist,不过我的面试官给我的是一个array of Color objects. 其它的和lee ...

很好,我看你的是二面,一面有木有。。。
回复 支持 反对

使用道具 举报

 楼主| kuaileziyou 发表于 2015-3-27 06:21:58 | 显示全部楼层
nathanwong 发表于 2015-3-27 05:22. 1point3acres.com/bbs
很好,我看你的是二面,一面有木有。。。

一面第一题是strstr,第二题是find top kth frequent element in array,第二题follow up了一下子问如果给的是data stream怎么办。当时已经40多分钟了,就没让implement,就大概说了一下子思路还有时间复杂度。
回复 支持 反对

使用道具 举报

nathanwong 发表于 2015-3-27 07:38:37 | 显示全部楼层
kuaileziyou 发表于 2015-3-27 06:21
一面第一题是strstr,第二题是find top kth frequent element in array,第二题follow up了一下子问如果 ...

好的,谢谢lz 这个data stream 请问你是怎么处理的? 我不知道我想的对不对。多谢。。
回复 支持 反对

使用道具 举报

 楼主| kuaileziyou 发表于 2015-3-27 12:32:11 | 显示全部楼层
nathanwong 发表于 2015-3-27 07:38
好的,谢谢lz 这个data stream 请问你是怎么处理的? 我不知道我想的对不对。多谢。。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不好意啊,之前忘了说了data stream 是sort过的。用iterator.next()读数据,然后统计element 的 frequency,放到priority queue, heap size 是k。 heap 满了以后,对比top element in heap的frequency和下一个element的frequency的大小,留下大的。这样子保证heap里面的总是当前的top k.

地里有一个帖子讲的还蛮细致的,还贴出来code,你可以找找参考一下子。
回复 支持 反对

使用道具 举报

 楼主| kuaileziyou 发表于 2015-3-27 12:32:37 | 显示全部楼层
nathanwong 发表于 2015-3-27 07:38
好的,谢谢lz 这个data stream 请问你是怎么处理的? 我不知道我想的对不对。多谢。。

不好意啊,之前忘了说了data stream 是sort过的。用iterator.next()读数据,然后统计element 的 frequency,放到priority queue, heap size 是k。 heap 满了以后,对比top element in heap的frequency和下一个element的frequency的大小,留下大的。这样子保证heap里面的总是当前的top k.

地里有一个帖子讲的还蛮细致的,还贴出来code,你可以找找参考一下子。
回复 支持 反对

使用道具 举报

nathanwong 发表于 2015-3-27 13:10:46 | 显示全部楼层
kuaileziyou 发表于 2015-3-27 12:32
不好意啊,之前忘了说了data stream 是sort过的。用iterator.next()读数据,然后统计element 的 frequenc ...

lz 按你说的 既然是先统计frequence 那不需要data stream 是sorted 的呀,难道我理解错了?

我的理解是 如果不是data stream 就统计frequence 然后基于frequence 就sort 就行了
如果是data stream, 就需要用priority 了吧。不过我有个问题 怎么感觉都要先计算所有的frequence? 不好意思 我比较弱
回复 支持 反对

使用道具 举报

 楼主| kuaileziyou 发表于 2015-3-27 16:13:57 | 显示全部楼层
nathanwong 发表于 2015-3-27 13:10
lz 按你说的 既然是先统计frequence 那不需要data stream 是sorted 的呀,难道我理解错了?. visit 1point3acres.com for more.

我的理解 ...

其实这道题,我自己也理解的不是特别好,可能说的也不对
之前是array的时候,我用的是hashmap记录element和它的frequency,所以我感觉无所谓是不是sort过。
后来改成data stream,我就说建一个新的Object,然后记录element和它的frequency比较方便。这时候,如果data stream不是sort的过的话,我感觉没法统计。
回复 支持 反对

使用道具 举报

kaywsy 发表于 2015-3-29 02:42:01 | 显示全部楼层
楼主我马上要二面了,有个问题想请教下,能不能留个邮箱?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 01:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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