传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 7043|回复: 17
收起左侧

Facebook电面两轮

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

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

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

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

x
五分钟前面完的Facebook二面, 在这个找intern已经如大海捞针的季节 Lz还是各种拖啊拖,到了这份田地。。。感觉不管面怎样,挂的机率不是一般的高啊高啊高啊。。。汇报地里,这里简单描述一下一面二面的过程。攒攒人品,希望上天给个offer

一面:印度小哥(无耐心+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被指出。。。哭了这会儿。。。. visit 1point3acres.com for more.
第二题:把第一题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)...丢脸

一面过后一直觉得要挂了。。。。过了一个周末收到二面通知。。。可能都会有二面吧。。。反正最后应该是综合来看。。。虽说过了一面也不抱什么希望了。。。。

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

这个写完已经20分钟过去了。。。就剩5分钟做第二题了
第二题:merge K sorted array。。。
怎能如此简单。。。却不让写code。。。说了merge sort的思想。。。两两merge, recursive搞定。。。但是偏偏不让写code。。。这是在整我们。我心里住着的码农真是急坏了。。。
人家是考官,只好听从命令了。。。哭again. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

最后问了问还有没有intern position之类他绝对不能回答的问题就结束了。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

估计Facebook家的面试就这样告终了。。。在错误的时间遇到了错误的题目们和面试官们。。。. more info on 1point3acres.com
希望大家一切顺利。。。都有好的归宿。。。

-google 1point3acres

评分

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. From 1point 3acres bbs

    i=0

    curr=0
    for j in xrange(len(nums)):
        curr+=nums[j]
        while curr>s:-google 1point3acres
            curr-=nums[i]
            i+=1
        if curr==s:. from: 1point3acres.com/bbs
            return True

    return False

def checkSubMatrix(target,matrix):

    if matrix==None or len(matrix)==0:
        return False. from: 1point3acres.com/bbs
    m=len(matrix)
    n=len(matrix[0]). 1point3acres.com/bbs

    for left in xrange(n):. 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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    return False
回复 支持 3 反对 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
求问, checkArraySum本身就有O(m)的复杂度,checkSubMatrix的三层循环里面调用这个checkArraySum的话不是 ...

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
for i in xrange(m):. From 1point 3acres bbs
    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

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. 1point 3acres 璁哄潧
  4.      * [url=home.php?mod=space&uid=160137]@return[/url] the coordinate of the left-up and right-down number. 1point3acres.com/bbs
  5.      */
  6.     public int[][] submatrixSum(int[][] matrix) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  7.         int[][] res = new int[][] {{0, 0}, {0, 0}};
    . 1point 3acres 璁哄潧
  8.         if (matrix != null && matrix.length > 0) {. visit 1point3acres.com for more.
  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++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  19.                     for (int k = 0; k < matrix[0].length; k++) {
  20.                         sum = getSum(matrix, i, 0, j, k);.1point3acres缃
  21.                         if (map.containsKey(sum)) {-google 1point3acres
  22.                             res = new int[][] {{i, map.get(sum) + 1}, {j, k}};
  23.                             return res;
  24.                         } else {
  25.                             map.put(sum, k);
  26.                         }
  27.                     }. 1point3acres.com/bbs
  28.                 }
  29.             }
  30.         }. 鍥磋鎴戜滑@1point 3 acres
  31.         return res;
  32.     }.1point3acres缃
  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. }
复制代码

-google 1point3acres
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
Accepted code for http://www.lintcode.com/en/problem/submatrix-sum/# on Lintcode

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-24 08:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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