《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1583|回复: 21
收起左侧

【亚麻社招】跪经……要刷透hard了呀,同志们

[复制链接] |试试Instant~ |关注本帖
Galoisgun 发表于 2017-9-15 09:38:39 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Amazon - 内推 - 技术电面 |Fail在职跳槽

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

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

x
刚收到拒信……亚麻AWS组电面,考了word break II的改版,只要输出一个结果就行。一开始想当然以为是word break I,写了一下被面试官纠正。之前刷题word breakII用backtracking做的,折腾了半天没弄好怎么只输出一个结果。
后面想了一下,应该用一个matrix存一下words的状态再dfs一下就好. 鍥磋鎴戜滑@1point 3 acres
提醒大家还是要刷透一些hard的题的,我这次就是hard没刷透。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Amazon|主题: 442, 订阅: 33
oldman09 发表于 2017-9-15 09:55:26 | 显示全部楼层
  1. public static String wordBreakII(String s, List<String> wordDict) {
  2.         return backtracking(s, new StringBuilder(), wordDict);
  3.     }
  4.    
  5.     public static String backtracking(String s, StringBuilder sentence, List<String> wordDict) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  6.         if(wordDict.contains(s)){
  7.             sentence.append(' ');. 1point3acres.com/bbs
  8.             sentence.append(s);
  9.             return sentence.toString();
  10.         }

  11.         for(String word : wordDict) {
  12.             if(s.startsWith(word)){.1point3acres缃
  13.                 String res = backtracking(s.substring(word.length()), sentence.length() == 0? sentence.append(word) : sentence.append(' ').append(word), wordDict);
  14.                 if(!res.isEmpty()) return res;
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15.             }
  16.         }
  17.         return "";
  18.     }
复制代码

