10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

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

Dropbox第一轮电面 2015.9.10

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

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

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

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

x
发帖攒人品。找同学的同学内推的,顺利拿到面试。今天下午刚面的所以很热乎。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
面试就一道题,为了方便描述要求,附上我的解法,如果各路大神有更科学的解法欢迎分享。. visit 1point3acres.com for more.

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

写了个暴力版的,用hashset保存词典,先生成所有可能的字符序列,然后对每一个可能的字符序列,用BFS来找全部可能的组成(当时我懵逼了,说用的是动态规划……挂了电话才意识到其实就是BFS),比如如果VISITME,VISIT和ME都在词典中,那么应该返回[[‘VISITME'], ['VISIT', 'ME']]。

对着手机拨号键盘打表,注意对于0和1的处理,可以直接返回空。然后写了个normalize的函数,把空格、连字符什么的去掉(其实就是去掉非数字字符)。

然后描述了一下用Trie Index的思路,用伪代码写了核心的搜索过程,然后分析一下复杂度blahblah。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

就是这样。. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

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.鏈枃鍘熷垱鑷1point3acres璁哄潧
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,. 鍥磋鎴戜滑@1point 3 acres
  3.       Map<Character, Set<Character>> map, StringBuilder sb) {
  4.     List<List<String>> ret = new ArrayList<>();
  5.     if (startPos == phone.length()) {
  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))) {-google 1point3acres
  14.       sb.append(c);
  15.       if (dict.contains(sb.toString())) {
  16.         List<List<String>> r = phone2words(phone, startPos + 1, dict, map, new StringBuilder());. From 1point 3acres bbs
  17.         for (List<String> l : r) {
  18.           l.add(0, sb.toString());
  19.           ret.add(l);.1point3acres缃
  20.         }
  21.       } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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;
  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');
  33.     map.put('4', new HashSet<Character>());-google 1point3acres
  34.     map.get('4').add('G');
  35.     map.get('4').add('H');
  36.     map.get('4').add('I');. From 1point 3acres bbs

  37.     Set<String> dict = new HashSet<>();
  38.     dict.add("TH");
  39.     dict.add("T");
  40.     dict.add("TI");
  41.     dict.add("I");
  42. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  43.     List<List<String>> r = phone2words("84", 0, dict, map, new StringBuilder());. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  44.     for (List<String> l : r) {
  45.       for (String s : l) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  46.         System.out.print(s);
  47.         System.out.print(" ");
  48.       }
  49.       System.out.println();
  50.     }
  51.   }
  52. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 02:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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