刚面完的狗狗

之前因为面试官的原因改了好几次时间， 最后约了今天一早店面。 但我记错日期了， 以为是明天早晨面。 导致自己毫无准备的在睡梦中被面试官电话叫起来面试， 整个人都是傻的。面的不太好

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

很经典的一道题了 ， dfs bfs都能做。 可惜我一开始理解错了题意，没能一遍bug free， 改完之后也没时间做follow up了。 可惜了这么简单的狗家面试。 顺便感慨一句他家店面的难度跨度是真的大 ， 我上一次面的OOD ， 这次居然这么简单 :(。


补充内容 (2019-10-11 04:44):
谢谢 joezie 的补充

您好！
本帖隐藏的内容需要积分高于 166 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 166 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-10-18 01:29):
居然过了。真是东边不亮西边亮啊…… 凌鹰 蠡口所有tag题刷了三遍bug free过两道medium一道hard follow up都挂了， 狗家居然就这么过了……  求大米看昂赛面经！！！

用Java实现了下brute force解法，复杂度太高了，楼主的[17, 3]例子都没跑出来，跑了个[8, 3]，代码和结果如下，大家来讨论下怎么优化吧。。。

揣摩意思写了一下， 每次dfs只要考虑新加的这一个元素和之前数组里所有元素的差值

1. class Solution:
   
2.     def findPath(self, nums):
   
3.         
   
4.         self.paths = []
   
5.         def helper(nums, n1, path):
   
6.             end = True
   
7.             cur = set()
   
8.             for n2 in nums:
   
9.                 if n1 == n2:
   
10.                     continue
    
11.                 n = abs(n1 - n2)
    
12.                 if n not in nums and n not in cur:
    
13.                     end = False
    
14.                     cur.add(n)
    
15.                     next_nums = nums | set([n])
    
16.                     helper(next_nums, n, path + [next_nums])
    
17.             if end:
    
18.                 self.paths.append(path)
    
19.         helper(set(nums), nums[-1], [])   
    
20.         return self.paths

复制代码

求问time complexity

没看懂您的描述。。。

5133709085 发表于 2019-10-11 02:27
没看懂您的描述。。。

哪个部分呢？ 我再重写一下

都没看懂 hhhhh

请问下如果path的路径不同,但是包含的数相同需要去重吗?

如果用 backtracking + hashset可以做吗? hashset存当前存在的所有数字
每次递归完, 将所有数字两两比较,然后找出不存在于hashset的diff后添加进去继续递归.

希望楼主能够顺利过！

另外可否请楼主再描述一下这个题目，看得不是特别明白...

5133709085 发表于 2019-10-11 02:27
没看懂您的描述。。。

我觉得意思应该是每一次扩展这个数组的时候，就尝试在当前数组里找两个数，使得它们的差的绝对值是不存在于当前数组里的。若找得到就将该值加到数组里，否则这个递归过程就终止。希望能够帮到你！

joezie 发表于 2019-10-11 04:22
我觉得意思应该是每一次扩展这个数组的时候，就尝试在当前数组里找两个数，使得它们的差的绝对值是不存在 ...

对的就是这个意思！！ 谢谢你！

adayxiang 发表于 2019-10-11 04:06
请问下如果path的路径不同,但是包含的数相同需要去重吗?

如果用 backtracking + hashset可以做吗? hashs ...

我就是这个做法~ path里不可以包含相同的数。

好难啊，有人想出efficient的解法了吗