一亩三分地论坛

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

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

Zenefits OA3 换题库了吗这是

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

2015(4-6月) 码农类 硕士 全职@Zenefits - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
Zenefits OA test 3。。。. more info on 1point3acres.com
这周是换题库了吗? 打开完全不是说好的good value 和 stock变种啊。。 准备了半天。。. Waral 鍗氬鏈夋洿澶氭枃绔,
因为是新题库就简单说下题目和思路,防止认出来。

1 longestchain
类似word ladder,对于一个单词删掉任何一个字母,如果新单词出现在给的词典里 那么就形成一个 chain: old word -> new word -> newer word, 求最长长度(return int) 比如给vector<string> w = {a,ba,bca,bda,bdca} 最长是4: bdca->bda->ba->a;
思路: 建一个map<长度,set<string>> 根据长度把输入的字典放到set里,然后从最长的长度所在的map[长度] 开始枚举每个单词并缩减然后进行recursive call, 比如bdca 那么就可能缩成dca,bca,bda 然后去map[3]里找,类推直到 word.size()==1 或找不到, 放个全局int去记最大长度。
注意找到后从字典里删除和word ladder一样 否则只能过4个case 会超时。

2 N queen 变种
题目巨长输入格式是
1
2
就是说 第1行第1个是queen 第2行第2个是queen,并保证输入的数字不重复,这样可以得出一个结论:同一行 同一列不会出现2个queen。
题目要求是求出 对于每个Queen, 最大的威胁次数,威胁指只要一个queen所能移动的范围内有别的queen就算威胁 P.S.同一方向上有2个queen威胁你 只算最近的那个。. from: 1point3acres.com/bbs
由于同一行 同一列不会出现2个queen。(由于输入限制)所以只要考虑对角线 和逆对角线。. Waral 鍗氬鏈夋洿澶氭枃绔,
举个例子: 棋盘是:
100           ---- 1号 queen
010           ---- 2号 queen
001           ---- 3号 queen.鐣欏璁哄潧-涓浜-涓夊垎鍦
1号和3号queen的受威胁次数都是1, 2号是2(被1和3) 所以答案是2
这题我是建了2个hash表 一个是正对角线一个逆对角线来表示对角线上是否有别的queen.
从row 0 开始到 最后行, 对于输入的 column位置 先判定 hash表是否有别的Queen没的话就set 1 继续下一行
有的话就threats[row]++ 然后向那个方向追踪是谁给你的威胁,把那个点的threat也++ 就好了。

因为换题临时比较匆忙,方法不好还请大家指出,就当抛砖引玉攒RP了。 . more info on 1point3acres.com
大家找工作加油 干死印度人。


补充内容 (2015-4-20 12:23):
hashset存最近的上一个queen就好了这样不用追踪回去浪费时间

评分

12

查看全部评分

本帖被以下淘专辑推荐:

shanks_le 发表于 2015-6-9 12:41:52 | 显示全部楼层
我也遇到了这个。。之前没看到这个帖子。 第二题楼主给的应该是最优解了。不过第一题是可以用DP做的,思路和楼主的也差不多. 只不过hashmap里存的是另一个word->maxchain的hashmap,然后从length=1时开始往上build,如果相邻的两个length差距超过1就跳过
回复 支持 1 反对 0

使用道具 举报

 楼主| kevinking813 发表于 2015-5-6 02:26:20 | 显示全部楼层
ohohgod 发表于 2015-5-6 01:46
楼主能上代码么

思路可以共享 代码不开源
回复 支持 1 反对 0

使用道具 举报

 楼主| kevinking813 发表于 2015-4-20 22:16:48 | 显示全部楼层
新手求大米。。。没人理。。
回复 支持 反对

使用道具 举报

xieqilu1989 发表于 2015-4-21 02:38:54 | 显示全部楼层
我大概两周前做的时候还不是这个题,估计是换题了吧,多谢分享!
回复 支持 反对

使用道具 举报

