Zenefits最近几道难题的解法

本人总结了一下最近zenefits面试中出现的难题
OA3

1. Longest Chain
给定一个词典，

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

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

color:rgb(255, 255, 255)">.鐣欏?璁哄潧-涓

http://www.1point3acres.com/bbs/thread-131422-1-1.html
valid binary tree

1. public class Solution1 {
   
2.         class TreeNode{
   
3.                 char value;
   
4.                 TreeNode left;
   
5.                 TreeNode right;
   
6.                 TreeNode(char inp){
   
7.                         this.value = inp;
   
8.                 }
   
9.         }
   
10.         public String sExp(char[][] pair){
    
11.                 // build an adj matrix row is the parent node, col is the child node
    
12.                 int len = pair.length;
    
13.                 if (len == 0) return "";
    
14.                 int[][] adjMat = new int[26][26];
    
15.                 int[] inNode = new int[26];        // count the incoming edges of each node
    
16.                 int[] children = new int[26]; // count the number of children of each node
    
17.                 Map<Character, TreeNode> nodes = new HashMap();
    
18.                 TreeNode parent, child;
    
19.                 UnionFind myUnion = new UnionFind(26);
    
20.                 // build binary tree based on pair
    
21.                 for (int i = 0; i < len; i++){
    
22.                         int row = pair[i][0] - 'A';
    
23.                         int col = pair[i][1] - 'A';
    
24.                         if (children[row] == 2 && adjMat[row][col] != 1){
    
25.                                 // more than 2 children but not the same edge
    
26.                                 return "E1";
    
27.                         }else if (adjMat[row][col] == 1){
    
28.                                 // duplicated edges
    
29.                                 return "E2";
    
30.                         } else if (myUnion.connected(row, col)){
    
31.                                 // if new link connect two that are already in same union there is loop
    
32.                                 return "E3";
    
33.                         }
    
34.                         adjMat[row][col] = 1;
    
35.                         children[row]++;
    
36.                         inNode[col]++;
    
37.                         myUnion.connect(row, col);
    
38.                         connectNodes(pair, nodes, i);
    
39.                 }
    
40.                
    
41.                 // check multiple roots
    
42.                 int rNum = 0;
    
43.                 TreeNode root = null;
    
44.                 for (char x : nodes.keySet()){
    
45.                         if (inNode[x - 'A'] == 0){
    
46.                                 rNum++;
    
47.                                 if (rNum > 1) return "E4";
    
48.                                 root = nodes.get(x);
    
49.                         }
    
50.                 }
    
51.                 if (root == null) return "E5";
    
52.                
    
53.                 // convert it to s-expression
    
54.                 return toSExpression(root);
    
55.         }
    
56.        
    
57.         // convert it to s-expression
    
58.         String toSExpression(TreeNode root){
    
59.                 if (root == null) return "";
    
60.                 return "(" + root.value + toSExpression(root.left) + toSExpression(root.right) + ")";
    
61.         }
    
62.        
    
63.         // connect parent and child node
    
64.         private void connectNodes(char[][] pair, Map<Character, TreeNode> nodes,
    
65.                         int i) {
    
66.                 TreeNode parent;
    
67.                 TreeNode child;
    
68.                 if (nodes.containsKey(pair[i][0])) parent = nodes.get(pair[i][0]);
    
69.                 else{
    
70.                         parent = new TreeNode(pair[i][0]);
    
71.                         nodes.put(pair[i][0], parent);
    
72.                 }
    
73.                 if (nodes.containsKey(pair[i][1])) child = nodes.get(pair[i][1]);
    
74.                 else{
    
75.                         child = new TreeNode(pair[i][1]);
    
76.                         nodes.put(pair[i][1], child);
    
77.                 }
    
78.                 if (parent.left == null) parent.left = child;
    
79.                 else {
    
80.                         if (parent.left.value < pair[i][1]){
    
81.                                 parent.right = child;
    
82.                         } else {
    
83.                                 parent.right = parent.left;
    
84.                                 parent.left = child;
    
85.                         }
    
86.                 }
    
87.         }
    
88.        
    
89.         public static void main(String[] args){
    
90.                 Solution1 sln = new Solution1();
    
91.                 // (A(B(D(E(G))))(C(F)))
    
92.                 // char[][] pair = {{'B', 'D'}, {'D', 'E'}, {'A', 'B'}, {'C', 'F'}, {'E', 'G'}, {'A', 'C'}};
    
93.                 // E3
    
94.                 // char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'D'}, {'D', 'C'}};
    
95.                 // (A(B(D)(G))(C(E(F))(H)))
    
96.                 // char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'G'}, {'C', 'H'}, {'E', 'F'}, {'B', 'D'}, {'C', 'E'}};
    
97.                 // E1
    
98.                 // char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'D'}, {'A', 'E'}};
    
99.                 // E2
    
100.                 // char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'D'}, {'A', 'C'}};
     
101.                 // E4
     
102.                 char[][] pair = {{'A', 'B'}, {'A', 'C'}, {'B', 'G'}, {'C', 'H'}, {'E', 'F'}, {'B', 'D'}};
     
103.                 System.out.println(sln.sExp(pair));
     
104.         }
     
105. }

