在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3384|回复: 9
收起左侧

Dropbox第一轮电面 2015.9.10

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

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

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

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

x
发帖攒人品。找同学的同学内推的,顺利拿到面试。今天下午刚面的所以很热乎。.本文原创自1point3acres论坛
.1point3acres网
面试就一道题,为了方便描述要求,附上我的解法,如果各路大神有更科学的解法欢迎分享。

米帝的电话号码经常会跟某个词联系起来。在手机的拨号键盘上,2可以表示ABC,3表示DEF,之类的。现在给一个电话号码,给一个词典,返回所有可能的词或者词组。
. visit 1point3acres for more.
写了个暴力版的,用hashset保存词典,先生成所有可能的字符序列,然后对每一个可能的字符序列,用BFS来找全部可能的组成(当时我懵逼了,说用的是动态规划……挂了电话才意识到其实就是BFS),比如如果VISITME,VISIT和ME都在词典中,那么应该返回[[‘VISITME'], ['VISIT', 'ME']]。

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

然后描述了一下用Trie Index的思路,用伪代码写了核心的搜索过程,然后分析一下复杂度blahblah。. 一亩-三分-地,独家发布
. from: 1point3acres
就是这样。

评分

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/. 围观我们@1point 3 acres

补充内容 (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/
不谢-:)

发错了发错了发错了
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

sealove999 发表于 2016-3-9 07:00:49 | 显示全部楼层
  1. public class Solution {
  2.   static List<List<String>> phone2words(String phone, int startPos, Set<String> dict,. from: 1point3acres
  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())) {.本文原创自1point3acres论坛
  7.         List<String> l = new ArrayList<>();.1point3acres网
  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);. 1point 3acres 论坛
  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.       }. 1point 3acres 论坛
  22.       ret.addAll(phone2words(phone, startPos + 1, dict, map, sb));
  23.       sb.setLength(sb.length() - 1);
  24.     }. 1point 3acres 论坛
  25.     return ret; 来源一亩.三分地论坛.
  26.   }
  27. . more info on 1point3acres
  28.   public static void main(String[] args) {
  29.     Map<Character, Set<Character>> map = new HashMap<>();
  30.     map.put('8', new HashSet<Character>());
  31.     map.get('8').add('T');
  32.     map.get('8').add('U');
  33.     map.get('8').add('V');
  34.     map.put('4', new HashSet<Character>());
  35.     map.get('4').add('G');
  36.     map.get('4').add('H');. visit 1point3acres for more.
  37.     map.get('4').add('I');

  38.     Set<String> dict = new HashSet<>();
  39.     dict.add("TH");
  40.     dict.add("T");
  41.     dict.add("TI");
  42.     dict.add("I");

  43.     List<List<String>> r = phone2words("84", 0, dict, map, new StringBuilder());
  44.     for (List<String> l : r) {
  45.       for (String s : l) {
  46.         System.out.print(s);
  47.         System.out.print(" ");. from: 1point3acres
  48.       }
  49.       System.out.println();
  50.     }. 一亩-三分-地,独家发布
  51.   }
  52. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-23 23:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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