一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1842|回复: 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,请我吃冰淇淋。
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
6 Shorest Path between 2 nodes in Graph

等结果!求人品!. from: 1point3acres.com/bbs
并且祝大家都能找到好工作!

爱大家!

M

评分

1

查看全部评分

Badger96 发表于 2016-11-5 13:58:42 | 显示全部楼层
其中一个方法是求出当前string和它的reversed string的LCS,然后用当前s.length()减去LCS长度就得出最少删除/插入字符的回文了,刚写完跑了下test cases应该没问题.鐣欏璁哄潧-涓浜-涓夊垎鍦
public class Solution {. visit 1point3acres.com for more.
    private static int minRemovalPalindrome(String s) {. 鍥磋鎴戜滑@1point 3 acres
        if (s == null || s.length() == 0) {. 1point3acres.com/bbs
            return 0;
        }
. visit 1point3acres.com for more.        int n = s.length();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        StringBuilder sb = new StringBuilder(s);
        String rev = sb.reverse().toString();
        return n - longestCommonSubsequence(s, rev, n, n);
    }. 1point 3acres 璁哄潧

    private static int longestCommonSubsequence(String a, String b, int a_len, int b_len) {
        int[][] dp = new int[a_len + 1][b_len + 1];
. 鍥磋鎴戜滑@1point 3 acres        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]);
                }
            }
        }. 1point3acres.com/bbs
        return dp[a_len][b_len];
    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}
回复 支持 1 反对 0

使用道具 举报

Badger96 发表于 2016-11-5 14:20:41 | 显示全部楼层
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题,你可以贴个代码么。
谢谢!
回复 支持 反对

使用道具 举报

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

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

def getDfs(self, root, dfs):
        if root is None:
            return
        self.getDfs(root.left, dfs)
        dfs.append(root.val)-google 1point3acres
        self.getDfs(root.right, dfs)
        

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-5 06:35:15 | 显示全部楼层
Rythm 发表于 2016-11-5 06:33.1point3acres缃
def bstToDoublyList(self, root):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        # Write your code here
        dfs = []

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

使用道具 举报

 楼主| Rythm 发表于 2016-11-5 06:38:32 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-5 06:35
是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

第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 | 显示全部楼层
.鏈枃鍘熷垱鑷1point3acres璁哄潧
去掉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, 2016-12-8 03:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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