一亩三分地论坛

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

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

Dropbox第一轮电面 2015.9.10

[复制链接] |试试Instant~ |关注本帖
clockwise9 发表于 2015-9-11 05:34:37 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Dropbox - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
发帖攒人品。找同学的同学内推的,顺利拿到面试。今天下午刚面的所以很热乎。

面试就一道题,为了方便描述要求,附上我的解法,如果各路大神有更科学的解法欢迎分享。

米帝的电话号码经常会跟某个词联系起来。在手机的拨号键盘上,2可以表示ABC,3表示DEF,之类的。现在给一个电话号码,给一个词典,返回所有可能的词或者词组。

写了个暴力版的,用hashset保存词典,先生成所有可能的字符序列,然后对每一个可能的字符序列,用BFS来找全部可能的组成(当时我懵逼了,说用的是动态规划……挂了电话才意识到其实就是BFS),比如如果VISITME,VISIT和ME都在词典中,那么应该返回[[‘VISITME'], ['VISIT', 'ME']]。
. From 1point 3acres bbs
对着手机拨号键盘打表,注意对于0和1的处理,可以直接返回空。然后写了个normalize的函数,把空格、连字符什么的去掉(其实就是去掉非数字字符)。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
然后描述了一下用Trie Index的思路,用伪代码写了核心的搜索过程,然后分析一下复杂度blahblah。

就是这样。

评分

1

查看全部评分

cbwcs 发表于 2015-9-11 06:42:17 | 显示全部楼层
楼主第二个思路是不是 word search II 的思路,那样会不会快一点?
回复 支持 反对

使用道具 举报

mint0715 发表于 2015-9-11 06:51:21 | 显示全部楼层
原题: https://leetcode.com/problems/le ... -of-a-phone-number/

补充内容 (2015-9-11 06:52):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
srry,原来还有字典。。。看了两行以为是原题。。。拙计了。。。
回复 支持 反对

使用道具 举报

Warren 发表于 2015-9-13 11:45:02 | 显示全部楼层
楼主求内推啊,可以帮忙内推么?
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-9-13 12:58:50 | 显示全部楼层
楼主是哪个面试官啊?知道他名字吗
回复 支持 反对

使用道具 举报

carthus 发表于 2016-2-19 13:40:42 | 显示全部楼层
楼主可以说一下Trie Index的思路吗?
回复 支持 反对

使用道具 举报

huai10 发表于 2016-3-3 06:11:08 | 显示全部楼层
https://nuttynanaus.wordpress.com/2014/03/09/software-engineer-interview-questions/
不谢-:)
回复 支持 反对

使用道具 举报

huai10 发表于 2016-3-3 06:11:37 | 显示全部楼层
huai10 发表于 2016-3-3 06:11
https://nuttynanaus.wordpress.com/2014/03/09/software-engineer-interview-questions/
不谢-:)

发错了发错了发错了
回复 支持 反对

使用道具 举报

sealove999 发表于 2016-3-9 07:00:49 | 显示全部楼层
  1. public class Solution {. Waral 鍗氬鏈夋洿澶氭枃绔,
  2.   static List<List<String>> phone2words(String phone, int startPos, Set<String> dict,
  3.       Map<Character, Set<Character>> map, StringBuilder sb) {
  4.     List<List<String>> ret = new ArrayList<>(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.     if (startPos == phone.length()) {. From 1point 3acres bbs
  6.       if (sb.length() > 0 && dict.contains(sb.toString())) {
  7.         List<String> l = new ArrayList<>();
  8.         l.add(sb.toString());
  9.         ret.add(l);
  10.       }
  11.       return ret;. visit 1point3acres.com for more.
  12.     }
  13.     for (Character c : map.get(phone.charAt(startPos))) {
  14.       sb.append(c);
  15.       if (dict.contains(sb.toString())) {
  16.         List<List<String>> r = phone2words(phone, startPos + 1, dict, map, new StringBuilder());
  17.         for (List<String> l : r) {
  18.           l.add(0, sb.toString());. visit 1point3acres.com for more.
  19.           ret.add(l);
  20.         }
  21.       }-google 1point3acres
  22.       ret.addAll(phone2words(phone, startPos + 1, dict, map, sb));. visit 1point3acres.com for more.
  23.       sb.setLength(sb.length() - 1);
  24.     }
  25.     return ret;. from: 1point3acres.com/bbs
  26.   }

  27.   public static void main(String[] args) {
  28.     Map<Character, Set<Character>> map = new HashMap<>();
  29.     map.put('8', new HashSet<Character>());
  30.     map.get('8').add('T');.鏈枃鍘熷垱鑷1point3acres璁哄潧
  31.     map.get('8').add('U');
  32.     map.get('8').add('V');.鏈枃鍘熷垱鑷1point3acres璁哄潧
  33.     map.put('4', new HashSet<Character>());
  34.     map.get('4').add('G');
  35.     map.get('4').add('H');
  36.     map.get('4').add('I');

  37.     Set<String> dict = new HashSet<>();. 鍥磋鎴戜滑@1point 3 acres
  38.     dict.add("TH");. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  39.     dict.add("T");
  40.     dict.add("TI");
  41.     dict.add("I");. from: 1point3acres.com/bbs
  42. . 鍥磋鎴戜滑@1point 3 acres
  43.     List<List<String>> r = phone2words("84", 0, dict, map, new StringBuilder());
  44.     for (List<String> l : r) {-google 1point3acres
  45.       for (String s : l) {
  46.         System.out.print(s);
  47.         System.out.print(" ");
  48.       }
  49.       System.out.println();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  50.     }
  51.   }
  52. }. 1point3acres.com/bbs
复制代码
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-2 07:33:20 | 显示全部楼层
个人意见,用TRIE会快一点,省去了中间很多无意义的DFS递归
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 13:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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