一亩三分地论坛

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

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

Facebook电面两轮

[复制链接] |试试Instant~ |关注本帖
ohyline 发表于 2016-1-26 08:56:45 | 显示全部楼层 |阅读模式

2016(1-3月) 工程类 博士 实习@Facebook - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
五分钟前面完的Facebook二面, 在这个找intern已经如大海捞针的季节 Lz还是各种拖啊拖,到了这份田地。。。感觉不管面怎样,挂的机率不是一般的高啊高啊高啊。。。汇报地里,这里简单描述一下一面二面的过程。攒攒人品,希望上天给个offer
. 1point3acres.com/bbs
一面:印度小哥(无耐心+hard follow up)
第一题: subarray sum target. return true or false(exist or not)... all elements are positive
leetcode minimum subarray sum 变形。 两个pointer sliding window 秒之。 之后问了复杂度O(n) no excuse. 有个边界小bug被指出。。。哭了这会儿。。。-google 1point3acres
第二题:把第一题extend到2D。给一个matrix, all elements are positive,问有没有个sub rectangle加起来和等于target。return true/false。
Lz听到题目有点懵,认真调整心态,解决之。先写了个cumulative sum。把所有从0,0 到i,j的和算在新的matrix的i,j上。方便之后算head到tail的sub rectangle的和。这一步O(n^2)。。。
之后Lz就开始纠结怎么移动2D的sliding window。一看时间不多了,没有耐心的阿三就开始催催催。。。。实在没办法只写了BruteForce。。。哭again。。。。
写出来最后O(n^4)...丢脸
. more info on 1point3acres.com
一面过后一直觉得要挂了。。。。过了一个周末收到二面通知。。。可能都会有二面吧。。。反正最后应该是综合来看。。。虽说过了一面也不抱什么希望了。。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

二面:ABC小哥(表面Nice不知心里如何。。。)
互相自我介绍15分钟,编程25分钟,5分钟聊天
第一题:PowerSet.
一听题目吓尿了。后来一看就是个Subset,LC原题。讲算法5分钟,coding5分钟秒之。整个过程我觉得他貌似不是很懂Backtracking algorithm。。。还是他在装傻啊。。。真心confusing。
之后发生的事情就震惊了。。。小哥非让我一步一步写出如下的iteration。。。他给了第一行。。。剩下的我一点点写。。。这个真心浪费时间啊,而且密密麻麻的很容易看错打错。。。哭again
// powerset([1, 2, 3])
// bt([1, 2, 3], [], [], 0).鏈枃鍘熷垱鑷1point3acres璁哄潧
//   bt([1, 2, 3], [[]], [1], 1)
//     bt([1, 2, 3], [[],[1]], [1,2], 2)
//       bt([1, 2, 3], [[],[1],[1,2]], [1,2,3], 3)
//     bt([1, 2, 3], [[],[1],[1,2],[1,2,3]],[1,3],3)
//   bt([1, 2, 3], [[],[1],[1,2],[1,2,3],[1,3]],[2],2)
//   bt([1, 2, 3], [[],[1],[1,2],[1,2,3],[1,3],[2]],[2,3],3)
//   bt([1, 2, 3], [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3]],[3],3).1point3acres缃


这个写完已经20分钟过去了。。。就剩5分钟做第二题了
第二题:merge K sorted array。。。
怎能如此简单。。。却不让写code。。。说了merge sort的思想。。。两两merge, recursive搞定。。。但是偏偏不让写code。。。这是在整我们。我心里住着的码农真是急坏了。。。
人家是考官,只好听从命令了。。。哭again
. 鍥磋鎴戜滑@1point 3 acres
最后问了问还有没有intern position之类他绝对不能回答的问题就结束了。

估计Facebook家的面试就这样告终了。。。在错误的时间遇到了错误的题目们和面试官们。。。
希望大家一切顺利。。。都有好的归宿。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

2

查看全部评分

本帖被以下淘专辑推荐:

kinggarden2001 发表于 2016-2-16 14:38:14 | 显示全部楼层
第一面第二题n^3应该是最好的解法 楼主算累加其实已经成功一半了 任取两行按一维的算法sliding 就可以 因为子矩阵的和 o(1)就能算出来
回复 支持 4 反对 0

