传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 865|回复: 14
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
Galoisgun 发表于 6 天前 | 显示全部楼层 |阅读模式

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

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

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

x
刚收到拒信……亚麻AWS组电面,考了word break II的改版,只要输出一个结果就行。一开始想当然以为是word break I,写了一下被面试官纠正。之前刷题word breakII用backtracking做的,折腾了半天没弄好怎么只输出一个结果。
后面想了一下,应该用一个matrix存一下words的状态再dfs一下就好
提醒大家还是要刷透一些hard的题的,我这次就是hard没刷透。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Amazon|主题: 207, 订阅: 14
oldman09 发表于 6 天前 | 显示全部楼层
  1. public static String wordBreakII(String s, List<String> wordDict) {
    .1point3acres缃
  2.         return backtracking(s, new StringBuilder(), wordDict);
  3.     }. From 1point 3acres bbs
  4.    
  5.     public static String backtracking(String s, StringBuilder sentence, List<String> wordDict) {
  6.         if(wordDict.contains(s)){
  7.             sentence.append(' ');
  8.             sentence.append(s);
  9.             return sentence.toString();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.         }
  11. . Waral 鍗氬鏈夋洿澶氭枃绔,
  12.         for(String word : wordDict) {. visit 1point3acres.com for more.
  13.             if(s.startsWith(word)){
  14.                 String res = backtracking(s.substring(word.length()), sentence.length() == 0? sentence.append(word) : sentence.append(' ').append(word), wordDict);
  15.                 if(!res.isEmpty()) return res;
  16.             }
  17.         }
  18.         return "";
  19.     }
复制代码
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2017-9-15 11:05):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
正如sugar所讲, dp可解。
static String wordBreakIIOneSolution(String s, List<String> wordDict) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        if(s.isEmpty()) return "";
        int[] dp = new int[s.length() + 1];
        Set<String> s...
回复 支持 反对

使用道具 举报

mdzzxswl 发表于 6 天前 | 显示全部楼层
你是跳槽的吗:(((
回复 支持 反对

使用道具 举报

sugar 发表于 6 天前 | 显示全部楼层
又是这题,昨天看到FB也考这题
只输出一个结果是word break I的变种,因为还可以用DP,boolean改成int,dp[i]记录子串的开始索引. visit 1point3acres.com for more.
不是要求返回所有结果,就不要先考虑DFS
回复 支持 反对

使用道具 举报

Charleschen 发表于 6 天前 | 显示全部楼层
会不会因为是AWS所以考的比较难?
回复 支持 反对

使用道具 举报

 楼主| Galoisgun 发表于 6 天前 | 显示全部楼层

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

使用道具 举报

 楼主| Galoisgun 发表于 6 天前 | 显示全部楼层
mdzzxswl 发表于 2017-9-15 10:01
你是跳槽的吗:(((

嗯嗯 投的社招职位
回复 支持 反对

使用道具 举报

 楼主| Galoisgun 发表于 6 天前 | 显示全部楼层
sugar 发表于 2017-9-15 10:17
又是这题,昨天看到FB也考这题. from: 1point3acres.com/bbs
只输出一个结果是word break I的变种,因为还可以用DP,boolean改成int,dp ...

对的 面完回过神发现 确实还是dp简单
回复 支持 反对

使用道具 举报

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

有可能!
回复 支持 反对

使用道具 举报

oldman09 发表于 6 天前 | 显示全部楼层
正如sugar所讲, dp可解。
  1. static String wordBreakIIOneSolution(String s, List<String> wordDict) {
  2.         if(s.isEmpty()) return "";. 1point3acres.com/bbs
  3.         int[] dp = new int[s.length() + 1];
  4.         Set<String> set = new HashSet<String>();
  5.         Arrays.fill(dp, -1);
  6.         set.addAll(wordDict);. from: 1point3acres.com/bbs
  7.         dp[0] = 0;
  8.         for(int i = 0; i <= s.length(); i++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.             }
  15.         }
  16.         if(dp[s.length()] == -1) return "";
  17.         StringBuilder res = new StringBuilder();
  18.         int j = s.length();
  19.         while(dp[j] > 0) {
  20.             if(j == s.length()) res.insert(0,s.substring(dp[j], j));
  21.             else res.insert(0,s.substring(dp[j], j) + " ");.1point3acres缃
  22.             j = dp[j];. Waral 鍗氬鏈夋洿澶氭枃绔,
  23.         }
  24.         if(j == s.length()) res.insert(0,s.substring(dp[j], j));. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  25.         else res.insert(0,s.substring(dp[j], j) + " ");
  26.         return res.toString();
  27.     }
复制代码
回复 支持 反对

使用道具 举报

jigsaw_Becky 发表于 6 天前 | 显示全部楼层
oldman09 发表于 2017-9-15 11:07
. visit 1point3acres.com for more.正如sugar所讲, dp可解。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
应该可以把最后那个while循环的判断条件改为 j > 0,然后就可以把最后的if else删了吧?
回复 支持 反对

使用道具 举报

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

使用道具 举报

oldman09 发表于 6 天前 | 显示全部楼层
jigsaw_Becky 发表于 2017-9-15 11:47
应该可以把最后那个while循环的判断条件改为 j > 0,然后就可以把最后的if else删了吧?
. 1point 3acres 璁哄潧
对 应该是可以那样
回复 支持 反对

使用道具 举报

facetothefate 发表于 6 天前 | 显示全部楼层
这俩题我都是dijkstra解的。。。 open集里都是1,很好写
回复 支持 反对

使用道具 举报

wojiushieyu 发表于 6 天前 | 显示全部楼层
dijkstra 怎么解?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 13:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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