一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1175|回复: 14
收起左侧

10分钟前的面经 Zenefits

[复制链接] |试试Instant~ |关注本帖
jiak94 发表于 2015-9-1 03:59:28 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Zenefits - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x
国人面的, 自己表现的太差, 脑子不好使. 挂了电话我就知道自己跪定了.

A, B两个String. 1point3acres.com/bbs
//example
A = XYZ;-google 1point3acres
A^2 = XXYYZZ;
A^3 = XXXYYYZZZ;


B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh. 鍥磋鎴戜滑@1point 3 acres

A^2 是B的subsequence, 所以
return k = 2;

A可能有重复的char, B可能有其他字符, 求k.


jiebour 发表于 2015-9-1 04:27:30 | 显示全部楼层
应该是最小k吧?. From 1point 3acres bbs

补充内容 (2015-9-1 04:28):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
最大...
回复 支持 反对

使用道具 举报

jimwallet 发表于 2015-9-1 04:31:36 | 显示全部楼层
请问lz 的oa是什么题目啊?
回复 支持 反对

使用道具 举报

 楼主| jiak94 发表于 2015-9-1 05:29:32 | 显示全部楼层
jimwallet 发表于 2015-9-1 04:31. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
请问lz 的oa是什么题目啊?

OA #1 valid BST 和 Super Stack
回复 支持 反对

使用道具 举报

 楼主| jiak94 发表于 2015-9-1 05:29:50 | 显示全部楼层
jiebour 发表于 2015-9-1 04:27
应该是最小k吧?
. visit 1point3acres.com for more.
补充内容 (2015-9-1 04:28):

对, 求最大K
回复 支持 反对

使用道具 举报

jimwallet 发表于 2015-9-1 05:30:40 | 显示全部楼层
多谢楼主,一会面试祝你好运!期待更新谢谢
回复 支持 反对

使用道具 举报

dwl1222 发表于 2015-9-1 06:16:31 | 显示全部楼层
用hashmap么。
先把每个char 计数然后存在map里面。.鐣欏璁哄潧-涓浜-涓夊垎鍦
然后每个循环里面生成一个新的map.每个char的个数*k就行了
然后遍历这个b string.每次遇到char就 -1 如果=0就删掉。 如果集合空了就表明都用玩了。可以。
如果到头了集合还有char说明没用完。返回上一个k
回复 支持 反对

使用道具 举报

dwl1222 发表于 2015-9-1 06:18:05 | 显示全部楼层
dwl1222 发表于 2015-9-1 06:16
用hashmap么。
先把每个char 计数然后存在map里面。
然后每个循环里面生成一个新的map.每个char的个数*k ...
. 1point 3acres 璁哄潧
不过是subsequence似乎不行啊
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-1 07:13:02 | 显示全部楼层
楼主, 打错了吗? eZafhajkefhlZadhflkejhZfagjhfebhh 这有三个Z.1point3acres缃
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-9-1 07:14):.1point3acres缃
eZafhajkefhlZadhflkejhZfagjhfebhh 这有三个Z
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-1 07:15:57 | 显示全部楼层
最好用regular expression
回复 支持 反对

使用道具 举报

 楼主| jiak94 发表于 2015-9-1 12:49:23 | 显示全部楼层
hulahu 发表于 2015-9-1 07:13
楼主, 打错了吗? eZafhajkefhlZadhflkejhZfagjhfebhh 这有三个Z

补充内容 (2015-9-1 07:14):

标少了...但是答案还是2 因为Y只有两个
回复 支持 反对

使用道具 举报

purplesky85 发表于 2015-9-2 05:26:23 | 显示全部楼层
不知道要求的时间复杂度是多少,简单想了下,可以用二分。

  public int StringPower(String A, String B) {
    if (A.length() > B.length()) {. 1point3acres.com/bbs
      return 0;
    }. from: 1point3acres.com/bbs
    int n = B.length() / A.length();

    int left = 0;
    int right = n;
    while (left + 1 < right) {
      int mid = left + (right - left) / 2;
      if (isValid(A, B, mid)) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        left = mid;
      } else {
        right = mid;
      }
    }

    if (isValid(A, B, right)) {
      return right;
    }
    return left;
  }

  private boolean isValid(String A, String B, int k) {
    int index = 0;
    for (int i = 0; i < A.length(); i++) {
      for (int j = 0; j < k; j++) {
        while (index < B.length() && A.charAt(i) != B.charAt(index)) {
          index++; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        }
        if (index == B.length()) {
          return false;
        }
        index++;
      }. Waral 鍗氬鏈夋洿澶氭枃绔,
    }
-google 1point3acres
    return true;
  }
回复 支持 反对

使用道具 举报

 楼主| jiak94 发表于 2015-9-3 01:10:03 | 显示全部楼层
purplesky85 发表于 2015-9-2 05:26
不知道要求的时间复杂度是多少,简单想了下,可以用二分。
. Waral 鍗氬鏈夋洿澶氭枃绔,
  public int StringPower(String A, String  ...

没太看懂, 但是简单的方法可以先从1开始, 判断是否是subseqence, 如果是, power++, 再判断, 直到不是为止.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

power = 0;
XYZ是, power++; 然后再 判断 XXYYZZ, 也是, power++;, 再判断XXXYYYZZZ, 结果不是, 此时power = 2. visit 1point3acres.com for more.

就return了. 时间复杂度是O(N)
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-4 00:51:03 | 显示全部楼层
public int findK(String a, String b) {
        int[] count_a = new int[256];.1point3acres缃
        int[] count_b = new int[256];
        for (int i = 0; i < a.length(); i++) {. 鍥磋鎴戜滑@1point 3 acres
            count_a[a.charAt(i)]++;
        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        for (int i = 0; i < b.length(); i++) {
            if (count_a[b.charAt(i)] == 0). 1point 3acres 璁哄潧
                count_b[b.charAt(i)] --;
            else
                count_b[b.charAt(i)] ++;
        }
        StringBuffer sb_b = new StringBuffer();. Waral 鍗氬鏈夋洿澶氭枃绔,
        for (int i = 0; i < b.length(); i++) {
            if (count_b[b.charAt(i)] > 0). Waral 鍗氬鏈夋洿澶氭枃绔,
                sb_b.append(b.charAt(i));
        }
        String t_b = encode(sb_b.toString());
        int min = Integer.MAX_VALUE;
        for (int i = 0; i <t_b.length(); i++) {
            if (t_b.charAt(i) <= '9' && t_b.charAt(i) >= '0')
                min = Math.min(min, t_b.charAt(i) - '0');
        }
        return min;
    }
    public String encode(String s) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            int counter = 1;
            while (i+1 < s.length() && s.charAt(i) == s.charAt(i+1)) {
                counter++;
                i++;
            }
            sb.append(counter);
            sb.append(s.charAt(i));. visit 1point3acres.com for more.
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        String a = "XYX";
        String b = "XXadhflakjhelXXzzqqkkpoYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhhXX";
        System.out.println(new Zenefits().findK(a,b));
    }
回复 支持 反对

使用道具 举报

夜行码农耗子 发表于 2015-9-6 04:35:30 | 显示全部楼层
readman 发表于 2015-9-4 00:51 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
public int findK(String a, String b) {
        int[] count_a = new int[256];
        int[] count_b ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
XXXYYYXZZZ 的话是否会return 1
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 08:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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