Zenefits最近几道难题的解法

kennethinsnow 发表于 2015-10-23 10:53
// Find the largest K such that A^K is a subsequence of B, where A, B are two strings. |A|

如果 A 和 B 的长度都是0的话，也是返回0吗？还是返回1？

Chasego 发表于 2015-10-26 10:14
如果 A 和 B 的长度都是0的话，也是返回0吗？还是返回1？

不过这样很像，不符合 |A| << |B|

Chasego 发表于 2015-10-26 10:14
如果 A 和 B 的长度都是0的话，也是返回0吗？还是返回1？

            if (len1 > len2) return 0;
            if (len1 <= 0) return 0;
我返回0，具体要和面试官沟通

kennethinsnow 发表于 2015-10-26 10:24
if (len1 > len2) return 0;
            if (len1

嗯，我是看到这一行。不过沟通就没问题了。

kennethinsnow 发表于 2015-10-23 10:53
// Find the largest K such that A^K is a subsequence of B, where A, B are two strings. |A|

第14行，sigA[A.charAt(i)] != 0 这个判断应该没必要吧？

Chasego 发表于 2015-10-26 10:55
第14行，sigA[A.charAt(i)] != 0 这个判断应该没必要吧？

恩，可以去掉

kennethinsnow 发表于 2015-10-23 11:09
http://www.1point3acres.com/bbs/thread-131422-1-1.html
valid binary tree

第24行 if (children[row] == 2 && adjMat[row][col] != 1){.
是不是应该改成 children[row] == 1，意思是对于row已经有一个孩子了，而保证col不是它已有的孩子才返回E1

kennethinsnow 发表于 2015-10-23 11:09
http://www.1point3acres.com/bbs/thread-131422-1-1.html
valid binary tree

代码很不错，赞楼主一个！

我当时想到“E5”情况应该是不存在，因为前面四种错误已经涵括所有情况。

第51行实际是永远不会执行的吗？

kennethinsnow 发表于 2015-10-23 11:10
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+ ...

29行: if (i - len < -1) return false;

这里是不是应该改成 i - len < 0 ???

我也来贴俩题 最近在准备电面 好没底儿。。。。。。。。。。。。

Find the largest K such that A^K is a subsequence of B, where A, B are two strings.
http://www.1point3acres.com/bbs/ ... p;highlight=zenefit

1. public class largestAK {
   
2.        
   
3.         public int findLargestK(String s1, String s2){
   
4.                 if(s1.length() < 1 || s1.length() > s2.length())
   
5.                         return -1;
   
6.                 int k = 1;
   
7.                 int left = 1, right = s2.length() / s1.length();
   
8.                 int lastK = -1;
   
9.                 while(left <= right){
   
10.                         k = left + (right - left)/2;
    
11.                         String akString = generateKth(s1, k);
    
12.                         if(isSub(akString, s2)){
    
13.                                 lastK = k;
    
14.                                 left = k + 1;
    
15.                         }else{
    
16.                                 right = k - 1;
    
17.                         }
    
18.                 }
    
19.                 return lastK;
    
20.         }
    
21.        
    
22.         private String generateKth(String s, int k){
    
23.                 StringBuilder temp = new StringBuilder();
    
24.                 for(int i = 0; i < s.length(); i++){
    
25.                         for(int j = 0; j < k; j++){
    
26.                                 temp.append(s.charAt(i));
    
27.                         }
    
28.                 }
    
29.                 return temp.toString();
    
30.         }
    
31.        
    
32.         private boolean isSub(String s1, String s2){
    
33.                 int i = 0;
    
34.                 int j = 0;
    
35.                 while(i < s1.length() && j < s2.length()){
    
36.                         if(s1.charAt(i) == s2.charAt(j)){
    
37.                                 i++;
    
38.                         }
    
39.                         j++;
    
40.                 }
    
41.                 if(i == s1.length())
    
42.                         return true;
    
43.                 return false;
    
44.         }
    
45. 
    
46.         public static void main(String[] args) {
    
47.                 // TODO Auto-generated method stub
    
48.                 largestAK ak = new largestAK();
    
49.                 String s1 = "ab";
    
50.                 String s2 = "acaaabcbbb";
    
51.                 String s3 = "xyxz";
    
52.                 String s4 = "xxyyxxzz";
    
53.                 System.out.println(ak.findLargestK(s3, s4));
    
54.         }
    
55. 
    
56. }

复制代码