周末读物之聊聊三观

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 6978|回复: 17
收起左侧

Facebook电面

[复制链接] |试试Instant~
我的人缘0
knight0clk 发表于 2016-10-22 22:07:08 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  91% (91)
 
 
9% (9)  踩

2016(10-12月) 码农类General 博士 实习@Facebook - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
第一次发帖,回报之前地里发帖子的各位xdjm,感觉面经很有用,虽然这次面,貌似不是重复的题目,至少能寻求心理安慰,但是和leetcode原题很像。.1point3acres网

第一题:给一个字符串 such as: "GoogleFacebookMicrosoft", 由字母构成,然后给一个字典,把给定的字符按照字典进行切割,然后输出分割后的一个解答,例如:dict=['Google', 'Facebook', 'Microsoft', 'GoogleFace', 'bookMicsoft']
如果有多个解答,输出一个即可,对于这个例子显然有两个解答,"Google Facebook Microsoft", "GoogleFace bookMicrosoft"。随便输出一个就行
我回答,递归可以做,然后给出了答案,分析了复杂度O(n^m)。这里复杂度分析卡了一下,不过还好

followup,有没有其他方法可以做?我说可以DP做,f[i] = True意味着0~i-1存在 matching,为了输出一个solution,用g[i+len(w)] = i记录结果,然后回溯方法可以输出一个答案。interviewer跑了个conner case比较满意。. 1point 3acres 论坛

大概就是这样。已经收到消息给了2面。

这里想说一下,对于某些人,如果发帖,就不要顾及NDA什么的,你模模糊糊说说题目,基本等于白说,多想想你看到的别人写的很好的帖子对你有多大的帮助。希望大家可以毫无保留,踊跃发帖,后续面试我会更新,谢谢各位。

评分

参与人数 6大米 +27 收起 理由
lee2009jian + 5 给你点个赞!
manmankan + 1 给你点个赞!
cytmike + 3 感谢分享!
cgq77 + 5 感谢分享!
Mark6 + 3 赞楼主!!!!
jisong_L + 10

查看全部评分


上一篇:snapchat oa
下一篇:Tapad新鲜oa

本帖被以下淘专辑推荐:

我的人缘0
iPhD 发表于 2016-10-23 03:02:23 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  87% (61)
 
 
12% (9)  踩
Badger96 发表于 2016-10-23 01:19. from: 1point3acres
刚才排版有点问题,再发一遍吧
第一问:
// find one possible way of breaking, backtracking:

你这个写得有点麻烦,我改写了下,其实就是word break 1:

public String wordBreak(String s, Set<String> dict) {
    if (s == null || s.isEmpty() || dict == null) {
        return "";
    }. 留学申请论坛-一亩三分地

    boolean[] dp = new boolean[s.length() + 1];
    String[] words = new String[s.length() + 1]; .留学论坛-一亩-三分地
    dp[0] = true;
    words[0] = "";

    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp = true;
                if (words[j].isEmpty()) {
                    words = s.substring(j, i);
                } else {
                    words = words[j] + " " + s.substring(j, i);
                }
            }. more info on 1point3acres
        }
    }

    if (dp[s.length()]) {
        return words[s.length()];
    } else {
        return "";
    }
}

其实面试官想要的应该就是这种解法,一开始递归那个方向完全想偏了,因为只要返回一组解,根本用不到word break 2的解法,那个复杂度太大了。

评分

参与人数 1大米 +5 收起 理由
lee2009jian + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
鼓頔娜夫 发表于 2016-11-13 00:41:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
100% (1)   【踩】
全局: 顶  80% (4)
 
 
20% (1)  踩
贴个follow up c++的代码:

string wordBreak(string s, unordered_set<string>& wordDict) { 来源一亩.三分地论坛.
  int n = s.size();
  vector<bool> dp(n+1, false);
  dp[0] = true;
  vector<int> parent(n+1, -1);
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < i; j++) {
      string w = s.substr(j, i - j);
      if (dp[j] && wordDict.find(w) != wordDict.end()) {. more info on 1point3acres
        dp[i] = true;
.本文原创自1point3acres论坛        parent[i] = j;
        break;
      }
    }
  }
  string result = "";
  int child = n;
  while (child > 0) {
    int p = parent[child];
    result = s.substr(p, child - p) + " " + result;
    child = p;
  }

  return result;
  
}
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-22 22:25:31 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  87% (61)
 
 
12% (9)  踩
多谢楼主分享!问下这题和LC上的word break有什么区别?

