• Facebook onsite 面经汇总 1

    November 30, 2016 Author: david
    No comment yet

    2013(10-12月) 码农类 硕士 实习@Facebook – 校园招聘会 – Onsite 校园招聘会 |Pass

    实际上我FB的offer2个多月前就拿了, 当时一直想发个帖分享经验, 但是当时竟然没有发现面经版… .

    闲话少说, 当时facebook网申和career fair都投过简历, 后来在career fair一周后收到了on-campus面试通知。入围面试的人实际上并不是很多, 我觉得我能被选中是因为我在career fair上和一个FB的员工聊了一下以前做的项目, 他似乎也对我说的挺感兴趣, 再加上简历也写得不错, 所以我就荣幸地入围面试了吧。所以说, career fair大家还是要重视的, 不要草草地扔了简历就了事, 要尽可能地和展台上的员工沟通一下。

    当时on-campus面试是我来美帝的第一面, 觉得特别紧张。他问的题是Dynamic Programming中最经典的问题coin change, 就是给定一个面额(比如100), 以及一些不同面额的硬币(2,3,5), 求所有的硬币组合, 使得他们的面额之和为100. 当时我还不懂DP, 所以就只提供了一个brute-force的解法, 就是假设100 = 2i+ 3j +5k, 先遍历所有的j和k, 然后看剩下的100-3j-5k是不是偶数。正确的解法应该是用DP, 大家可以去google一下, 结果很多。当时是一个45分钟的面试, 按理说应该要做两道题, 我却只做了一道, 当时觉得估计跪了, 不过老天保佑, 我竟然又庆幸地进入了on-site面试。

    on-site面试题觉得更简单, 有两道题, 不过我现在就记得后一道了。问的就是给你一个字符串的list, 把它们重新排序一下, 使得互为anagram的词放在一块。对于anagram的题, 一般情况下只要把所有字符串按字母表顺序重新排列一下就成了, 这题也不例外, 如果是Java写的话, 只用自己写一个判断两个词是否为anagram的comparator就行了。

    on-site之后的第四天我就收到了offer，能在那么早的时候收到facebook这么好的offer, 我只能说我这肯定是我上半辈子积下的德。facebook是一个效率超高的公司, 从我第一轮面试到最终收到offer, 只花了不到一个月的时间, 非常符合它的”Move fast and Break things”的理念。并且从面试过程中, 我能感觉到facebook的员工之间的交流成本肯定很低, 所有的邮件都是简洁到极致, 不像我面Google的时候邮件里面各种rules, tips写一大堆(作为一个被Google拒的人, 我觉得我没有资格黑它..)。

    另外, 我觉得面试的时候要注意以下两个方面:
    1) 多和面试官沟通, 边写代码的时候边说自己的想法, 不要只自顾自地写代码而把面试官晾在一边。说完想法的时候, 问一下:”Does it make sense to you?”,

    [Read More...]

  • Leetcode – Maximal Rectangle solution 1 (Java)

    July 5, 2016 Author: david
    No comment yet

    Maximum Rectangle area for a 0 1 matrix.

    Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

    Source: https://leetcode.com/problems/maximal-rectangle/
     
    This is a hard one from Facebook.
     
    The key to solve this problem is to first build a matrix ones[][], where ones[i][j] means the number of continuous 1s to the cell matrix[i][j] in jth column. See the following figure. 
     
     
     leetcode maximal rectangle
     
     
    We have:

    We can fill up the matrix ones[][] using dynamic programming. The formula is :

    How to use the ones[][] matrix to calculate the maximum area?

    [Read More...]

  • Leetcode – Word Ladder solution In Java

    July 4, 2016 Author: david
    No comment yet
    leetcode word ladder

    Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time and each intermediate word must exist in the dictionary. For example, given:

    One shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, the program should return its length 5.

    Analysis

    From each word, we can change its letter one by one, thus a bread first search tree is constructed. The problem becomes to find the shortest path from the start word to the end word.

    [Read More...]

  • Leetcode – Paint House II solution (Java)

    July 4, 2016 Author: david
    No comment yet

    There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different.

    You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by a n x k cost matrix.

    For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2,

    [Read More...]

  • Leetcode – Meeting Rooms II (Java)

    July 4, 2016 Author: david
    No comment yet

    Meeting Rooms II
    Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

    For example, Given [[0, 30],[5, 10],[15, 20]], return 2.

    This is a follow up question for the Meeting Rooms one. 

    Analysis

    This problem can be solved using the greedy method. We sort the intervals using the start time, then we try to merge the next one that has the smallest start time ts from the remaining intervals with the previous interval that has smallest end time te. 

    [Read More...]

  • LeetCode – Excel Sheet Column Title solution in Java

    July 4, 2016 Author: david
    No comment yet

    Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example:

    1 -> A
    2 -> B
    3 -> C
    …
    26 -> Z
    27 -> AA
    28 -> AB

    To convert a number from a system with base m to Decimal number system, we can use the following formula:

    xyz = x * m^2 + y * m^1 + z * m^0.

    For instance, the binary number 1010 = 1 * 2^3 + 1 * 2^1 = 10. 

    Now to convert a number N in decimal system to a system with base m,

    [Read More...]

  • Leetcode – paint house I solution (Java)

    July 4, 2016 Author: david
    No comment yet

    Paint House I
    There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

    The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green,

    [Read More...]

  • Leetcode – Graph valid tree solution based on Union find set

    July 4, 2016 Author: david
    No comment yet

    Graph Valid Tree
    Given n nodes labeled from 0 to n – 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

    For example:

    Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

    Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

    Hint:

    Given n = 5 and edges = [[0, 1], [1, 2],

    [Read More...]

  • Leetcode – Meeting rooms solution in Java

    July 4, 2016 Author: david
    No comment yet

    Meeting Rooms
    Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), determine if a person could attend all meetings.

    For example, Given [[0, 30],[5, 10],[15, 20]], return false.

    Analysis

    We can sort the intervals using the start time. Then we check whether there is conflict.  For instance. for this two pairs,  [0, 30],[5, 10] As 5 is smaller than 30, the person cannot attend both. 

    When we do the check, we should record the latest end time before the current interval. For current interval,

    [Read More...]