聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 5990|回复: 29
收起左侧

Zenefits最近几道难题的解法

[复制链接] |试试Instant~ |关注本帖
kennethinsnow 发表于 2015-10-23 10:35:24 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类General 博士 全职@zenefits - 内推 - 技术电面 Onsite 在线笔试  | Other | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
本人总结了一下最近zenefits面试中出现的难题
OA3
http://www.1point3acres.com/bbs/ ... ;highlight=zenefits. 一亩-三分-地,独家发布
1. Longest Chain
给定一个词典, 对于里面单词删掉任何一个字母,如果新单词还在词典里,就形成一个 chain:old word -> new word, 求最长长
比如给List<String> dict = {a,ba,bca,bda,bdca} 最长是4:bdca->bda->ba->a;
.鐣欏?璁哄潧-涓

评分

7

查看全部评分

本帖被以下淘专辑推荐:

 楼主| kennethinsnow 发表于 2015-10-23 11:09:16 | 显示全部楼层
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.         }. from: 1point3acres
  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;. more info on 1point3acres
  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';. 围观我们@1point 3 acres
  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){. more info on 1point3acres
  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]++;. from: 1point3acres
  36.                         inNode[col]++;-google 1point3acres
  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.                 }. from: 1point3acres
  51.                 if (root == null) return "E5";
  52.                
  53.                 // convert it to s-expression. from: 1point3acres
  54.                 return toSExpression(root);
  55.         }
  56.        
  57.         // convert it to s-expression-google 1point3acres
  58.         String toSExpression(TreeNode root){
  59.                 if (root == null) return "";. 1point3acres
  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;. 围观我们@1point 3 acres
  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);. 围观我们@1point 3 acres
  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.                 }. 1point 3acres 论坛
  78.                 if (parent.left == null) parent.left = child;. 1point3acres
  79.                 else {
  80.                         if (parent.left.value < pair[i][1]){. from: 1point3acres
  81.                                 parent.right = child;
  82.                         } else {. From 1point 3acres bbs
  83.                                 parent.right = parent.left;. 1point3acres
  84.                                 parent.left = child;
  85.                         }
  86.                 }. 围观我们@1point 3 acres
  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'}};. from: 1point3acres
  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'}};. From 1point 3acres bbs
  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. }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:36:22 | 显示全部楼层
  1. public class Solution {
  2.         int longest_chain(String[] w) {
  3.         int len = w.length;
  4.         if (len == 0) return 0;. from: 1point3acres
  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();. visit 1point3acres for more.
  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();. 围观我们@1point 3 acres
  16.                 curSet.add(w[i]);
  17.                 allWd.put(curLen, curSet);
  18.             }
  19.         }. From 1point 3acres bbs
  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;. from: 1point3acres
  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);. 1point 3acres 论坛
  35.                         if (nextSet.contains(tt)){
  36.                             cBuf.offer(tt);
  37.                             nextSet.remove(tt);
  38.                         }
  39.                     }
  40.                 }. 一亩-三分-地,独家发布
  41.             }
  42.             maxCLen = Math.max(maxCLen, clen);.本文原创自1point3acres论坛
  43.             i -= Math.max(clen - 1, 0);
  44.         }
  45.         return maxCLen;
  46.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:38:36 | 显示全部楼层
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. 1point3acres
  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]++;.本文原创自1point3acres论坛
  11.                 threat[diag1.get(i - col)]++;
  12.             }
  13.             diag1.put(i - col, i);. 1point 3acres 论坛
  14.             if (diag2.containsKey(i + col)){
  15.                 threat[i]++;. 1point3acres
  16.                 threat[diag2.get(i + col)]++;
  17.             }
  18.             diag2.put(i + col, i);. 围观我们@1point 3 acres
  19.         }
  20.         int maxThreat = 0;
  21.         for (int i = 0; i < len; i++){
  22.             maxThreat = Math.max(maxThreat, threat[i]);
  23.         }
  24.         return maxThreat;.1point3acres网
  25.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:43:13 | 显示全部楼层
