Fall 18 我的 HCI 申请复盘与策略总结

一亩三分地论坛

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

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 6689|回复: 17
收起左侧

Facebook电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
knight0clk 发表于 2016-10-22 22:07:08 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x
第一次发帖,回报之前地里发帖子的各位xdjm,感觉面经很有用,虽然这次面,貌似不是重复的题目,至少能寻求心理安慰,但是和leetcode原题很像。
. Waral 博客有更多文章,
第一题:给一个字符串 such as: "GoogleFacebookMicrosoft", 由字母构成,然后给一个字典,把给定的字符按照字典进行切割,然后输出分割后的一个解答,例如:dict=['Google', 'Facebook', 'Microsoft', 'GoogleFace', 'bookMicsoft']
如果有多个解答,输出一个即可,对于这个例子显然有两个解答,"Google Facebook Microsoft", "GoogleFace bookMicrosoft"。随便输出一个就行
我回答,递归可以做,然后给出了答案,分析了复杂度O(n^m)。这里复杂度分析卡了一下,不过还好
-google 1point3acres
followup,有没有其他方法可以做?我说可以DP做,f[i] = True意味着0~i-1存在 matching,为了输出一个solution,用g[i+len(w)] = i记录结果,然后回溯方法可以输出一个答案。interviewer跑了个conner case比较满意。

大概就是这样。已经收到消息给了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 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Badger96 发表于 2016-10-23 01:19
刚才排版有点问题,再发一遍吧
第一问:
// find one possible way of breaking, backtracking:

你这个写得有点麻烦,我改写了下,其实就是word break 1:. 1point 3acres 论坛

public String wordBreak(String s, Set<String> dict) {. 一亩-三分-地,独家发布
    if (s == null || s.isEmpty() || dict == null) {
        return "";-google 1point3acres
    }

    boolean[] dp = new boolean[s.length() + 1];
    String[] words = new String[s.length() + 1];
    dp[0] = true;
    words[0] = "";. from: 1point3acres

    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);-google 1point3acres
                } else {
                    words = words[j] + " " + s.substring(j, i);
                }
            }
        }
    }

    if (dp[s.length()]) {
        return words[s.length()];
    } else {.留学论坛-一亩-三分地
        return "";
    }. 留学申请论坛-一亩三分地
}

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

评分

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

查看全部评分

回复 支持 3 反对 0

使用道具 举报

我的人缘0
鼓頔娜夫 发表于 2016-11-13 00:41:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
贴个follow up c++的代码:. 留学申请论坛-一亩三分地

string wordBreak(string s, unordered_set<string>& wordDict) {.本文原创自1point3acres论坛
  int n = s.size();. 留学申请论坛-一亩三分地
  vector<bool> dp(n+1, false);. 围观我们@1point 3 acres
  dp[0] = true;
  vector<int> parent(n+1, -1);. 1point 3acres 论坛
  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()) {
        dp[i] = true;
        parent[i] = j;-google 1point3acres
        break;
      }.本文原创自1point3acres论坛
    }
  }
  string result = "";. from: 1point3acres
  int child = n;
  while (child > 0) {
    int p = parent[child];
    result = s.substr(p, child - p) + " " + result;
    child = p;
  }

  return result;
  
. 1point3acres}
回复 支持 0 反对 1

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-22 22:25:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
多谢楼主分享!问下这题和LC上的word break有什么区别?
. from: 1point3acres
第一问如果只找出一个结果,是不是比word break 2要简单很多?也需要O(n^m)的解法吗?

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

使用道具 举报

我的人缘0
leixiang5 发表于 2016-10-22 22:41:44 | 显示全部楼层
  此人我要顶:
 
22% (1) 【我投】
  此人我要踩:
 
78% (8) 【我投】
楼主的题目就是word break吧~。 顶楼主的comment。
回复 支持 反对

使用道具 举报

我的人缘0
wtcupup 发表于 2016-10-23 00:49:57 | 显示全部楼层
  此人我要顶:
 
11% (0) 【我投】
  此人我要踩:
 
89% (9) 【我投】
恭喜,能贴下你follow-up的代码吗?没怎么看懂你说的
回复 支持 反对

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-23 01:17:23 | 显示全部楼层
  此人我要顶:
 
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
    . Waral 博客有更多文章,
  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) {
  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>
复制代码
仅供参考,大家可以顺便帮忙看看复杂度之类的有没弄错,谢谢!. Waral 博客有更多文章,


回复 支持 反对

使用道具 举报

我的人缘0
Badger96 发表于 2016-10-23 01:19:23 | 显示全部楼层
  此人我要顶:
 
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<>();. From 1point 3acres bbs
        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++) {.1point3acres网
            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:.1point3acres网
//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) {
        if (s == null || s.length() == 0) {
            return true;
        }. Waral 博客有更多文章,
        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).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);
                    break;
                }
            }. Waral 博客有更多文章,
        }
        return dp[s.length()] ? words[s.length()].substring(1) : "";//remember to check dp[s.length()] first !!!
    }. 牛人云集,一亩三分地

    private int getMaxLength(Set<String> dict) {. Waral 博客有更多文章,
        int max = 0;
        for (String s : dict) {
            max = Math.max(max, s.length());. 留学申请论坛-一亩三分地
        }
        return max;
    }. From 1point 3acres bbs
}
仅供参考,大家可以顺便帮忙看看复杂度之类的有没弄错,谢谢!.1point3acres网

补充内容 (2016-10-23 01:21):
修改一下第一问,res应该返回String,一开始写成List<String>了
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-10-23 11:53:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
iPhD 发表于 2016-10-22 22:25
. 牛人云集,一亩三分地多谢楼主分享!问下这题和LC上的word break有什么区别?
. more info on 1point3acres
第一问如果只找出一个结果,是不是比word break ...

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

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-10-23 12:02:22 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
wtcupup 发表于 2016-10-23 00:49. 1point3acres
恭喜,能贴下你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串去发现即可
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| knight0clk 发表于 2016-10-23 12:03:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Badger96 发表于 2016-10-23 01:19
刚才排版有点问题,再发一遍吧. From 1point 3acres bbs
第一问:
// 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
 楼主| knight0clk 发表于 2016-10-30 05:28:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
lic10 发表于 2016-10-25 06:32
请问楼主,两次面试时间不是一次约好的吗?现在变成了过了一面才给二面了吗?

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

使用道具 举报

我的人缘0
鼓頔娜夫 发表于 2016-11-12 23:27:29 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
赞最后的comment
回复 支持 反对

使用道具 举报

我的人缘0
xuzhikun 发表于 2016-11-23 13:46:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

使用道具 举报

我的人缘0
sherlockzzq 发表于 2017-10-5 07:14:44 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
请问这歌时间复杂度怎么分析啊
回复 支持 反对

使用道具 举报

我的人缘0
get_bits 发表于 2017-11-30 17:22:27 来自手机 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
mark一下 谢谢楼主
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-20 19:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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