Yammer面试

刚刚店面完yammer，之前发现地里几乎没有他家面筋，来发一个题大家一起讨论吧，但是估计挂了。
一个白人大叔，非常不耐烦（只有说bye的时候比较热情），第一句就是我没时间看你cv 给你道题先做吧。
题目：  
write a f

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

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

n be traversed to -2 or 4 since the value is 3.


楼主用了recursive，有人有啥好建议么。。。

能解释一下啥意思吗？用人话解释一下

我写了下面这个，貌似是正确的：

1. public static boolean canReachZero(int[] A, int index) {
   
2. 
   
3.         if (index < 0 || index >= A.length) return false;
   
4.         if (A[index] == 0) return true;
   
5.         int num = A[index];
   
6. 
   
7.         return canReachZero(A, index - num) || canReachZero(A, index + num);
   
8.     }

复制代码

补充内容 (2016-12-6 07:30):
working example:

1. 
   
2. int[] nums = {5,3,1,4,0,6};
   
3.         int index = 1;
   
4. 
   
5.         boolean res = canReachZero(nums, index);
   

复制代码

就是给一个array和一初始index ，例如 nums＝［2，4，5，0，5］ index ＝ 0
那么下一个可到的值是 0 － nums［0］= －2  or 0 ＋ nums［0］＝2 ； －2 out of boundry
然后 下一个值就是 nums［2］＝ 5 然后 2- 5； 2 ＋5； 问可不可以到达 ，值为 0 的 index 这里就是nums［3］；

joannana 发表于 2016-12-6 07:42
就是给一个array和一初始index ，例如 nums＝［2，4，5，0，5］ index ＝ 0
那么下一个可到的值是 0 － nu ...

看我上面写的code，work的，也是recursion思路

但是，如果第一次和第三次得到index相同，但是并没有 out of boundry，这就是一个死循环。
然后我加了个 global 的 hashset... 然后就被白人大叔说了...

joannana 发表于 2016-12-6 07:48
但是，如果第一次和第三次得到index相同，但是并没有 out of boundry，这就是一个死循环。
然后我加了个 g ...

还真是，忘记死循环这个可能性了。但是加一个参数lastNum来记录上次访问的数，下面的code就work了吧：

1. private static boolean canReachZero(int[] A, int index, int lastNum) {
   
2. 
   
3.         if (index < 0 || index >= A.length) return false;
   
4.         if (A[index] == 0) return true;
   
5.         if (A[index] == lastNum) return false;
   
6. 
   
7.         int num = A[index];
   
8.         return canReachZero(A, index - num, A[index]) || canReachZero(A, index + num, A[index]);
   
9.     }

复制代码

补充内容 (2016-12-6 08:07):
使用这个method，应该这样做：

1. 
   
2. boolean result = canReachZero(A, index, A[index]-1);
   

复制代码

要是我木有理解错的话， lastNum 只记录了上一个，要是第一次和第五次得到了相同的index，那还是死循环呀。。。

最终代码：

1. public static boolean canReachZero(int[] A, int index) {
   
2. 
   
3.         return canReachZero(A, index, index); // NOTE: A[index]-1 is for avoiding the return false in line 24
   
4.     }
   
5. 
   
6.     private static boolean canReachZero(int[] A, int index, int lastIndex) {
   
7. 
   
8.         if (index < 0 || index >= A.length) return false;
   
9.         if (A[index] == 0) return true;
   
10. 
    
11.         int num = A[index];
    
12.         if (index - num == lastIndex || index + num == lastIndex) return false; // avoids dead loop here
    
13.         return canReachZero(A, index - num, index) || canReachZero(A, index + num, index);
    
14.     }

复制代码

joannana 发表于 2016-12-6 08:08
要是我木有理解错的话， lastNum 只记录了上一个，要是第一次和第五次得到了相同的index，那还是死循环呀。 ...

给一个test case啊