一亩三分地论坛

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

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

Facebook电面

[复制链接] |试试Instant~ |关注本帖
knight0clk 发表于 2016-10-22 22:07:08 | 显示全部楼层 |阅读模式

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

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

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

x
第一次发帖,回报之前地里发帖子的各位xdjm,感觉面经很有用,虽然这次面,貌似不是重复的题目,至少能寻求心理安慰,但是和leetcode原题很像。. Waral 鍗氬鏈夋洿澶氭枃绔,

第一题:给一个字符串 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比较满意。. Waral 鍗氬鏈夋洿澶氭枃绔,

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

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

评分

4

查看全部评分

iPhD 发表于 2016-10-22 22:25:31 | 显示全部楼层
多谢楼主分享!问下这题和LC上的word break有什么区别?

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

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

使用道具 举报

iPhD 发表于 2016-10-23 03:02:23 | 显示全部楼层
Badger96 发表于 2016-10-23 01:19
刚才排版有点问题,再发一遍吧. 1point3acres.com/bbs
第一问:
// find one possible way of breaking, backtracking:

你这个写得有点麻烦,我改写了下,其实就是word break 1:
. 鍥磋鎴戜滑@1point 3 acres
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]; . 1point3acres.com/bbs
    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);
                }
            }
        }
    }

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

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

使用道具 举报

leixiang5 发表于 2016-10-22 22:41:44 | 显示全部楼层
楼主的题目就是word break吧~。 顶楼主的comment。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-23 00:49:57 | 显示全部楼层
恭喜,能贴下你follow-up的代码吗?没怎么看懂你说的
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-10-23 01:17:23 | 显示全部楼层
wtcupup 发表于 2016-10-23 00:49
恭喜,能贴下你follow-up的代码吗?没怎么看懂你说的
. 鍥磋鎴戜滑@1point 3 acres
码了一下,欢迎讨论和指正!
第一问:
  1. // find one possible way of breaking, backtracking:. visit 1point3acres.com for more.
  2. //O(dictWordLength^lengthOfString) time, O(lengthOfString) stack space. 1point3acres.com/bbs
  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 {
  4.     public String wordBreak(String s, Set<String> dict) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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>
复制代码
仅供参考,大家可以顺便帮忙看看复杂度之类的有没弄错,谢谢!.鐣欏璁哄潧-涓浜-涓夊垎鍦


回复 支持 反对

使用道具 举报

Badger96 发表于 2016-10-23 01:19:23 | 显示全部楼层
刚才排版有点问题,再发一遍吧
第一问:
// find one possible way of breaking, backtracking:
//O(dictWordLength^lengthOfString) time, O(lengthOfString) stack space.鏈枃鍘熷垱鑷1point3acres璁哄潧
public class Solution {
    public String wordBreak(String s, Set<String> dict) {
        List<String> res = new ArrayList<>();
        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));
            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. more info on 1point3acres.com
                return true;
            }
        }
    }
}
Follow up:
//find whether there is a possible way of breaking, dp:
//O(lengthOfString * maxLength) time, O(lengthOfString) space
public class Solution {
    public String wordBreak(String s, Set<String> dict) {. from: 1point3acres.com/bbs
        if (s == null || s.length() == 0) {
            return true;
        }-google 1point3acres
        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). more info on 1point3acres.com
            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);
                    break;
                }
            }.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }
        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());
        }. more info on 1point3acres.com
        return max;
    }
}
仅供参考,大家可以顺便帮忙看看复杂度之类的有没弄错,谢谢!

补充内容 (2016-10-23 01:21):. 1point3acres.com/bbs
修改一下第一问,res应该返回String,一开始写成List<String>了
回复 支持 反对

使用道具 举报

萌萌软妹子 发表于 2016-10-23 04:40:33 | 显示全部楼层
哈哈哈楼主!同感 就是嘛 要分享面经就讲清楚嘛
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-10-23 11:53:59 | 显示全部楼层
iPhD 发表于 2016-10-22 22:25
多谢楼主分享!问下这题和LC上的word break有什么区别?

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

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

使用道具 举报

 楼主| knight0clk 发表于 2016-10-23 12:02:22 | 显示全部楼层
wtcupup 发表于 2016-10-23 00:49
恭喜,能贴下你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串去发现即可
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-10-23 12:03:47 | 显示全部楼层
Badger96 发表于 2016-10-23 01:19
刚才排版有点问题,再发一遍吧. 鍥磋鎴戜滑@1point 3 acres
第一问:
// 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
回复 支持 反对

使用道具 举报

lic10 发表于 2016-10-25 06:32:31 | 显示全部楼层
请问楼主,两次面试时间不是一次约好的吗?现在变成了过了一面才给二面了吗?
回复 支持 反对

使用道具 举报

 楼主| knight0clk 发表于 2016-10-30 05:28:47 | 显示全部楼层
lic10 发表于 2016-10-25 06:32
请问楼主,两次面试时间不是一次约好的吗?现在变成了过了一面才给二面了吗?

现在的确是这样的政策
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-12 23:27:29 | 显示全部楼层
赞最后的comment
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-13 00:41:24 | 显示全部楼层
贴个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++) {.1point3acres缃
      string w = s.substr(j, i - j);
      if (dp[j] && wordDict.find(w) != wordDict.end()) {
        dp[i] = true;
        parent[i] = j;
        break;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
      }
    }. 鍥磋鎴戜滑@1point 3 acres
  }
  string result = "";
  int child = n;
  while (child > 0) {
. 鍥磋鎴戜滑@1point 3 acres    int p = parent[child];
    result = s.substr(p, child - p) + " " + result;
    child = p;
  }

. 鍥磋鎴戜滑@1point 3 acres  return result;
  
}
回复 支持 反对

使用道具 举报

xuzhikun 发表于 2016-11-23 13:46:30 | 显示全部楼层

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 12:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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