一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3461|回复: 39
收起左侧

Facebook Oct Nov 3轮面试 经验

[复制链接] |试试Instant~ |关注本帖
Rythm 发表于 2016-11-5 06:22:48 | 显示全部楼层 |阅读模式

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

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

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

x
看了这么多地里的面经,我也贡献力量来了!
HR超级nice, 聊简历,带我逛facebook,请我吃冰淇淋。. 1point3acres.com/bbs
2017 Summer SDE Intern(非cs背景)

进入正题:
3 轮 (2onsite + 1phone, 两个中国小哥一个欧洲人 都超级nice)6 个题

1 BST to Double Linked List (in place)
2 Palindrome 修改
3 LCA . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
4 Move Zeros
5 First Bad Version. From 1point 3acres bbs
6 Shorest Path between 2 nodes in Graph
. Waral 鍗氬鏈夋洿澶氭枃绔,
等结果!求人品!
并且祝大家都能找到好工作!

爱大家!

M

评分

1

查看全部评分

Badger96 发表于 2016-11-5 13:58:42 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
其中一个方法是求出当前string和它的reversed string的LCS,然后用当前s.length()减去LCS长度就得出最少删除/插入字符的回文了,刚写完跑了下test cases应该没问题
public class Solution {
    private static int minRemovalPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
鏉ユ簮涓浜.涓夊垎鍦拌鍧.         int n = s.length();
        StringBuilder sb = new StringBuilder(s);
        String rev = sb.reverse().toString();
. Waral 鍗氬鏈夋洿澶氭枃绔,        return n - longestCommonSubsequence(s, rev, n, n);
    }

    private static int longestCommonSubsequence(String a, String b, int a_len, int b_len) {
        int[][] dp = new int[a_len + 1][b_len + 1];
        for (int i = 1; i <= a_len; i++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            for (int j = 1; j <= b_len; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                }
            }
        }
        return dp[a_len][b_len];
    }
}

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

Badger96 发表于 2016-11-5 14:20:41 | 显示全部楼层
关注一亩三分地微博:
Warald
wtcupup 发表于 2016-11-5 14:11
关键是楼主没说清楚edit string的规则, 能删除/插入string任意位置的char,还是只能删除/插入 tail or h ...

你可以试试看,我这个方法是通用的,比如输入abca,它会输出1而不会是3,若输出3那就成了只解决删头尾情况了

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-5 06:28:18 | 显示全部楼层
祝lz拿offer, 经常看到第1题,你可以贴个代码么。.鏈枃鍘熷垱鑷1point3acres璁哄潧
谢谢!
回复 支持 反对

使用道具 举报

 楼主| Rythm 发表于 2016-11-5 06:33:26 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-5 06:28
祝lz拿offer, 经常看到第1题,你可以贴个代码么。
谢谢!

def bstToDoublyList(self, root):
        # Write your code here.鐣欏璁哄潧-涓浜-涓夊垎鍦
        dfs = []. visit 1point3acres.com for more.
        self.getDfs(root, dfs)
        if len(dfs) == 0:
            return None-google 1point3acres
        head = None
        prev = None
        for val in dfs:
            node = DoublyListNode(val)
            if head is None:
                head = node. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            else:
                prev.next = node
            node.prev = prev
            prev = node
        return head
   
Sure!

def getDfs(self, root, dfs):
        if root is None:-google 1point3acres
            return
        self.getDfs(root.left, dfs). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        dfs.append(root.val)
        self.getDfs(root.right, dfs)
        

评分

1

查看全部评分

求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-5 06:35:15 | 显示全部楼层
Rythm 发表于 2016-11-5 06:33
def bstToDoublyList(self, root):.鏈枃鍘熷垱鑷1point3acres璁哄潧
        # Write your code here
        dfs = []

是circular的 linked list么?
你第6题怎么做的呢。
回复 支持 反对

使用道具 举报

 楼主| Rythm 发表于 2016-11-5 06:38:32 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-5 06:35. 1point 3acres 璁哄潧
是circular的 linked list么?
你第6题怎么做的呢。

不是circle, Inorder Traversal .鐣欏璁哄潧-涓浜-涓夊垎鍦

第6题我之前没遇见过,直接bfs了。构建queue,然后加一个临时path记录。 这题墨迹了很久。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-5 06:39:59 | 显示全部楼层
Rythm 发表于 2016-11-5 06:38
不是circle, Inorder Traversal . visit 1point3acres.com for more.

第6题我之前没遇见过,直接bfs了。构建queue,然后加一个临时path记 ...

你这题给的输入是什么呢?
回复 支持 反对

使用道具 举报

 楼主| Rythm 发表于 2016-11-5 06:48:13 来自手机 | 显示全部楼层
graph and nodes
回复 支持 反对

使用道具 举报

 楼主| Rythm 发表于 2016-11-5 06:49:45 来自手机 | 显示全部楼层
graph and nodes
回复 支持 反对

使用道具 举报

111180611 发表于 2016-11-5 06:56:47 | 显示全部楼层
最后一个题可以用heap做,需要建一个新的类
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-5 08:32:07 | 显示全部楼层
"Palindrome 修改" 是什么?
回复 支持 反对

使用道具 举报

cookielee77 发表于 2016-11-5 11:45:29 | 显示全部楼层
请问楼主是什么phd?
回复 支持 反对

使用道具 举报

 楼主| Rythm 发表于 2016-11-5 12:45:28 来自手机 | 显示全部楼层
做最小的修改把invalid 变成valid
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-5 12:54:43 | 显示全部楼层
Rythm 发表于 2016-11-5 12:45
做最小的修改把invalid 变成valid

请问是类似这道题吗? http://www.geeksforgeeks.org/dyn ... -form-a-palindrome/
回复 支持 反对

使用道具 举报

 楼主| Rythm 发表于 2016-11-5 12:57:38 来自手机 | 显示全部楼层
abbcc 去掉a        
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-5 13:07:18 | 显示全部楼层

去掉a之后bbcc并不是palindrome啊
回复 支持 反对

使用道具 举报

Badger96 发表于 2016-11-5 13:13:45 | 显示全部楼层
楼主用什么做的,面试官有要求dp解吗,还是bfs?
回复 支持 反对

使用道具 举报

 楼主| Rythm 发表于 2016-11-5 13:16:01 来自手机 | 显示全部楼层
acbbc 去掉a 写错了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| Rythm 发表于 2016-11-5 13:17:17 来自手机 | 显示全部楼层
Badger96 发表于 2016-11-5 13:13
楼主用什么做的,面试官有要求dp解吗,还是bfs?

dp可以做
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-5 13:20:06 | 显示全部楼层
Rythm 发表于 2016-11-5 13:16
acbbc 去掉a 写错了
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
能贴下 palindrome 修改 这道题的代码? 实在不知道需要哪些要求
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-26 07:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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