📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5341| 回复: 37
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft on-compus 面试题一道

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
刚才面完了微软summer intern的on campus面试,上来先是behavioral的问题,谈了谈自己以前的project,然后在白纸上写了一道题目具体是给你一个double linked list,里面存了浮点数,要你把所有重复出现过的浮点数放到一个新的double linked list,然后返回它的头指针

Sample input:
1.1<->2.5<->1.1<->3.1<->4.10<->2.50

Sample output:
1.1<->1.1<->2.5<->2.50


补充内容 (2013-10-19 01:45):
输出应该是1.1<->2.5<->1.1<->2.50,按照原来的顺序,其实我忘记问这个输出顺序的问题了,他也没挑我这个错=。=

评分

参与人数 2大米 +35 收起 理由
landuostorm + 20 感谢分享
北美农民 + 15

查看全部评分


上一篇:小福利,编程面试算法50题解答手册pdf~
下一篇:菜鸟刷题的困惑,望大牛指点
🔗
crusaderay 2013-10-19 03:15:05 | 只看该作者
全局:
有啥具体要求么。。。?额外的。。。时间 空间?
这样不就是从头扫到尾每一个节点都再扫一遍,有重复就保留,没有的就删掉。。。
没学过算法的飘过。。。
回复

使用道具 举报

🔗
 楼主| 1guangnian 2013-10-19 06:17:21 | 只看该作者
全局:
crusaderay 发表于 2013-10-19 03:15
有啥具体要求么。。。?额外的。。。时间 空间?
这样不就是从头扫到尾每一个节点都再扫一遍,有重复就保留 ...

没啥具体要求。。很水
回复

使用道具 举报

🔗
austurela 2013-10-19 09:34:20 | 只看该作者
全局:
crusaderay 发表于 2013-10-19 03:15
有啥具体要求么。。。?额外的。。。时间 空间?
这样不就是从头扫到尾每一个节点都再扫一遍,有重复就保留 ...

这样是不是就改动原LinkedList了?题目要求放到新的list里,除非在开头先把linkedlist复制一下?想听听各位有没有特别巧的解法

补充内容 (2013-10-19 09:37):
请问lz是怎么解的?
回复

使用道具 举报

🔗
austurela 2013-10-19 09:50:49 | 只看该作者
全局:
可以从头到尾扫两边,第一遍把所有的数字放进HashMap<Double, 0>,遇到重复的就改成<Double, 1>
然后扫第二遍,把每个double在hashmap里面搜,如果搜出来Value是1就放到新LinkedList里,否则就pass掉
这个时间是O(n),但牺牲了空间

补充内容 (2013-10-19 09:51):
两边→两遍

补充内容 (2013-10-19 09:52):
求讨论
回复

使用道具 举报

🔗
 楼主| 1guangnian 2013-10-19 10:33:36 | 只看该作者
全局:
austurela 发表于 2013-10-19 09:50
可以从头到尾扫两边,第一遍把所有的数字放进HashMap,遇到重复的就改成
然后扫第二遍,把每个double在has ...

每个点往左右各扫一次,直到碰到相同的
回复

使用道具 举报

🔗
xwb1989 2013-10-19 12:11:40 | 只看该作者
全局:
1guangnian 发表于 2013-10-19 10:33
每个点往左右各扫一次,直到碰到相同的

这样时间复杂度O(n^2)?
回复

使用道具 举报

🔗
 楼主| 1guangnian 2013-10-19 12:32:10 | 只看该作者
全局:
xwb1989 发表于 2013-10-19 12:11
这样时间复杂度O(n^2)?

yep, the worst case
回复

使用道具 举报

🔗
crusaderay 2013-10-19 12:48:31 | 只看该作者
全局:
austurela 发表于 2013-10-18 17:34
这样是不是就改动原LinkedList了?题目要求放到新的list里,除非在开头先把linkedlist复制一下?想听听各 ...

对哦。。。那就是要新建一个了
回复

使用道具 举报

🔗
crusaderay 2013-10-19 12:50:37 | 只看该作者
全局:
1guangnian 发表于 2013-10-18 14:17
没啥具体要求。。很水

不会吧。。。不适Microsoft么。。。怎么会搞出这种题。。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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