第一问如果只找出一个结果,是不是比word break 2要简单很多?也需要O(n^m)的解法吗?

第二问是不是先找出第一个匹配的substring(0, i),然后递归找剩下的substring(i)?是这个意思吗?不是回溯吧?
回复

使用道具 举报

我的人缘0
leixiang5 发表于 2016-10-22 22:41:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  82% (196)
 
 
17% (41)  踩
楼主的题目就是word break吧~。 顶楼主的comment。

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
wtcupup 发表于 2016-10-23 00:49:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  61% (347)
 
 
38% (215)  踩
恭喜,能贴下你follow-up的代码吗?没怎么看懂你说的
回复

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-23 01:17:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (165)
 
 
0% (0)  踩
wtcupup 发表于 2016-10-23 00:49
恭喜,能贴下你follow-up的代码吗?没怎么看懂你说的

码了一下,欢迎讨论和指正!
第一问:
  1. // find one possible way of breaking, backtracking:
  2. //O(dictWordLength^lengthOfString) time, O(lengthOfString) stack space
  3. public class Solution {
  4.     public String wordBreak(String s, Set<String> dict) {
  5.         List<String> res = new ArrayList<>();
  6.         if (s == null || s.length() == 0 || dict == null || dict.size() == 0) {
  7.         <span style="line-height: 1.5;">   </span><span style="line-height: 1.5;"> </span><span style="line-height: 1.5;">return res;</span>
复制代码
Follow up:
  1. //find whether there is a possible way of breaking, dp:
  2. //O(lengthOfString * maxLength) time, O(lengthOfString) space
  3. public class Solution {. 围观我们@1point 3 acres
  4.     public String wordBreak(String s, Set<String> dict) {
  5.     <span style="line-height: 1.5;">   </span><span style="line-height: 1.5;"> </span><span style="line-height: 1.5;">if (s == null || s.length() == 0) {</span>
复制代码
仅供参考,大家可以顺便帮忙看看复杂度之类的有没弄错,谢谢!


回复

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-23 01:19:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (165)
 
 
0% (0)  踩
刚才排版有点问题,再发一遍吧
第一问:.留学论坛-一亩-三分地
// find one possible way of breaking, backtracking:
//O(dictWordLength^lengthOfString) time, O(lengthOfString) stack space
public class Solution {
    public String wordBreak(String s, Set<String> dict) {
        List<String> res = new ArrayList<>();
-google 1point3acres        if (s == null || s.length() == 0 || dict == null || dict.size() == 0) {
            return res;
        }.留学论坛-一亩-三分地
        helper(res, s, dict, "", 0);
        return res;
    }

    private boolean helper(List<String> res, String s, Set<String> dict, String path, int index) {
        if (index == s.length()) {
            res.add(path.substring(1));. visit 1point3acres for more.
            return true;
        }
        for (int i = index + 1; i <= s.length(); i++) {
            String word = s.substring(index, i);
            if (dict.contains(word) && helper(res, s, dict, path + " " + word, i)) {//if one solution found, return true
                return true;
            }
        }
    }
}
Follow up:
//find whether there is a possible way of breaking, dp:
//O(lengthOfString * maxLength) time, O(lengthOfString) space. Waral 博客有更多文章,
public class Solution {
    public String wordBreak(String s, Set<String> dict) {. Waral 博客有更多文章,
        if (s == null || s.length() == 0) {.留学论坛-一亩-三分地
            return true;
        }
        int maxLength = getMaxLength(dict);
        boolean[] dp = new boolean[s.length() + 1];//dp:whether 0 to i part of string can be segmented into words in dict 来源一亩.三分地论坛.
        String[] words = new String[s.length() + 1];//words:a string of a possible way of segmenting s.substring(0, i)
        dp[0] = true;
        words[0] = "";
        for (int i = 1; i <= s.length(); i++) {//O(n) * O(maxLength). from: 1point3acres
            for (int lastWordLength = 1; lastWordLength <= maxLength && lastWordLength <= i; lastWordLength++) {
                if (dp[i - lastWordLength] && dict.contains(s.substring(i - lastWordLength, i))) {
                    dp = true;//if string from 0 to i-lastWordLength is segmentable, and i-lastWordLength to i is in dict
                    words = words[i - lastWordLength] + " " + s.substring(i - lastWordLength, i);-google 1point3acres
                    break;
                }
            }
        }
        return dp[s.length()] ? words[s.length()].substring(1) : "";//remember to check dp[s.length()] first !!!
    }

    private int getMaxLength(Set<String> dict) {
        int max = 0;
        for (String s : dict) {
            max = Math.max(max, s.length());
        }
        return max;
    }
}.留学论坛-一亩-三分地
仅供参考,大家可以顺便帮忙看看复杂度之类的有没弄错,谢谢!

补充内容 (2016-10-23 01:21):
修改一下第一问,res应该返回String,一开始写成List<String>了
回复

使用道具 举报

我的人缘0
萌萌软妹子 发表于 2016-10-23 04:40:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (42)
 
 
2% (1)  踩
哈哈哈楼主!同感 就是嘛 要分享面经就讲清楚嘛
回复

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-10-23 11:53:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (91)
 
 
9% (9)  踩
iPhD 发表于 2016-10-22 22:25. more info on 1point3acres
多谢楼主分享!问下这题和LC上的word break有什么区别?

第一问如果只找出一个结果,是不是比word break ...

看了下你说的题目,和word break区别就是要给出一组解,而不是True False。第一问我是递归算法,所以理论上就是O(n^m)。第二问是iterative 的DP算法,不是递归了,和回溯没关系
回复

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-10-23 12:02:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (91)
 
 
9% (9)  踩
wtcupup 发表于 2016-10-23 00:49. 围观我们@1point 3 acres
恭喜,能贴下你follow-up的代码吗?没怎么看懂你说的

意思很简单,就是说f[0] = True, ”Google“ is matched, 所以f[6]更新为True,同时更新g[6] = 0,这样你就能记录路径了,就是当前的状态是怎么过来的。“GoogleFacebookMicrosoft”,对于这个输入f[0] = True, f[6] = True, f[14]=True, f[22]=True, 同时g[0] =-1, g[6] = 0, g[14] = 6, g[22] = 14。你懂了吧?我一步步回溯,就可以通过G数组输出一个解答。楼下哥们给的代码基本正确,但是没必要记录string,只要记录关键节点就行,然后用input串去发现即可

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-10-23 12:03:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (91)
 
 
9% (9)  踩
Badger96 发表于 2016-10-23 01:19. more info on 1point3acres
刚才排版有点问题,再发一遍吧
第一问:
// find one possible way of breaking, backtracking:

代码基本正确,但是dp = true;//if string from 0 to i-lastWordLength is segmentable, and i-lastWordLength to i is in dict,这里index没写,后面words数组没必要记录string
回复

使用道具 举报

我的人缘0
lic10 发表于 2016-10-25 06:32:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
请问楼主,两次面试时间不是一次约好的吗?现在变成了过了一面才给二面了吗?
回复

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-10-30 05:28:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (91)
 
 
9% (9)  踩
lic10 发表于 2016-10-25 06:32. 一亩-三分-地,独家发布
请问楼主,两次面试时间不是一次约好的吗?现在变成了过了一面才给二面了吗?

现在的确是这样的政策
回复

使用道具 举报

我的人缘0
鼓頔娜夫 发表于 2016-11-12 23:27:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (4)
 
 
20% (1)  踩
赞最后的comment
回复

使用道具 举报

我的人缘0
xuzhikun 发表于 2016-11-23 13:46:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  78% (18)
 
 
21% (5)  踩

我也觉得,嘴里说着nda,还看别人面经收益的实在是不知道说啥好。。。
回复

使用道具 举报

我的人缘0
sherlockzzq 发表于 2017-10-5 07:14:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (76)
 
 
7% (6)  踩
请问这歌时间复杂度怎么分析啊
回复

使用道具 举报

我的人缘0
get_bits 发表于 2017-11-30 17:22:27 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  50% (3)
 
 
50% (3)  踩
mark一下 谢谢楼主
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-22 21:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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