补充内容 (2017-9-15 11:05):.鏈枃鍘熷垱鑷1point3acres璁哄潧
正如sugar所讲, dp可解。-google 1point3acres
static String wordBreakIIOneSolution(String s, List<String> wordDict) {
        if(s.isEmpty()) return "";. 1point3acres.com/bbs
        int[] dp = new int[s.length() + 1];
        Set<String> s...
回复 支持 反对

使用道具 举报

mdzzxswl 发表于 2017-9-15 10:01:06 | 显示全部楼层
你是跳槽的吗:(((
回复 支持 反对

使用道具 举报

sugar 发表于 2017-9-15 10:17:44 | 显示全部楼层
又是这题,昨天看到FB也考这题
只输出一个结果是word break I的变种,因为还可以用DP,boolean改成int,dp[i]记录子串的开始索引. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不是要求返回所有结果,就不要先考虑DFS
回复 支持 反对

使用道具 举报

Charleschen 发表于 2017-9-15 10:18:32 | 显示全部楼层
会不会因为是AWS所以考的比较难?
回复 支持 反对

使用道具 举报

 楼主| Galoisgun 发表于 2017-9-15 10:20:40 | 显示全部楼层

嚯!多谢多谢~我研究一下!
回复 支持 反对

使用道具 举报

 楼主| Galoisgun 发表于 2017-9-15 10:20:59 | 显示全部楼层
mdzzxswl 发表于 2017-9-15 10:01
你是跳槽的吗:(((
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
嗯嗯 投的社招职位
回复 支持 反对

使用道具 举报

 楼主| Galoisgun 发表于 2017-9-15 10:21:29 | 显示全部楼层
sugar 发表于 2017-9-15 10:17
又是这题,昨天看到FB也考这题
只输出一个结果是word break I的变种,因为还可以用DP,boolean改成int,dp ...
. 1point 3acres 璁哄潧
对的 面完回过神发现 确实还是dp简单
回复 支持 反对

使用道具 举报

 楼主| Galoisgun 发表于 2017-9-15 10:21:40 | 显示全部楼层
Charleschen 发表于 2017-9-15 10:18
会不会因为是AWS所以考的比较难?

有可能!
回复 支持 反对

使用道具 举报

oldman09 发表于 2017-9-15 11:07:13 | 显示全部楼层
正如sugar所讲, dp可解。
  1. static String wordBreakIIOneSolution(String s, List<String> wordDict) {. 鍥磋鎴戜滑@1point 3 acres
  2.         if(s.isEmpty()) return "";. visit 1point3acres.com for more.
  3.         int[] dp = new int[s.length() + 1];
  4.         Set<String> set = new HashSet<String>();
  5.         Arrays.fill(dp, -1);. from: 1point3acres.com/bbs
  6.         set.addAll(wordDict);
  7.         dp[0] = 0;-google 1point3acres
  8.         for(int i = 0; i <= s.length(); i++) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.             for(int j = 0; j < i; j++) {
  10.                 if(dp[j] != -1 && set.contains(s.substring(j, i))) {
  11.                     dp[i] = j;
  12.                     break;
  13.                 }
  14.             }. 1point3acres.com/bbs
  15.         }
  16.         if(dp[s.length()] == -1) return "";
  17.         StringBuilder res = new StringBuilder();
  18.         int j = s.length();
  19.         while(dp[j] > 0) {. more info on 1point3acres.com
  20.             if(j == s.length()) res.insert(0,s.substring(dp[j], j));
  21.             else res.insert(0,s.substring(dp[j], j) + " ");
  22.             j = dp[j];
  23.         }
  24.         if(j == s.length()) res.insert(0,s.substring(dp[j], j));
  25.         else res.insert(0,s.substring(dp[j], j) + " ");. more info on 1point3acres.com
  26.         return res.toString();
  27.     }
复制代码
回复 支持 反对

使用道具 举报

jigsaw_Becky 发表于 2017-9-15 11:47:16 | 显示全部楼层
oldman09 发表于 2017-9-15 11:07-google 1point3acres
正如sugar所讲, dp可解。
. 1point 3acres 璁哄潧
应该可以把最后那个while循环的判断条件改为 j > 0,然后就可以把最后的if else删了吧?
回复 支持 反对

使用道具 举报

woodman 发表于 2017-9-15 11:49:06 | 显示全部楼层
问一下楼主是过了第一轮OA  跪在第二轮电面了? 电面现在都这么难了?   OA 部分什么内容还能记起来吗?
回复 支持 反对

使用道具 举报

oldman09 发表于 2017-9-15 11:50:35 | 显示全部楼层
jigsaw_Becky 发表于 2017-9-15 11:47
应该可以把最后那个while循环的判断条件改为 j > 0,然后就可以把最后的if else删了吧?

对 应该是可以那样
回复 支持 反对

使用道具 举报

facetothefate 发表于 2017-9-15 11:57:47 | 显示全部楼层
这俩题我都是dijkstra解的。。。 open集里都是1,很好写
回复 支持 反对

使用道具 举报

wojiushieyu 发表于 2017-9-15 12:33:21 | 显示全部楼层
dijkstra 怎么解?
回复 支持 反对

使用道具 举报

broadway_he 发表于 2017-11-15 15:58:16 | 显示全部楼层
确实好恶心,word break II的实现包含BFS和DFS,先生成图再在上面找最短路径,代码量可谓巨大。我觉得aws组纯粹就是在坑你或者没有hc,不想再招人了。

补充内容 (2017-11-15 16:01):
好像我看错题了,晕
回复 支持 反对

使用道具 举报

 楼主| Galoisgun 发表于 2017-11-15 16:02:52 | 显示全部楼层
broadway_he 发表于 2017-11-15 15:58
确实好恶心,word break II的实现包含BFS和DFS,先生成图再在上面找最短路径,代码量可谓巨大。我觉得aws组 ...

可能是最近的高频题?我在别的面试也遇到了其实
回复 支持 反对

使用道具 举报

ws3109 发表于 2017-11-16 00:51:20 | 显示全部楼层
求问楼主timeline
回复 支持 反对

使用道具 举报

 楼主| Galoisgun 发表于 2017-11-16 03:11:15 | 显示全部楼层
ws3109 发表于 2017-11-16 00:51
-google 1point3acres求问楼主timeline
. 1point3acres.com/bbs
我记得是
请朋友内推后一周收到OA
做完OA后半个月收到电面通知
电面后一周跪了
回复 支持 反对

使用道具 举报

ws3109 发表于 2017-11-16 03:46:11 | 显示全部楼层
Galoisgun 发表于 2017-11-16 03:11
我记得是
请朋友内推后一周收到OA
做完OA后半个月收到电面通知

谢谢楼主,我今天是店面后第五天,一直提心吊胆的。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 17:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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