复制代码

机器人距离和最小问题
注意问题参见 http://www.1point3acres.com/bbs/thread-145166-1-1.html

1. /*//problem: robot merge point
   
2. //input:
   
3. //robot: 1
   
4. //obstacle: X
   
5. [
   
6. 0   0   0   M   1
   
7. 0   1   X   0   0
   
8. 0   X   0   0   0
   
9. 0   0   0   1   0
   
10. 0   0   0   0   0
    
11. ]
    
12. //output:
    
13. //best merge point: M
    
14. 3 + 1 + 3 = 7
    
15. 
    
16. Definition: Best merge point: minimal sum of path num between robots and merge point*/
    
17. public class Solution{
    
18.         class Point{
    
19.                 int x;
    
20.                 int y;
    
21.                 public Point(int x, int y){
    
22.                         this.x = x;
    
23.                     this.y = y;
    
24.                 }
    
25.         }
    
26.         Point bestMergePoint(char[][] mat){
    
27.          int m = mat.length;
    
28.          if (m == 0) return null;
    
29.          int n  = mat[0].length;
    
30.        
    
31.          // bfs each point that is 1
    
32.          int[][] dis = new int[m][n];
    
33.          for (int i = 0; i < m; i++){
    
34.              for (int j = 0; j < n; j++){
    
35.                  if (mat[i][j] == '1') bfs(mat, i, j, dis);
    
36.              }
    
37.          }
    
38.          // count number
    
39.          int min = Integer.MAX_VALUE;
    
40.          Point ret = null;
    
41.          for (int i = 0; i < m; i++){
    
42.              for (int j = 0; j < n; j++){
    
43.                      // if this point is not visited by a robot
    
44.                      if (dis[i][j] == 0 && mat[i][j] == '0') continue;
    
45.                  if (mat[i][j] != 'X' && dis[i][j] < min){
    
46.                      min = dis[i][j];
    
47.                      ret = new Point(i, j);
    
48.                  }
    
49.              }
    
50.          }
    
51.          return ret;
    
52.         }
    
53. 
    
54.         //bfs matrix to mark the distance from x and y
    
55.         void bfs(char[][] mat, int x, int y, int[][] dis){
    
56.                  Queue<Point> path = new LinkedList();
    
57.                  int[] dx = {1,-1,0,0};
    
58.                  int[] dy = {0,0,1,-1};
    
59.                  int m = mat.length;
    
60.                  int n = mat[0].length;
    
61.                  boolean[][] visited = new boolean[m][n];
    
62.                  int ct = 0;
    
63.                  System.out.println("Started at: " + x + " " + y);
    
64.                  int di = 0;
    
65.                  path.offer(new Point(x, y));
    
66.                  visited[x][y] = true;
    
67.                  while (!path.isEmpty()){
    
68.                      int count = path.size();
    
69.                      for (int i = 0; i < count; i++){
    
70.                          Point cur = path.poll();
    
71.                          ct++;
    
72.                          // System.out.println(cur.x + " " + cur.y);
    
73.                          // visited[cur.x][cur.y] = true;
    
74.                          // update cur.value
    
75.                          dis[cur.x][cur.y] += di;
    
76.                          // check its neighbors
    
77.                          for (int j = 0; j < 4; j++){
    
78.                              int nx = cur.x + dx[j];
    
79.                              int ny = cur.y + dy[j];
    
80.                              if (nx >= 0 && nx < m && ny >= 0 && ny < m && mat[nx][ny] != 'X' && !visited[nx][ny]){
    
81.                                  path.offer(new Point(nx, ny));
    
82.                                  visited[nx][ny] = true;
    
83.                              }
    
84.                          }
    
85.                      }
    
86.                      di++;
    
87.                  }
    
88.                  System.out.println("total points added to queue: " + ct);
    
89.         }
    
90.         public static void main(String[] args){
    
91.                 Solution sln = new Solution();
    
92.                 char[][] mat = {{'0', '0', '0', '0', '1'},
    
93.                                                 {'0', '1', 'X', '0', '0'},
    
94.                                                 {'0', 'X', '0', '0', '0'},
    
95.                                                 {'0', '0', '0', '1', '0'},
    
96.                                                 {'0', '0', '0', '0', '0'}};
    
97.                 Point ret = sln.bestMergePoint(mat);
    
98.                 System.out.println(ret.x + " " + ret.y);
    
99.         }
    
100. }

