一亩三分地论坛

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

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

处女面Facebook I跪经总结

[复制链接] |试试Instant~ |关注本帖
芥末青豆 发表于 2016-2-20 15:55:00 | 显示全部楼层 |阅读模式

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

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

x
2.19日下午三点Facebook一面跪经总结
可怜兮兮地只做了一道题:.鏈枃鍘熷垱鑷1point3acres璁哄潧
input: a string (eg. "cat")
input: a map (eg. c -> [c, C, %], a -> [a, A, *], t -> [t, T, &])
output all the combination: cat, Cat, %at, ......

-google 1point3acres
狠狠简单的一道题,楼主吭吭哧哧写完,小哥让我手动跑程序,就是输入和固定字符串,在代码每一行写下来当前结果……然后楼主写到一半发现了bug,然后火速改掉。
楼主心心念念想多做题啊,小哥让我优化,果断不是最优解,然后又吭吭哧哧优化……剩十五分钟了,我说快我们来做下一题! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
小哥说可我还想follow up 的问问题啊,然后问了我一个特别脑残的问题,说如果输入字符串长度是N, map的value里的那个长度是M,有多少不同的子串输出……我说是MN,他还让我解释……
然后就让我问问题了,根本不想问!!但是还是很感兴趣的问他在Facebook工作的感受啊,做过最有意思的project啊,并不断捧哏……
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
.鐣欏璁哄潧-涓浜-涓夊垎鍦
已跪,勿念。
PS:听名字是印度小哥,但是根本听不出来口音,对我也特别照顾,我写代码的时候不断bgm般的捧哏:"good job!""nice!""very close!", 感激不尽。
. visit 1point3acres.com for more.

楼主写于2016.2.19


补充内容 (2016-2-24 06:10):
昨天收到了hr的回复,第一轮面试果然挂了,但是值得安慰的是hr说在fall-fulltime的时候让我再联系她,也就是并没有冷冻一年,坏消息中的好消息吧。
谢谢大家,楼主会继续努力的:)

评分

3

查看全部评分

iammajian 发表于 2016-2-21 05:12:07 | 显示全部楼层
写了个iterative版本,改编自leetcode的phone那题。。不知道有什么iterative版本可以边修改result边打印的
  1.     public static void printAllCombinations(String str, Map<Character, char[]> map) {
  2.         List<String> result = new ArrayList<String>();
  3.         if (str.length() == 0) {
  4.                 System.out.print("");
  5.         }
  6.         result.add("");. 1point 3acres 璁哄潧
  7.         for (int i = 0; i < str.length(); i++) {
  8.                 result = merge(map.get(str.charAt(i)), result);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.         }
  10.        System.out.println(result);
  11.     }. from: 1point3acres.com/bbs
  12.    
  13.     public static List<String> merge(char[] chars, List<String> list) {
  14.         List<String> result = new ArrayList<String>();
  15.         for (int i = 0; i < chars.length; i++) {
  16.             for (String str : list) {
  17.                 result.add(str + chars[i]);
  18.             }
  19.         }
  20.         return result;
  21.     }
复制代码
回复 支持 2 反对 0

使用道具 举报

jinlan940713 发表于 2016-2-20 15:59:45 | 显示全部楼层
雷雷姐肯定中!
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-2-20 16:10:45 | 显示全部楼层
%*& 算是一个解吗?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-20 16:14:27 | 显示全部楼层
lz有点萌阿。你用啥方法做的。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-20 16:43:35 | 显示全部楼层
  1.         public static Set<String> FB_PracticeCombnationWordsFromMap(String input, Map<Character,char[]> stringMap)
  2.         {
  3.                 Set<String> results = new HashSet<String>();
  4.                 FB_PracticeCombnationWordsFromMap_Helper(input,input,stringMap,0,results);
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5.                 return results;
  6.         }
  7.        
  8.         public static void FB_PracticeCombnationWordsFromMap_Helper(String input,String sb,Map<Character,char[]> stringMap,int index,Set<String> results)
  9.         {
  10.                 for(int i = index;i < input.length();i++)
  11.                 {. Waral 鍗氬鏈夋洿澶氭枃绔,
  12.                         for(char temp: stringMap.get(input.charAt(i)))
  13.                         {. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.                                 StringBuilder stringSB= new StringBuilder(sb);
  15.                                 stringSB.setCharAt(i, temp);
  16.                                 results.add(stringSB.toString());
  17.                                 FB_PracticeCombnationWordsFromMap_Helper(input,stringSB.toString(),stringMap,index+1,results);       
  18.                         }
  19.                 }
  20.         }
