一亩三分地论坛

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

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

BB on campus 9/23

[复制链接] |试试Instant~ |关注本帖
suozhoutangxin 发表于 2016-9-27 00:44:49 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Bloomberg - 校园招聘会 - 校园招聘会 |Otherfresh grad应届毕业生

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

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

x
周三(9/21)进行了电面,紧接着当天给了周五的on campus, 一小时。上次的面经链接:http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311
. From 1point 3acres bbs
周五约好的十一点,到了点儿里面的人还不走。门外听着面试官不停地说last minute,然后三哥哥还说个不停,我的面试11:15才开始。
面试官两个人,一个姑娘一个汉子,一人问了一道题。
姑娘:. from: 1point3acres.com/bbs
merge interval LC56. 区别是输入输出类型要自己定义,并且一开始告诉你intervals 是按开始时间sort 好的。 follow up把输入改成了乱序,那当然告诉她先sort就好了。 sort用的是STL,于是问了不少关于STL的问题, pair怎么构造,有哪几种方法,sort函数里面要写compare function么,pair的默认比较方式是什么,如何写一个类的copy constuctor, C++和java的传值方式有什么区别(能记住的只有这些了)。
汉子:
给你一个没有sort的char array,返回第一个没有重复的char。
第一种方法:bit map,建立256长的array,第一次扫描每个char出现的次数,然后再扫描一次输出第一个count=1的char。 要求改进
第二种方法:hashmap。 同样的思想。问有什么好处:不局限在ASCII码范围内,可以包含任何char。 继续要求改进
第三种方法:依旧使用hashmap,不过用了pointer,只需要one pass即可。问什么好处: 减少了map的lookup。貌似还不是很满意,但我已经没辙了。

此时还剩下五分钟到12点,他说就五分钟了,不做题了,你来问我们吧(好想问你知道我是几点进来的么= =)。问了些无关痛痒的问题,结束。. From 1point 3acres bbs

今天周一,还没有收到消息, 于是给hr打了电话。hr说并不是挂了,是因为上周五就是他们on campus的最后一天。现在他们的人都撤了,于是在商议是否会给onsite,要我继续等。。。

求onsite, 求其他家on campus,电面各种顺利

.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

1

查看全部评分

 楼主| suozhoutangxin 发表于 2016-9-27 11:23:40 | 显示全部楼层
收到onsite邀请了。。字数字数字数
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-9-28 02:32:14 | 显示全部楼层
感谢分享~ 我想请问第二题 还有什么更好的方法吗?~ 面试官期待的是什么呢0.0
回复 支持 反对

使用道具 举报

uuuu99199 发表于 2016-9-28 02:40:24 | 显示全部楼层
会不会是让用LinkedHashMap?
回复 支持 反对

使用道具 举报

 楼主| suozhoutangxin 发表于 2016-9-28 02:51:53 | 显示全部楼层
何打发123 发表于 2016-9-28 02:32
感谢分享~ 我想请问第二题 还有什么更好的方法吗?~ 面试官期待的是什么呢0.0

我也不知道了,我能想到的就那么多了。
回复 支持 反对

使用道具 举报

 楼主| suozhoutangxin 发表于 2016-9-28 02:53:14 | 显示全部楼层
uuuu99199 发表于 2016-9-28 02:40
会不会是让用LinkedHashMap?
.1point3acres缃
怎么做呢?当时我感觉已经不可能再简化了。runtime n, one pass
回复 支持 反对

使用道具 举报

uuuu99199 发表于 2016-9-28 03:04:45 | 显示全部楼层
suozhoutangxin 发表于 2016-9-28 02:53-google 1point3acres
怎么做呢?当时我感觉已经不可能再简化了。runtime n, one pass

runtime应该是不能再优化了,只是感觉选第一个这种题优先用链表结构吧。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-9-28 03:27:15 | 显示全部楼层
suozhoutangxin 发表于 2016-9-28 02:53
怎么做呢?当时我感觉已经不可能再简化了。runtime n, one pass
. visit 1point3acres.com for more.
你好 我用java 所以不太懂您说的第三种方法为什么用pointer one pass就可以了呢?
回复 支持 反对

使用道具 举报

littlebearull 发表于 2016-9-28 03:38:01 | 显示全部楼层
请问楼主,第二个题的第三种方法是怎么做到one pass的呢?具体是怎么用的pointer呢?谢谢回复哦!
回复 支持 反对

使用道具 举报

 楼主| suozhoutangxin 发表于 2016-9-28 04:24:34 | 显示全部楼层
何打发123 发表于 2016-9-28 03:27. From 1point 3acres bbs
你好 我用java 所以不太懂您说的第三种方法为什么用pointer one pass就可以了呢?

我用pos记录来可能是结果的位置,然后在循环过程中比较当前的char和pos位置上的char是否一样,如果一样,pos自增到下一个目前为止只出现过一次的char,最后输出pos位置的char。
. from: 1point3acres.com/bbs 现在想想其实并没有优化什么,只是把两个循环整合成一个了而已,非但没有减少map的lookup,还增加了比较。。。。尴尬
回复 支持 反对

使用道具 举报

littlebearull 发表于 2016-9-28 09:53:11 | 显示全部楼层
suozhoutangxin 发表于 2016-9-28 04:24
我用pos记录来可能是结果的位置,然后在循环过程中比较当前的char和pos位置上的char是否一样,如果一样, ...
. visit 1point3acres.com for more.
谢谢楼主回复。我也是琢磨着,好像不太能实现真正意义上的one pass。如果有人知道,麻烦分享一下啦~
回复 支持 反对

使用道具 举报

 楼主| suozhoutangxin 发表于 2016-9-28 09:56:54 | 显示全部楼层
littlebearull 发表于 2016-9-28 09:53
谢谢楼主回复。我也是琢磨着,好像不太能实现真正意义上的one pass。如果有人知道,麻烦分享一下啦~

我觉得也是,要确定一个是不是,总得知道后面还有没有它出现吧。那就得先预处理一遍,然后真正意义上的one pass就不太可能了。
回复 支持 反对

使用道具 举报

uuuu99199 发表于 2016-9-28 10:31:37 | 显示全部楼层
suozhoutangxin 发表于 2016-9-28 09:56
我觉得也是,要确定一个是不是,总得知道后面还有没有它出现吧。那就得先预处理一遍,然后真正意义上的on ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
用LinkedHashMap实现一个类似LRU的结构理论上就是O(n),one pass。.鏈枃鍘熷垱鑷1point3acres璁哄潧
但是仿佛这也不是最优解,因为每次需要删除再添加。
回复 支持 反对

使用道具 举报

 楼主| suozhoutangxin 发表于 2016-9-28 19:45:49 | 显示全部楼层
uuuu99199 发表于 2016-9-28 10:31. Waral 鍗氬鏈夋洿澶氭枃绔,
用LinkedHashMap实现一个类似LRU的结构理论上就是O(n),one pass。
但是仿佛这也不是最优解,因为每次需 ...
. 1point 3acres 璁哄潧
但是也得从后面开始遍历linkedhashmap吧,找到第一个count=1的字符。假设第一个和第二个字符是一样的,并且之后再没有出现过,那么它会留在lru的最后位置,但是它并不是结果
回复 支持 反对

使用道具 举报

uuuu99199 发表于 2016-9-28 20:57:17 | 显示全部楼层
suozhoutangxin 发表于 2016-9-28 19:45
但是也得从后面开始遍历linkedhashmap吧,找到第一个count=1的字符。假设第一个和第二个字符是一样的,并 ...

就看开头的第一个元素就行了,count是1返回,否则不存在。不用遍历
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 20:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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