📣 独立日限时特惠: VIP通行证立减$68
楼主: kid1314
跳转到指定楼层
上一主题 下一主题
收起左侧

狗狗4月 Cambridge onsite

🔗
idatascience 2018-5-20 04:20:19 | 只看该作者
全局:
774913744 发表于 2018-5-10 00:11
这些题目不简单啊,第一题的follow up不好搞的,有O(N)解。第二题算常规题改编,中等偏难。第三题也是比 ...

给一个integer array 表示不同符号的个数, 和输入n, 返回所有可能的n个符号的组合(不在乎顺序)
follow up: 返回这些组合的个数, 优化时间空间复杂度



请问一下大神,这是哪道常规题的改编呀?
回复

使用道具 举报

🔗
 楼主| kid1314 2018-5-20 04:21:36 | 只看该作者
全局:
idatascience 发表于 2018-5-20 04:20
给一个integer array 表示不同符号的个数, 和输入n, 返回所有可能的n个符号的组合(不在乎顺序)
follow u ...

应该就是典型的dfs吧?
回复

使用道具 举报

🔗
idatascience 2018-5-20 04:30:33 | 只看该作者
全局:
kid1314 发表于 2018-5-20 04:21
应该就是典型的dfs吧?

你是如何避免重复count?比如(0. 0,1)和(1, 0, 0)只能算一个解。
回复

使用道具 举报

🔗
 楼主| kid1314 2018-5-20 04:32:40 | 只看该作者
全局:
idatascience 发表于 2018-5-20 04:30
你是如何避免重复count?比如(0. 0,1)和(1, 0, 0)只能算一个解。

dfs 不要重复走, 经过一个index选择之后, 只在之后的index 中选择就可以了, 或者麻烦一点, 自己sort之后用个set记录是否出现过,不过这样感觉cost很大, 当时我没有用这种

评分

参与人数 1大米 +5 收起 理由
idatascience + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
idatascience 2018-5-20 23:02:41 | 只看该作者
全局:
kid1314 发表于 2018-5-20 04:32
dfs 不要重复走, 经过一个index选择之后, 只在之后的index 中选择就可以了, 或者麻烦一点, 自己sort之后 ...

我用了你说的前一种,发现去重的题我总是有点做不好~你的follow up节省空间是如何做的?

补充内容 (2018-5-20 23:05):
哦,看到了,你就说是用combination,对吧,这样的话,只是数组不用传递了,但是每种可能性还是要传递的吧?还是你有formula一下就出来了?
回复

使用道具 举报

🔗
yangyuan 2018-5-20 23:08:12 | 只看该作者
全局:
Cambridge 这边面试好像都偏简单,更注重能不能干活。
简历直接被刷的飘过。。。
回复

使用道具 举报

🔗
 楼主| kid1314 2018-5-21 01:31:57 | 只看该作者
全局:
idatascience 发表于 2018-5-20 23:02
我用了你说的前一种,发现去重的题我总是有点做不好~你的follow up节省空间是如何做的?

补充内容 (2018 ...

要返回具体组合的时候我会有一个类似path的东西存着, 返回个数的时候只需要用dictionary记录个数就行了啊~
我是这么理解的反正.
回复

使用道具 举报

🔗
 楼主| kid1314 2018-5-21 01:32:17 | 只看该作者
全局:
yangyuan 发表于 2018-5-20 23:08
Cambridge 这边面试好像都偏简单,更注重能不能干活。
简历直接被刷的飘过。。。

所以...是team match 的时候更容易挂人吗?
回复

使用道具 举报

🔗
idatascience 2018-5-21 03:49:29 | 只看该作者
全局:
kid1314 发表于 2018-5-21 01:31
要返回具体组合的时候我会有一个类似path的东西存着, 返回个数的时候只需要用dictionary记录个数就行了啊 ...

没有用数学公式可以套的解么?你的dict里面key和value分别存什么啊?
回复

使用道具 举报

🔗
 楼主| kid1314 2018-5-21 03:53:21 | 只看该作者
全局:
idatascience 发表于 2018-5-21 03:49
没有用数学公式可以套的解么?你的dict里面key和value分别存什么啊?

当前位置, 剩余可选位数 的一个tuple,
数学解就是就排列组合的解呗, 关键是我觉得数学解也体现不出我的编程能力和对数据结构的理解,
一般都是从brute force 开始写, 他要我优化我就优化给他看哪种, 我觉得面试官会比较喜欢吧
回复

使用道具 举报

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

本版积分规则

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