一亩三分地论坛

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

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

谷歌电面+facebook校园面试

[复制链接] |试试Instant~ |关注本帖
abc235153452 发表于 2015-11-3 08:41:22 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@GoogleFacebook - 校园招聘会 - 技术电面 校园招聘会 在线笔试 |Otherfresh grad应届毕业生

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

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

x
今天刚刚面完两轮的谷歌,感觉自己萌萌哒了。。。. 鍥磋鎴戜滑@1point 3 acres
为了造福大家,把我两轮谷歌电面的题目,还有Facebook一轮面试的题目发这里,希望对后面的同学有帮助,话说你们谁要是拿到了谷歌和Facebook的工作,记得内推我啊。
谷歌第一轮电面:
第一题:
Given an array of decimal digits: 132
increment it by 1, so 132->133
其实这个就是一个用C++来写大整数的加法的,解法很简单,先把整个array reverse,然后for循环,超过9的就加一到下一位,并且该位设置为0.

第二题:
还是上面那题的follow up不过不是加一了,而是加n 并且n<9
我直接使用以前写过的大整数的模版了,我给的答案是 n+9<INF 都可以。想知道大整数怎么写的,请直接搜索楼天城 大整数模版,当年我们就是直接照的他的代码敲的。在此感谢楼教主~-google 1point3acres

第三题:. From 1point 3acres bbs
Given a sorted arrya of integers. find the closest number to given integer.
一开始不知道要干嘛,后来她举了个例子就明白了,找绝对值的差最小的数字,不用想了,直接binary search。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
最后,我问了她几个问题,大概35分钟面试就结束了。。。
顺便吐槽下,这个妹子面试官,一开始发音还是很标准的,到后面开始讲题目的时候 语速一快,我就听到了一股浓浓的三姐的味道。。。

谷歌第二轮电面:(感觉已跪)
第一题:. Waral 鍗氬鏈夋洿澶氭枃绔,
直接copy
Find the longest path of increasing values through a 2D array (starts anywhere, only step to 4 orthogonal neighbors).
- May assume values are positive integers.
- e.g. Input:
   10 15 2  5
   4  23 6  19
   1  8  9  21

   Output: [1, 4, 10, 15, 23].1point3acres缃