复制代码

1. public class Solution {
   
2.         int longest_chain(String[] w) {
   
3.         int len = w.length;
   
4.         if (len == 0) return 0;
   
5.         Queue<String> cBuf = new LinkedList();
   
6.         Map<Integer, Set<String>> allWd = new HashMap();
   
7.         int maxLen = 0;
   
8.         int maxCLen = 0;
   
9.         // find the longest length of strings in w
   
10.         for (int i = 0; i < w.length; i++){
    
11.             int curLen = w[i].length();
    
12.             maxLen = Math.max(maxLen, curLen);
    
13.             if (allWd.containsKey(curLen)) allWd.get(curLen).add(w[i]);
    
14.             else{
    
15.                 Set<String> curSet = new HashSet();
    
16.                 curSet.add(w[i]);
    
17.                 allWd.put(curLen, curSet);
    
18.             }
    
19.         }
    
20.         // search from certain length of words
    
21.         for (int i = maxLen; i > maxCLen; i--){
    
22.             cBuf = new LinkedList(allWd.get(i));
    
23.             // start from initial set of words to search for chain
    
24.             int clen = 0;
    
25.             while (!cBuf.isEmpty()){
    
26.                 clen++;
    
27.                 Set<String> nextSet = allWd.get(i - clen);
    
28.                 if (nextSet == null) break;
    
29.                 int count = cBuf.size();
    
30.                 for (int h = 0; h < count; h++){
    
31.                     String t = cBuf.poll();
    
32.                     // get next string by deleting one letter
    
33.                     for (int l = 0; l < t.length(); l++){
    
34.                         String tt = t.substring(0, l) + t.substring(l + 1);
    
35.                         if (nextSet.contains(tt)){
    
36.                             cBuf.offer(tt);
    
37.                             nextSet.remove(tt);
    
38.                         }
    
39.                     }
    
40.                 }
    
41.             }
    
42.             maxCLen = Math.max(maxCLen, clen);
    
43.             i -= Math.max(clen - 1, 0);
    
44.         }
    
45.         return maxCLen;
    
46.     }

复制代码

nqueen变形
棋盘上放queen 已经保证同一行或者同一列不会出现2个queen，求出对于每个Queen最大的威胁次数威胁指只要一个queen所能移动的范围（对于这道题就是对角线）内有别的queen就算威胁。

1.         int maxThreats(int[] a) {
   
2.         int len = a.length;
   
3.         if (len == 0) return 0;
   
4.         int[] threat = new int[len]; // max threats for queen in each row
   
5.         Map<Integer, Integer> diag1 = new HashMap();
   
6.         Map<Integer, Integer> diag2 = new HashMap();
   
7.         for (int i = 0; i < len; i++){
   
8.             int col = a[i] - 1;
   
9.             if (diag1.containsKey(i - col)){
   
10.                 threat[i]++;
    
11.                 threat[diag1.get(i - col)]++;
    
12.             }
    
13.             diag1.put(i - col, i);
    
14.             if (diag2.containsKey(i + col)){
    
15.                 threat[i]++;
    
16.                 threat[diag2.get(i + col)]++;
    
17.             }
    
18.             diag2.put(i + col, i);
    
19.         }
    
20.         int maxThreat = 0;
    
21.         for (int i = 0; i < len; i++){
    
22.             maxThreat = Math.max(maxThreat, threat[i]);
    
23.         }
    
24.         return maxThreat;
    
25.     }

复制代码

虫吃叶子 给定一个int作为叶子的数量，再给一个数组，其中每个数代表一个虫行走的步数， 求没有被吃掉的叶子数量。 比如n = 100, bug = {2,5}, 那么一百片叶子中号码是2或者5的倍数的叶子全部被吃掉了。

1. int numberOfUneaten(int n, int[] p){
   
2.                 // find non divisible numbers in p
   
3.                 Arrays.sort(p);
   
4.                 for (int i = 0; i < p.length; i++){
   
5.                         for (int j = 0; j < i; j++){
   
6.                                 if (p[j] != 0 && p[i] % p[j] == 0){
   
7.                                         p[i] = 0;
   
8.                                         break;
   
9.                                 }
   
10.                         }
    
11.                 }
    
12.                 // find lcm of numbers in p
    
13.                 int l = 1;
    
14.                 for (int i = 0; i < p.length; i++){
    
15.                         if (p[i] != 0){
    
16.                                 l = lcm(l, p[i]);
    
17.                         }
    
18.                 }
    
19.                 int res = n % l;
    
20.                 // find undivisible numbers from 1 to min(lcm, n)
    
21.                 int[] mark = new int[Math.min(l, n) + 1];
    
22.                 for (int i = 0; i < p.length; i++){
    
23.                         if (p[i] != 0){
    
24.                                 for (int j = p[i]; j <= Math.min(l, n); j += p[i]){
    
25.                                         mark[j] = 1;
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.                 int count = 0;
    
30.                 int count1 = 0;
    
31.                 for (int i = 1; i < Math.min(l, n); i++){
    
32.                         if (mark[i] == 0){
    
33.                                 count++;
    
34.                                 if (i <= res) count1++;
    
35.                         }
    
36.                 }
    
37.                
    
38.                 // find undivisible numbers from 1 to n
    
39.                 if (n < l) return count;
    
40.                 else{
    
41.                         return n / l * count + count1;
    
42.                 }
    
43.         }
    
44.         int lcm(int a, int b){
    
45.                 return a * b / gcd(a, b);
    
46.         }
    
47.         int gcd(int a, int b){
    
48.                 if (a < b) return gcd(b, a);
    
49.                 return b == 0 ? a : gcd(b, a % b);
    
50.         }

复制代码

赞，楼主很用心啊

kennethinsnow 发表于 2015-10-23 10:45
机器人距离和最小问题
注意问题参见 http://www.1point3acres.com/bbs/thread-145166-1-1.html

// Find the largest K such that A^K is a subsequence of B, where A, B are two strings. |A| << |B|.

// Power of a string:
// Let A = xyxz
// Then,
// A^1 = A = xyxz
// A^2 = xxyyxxzz
// A^3 = xxxyyyxxxzzz
. 1point 3acres 璁哄潧
// Example:
// A = xyxz
// B = xabyzxz

// B xaybyxzxxxzz

// A xxyyxxzz

1. public int findK(String A, String B){
   
2.             int len1 = A.length(), len2 = B.length();
   
3.             if (len1 > len2) return 0;
   
4.             if (len1 <= 0) return 0;
   
5.             // remove space weird characters, capital to lower case etc if needed.
   
6.             A = preprocess(A);
   
7.             // find signature for each A and B and get the max possible value for k
   
8.             int[] sigA = new int[256];
   
9.             int[] sigB = new int[256];
   
10.             for (int i = 0; i < len1; i++) sigA[A.charAt(i)]++;
    
11.             for (int i = 0; i < len2; i++) sigB[B.charAt(i)]++;
    
12.             int kMax = Integer.MAX_VALUE;
    
13.             for (int i = 0; i < len1; i++){
    
14.                 if (sigA[A.charAt(i)] != 0) kMax = Math.min(sigB[A.charAt(i)] / sigA[A.charAt(i)], kMax);
    
15.             }
    
16.             int lo = 0, hi = kMax;
    
17.             int ret = 0;
    
18.             while (lo <= hi){
    
19.                 int med = lo + (hi - lo) / 2;
    
20.                 if (isSubSeq(expand(A, med), B)){
    
21.                     ret = med;
    
22.                     lo = med + 1;
    
23.                 } else {
    
24.                     hi = med - 1;
    
25.                 }
    
26.             }
    
27.             return ret;
    
28.         }
    
29.        
    
30.         String expand(String A, int k){
    
31.             StringBuilder sbuf = new StringBuilder();
    
32.             for (int i = 0; i < A.length(); i++){
    
33.                 char c = A.charAt(i);
    
34.                 for (int j = 0; j < k; j++) sbuf.append(c);
    
35.             }
    
36.             return sbuf.toString();
    
37.         }
    
38.        
    
39.         boolean isSubSeq(String A, String B){
    
40.             int len1 = A.length(), len2 = B.length();
    
41.             int a = 0, b = 0;
    
42.             while (a < len1 && b < len2){
    
43.                 if (A.charAt(a) == B.charAt(b)){
    
44.                     a++;
    
45.                     b++;
    
46.                 } else {
    
47.                     b++;
    
48.                 }
    
49.             }
    
50.             return a == len1;
    
51.         }
    
52.        
    
53.         String preprocess(String A){
    
54.             return A.toLowerCase();
    
55.         }

复制代码

/*一个正方形的矩阵，左上角的位置保证是0，其他的每个坐标位置上都有一个大于等于0的数。
* 一个人最初携带着的钱数为K，然后要从左上角走到右下角，每次只能向右或者向下走，
* 每到一个位置上就需要花掉该位置上对应的钱数，要求编程看看这个人能不能走到右下角，
* 如果不能，就返回-1，如果能，那就要找到一个解法，使得这个人剩余的钱数尽可能少，
* 也就是最终剩余的钱数要大于等于0，并且尽可能接近于0.*/

1. public class Solution {
   
2.         public int findMaxSpent(int[][] mat, int k){
   
3.                 // dp[i][j][n] is the max mount spent at i,j but less than n
   
4.                 // dp[i][j][n] = max(dp[i - 1][j][n - mat[i][j]], dp[i][j - 1][n - mat[i][j]])
   
5.                 int m = mat.length;
   
6.                 if (m == 0) return -1;
   
7.                 int n = mat[0].length;
   
8.                 int[][] dp1 = new int[n + 1][k + 1];
   
9.                 int[][] dp2 = new int[n + 1][k + 1];
   
10.                 // when i == -1; edge case
    
11.                 for (int j = 0; j < n; j++){
    
12.                         for (int h = 0; h <= k; h++){
    
13.                                 dp1[j + 1][h] = -1;
    
14.                         }
    
15.                 }
    
16.                 // when j = -1 edge case
    
17.                 for (int h = 0; h <= k; h++){
    
18.                         dp2[0][h] = -1;
    
19.                 }
    
20.                
    
21.                 for (int i = 0; i < m; i++){
    
22.                         for (int j = 0; j < n; j++){
    
23.                                 for (int h = 0; h <= k; h++){
    
24.                                         if (i == 0 && j == 0) dp2[j + 1][h] = 0;
    
25.                                         else if (h < mat[i][j]) dp2[j + 1][h] = -1;
    
26.                                         else {
    
27.                                                 int pre1 = dp2[j][h - mat[i][j]];
    
28.                                                 int pre2 = dp1[j + 1][h - mat[i][j]];
    
29.                                                 if (pre1 == -1 && pre2 == -1) dp2[j + 1][h] = -1;
    
30.                                                 else dp2[j + 1][h] = Math.max(pre1, pre2) + mat[i][j];
    
31.                                         }
    
32.                                 }
    
33.                         }
    
34.                         dp1 = Arrays.copyOf(dp2, n + 1);
    
35.                 }
    
36.                 return dp1[n][k];
    
37.         }
    
38.        
    
39.         public static void main(String[] args){
    
40.                 Solution sln = new Solution();
    
41.                 int[][] mat = {{0,4,5}, {1,3,2}, {0,1,1}};
    
42.                 System.out.println(sln.findMaxSpent(mat, 12));
    
43.         }
    
44. }

复制代码

String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";

s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有四个。

1. public class Solution {
   
2.         public int findMatches(String s1, String s2){
   
3.        int len1 = s1.length(), len2 = s2.length();
   
4.        if (len2 > len1) return 0;
   
5.        if (len2 == 0 || len2 %2 != 0) return 0;
   
6.        // DP matches each pattern
   
7.        // number of matches between s1.substring(0, i + 1) and s2.substring(j * 2, j * 2 + 2)
   
8.        int[][] dp = new int[len1 + 1][len2 / 2 + 1];
   
9.        // no match for dp[0][j]
   
10.        for (int i = 1; i < len1; i++){
    
11.            dp[i + 1][0] = 1;
    
12.            for (int j = 0; j < len2 / 2; j++){
    
13.                dp[i + 1][j + 1] = dp[i][j + 1];
    
14.                if (isMatch(s1, s2, i, j)){
    
15.                    if (s2.charAt(2*j + 1) == '+')
    
16.                        dp[i + 1][j + 1] += dp[i - 1][j];
    
17.                    else
    
18.                        dp[i + 1][j + 1] += dp[i - 3][j];
    
19.                }
    
20.            }
    
21.        }
    
22.        return dp[len1][len2 / 2];
    
23.    }
    
24. 
    
25.    boolean isMatch(String s1, String s2, int i, int j){
    
26.        char c = s2.charAt(j * 2);
    
27.        char p = s2.charAt(j * 2 + 1);
    
28.        int len = p == '+' ? 2 : 4;
    
29.        if (i - len < -1) return false;
    
30.        for (int h = i - len + 1; h <= i; h++){
    
31.            if (s1.charAt(h) != c) return false;
    
32.        }
    
33.        return true;
    
34.    }
    
35.    
    
36.    public static void main(String[] args){
    
37.            Solution sln = new Solution();
    
38.            // 4
    
39.            System.out.println(sln.findMatches("waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c-"));
    
40.            // 5
    
41.            System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-"));
    
42.    }
    
43. }

复制代码