狗狗4月 Cambridge onsite

774913744 发表于 2018-5-10 00:11
这些题目不简单啊，第一题的follow up不好搞的，有O（N）解。第二题算常规题改编，中等偏难。第三题也是比 ...

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


请问一下大神，这是哪道常规题的改编呀？

idatascience 发表于 2018-5-20 04:20
给一个integer array 表示不同符号的个数, 和输入n, 返回所有可能的n个符号的组合(不在乎顺序)
follow u ...

应该就是典型的dfs吧?

kid1314 发表于 2018-5-20 04:21
应该就是典型的dfs吧?

你是如何避免重复count？比如（0. 0，1）和（1， 0， 0）只能算一个解。

idatascience 发表于 2018-5-20 04:30
你是如何避免重复count？比如（0. 0，1）和（1， 0， 0）只能算一个解。

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

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

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

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

Cambridge 这边面试好像都偏简单，更注重能不能干活。
简历直接被刷的飘过。。。

idatascience 发表于 2018-5-20 23:02
我用了你说的前一种，发现去重的题我总是有点做不好~你的follow up节省空间是如何做的？

补充内容 (2018 ...

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

yangyuan 发表于 2018-5-20 23:08
Cambridge 这边面试好像都偏简单，更注重能不能干活。
简历直接被刷的飘过。。。

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

kid1314 发表于 2018-5-21 01:31
要返回具体组合的时候我会有一个类似path的东西存着, 返回个数的时候只需要用dictionary记录个数就行了啊 ...

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

idatascience 发表于 2018-5-21 03:49
没有用数学公式可以套的解么？你的dict里面key和value分别存什么啊？

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