一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2578|回复: 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']]。
. Waral 鍗氬鏈夋洿澶氭枃绔,
对着手机拨号键盘打表,注意对于0和1的处理,可以直接返回空。然后写了个normalize的函数,把空格、连字符什么的去掉(其实就是去掉非数字字符)。.鐣欏璁哄潧-涓浜-涓夊垎鍦
. From 1point 3acres bbs
然后描述了一下用Trie Index的思路,用伪代码写了核心的搜索过程,然后分析一下复杂度blahblah。

就是这样。. 1point3acres.com/bbs

评分

1

查看全部评分

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

使用道具 举报

mint0715 发表于 2015-9-11 06:51:21 | 显示全部楼层
关注一亩三分地微博:
Warald
原题: https://leetcode.com/problems/le ... -of-a-phone-number/

补充内容 (2015-9-11 06:52):-google 1point3acres
srry,原来还有字典。。。看了两行以为是原题。。。拙计了。。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

leixiang5 发表于 2015-9-13 12:58:50 | 显示全部楼层
楼主是哪个面试官啊?知道他名字吗
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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. 1point3acres.com/bbs
https://nuttynanaus.wordpress.com/2014/03/09/software-engineer-interview-questions/. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
不谢-:)

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

使用道具 举报

sealove999 发表于 2016-3-9 07:00:49 | 显示全部楼层
  1. public class Solution {
  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()) {
    . more info on 1point3acres.com
  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;
  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());
  19.           ret.add(l);
  20.         }
  21.       }
  22.       ret.addAll(phone2words(phone, startPos + 1, dict, map, sb)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  23.       sb.setLength(sb.length() - 1);
  24.     }
  25.     return ret;
  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');
  31.     map.get('8').add('U');
  32.     map.get('8').add('V');. 1point 3acres 璁哄潧
  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<>();
  38.     dict.add("TH");
  39.     dict.add("T");
  40.     dict.add("TI");
  41.     dict.add("I");

  42.     List<List<String>> r = phone2words("84", 0, dict, map, new StringBuilder());. visit 1point3acres.com for more.
  43.     for (List<String> l : r) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  44.       for (String s : l) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  45.         System.out.print(s);
  46.         System.out.print(" ");
  47.       }. 1point3acres.com/bbs
  48.       System.out.println();
  49.     }
  50.   }. Waral 鍗氬鏈夋洿澶氭枃绔,
  51. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-26 13:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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