使用道具 举报

ppuliu 发表于 2016-1-26 10:17:01 | 显示全部楼层
多谢楼主分享,一面第二题我只找到一个n^3的解法,不知道有没有更好的方法。贴下代码
def checkSubArraySum(s, nums):

    if len(nums)==0:
        return 0. visit 1point3acres.com for more.

    i=0. 鍥磋鎴戜滑@1point 3 acres

    curr=0
    for j in xrange(len(nums)):
        curr+=nums[j]
        while curr>s:. more info on 1point3acres.com
            curr-=nums[i]
            i+=1
        if curr==s:
            return True

    return False

def checkSubMatrix(target,matrix):

    if matrix==None or len(matrix)==0:
        return False
    m=len(matrix). Waral 鍗氬鏈夋洿澶氭枃绔,
    n=len(matrix[0])

    for left in xrange(n):. visit 1point3acres.com for more.
. Waral 鍗氬鏈夋洿澶氭枃绔,
        temp=[0]*m
        for right in xrange(left,n):
            for i in xrange(m):
                temp[i]+=matrix[i][right]

            if checkSubArraySum(target,temp):
                return True
. from: 1point3acres.com/bbs     return False
回复 支持 2 反对 0

使用道具 举报

echoruiko 发表于 2016-2-14 16:51:47 | 显示全部楼层
ppuliu 发表于 2016-1-26 10:17
多谢楼主分享,一面第二题我只找到一个n^3的解法,不知道有没有更好的方法。贴下代码
def checkSubArraySu ...

求问, checkArraySum本身就有O(m)的复杂度,checkSubMatrix的三层循环里面调用这个checkArraySum的话不是总共O(n^4)吗?
回复 支持 反对

使用道具 举报

Jester_Z 发表于 2016-2-15 00:48:00 | 显示全部楼层
echoruiko 发表于 2016-2-14 16:51. 1point3acres.com/bbs
求问, checkArraySum本身就有O(m)的复杂度,checkSubMatrix的三层循环里面调用这个checkArraySum的话不是 ...
. from: 1point3acres.com/bbs
for i in xrange(m):
    temp+=matrix[right]

if checkSubArraySum(target,temp):
    return True
这俩是平行的  所以是N*N*(N+N)
回复 支持 反对

使用道具 举报

lyburke 发表于 2016-2-16 12:33:21 | 显示全部楼层
这道题和Maximum Sum Rectangle in 2D Matrix是不是有点像。。。最后从n^4优化到n^3
回复 支持 反对

使用道具 举报

 楼主| ohyline 发表于 2016-2-16 12:34:56 | 显示全部楼层
lyburke 发表于 2016-2-16 12:33
这道题和Maximum Sum Rectangle in 2D Matrix是不是有点像。。。最后从n^4优化到n^3

是的 用dp优化到n^3
回复 支持 反对

使用道具 举报

lyburke 发表于 2016-2-16 12:41:22 | 显示全部楼层
ohyline 发表于 2016-2-16 12:34
是的 用dp优化到n^3

冒昧问一句LZ二面过了吗
回复 支持 反对

使用道具 举报

 楼主| ohyline 发表于 2016-2-16 12:42:53 | 显示全部楼层
lyburke 发表于 2016-2-16 12:41
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 冒昧问一句LZ二面过了吗
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
可能一面不好 加面了3面 已进pool一周多。。。在match
回复 支持 反对

使用道具 举报

echoruiko 发表于 2016-2-17 07:31:01 | 显示全部楼层
Jester_Z 发表于 2016-2-15 00:48. visit 1point3acres.com for more.
for i in xrange(m):
    temp+=matrix[right]

啊, 是哦~!觉得自己好蠢😂
回复 支持 反对

使用道具 举报