yangxican 发表于 2015-4-21 07:32:12 | 显示全部楼层
顶楼主,按照楼主的方法过了OA,但是1有个问题,假如最长的单词和其他的单词不是连起来的 比如vector<string> w = {a,ba,bca,bda,bdca,adsasdasda}这样最长的长度所在的map[长度] 开始枚举就不行了 . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

但是OA里面是可行的 lol

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| kevinking813 发表于 2015-4-21 08:19:46 | 显示全部楼层
yangxican 发表于 2015-4-21 07:32
顶楼主,按照楼主的方法过了OA,但是1有个问题,假如最长的单词和其他的单词不是连起来的 比如vector w = { ...

这个我考虑过的 对于每个长度的所有集合 我最外层都会迭代的 最差是O(n2) 但是由于删除元素和 如果当前比如最长已经4了 那么就不会从map[3]继续迭代了 这样最优或平均下能O(n)
回复 支持 反对

使用道具 举报

ManitobaFarmer 发表于 2015-4-26 11:33:29 | 显示全部楼层
是的,我也做的这个。这两道题还算简单。
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-4-26 15:41:55 | 显示全部楼层
ManitobaFarmer 发表于 2015-4-26 11:33. more info on 1point3acres.com
是的,我也做的这个。这两道题还算简单。

请问第二题是不是只要遇到一个queen受到4个方向的威胁就可以返回了,因为最多威胁也就是4,对吗?
回复 支持 反对

使用道具 举报

 楼主| kevinking813 发表于 2015-4-27 04:01:33 | 显示全部楼层
refurbish 发表于 2015-4-26 15:41
请问第二题是不是只要遇到一个queen受到4个方向的威胁就可以返回了,因为最多威胁也就是4,对吗?

是的 最多4
回复 支持 反对

使用道具 举报

ManitobaFarmer 发表于 2015-5-1 01:38:29 | 显示全部楼层
refurbish 发表于 2015-4-26 15:41
请问第二题是不是只要遇到一个queen受到4个方向的威胁就可以返回了,因为最多威胁也就是4,对吗?

6个吧。上下和四个斜面。
回复 支持 反对

使用道具 举报

 楼主| kevinking813 发表于 2015-5-1 01:54:33 | 显示全部楼层
ManitobaFarmer 发表于 2015-5-1 01:38
6个吧。上下和四个斜面。

好像题目的输入方式决定了每列每行只有1个queen
回复 支持 反对

使用道具 举报

ManitobaFarmer 发表于 2015-5-1 10:59:00 | 显示全部楼层
kevinking813 发表于 2015-5-1 01:54-google 1point3acres
好像题目的输入方式决定了每列每行只有1个queen

每行只有一个 Queen,但是每列是可以有多个的。
回复 支持 反对

使用道具 举报

 楼主| kevinking813 发表于 2015-5-2 00:03:28 | 显示全部楼层
ManitobaFarmer 发表于 2015-5-1 10:59
每行只有一个 Queen,但是每列是可以有多个的。

输入说了 不重复的序列 所以不可能有
回复 支持 反对

使用道具 举报

ManitobaFarmer 发表于 2015-5-2 00:21:48 | 显示全部楼层
kevinking813 发表于 2015-5-2 00:03
输入说了 不重复的序列 所以不可能有

没注意这个,我当6个威胁来做的,也过了。不考虑总威胁数,遍历所有 Queen 也是可以通过的。Hackerrank 的 test cases 没有 LeetCode 的严谨。第二题有个巨大的 Bug 也可以通过。
回复 支持 反对

使用道具 举报

ohohgod 发表于 2015-5-6 01:46:52 | 显示全部楼层
kevinking813 发表于 2015-4-21 08:19
这个我考虑过的 对于每个长度的所有集合 我最外层都会迭代的 最差是O(n2) 但是由于删除元素和 如果当前 ...

楼主能上代码么
回复 支持 反对

使用道具 举报

edussx 发表于 2015-5-14 10:22:04 | 显示全部楼层
刚才做了OA3,第二题用lz思路dfs做的,我字典里删了单词还是会超时
python只过了6个case,一怒之下换c++重写,结果只过了3个……
回复 支持 反对

使用道具 举报

 楼主| kevinking813 发表于 2015-5-14 11:44:29 | 显示全部楼层
edussx 发表于 2015-5-14 10:22
刚才做了OA3,第二题用lz思路dfs做的,我字典里删了单词还是会超时
python只过了6个case,一怒之下换c++重 ...

不会吧 我也是C++ case全过了 估计哪里有问题吧
回复 支持 反对

使用道具 举报

edussx 发表于 2015-5-14 14:52:48 | 显示全部楼层
kevinking813 发表于 2015-5-14 11:44
不会吧 我也是C++ case全过了 估计哪里有问题吧

我C++版本的代码用gist发你了,可以帮我看下吗?谢谢!
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-17 05:24:57 | 显示全部楼层
longest chain怎么解决比较巧妙呢? 我完全套不上word ladder的路子, 这种题目太缺练了

最后写了一个暴力的,用greedy的方法对每一个词找longest chain, 把所有词都扫一遍找longest chain

  HashMap<String, Integer> found = new HashMap<>();
  public int getLongestChainHelper(Set<String> dict, String word) {
    if(dict == null){
      return 0;
    }
    if(word.length() == 1){
      return 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
    }
    if(found.containsKey(word)) {
      return found.get(word);
    }
    int maxLen = -1;
    for(int i = 0; i < word.length(); i++) {
       String newWord = removeCharAt(word, i);
.鐣欏璁哄潧-涓浜-涓夊垎鍦       if(dict.contains(newWord)) {
            int longestChainNewWord = getLongestChainHelper(dict, newWord);
            if(longestChainNewWord + 1 > maxLen) {
              maxLen = longestChainNewWord + 1;
            }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
       }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    }
    maxLen = maxLen == -1 ? 1 : maxLen;
    found.put(word, maxLen);.1point3acres缃
    return maxLen;
  }

  public int getLongestChain(Set<String> dict) {
    if(dict == null){
      return 0;
    }. 1point 3acres 璁哄潧
    int longestChain = -1;. visit 1point3acres.com for more.
    for( String word : dict) {
      int currLongest = getLongestChainHelper(dict, word);
      if( currLongest > longestChain) {. more info on 1point3acres.com
        longestChain = currLongest;
      }
    }
    return longestChain;
  }
回复 支持 反对

使用道具 举报

huahuazhu 发表于 2015-5-17 06:19:00 | 显示全部楼层
写了一下n queen变种那个, 看不出我这个跟递归有啥关系, 遇到新题就彻底死机只会bruteforce

  public int maxThreats(int[] queens) {
    if(queens == null || queens.length ==0) {
. visit 1point3acres.com for more.      return 0;
    }
    int maxThreats = -1;
    int[] threats = new int[queens.length];.鏈枃鍘熷垱鑷1point3acres璁哄潧
    for(int i = 0; i < queens.length; i++) {
      boolean[] hasThreats = new boolean[queens.length];
      for(int j = i + 1; j < queens.length; j++) {
        int t = isThreats(i, queens[i], j, queens[j]);
        if(t >= 0 && hasThreats[t] == false) {
          threats[i] += 1;
          threats[j] += 1;
          hasThreats[t] = true;
        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
      }
    }
    for(int t : threats) {
      if(t > maxThreats) {
        maxThreats = t;
      }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    }
    return maxThreats;
  }

  private static int isThreats(int row1, int col1, int row2, int col2) {
    if (col2 - col1 == row2 - row1) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
      if (col2 > col1) {
        return 0;
      } else {
        return 1;
      }
    }.1point3acres缃
    if (col2 - col1 == row1 - row2) {. more info on 1point3acres.com
      if (col2 > col1) {
        return 2;
      } else {
        return 3;. From 1point 3acres bbs
      }
    }
    return -1;
  }
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 04:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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