虫吃叶子 给定一个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){. from: 1point3acres
  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){.本文原创自1point3acres论坛
  16.                                 l = lcm(l, p[i]);
  17.                         }
  18.                 }. from: 1point3acres
  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];. from: 1point3acres
  22.                 for (int i = 0; i < p.length; i++){
  23.                         if (p[i] != 0){. 1point3acres
  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.                 . visit 1point3acres for more.
  38.                 // find undivisible numbers from 1 to n
  39.                 if (n < l) return count;. visit 1point3acres for more.
  40.                 else{
  41.                         return n / l * count + count1;. From 1point 3acres bbs
  42.                 }
  43.         }
  44.         int lcm(int a, int b){
  45.                 return a * b / gcd(a, b);
  46.         }.留学论坛-一亩-三分地
  47.         int gcd(int a, int b){.本文原创自1point3acres论坛
  48.                 if (a < b) return gcd(b, a);
  49.                 return b == 0 ? a : gcd(b, a % b);
  50.         }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:45:06 | 显示全部楼层
机器人距离和最小问题
注意问题参见 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. Definition: Best merge point: minimal sum of path num between robots and merge point*/
  16. public class Solution{
  17.         class Point{
  18.                 int x;
  19.                 int y;
  20.                 public Point(int x, int y){
  21.                         this.x = x;
  22.                     this.y = y;.1point3acres网
  23.                 }
  24.         }
  25.         Point bestMergePoint(char[][] mat){
  26.          int m = mat.length;
  27.          if (m == 0) return null;
  28.          int n  = mat[0].length;
  29.         . 留学申请论坛-一亩三分地
  30.          // bfs each point that is 1
  31.          int[][] dis = new int[m][n];
  32.          for (int i = 0; i < m; i++){
  33.              for (int j = 0; j < n; j++){
  34.                  if (mat[i][j] == '1') bfs(mat, i, j, dis);
  35.              }
  36.          }. more info on 1point3acres
  37.          // count number
  38.          int min = Integer.MAX_VALUE;-google 1point3acres
  39.          Point ret = null;. 留学申请论坛-一亩三分地
  40.          for (int i = 0; i < m; i++){. 1point3acres
  41.              for (int j = 0; j < n; j++){
  42.                      // if this point is not visited by a robot
  43.                      if (dis[i][j] == 0 && mat[i][j] == '0') continue;
  44.                  if (mat[i][j] != 'X' && dis[i][j] < min){
  45.                      min = dis[i][j];
  46.                      ret = new Point(i, j);
  47.                  }
  48.              }
  49.          }
  50.          return ret;
  51.         }

  52.         //bfs matrix to mark the distance from x and y
  53.         void bfs(char[][] mat, int x, int y, int[][] dis){
  54.                  Queue<Point> path = new LinkedList();
  55.                  int[] dx = {1,-1,0,0};
  56.                  int[] dy = {0,0,1,-1};
  57.                  int m = mat.length;
  58.                  int n = mat[0].length;. 1point 3acres 论坛
  59.                  boolean[][] visited = new boolean[m][n];
  60.                  int ct = 0;-google 1point3acres
  61.                  System.out.println("Started at: " + x + " " + y);. more info on 1point3acres
  62.                  int di = 0;
  63.                  path.offer(new Point(x, y));
  64.                  visited[x][y] = true;
  65.                  while (!path.isEmpty()){.1point3acres网
  66.                      int count = path.size();
  67.                      for (int i = 0; i < count; i++){. 牛人云集,一亩三分地
  68.                          Point cur = path.poll();
  69.                          ct++;. 一亩-三分-地,独家发布
  70.                          // System.out.println(cur.x + " " + cur.y);. visit 1point3acres for more.
  71.                          // visited[cur.x][cur.y] = true;
  72.                          // update cur.value
  73.                          dis[cur.x][cur.y] += di;
  74.                          // check its neighbors
  75.                          for (int j = 0; j < 4; j++){. 1point3acres
  76.                              int nx = cur.x + dx[j];
  77.                              int ny = cur.y + dy[j];
  78.                              if (nx >= 0 && nx < m && ny >= 0 && ny < m && mat[nx][ny] != 'X' && !visited[nx][ny]){
  79.                                  path.offer(new Point(nx, ny));
  80.                                  visited[nx][ny] = true;
  81.                              }
  82.                          } 来源一亩.三分地论坛.
  83.                      }
  84.                      di++;
  85.                  }
  86.                  System.out.println("total points added to queue: " + ct);
  87.         }
  88.         public static void main(String[] args){
  89.                 Solution sln = new Solution();
  90.                 char[][] mat = {{'0', '0', '0', '0', '1'},. more info on 1point3acres
  91.                                                 {'0', '1', 'X', '0', '0'},.1point3acres网
  92.                                                 {'0', 'X', '0', '0', '0'},
  93.                                                 {'0', '0', '0', '1', '0'},
  94.                                                 {'0', '0', '0', '0', '0'}};
  95.                 Point ret = sln.bestMergePoint(mat);. Waral 博客有更多文章,
  96.                 System.out.println(ret.x + " " + ret.y);
  97.         }
  98. }
复制代码
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-10-23 10:50:05 | 显示全部楼层
赞,楼主很用心啊
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:53:33 | 显示全部楼层
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|.. From 1point 3acres bbs

// Power of a string:.本文原创自1point3acres论坛
// Let A = xyxz 来源一亩.三分地论坛.
// Then,
// A^1 = A = xyxz
// A^2 = xxyyxxzz
// A^3 = xxxyyyxxxzzz
. 1point 3acres 璁哄潧
// Example:
. 1point 3acres 论坛// 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.                 }. more info on 1point3acres
  26.             }
  27.             return ret;
  28.         }
  29.         . from: 1point3acres
  30.         String expand(String A, int k){.本文原创自1point3acres论坛
  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)){. From 1point 3acres bbs
  44.                     a++;
  45.                     b++;. more info on 1point3acres
  46.                 } else {
  47.                     b++;.本文原创自1point3acres论坛
  48.                 }
  49.             }
    -google 1point3acres
  50.             return a == len1;
  51.         }
  52.        
  53.         String preprocess(String A){
  54.             return A.toLowerCase();
  55.         }