eko910817 发表于 2016-2-17 09:21:45 | 显示全部楼层
请问Lz是因为phd所以要match吗?还是所有intern都要match上才有offer?
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-18 08:49:21 | 显示全部楼层
ohyline 发表于 2016-2-16 12:42
可能一面不好 加面了3面 已进pool一周多。。。在match
-google 1point3acres
FB不是都直接发offer吗为啥会match呢。。
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-18 09:02:50 | 显示全部楼层
ppuliu 发表于 2016-1-26 10:17
多谢楼主分享,一面第二题我只找到一个n^3的解法,不知道有没有更好的方法。贴下代码
def checkSubArraySu ...

可以像range sum query一样先把sum都算出来,complexity就是O(n^2), 然后在那个sum的matrix上用两个for循环把所有range 的query全查一遍看是不是有等于target的,这两个for循环也是O(n^2),总的complexity也是O(n^2)。对吗?. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不过这么做感觉并没有像1D的情况下利用到全是正数的这个信息,感觉还能优化。。。可是在移动窗口两个角的时候并无法决定是往左移还是往下移
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-2-28 14:28:54 | 显示全部楼层
第一面第二题那个2d matrix其实lintcode上有类似的 http://www.lintcode.com/en/problem/submatrix-sum/#
回复 支持 反对

使用道具 举报

sjph 发表于 2016-8-2 19:44:51 | 显示全部楼层
第一面第二题的2d matrix,大家谁有code可以分享一下吗,刚才试着实现,还是问题不断。。。多谢了!
回复 支持 反对

使用道具 举报

ShutingChen 发表于 2016-8-8 03:20:45 | 显示全部楼层
心理住着是码农真是极坏了。。。
回复 支持 反对

使用道具 举报

jiya 发表于 2016-9-4 07:44:21 | 显示全部楼层
  1. public class Solution {
  2.     /**
  3.      * @param matrix an integer matrix
  4.      * [url=home.php?mod=space&uid=160137]@return[/url] the coordinate of the left-up and right-down number
  5.      */
  6.     public int[][] submatrixSum(int[][] matrix) {
  7.         int[][] res = new int[][] {{0, 0}, {0, 0}};
  8.         if (matrix != null && matrix.length > 0) {
  9.             for (int i = 0; i < matrix.length; i++) {
  10.                 for (int j = 0; j < matrix[0].length; j++) {
  11.                     matrix[i][j] += (i - 1 >= 0 ? matrix[i - 1][j] : 0) + (j - 1 >= 0 ? matrix[i][j - 1] : 0) - (i - 1 >= 0 && j - 1 >= 0 ? matrix[i - 1][j - 1] : 0);
  12.                 }
  13.             }
  14.             for (int i = 0; i < matrix.length; i++) {
  15.                 for (int j = i; j < matrix.length; j++) {
  16.                     Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  17.                     int sum = 0;
  18.                     map.put(0, -1);
  19.                     for (int k = 0; k < matrix[0].length; k++) {
  20.                         sum = getSum(matrix, i, 0, j, k);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.                         if (map.containsKey(sum)) {
  22.                             res = new int[][] {{i, map.get(sum) + 1}, {j, k}};
  23.                             return res;
  24.                         } else {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  25.                             map.put(sum, k);
  26.                         }
  27.                     }
  28.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  29.             }
  30.         }
  31.         return res;
  32.     }
  33.     private int getSum(int[][] matrix, int x1, int y1, int x2, int y2) {
  34.         return matrix[x2][y2] - (x1 - 1 >= 0 ? matrix[x1 - 1][y2] : 0) - (y1 - 1 >= 0 ? matrix[x2][y1 - 1] : 0) + (x1 - 1 >= 0 && y1 - 1 >= 0 ? matrix[x1 - 1][y1 - 1] : 0);
  35.     }
  36. }
复制代码


Accepted code for http://www.lintcode.com/en/problem/submatrix-sum/# on Lintcode
回复 支持 反对

使用道具 举报

jiya 发表于 2016-9-4 07:45:05 | 显示全部楼层
jiya 发表于 2016-9-4 07:44. 鍥磋鎴戜滑@1point 3 acres
Accepted code for http://www.lintcode.com/en/problem/submatrix-sum/# on Lintcode

时间复杂度:O(n^3)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 01:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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