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

Microsoft on-compus 面试题一道

🔗
 楼主| 1guangnian 2013-10-21 01:56:28 | 只看该作者
全局:
lixiang.xjtu 发表于 2013-10-20 16:06
额外的数组存得是pointer,所以开销不会很大

如果不采用额外数组,可以在O(nlogn)之内做吗?除了那个O ...

可以像之前有人说的在double linked list上进行快排,但最坏也是O(n^2),平均可以到O(nlgn)
回复

使用道具 举报

🔗
csgtc 2013-10-21 02:45:13 | 只看该作者
全局:
面试官要的应该是O(n)的space和time,用个hashset
回复

使用道具 举报

🔗
csgtc 2013-10-21 02:47:08 | 只看该作者
全局:
tangxukai 发表于 2013-10-19 01:19
给定一个新的数组按照data快排nlogn,数组里面的是节点,node{data,pos};从前往后找,只要前后紧挨着的一 ...

找重复这种题不应该用sort,既然用了extra space,那么就用hashtable或者hashset。时间是n,空间是n
回复

使用道具 举报

🔗
twfx1123 2013-10-27 02:17:39 | 只看该作者
全局:
浮点数的相等的问题需要考虑一个边界值吧~~有很多无限循环的小数 呢~~要是我的话 就设个e = 0.0001,然后只有a-b < e的时候才可以考虑为相等。。。
回复

使用道具 举报

🔗
 楼主| 1guangnian 2013-10-27 02:34:58 | 只看该作者
全局:
gy21 发表于 2013-10-27 02:17
浮点数的相等的问题需要考虑一个边界值吧~~有很多无限循环的小数 呢~~要是我的话 就设个e = 0.0001,然后只 ...

问了面试官,说可以直接用==判
回复

使用道具 举报

🔗
wyc9004 2013-11-1 03:55:43 | 只看该作者
全局:
为何不用Hash...
回复

使用道具 举报

🔗
xtugator 2013-12-31 04:29:12 | 只看该作者
全局:
1guangnian 发表于 2013-10-27 02:34
问了面试官,说可以直接用==判

可以直接用==,为毛不说int类的链表就行了=。=
回复

使用道具 举报

🔗
ifloating 2014-3-13 15:04:58 | 只看该作者
全局:
用HashMap的话时间和空间都是O(n)吧?
回复

使用道具 举报

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

本版积分规则

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