DFS 搜索搞定,中间出了一个意外,面试官说我的那个visited数组会因为引用出问题,我去,妈蛋的,我每次搜索的时候visited都是copy过去的,不存在这个问题好吗。。。最后面试官道歉,他是玩java的不怎么会C++。。。深深的对谷歌码农水平感到怀疑。。。
第二题:
2. Given a list of matrix dimensions (#row) x (#col), find the dimensions of the matrix with the *largest possible number of entries* that can be created by multiplying two of the matrices.. 1point3acres.com/bbs
- Behaviour of matrix dimensions: (A x B) * (B x C) => A x C. more info on 1point3acres.com
- e.g. 4x2, 3x2, 2x5, 6x3 => 4x5 (20 entries, created by (4x2) * (2x5))
- Square matrices are possible; a matrix may be reused..鐣欏璁哄潧-涓浜-涓夊垎鍦
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这个题目我悲剧了,半天没有听懂题目,后来他解释了好几遍我才弄明白,这个小哥估计是在家里工作,不然信号怎么会那么差。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
题目大意是再给出的矩阵中,找出两个矩阵乘 得出一个新的矩阵,求出新的矩阵entries最大的值是多少. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
一开始我给出了一个N^2的算法,小哥建议我优化下,我就给了一个linear time的算法
简单的说就是用一个hash map来保存所有的矩阵,rows为key, cols为values
然后再搜索所有的矩阵,看是否存在一个矩阵,他的rows等于我这个矩阵的cols,把这个新的矩阵的entries保存,比较一下即可。

因为第二题我浪费太多时间和小哥胡扯题目了,代码都没写,就给了个思路。。。估计悲剧了。

Facebook on campus 面试
我比较的悲剧,三个面试官,两个中国人,我就那么倒霉的又抽到了一个阿三哥。咦,我为什么要说又?. 鍥磋鎴戜滑@1point 3 acres
第一题:
Given an array, find whether it exist an subarray that sum of subarray is equal to given number
简单的说就是给一个array,和一个数字,问存在一个subarray,他的和等于那个数字。注意,subarray的意思是一个连续的元素的subarray from array。
一开始给了N^2的暴力算法,之后给了O(N)的算法,解法是用一个新的数组保存从0到当前元素的和,然后再用hash表保存下,再搜索一次即可。

第二题:. more info on 1point3acres.com
上面那题的follow up,不过array变成了matrix,找的也是submatrix。。。
先给了个错误的解,阿三哥叫我自己跑下我的算法,悲剧的跪了。。。实在没办法了,我给了个暴力解O(N^4)。折腾了半天也没想法,最后时间到了。。。

说实话到现在我还是想不出有什么更优的解,哪位大神想出来了,麻烦告诉下我啊,洛杉矶请客吃饭。
不过最后运气真的很好,最后还是拿到了FB的onsite机会,下个礼拜就onsite,求人品啊~~~

评分

4

查看全部评分

本帖被以下淘专辑推荐:

haifengc 发表于 2015-11-3 12:51:05 | 显示全部楼层
Facebook第二题:
这一题可以n^3,和这个题目类似
http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

用两个循环转化成一维的数组,然后再用一位的方法,总共n^3
回复 支持 1 反对 0

使用道具 举报

haifengc 发表于 2015-11-3 12:58:54 | 显示全部楼层
谷歌第二轮第一题. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Find the longest path of increasing values through a 2D array (starts anywhere, only step to 4 orthogonal neighbors).. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

感觉应该是DP啊,DFS怎么保证正确性呢?
回复 支持 反对

使用道具 举报

翔在天空 发表于 2015-11-3 14:18:37 | 显示全部楼层
感觉有hashmap还是n^2啊
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-3 15:07:46 | 显示全部楼层
haifengc 发表于 2015-11-3 12:51
Facebook第二题:
这一题可以n^3,和这个题目类似.鏈枃鍘熷垱鑷1point3acres璁哄潧
http://www.geeksforgeeks.org/dynamic-programming-set ...

大神好厉害!顺便问一下,matrix subsume的题记得看面经里提到都可以用二维树状数组做,我今天终于看明白了 query node,但是不明白如何query sum,请大神指点一下,解释下或者给一个学习的链接,多谢啦!
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-3 23:12:57 | 显示全部楼层
marthew777 发表于 2015-11-3 15:07
大神好厉害!顺便问一下,matrix subsume的题记得看面经里提到都可以用二维树状数组做,我今天终于看明白 ...

我是**啊。.1point3acres缃
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
感觉是 sum(x1, y1, x2, y2) = sum(0, 0, x2, y2) - sum(0, 0, x1, y2) - sum(0, 0, x2, y1) + sum(0, 0, x1, y1)
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-4 00:19:23 | 显示全部楼层
haifengc 发表于 2015-11-3 23:12
我是**啊。

感觉是 sum(x1, y1, x2, y2) = sum(0, 0, x2, y2) - sum(0, 0, x1, y2) - sum(0, 0, x2, y ...

我想确认一下学的树状数组是不是理解到了用法。。帮我确认一下好吗,那么我们除了你发的DP方法以外,是不是可以先O(nlgn) set。然后query 时间是不是,  sumation of 1 + 2^2 * lg2 + 3^2 * lg3 + ...(n-1)^2 * lg(n-1) = O(n^3 * lgn); 虽然查询慢了但是set更快,如果query次数多就用你链接上的dp, query次数少就用BIT
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-4 00:26:22 | 显示全部楼层
marthew777 发表于 2015-11-4 00:19
我想确认一下学的树状数组是不是理解到了用法。。帮我确认一下好吗,那么我们除了你发的DP方法以外,是不 ...

呵呵,我是**啊,找大牛确认,我不能树状数组,
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-4 03:57:16 | 显示全部楼层
请问楼主Google二面第一题,为啥要用个visited啊?我觉得不用啊,因为每次新加的元素肯定大于之前被访问过的元素,所以不可能会再去添加之前的元素啊?
回复 支持 反对

使用道具 举报

 楼主| abc235153452 发表于 2015-11-4 10:26:59 | 显示全部楼层
haifengc 发表于 2015-11-3 12:51. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Facebook第二题:
这一题可以n^3,和这个题目类似
http://www.geeksforgeeks.org/dynamic-programming-set ...

多谢,我终于明白facebook那题怎么做了,用二维的树状数组来做。谷歌第二轮的DFS是最优解的,没有问题的,不过话说这题用DP怎么做啊,表示没思路
回复 支持 反对

使用道具 举报

 楼主| abc235153452 发表于 2015-11-4 10:27:45 | 显示全部楼层
翔在天空 发表于 2015-11-3 14:18
感觉有hashmap还是n^2啊
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不是的,建立hashmap时间为O(N)后面搜索的时候时间也是O(N),所以总时间是O(N)
回复 支持 反对

使用道具 举报

 楼主| abc235153452 发表于 2015-11-4 10:31:00 | 显示全部楼层
小A要当码农 发表于 2015-11-4 03:57
请问楼主Google二面第一题,为啥要用个visited啊?我觉得不用啊,因为每次新加的元素肯定大于之前被访问过 ...

说的好有道理,我想多了,额,时间复杂度还是不会变的,不过这样可以节省很多空间
回复 支持 反对

使用道具 举报

dong882205 发表于 2015-11-4 12:10:23 | 显示全部楼层
Google二面第一题,百度下“滑雪问题”~~
回复 支持 反对

使用道具 举报

latioswang 发表于 2015-11-4 15:10:02 | 显示全部楼层
楼主好,Google第二题,我简化为数对pair<int, int>,hashmap做法,代码如下,如有问题,请指正:
pair<int, int> square(vector<pair<int, int>>& matrix) {
    pair<int, int> res;
    if (matrix.empty()) return res;
    unordered_map<int, int> mp;
    int mul = 0;
    for (auto p : matrix) {
        mp[p.first] = p.second;
    }
    for (auto p : matrix) {
        if (mp.find(p.second) != mp.end()) {
            entries = p.first * mp[p.second];. Waral 鍗氬鏈夋洿澶氭枃绔,
        }
        if (entries > mul) {
            mul = entries;. 1point3acres.com/bbs
            res = make_pair(p.first, mp[p.second]);
        }
    }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    return res;
}

补充内容 (2015-11-4 15:12):
是Google二面的第二题
回复 支持 反对

使用道具 举报

 楼主| abc235153452 发表于 2015-11-4 15:12:31 | 显示全部楼层
latioswang 发表于 2015-11-4 15:10
楼主好,Google第二题,我简化为数对pair,hashmap做法,代码如下,如有问题,请指正:. 1point3acres.com/bbs
pair square(vecto ...
. visit 1point3acres.com for more.
好像应该return mul吧?
回复 支持 反对

使用道具 举报

latioswang 发表于 2015-11-4 15:15:30 | 显示全部楼层
abc235153452 发表于 2015-11-4 15:12
好像应该return mul吧?

- e.g. 4x2, 3x2, 2x5, 6x3 => 4x5 (20 entries, created by (4x2) * (2x5))
根据这里,我的理解是return 4x5,因为20在后面的括号里,表明它是求得的最大的mul,不过返回什么都都可以,只要逻辑和代码是对的,就OK了,你觉得呢?
回复 支持 反对

使用道具 举报

 楼主| abc235153452 发表于 2015-11-4 15:16:32 | 显示全部楼层
都行,差不多就可以了。
回复 支持 反对

使用道具 举报

latioswang 发表于 2015-11-4 15:43:55 | 显示全部楼层
楼主,您好,冒昧请问,您的Google二面的第一题,我的第一直觉也是BFS/DFS搜索,两种都可以,类似leetcode Surrounded Regions和Word Search, 但是和 Triangle的做法也非常类似,关键在于search的同时要维护一个到达当前点的最长递增序列的长度,这里有点tricky,可否看下你的代码啊?
回复 支持 反对

使用道具 举报

latioswang 发表于 2015-11-4 18:54:03 | 显示全部楼层
楼主,您好,Facebook的两道题,我的代码如下,如有问题,请指正:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一问,是否存在subarray,其数字和等于target, 用hashset保存从0到当前数字的和,再重新遍历一遍,如果有两个数字和只差等于target,那么这两个数字和中间的数字就是所求的子数组。
bool existSubarray(vector<int> &data, int target) {
    unordered_set<int> st;
    sum[0] = data[0];
    st.insert(sum[0]);
    for (int i = 1; i < data.size(); ++i) {
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴        sum += sum[i-1] + data;
        st.insert(sum);
    }
    for (int i = 0; i < data.size(); ++i) {
        if (st.find(sum - target) != st.end()) {
            return true;
        }
    }
    return false;.鐣欏璁哄潧-涓浜-涓夊垎鍦
}
第二问,array变为matrix, 是否存在submatrix,其数字和等于target
int existMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            matrix[j] += matrix[i-1][j]; //指的是第j列从上到下累加到第i行的元素和,
        }. from: 1point3acres.com/bbs
    }
    int dp[n+1];
    dp[0] = matrix[0][0];
    unordered_set<int> st;
    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j < i; ++j) {
            for (int k = 1; k <= n; ++k) {
                dp[k] = matrix[k] - matrix[j][k]; //指的是第k列,从第j行到第i行的元素和.鐣欏璁哄潧-涓浜-涓夊垎鍦
                dp[k] += dp[k-1]; //从第j行到第i行,前k列的元素和
                st.insert(dp[k]);. 1point3acres.com/bbs
            }. more info on 1point3acres.com
            for (int k = 0; k <= n; ++k) {
                if (st.find(dp[k] - target) != st.end()) {
                    return true;. more info on 1point3acres.com
                }
            }
            st.clear();
        }. more info on 1point3acres.com
    }
    return false;
}

. From 1point 3acres bbs补充内容 (2015-11-4 18:58):
时间复杂度: subarray : O(n),submatrix : O(m * m * n),
空间复杂度:  subarray : O(n),submatrix : O (n), n为矩阵的列
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-11-4 19:38):
不知道为什么代码贴出来是斜的,可读性变差了很多,方便的话贴到sublime看下吧
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-11-5 00:30:32 | 显示全部楼层
abc235153452 发表于 2015-11-4 10:31. from: 1point3acres.com/bbs
说的好有道理,我想多了,额,时间复杂度还是不会变的,不过这样可以节省很多空间

额,好像是我搞错了。 visited的作用是在主函数里面吧? 之前被搜索过的函数, 之后就不用再以它为起点进行搜索了,是这个意思么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 02:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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