复制代码
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 10:54:45 | 显示全部楼层
/*一个正方形的矩阵,左上角的位置保证是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;-google 1point3acres
  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. 1point3acres
  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++){. more info on 1point3acres
  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);.本文原创自1point3acres论坛
  35.                 }
  36.                 return dp1[n][k];. more info on 1point3acres
  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}};. 1point3acres
  42.                 System.out.println(sln.findMaxSpent(mat, 12));
  43.         }
  44. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 11:10:38 | 显示全部楼层
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+b+c-";. 围观我们@1point 3 acres

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++){. visit 1point3acres for more.
  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)){. visit 1point3acres for more.
  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.    boolean isMatch(String s1, String s2, int i, int j){
  25.        char c = s2.charAt(j * 2);
  26.        char p = s2.charAt(j * 2 + 1);
  27.        int len = p == '+' ? 2 : 4;. Waral 博客有更多文章,
  28.        if (i - len < -1) return false;. From 1point 3acres bbs
  29.        for (int h = i - len + 1; h <= i; h++){
  30.            if (s1.charAt(h) != c) return false;
  31.        }
  32.        return true;
  33.    }. 1point3acres
  34.    
  35.    public static void main(String[] args){
  36.            Solution sln = new Solution();
  37.            // 4
  38.            System.out.println(sln.findMatches("waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c-"));
  39.            // 5. Waral 博客有更多文章,
  40.            System.out.println(sln.findMatches("waeginsapnaabangpisebbasccepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc", "a+b+c+c-"));
  41.    }
  42. }
复制代码
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-26 10:14:57 | 显示全部楼层
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:19:19 | 显示全部楼层
Chasego 发表于 2015-10-26 10:14
如果 A 和 B 的长度都是0的话,也是返回0吗?还是返回1?
. visit 1point3acres for more.
不过这样很像,不符合 |A| << |B|
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-26 10:24:27 | 显示全部楼层
Chasego 发表于 2015-10-26 10:14
如果 A 和 B 的长度都是0的话,也是返回0吗?还是返回1?
. 留学申请论坛-一亩三分地
            if (len1 > len2) return 0;
            if (len1 <= 0) return 0;
我返回0,具体要和面试官沟通
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-26 10:27:05 | 显示全部楼层
kennethinsnow 发表于 2015-10-26 10:24.本文原创自1point3acres论坛
if (len1 > len2) return 0;
            if (len1

嗯,我是看到这一行。不过沟通就没问题了。
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-26 10:55:35 | 显示全部楼层
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 这个判断应该没必要吧?
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-26 12:09:12 | 显示全部楼层
Chasego 发表于 2015-10-26 10:55
第14行,sigA[A.charAt(i)] != 0 这个判断应该没必要吧?

恩,可以去掉
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-27 00:50:45 | 显示全部楼层
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){.. 围观我们@1point 3 acres
是不是应该改成 children[row] == 1,意思是对于row已经有一个孩子了,而保证col不是它已有的孩子才返回E1
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-27 01:32:55 | 显示全部楼层
kennethinsnow 发表于 2015-10-23 11:09
http://www.1point3acres.com/bbs/thread-131422-1-1.html
valid binary tree
. Waral 博客有更多文章,
代码很不错,赞楼主一个!
. From 1point 3acres bbs
我当时想到“E5”情况应该是不存在,因为前面四种错误已经涵括所有情况。. Waral 博客有更多文章,

第51行实际是永远不会执行的吗?
回复 支持 反对

使用道具 举报

Chasego 发表于 2015-10-27 10:22:37 | 显示全部楼层
kennethinsnow 发表于 2015-10-23 11:10-google 1point3acres
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc";
String s2 = "a+ ...

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

这里是不是应该改成 i - len < 0 ???
回复 支持 反对

使用道具 举报

zhuo 发表于 2015-10-27 23:15:53 | 显示全部楼层
我也来贴俩题 最近在准备电面 好没底儿。。。。。。。。。。。。
. 牛人云集,一亩三分地
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();-google 1point3acres
  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)){. 1point3acres
  13.                                 lastK = k;
  14.                                 left = k + 1;
  15.                         }else{
  16.                                 right = k - 1;
  17.                         }
  18.                 }. visit 1point3acres for more.
  19.                 return lastK;
  20.         }
  21.         . 围观我们@1point 3 acres
  22.         private String generateKth(String s, int k){.本文原创自1point3acres论坛
  23.                 StringBuilder temp = new StringBuilder();
  24.                 for(int i = 0; i < s.length(); i++){
  25.                         for(int j = 0; j < k; j++){. 1point3acres
  26.                                 temp.append(s.charAt(i));
  27.                         }. 留学申请论坛-一亩三分地
  28.                 }
  29.                 return temp.toString();
  30.         }
  31.         . From 1point 3acres bbs
  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.         }.本文原创自1point3acres论坛

  45.         public static void main(String[] args) {
  46.                 // TODO Auto-generated method stub. Waral 博客有更多文章,
  47.                 largestAK ak = new largestAK();
  48.                 String s1 = "ab";
  49.                 String s2 = "acaaabcbbb";
  50.                 String s3 = "xyxz";
  51.                 String s4 = "xxyyxxzz";
  52.                 System.out.println(ak.findLargestK(s3, s4));. 一亩-三分-地,独家发布
  53.         }. visit 1point3acres for more.

  54. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 14:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表