复制代码


写了大概15分钟,不知道对不对。应该还可以优化。
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-20 16:45:50 | 显示全部楼层
决定每天都写完facebook面经。
希望能感动facebook爸爸,给我各面试。
回复 支持 反对

使用道具 举报

justvincent 发表于 2016-2-20 22:59:09 | 显示全部楼层
如果没算错的话,应该是M的N次方种情况
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-2-20 23:28:18 来自手机 | 显示全部楼层
这题感觉只能用回溯做啊。。怎么优化?
回复 支持 反对

使用道具 举报

beer 发表于 2016-2-21 00:04:09 | 显示全部楼层
感觉是用DFS吧
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-2-21 01:27:48 | 显示全部楼层
不是M^N吗,复杂度还能更低吗,毕竟至少要遍历每个输出
回复 支持 反对

使用道具 举报

 楼主| 芥末青豆 发表于 2016-2-21 03:33:24 | 显示全部楼层
楼主二逼了,解释过程是M^N,最后说是MN
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-21 03:51:45 | 显示全部楼层
芥末青豆 发表于 2016-2-21 03:33
楼主二逼了,解释过程是M^N,最后说是MN

你写的iterative的方法么?
求教
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-21 06:02:40 | 显示全部楼层
iammajian 发表于 2016-2-21 05:12
写了个iterative版本,改编自leetcode的phone那题。。不知道有什么iterative版本可以边修改result边打印的. from: 1point3acres.com/bbs
...

time complexity?
回复 支持 反对

使用道具 举报

TMAC135 发表于 2016-2-21 06:13:00 | 显示全部楼层
跟pemutation 的iterative的解法类似啊,遍历字符串的时候然后每次加一个
回复 支持 反对

使用道具 举报

iammajian 发表于 2016-2-21 06:39:40 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-2-21 06:02.鏈枃鍘熷垱鑷1point3acres璁哄潧
time complexity?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
跟上面的一样k^n
回复 支持 反对

使用道具 举报

 楼主| 芥末青豆 发表于 2016-2-24 06:26:17 | 显示全部楼层

can you be more specific?
回复 支持 反对

使用道具 举报

beer 发表于 2016-2-24 07:46:35 | 显示全部楼层
芥末青豆 发表于 2016-2-24 06:26. 1point3acres.com/bbs
can you be more specific?

把map类比成tree的level,也就是[c, C, %]第一层,[a, A, *]第二层.....鏈枃鍘熷垱鑷1point3acres璁哄潧
然后就是DFS搜索这个tree,end condition就是到达leaf的时候。
这题和phone number那题很像唉, https://leetcode.com/problems/le ... -of-a-phone-number/
回复 支持 反对

使用道具 举报

 楼主| 芥末青豆 发表于 2016-2-24 08:54:43 | 显示全部楼层
beer 发表于 2016-2-24 07:46
把map类比成tree的level,也就是[c, C, %]第一层,[a, A, *]第二层.....1point3acres缃
然后就是DFS搜索这个tree,end c ...

题刷的不熟没有变通的能力……楼主哭去了,谢谢回复~
回复 支持 反对

使用道具 举报

 楼主| 芥末青豆 发表于 2016-2-25 04:11:02 | 显示全部楼层
iammajian 发表于 2016-2-21 05:12
写了个iterative版本,改编自leetcode的phone那题。。不知道有什么iterative版本可以边修改result边打印的
...
. more info on 1point3acres.com
层主写得好!资辞!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 00:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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