周末读物之聊聊三观

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 3656|回复: 19
收起左侧

随便写写骨骼家两次电面

[复制链接] |试试Instant~
我的人缘0
sothink 发表于 2016-10-19 15:57:07 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  88% (8)
 
 
11% (1)  踩

2016(10-12月) 码农类General 本科 全职@Google - 猎头 - 技术电面  | Other | 在职跳槽

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

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

x
第一次电面是一个拒镇旋转的问题,以及给定一个拒镇判定是否是从N个给定拒镇中的某一个旋转得出的。。。
然后,加面了。。。

加面是这样的,

1 给定一个字符串,只有两种字符,左右括号,写一段代码统计有多少种配对方案. From 1point 3acres bbs
2.从map reduce开始讨论了一些和大数据处理有关的问题

感觉G家喜欢问map reduce,楼主没特别准备过,估计要挂

评分

参与人数 1大米 +3 收起 理由
dobbin + 3 感谢分享!

查看全部评分


上一篇:关于snapchat的一些事项提问
下一篇:10.16 Amazon OA2

本帖被以下淘专辑推荐:

我的人缘0
zzgzzm 发表于 2016-11-11 23:36:48 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
chaosMonkey 发表于 2016-11-11 15:43
这个有办法优化吗? 感觉做法太直白不像是follow-up的风格啊,总觉得应该有个什么比较巧妙的规律
. 围观我们@1point 3 acres
其实我也在想这个题的考点在哪里。也许LZ可以有当时更多的上下文信息来澄清一下。-google 1point3acres
如果仅仅从这里字面的题意上看的话,给定一个任意vector<Matrix>,没有任何限制,那么光input data的自由度就是M*N^2,其中M=vector长度,N为矩阵维度。如果存在一个算法的复杂度是O(M*N^2)的话我觉得已经是最优的了。因为更快的算法不能覆盖所有input data,而很容易举出反例只要改变M*N^2中的一个值就可以改变最后返回矩阵的index。除了做一个(i,j)->(j,N-1-i)的变换外,这个题就是等价于直接问给定一堆Objects,问有没有一个和另一个给定的object相等,而判断类object相等的耗费就是O(N^2).

如果这个题这么变一下:给定一个vector<Matrix> smalls, matrix维度为N1 (vector长度为M)。再给定一个大矩阵Matrix big维度为N2 (N2 > N1)。问smalls中有没有一个是big的子阵(submatrix)。那么这个题的显然时间上界O(M*N2^2)就不一定是最优的了。因为光判断一个N1维小矩阵是不是N2维大矩阵的子阵就至少O(N2^2),暴力和每个小矩阵单独比较的话就会有浪费(因为小矩阵彼此之间可能有相似之处),需要将vector按照"Trie"之类思想的预处理一下。这样可以走捷径的原因是固定的大矩阵N2会远远大于N1. 但对于LZ本身这道题就不存在这个问题了。

补充内容 (2016-11-11 23:39):
因为任何预处理的代价是O(M*N1^2)。所以若暴力的算法复杂度也是一样的话就无所谓预处理了。
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-10 00:31:55 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
chaosMonkey 发表于 2016-11-9 18:11
怎么判断一个矩阵是从N个矩阵中某一个旋转得到的呢

矩阵旋转: LZ的矩阵旋转是指顺时针旋转90度,所以元素(i, j)被移到(j, n-1-i)。然后其它的应该就是一个一个比较了吧,时间复杂度O(n^2*numMatrices).
  1. typedef vector<vector<double>> Matrix;
  2. int findFirstRotation(Matrix& matrix, vector<Matrix>& matrices, int n) {
  3.   for (int i = 0; i < matrices.size(); ++i) {
  4.     int j = 0, k = 0;
  5.     for (; j < n; ++j) {. Waral 博客有更多文章,
  6.       for (k = 0; k < n; ++k).1point3acres网
  7.         if (matrix[j][k] != matrices[i][k][n - 1 - j]) j = k = n+1; // break out of inner 2 loops
  8.     }
  9.     if (j == n && k == n) return i; // found first rotated matrix
  10.   }.本文原创自1point3acres论坛
  11.   return -1; // no rotated matrix found
  12. }
复制代码
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-24 04:57:51 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
何打发123 发表于 2016-10-23 23:58. 围观我们@1point 3 acres
感谢分享~~~. Waral 博客有更多文章,

是不是左边括号的数量n1*右边括号的数量n2 当n1  n2 都set 回0重新开始数?

数valid括号:One pass O(N) time complexity and O(1) space complexity. . 一亩-三分-地,独家发布
Note: 每个valid pair都有一个右括号,总的valid pair个数就是数每个')'之前有多少个'(', 然后叠加起来即可。
  1. int numValidPairs(string& s) {
  2.     int res = 0, nLeft = 0; // number of '(' up to current index position
  3.     for (int i = 0; i < s.length(); ++i) {
  4.         if (s[i] == '(') nLeft++;
  5.         else res += nLeft; // current char is ')' which can pair with any previous '('
  6.     }. visit 1point3acres for more.
  7.     return res;. Waral 博客有更多文章,
  8. }
复制代码
回复

使用道具 举报

我的人缘0
小飞侠我去 发表于 2016-10-20 13:58:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (71)
 
 
5% (4)  踩
楼主,字符串那道题是什么意思啊?是说本来没配对,可以删一些字符变成配对的,还是找出所有的subarray,使其是配对的?

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| sothink 发表于 2016-10-20 17:34:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (8)
 
 
11% (1)  踩
小飞侠我去 发表于 2016-10-20 13:58
楼主,字符串那道题是什么意思啊?是说本来没配对,可以删一些字符变成配对的,还是找出所有的subarray,使 ...

比如 ())) 返回3, (())返回4
回复

使用道具 举报

我的人缘0
小飞侠我去 发表于 2016-10-21 01:51:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (71)
 
 
5% (4)  踩
sothink 发表于 2016-10-20 17:34
比如 ())) 返回3, (())返回4

呃,想了想没什么好思路,楼主能讲一下思路吗?谢谢
回复

使用道具 举报

我的人缘0
 楼主| sothink 发表于 2016-10-21 16:38:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (8)
 
 
11% (1)  踩
小飞侠我去 发表于 2016-10-21 01:51
呃,想了想没什么好思路,楼主能讲一下思路吗?谢谢

这。。。O(N) 的遍历就可以了
回复

使用道具 举报

我的人缘0
何打发123 发表于 2016-10-23 23:58:19 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (38)
 
 
7% (3)  踩
sothink 发表于 2016-10-21 16:38. from: 1point3acres
这。。。O(N) 的遍历就可以了

感谢分享~~~

是不是左边括号的数量n1*右边括号的数量n2 当n1 <= n2
如果 n1 > n2 都set 回0重新开始数?
回复

使用道具 举报

我的人缘0
lzy315754058 发表于 2016-10-24 03:59:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
楼主你好,可以详细说说矩阵旋转那道题的题目吗?是旋转90度还是什么?
回复

使用道具 举报

我的人缘0
何打发123 发表于 2016-10-24 07:15:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (38)
 
 
7% (3)  踩
zzgzzm 发表于 2016-10-24 04:57
数valid括号:One pass O(N) time complexity and O(1) space complexity.
Note: 每个valid pair都有一 ...
-google 1point3acres
赞!~~~~~~·

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
gabrielleL 发表于 2016-10-24 08:31:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
可以问一下投的什么职位么?software也会店面就问到大数据的问题么
回复

使用道具 举报

我的人缘0
 楼主| sothink 发表于 2016-10-24 10:18:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (8)
 
 
11% (1)  踩
lzy315754058 发表于 2016-10-24 03:59
楼主你好,可以详细说说矩阵旋转那道题的题目吗?是旋转90度还是什么?
. 留学申请论坛-一亩三分地
对,就是转90度
回复

使用道具 举报

我的人缘0
 楼主| sothink 发表于 2016-10-24 10:20:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (8)
 
 
11% (1)  踩
gabrielleL 发表于 2016-10-24 08:31. 1point3acres
可以问一下投的什么职位么?software也会店面就问到大数据的问题么

我是工作多年,跳槽的,不知道fresh grad会不会问
最好也关注一下吧
回复

使用道具 举报

我的人缘0
 楼主| sothink 发表于 2016-10-24 10:20:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (8)
 
 
11% (1)  踩
gabrielleL 发表于 2016-10-24 08:31
可以问一下投的什么职位么?software也会店面就问到大数据的问题么

G HR 找来的,面完再match
回复

使用道具 举报

我的人缘0
pst242 发表于 2016-10-24 11:13:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
請問樓主,矩陣旋轉角度有給定嗎?
. 留学申请论坛-一亩三分地
补充内容 (2016-10-24 11:15):
抱歉耍笨了,現在才看到璇轉90度, 祝樓主順利拿offer
回复

使用道具 举报

我的人缘0
chaosMonkey 发表于 2016-11-9 18:11:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (8)
 
 
11% (1)  踩
怎么判断一个矩阵是从N个矩阵中某一个旋转得到的呢
回复

使用道具 举报

我的人缘0
chaosMonkey 发表于 2016-11-10 15:32:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (8)
 
 
11% (1)  踩
zzgzzm 发表于 2016-11-10 00:31
矩阵旋转: LZ的矩阵旋转是指顺时针旋转90度,所以元素(i, j)被移到(j, n-1-i)。然后其它的应该就是一个一 ...

都是旋转90的判断是吧 我还以为可以旋转180 270这种
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-10 21:13:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
chaosMonkey 发表于 2016-11-10 15:32
都是旋转90的判断是吧 我还以为可以旋转180 270这种
. 1point3acres
嗯,看LZ的回复就是转90度。若有多个角度就得多个判断了。
回复

使用道具 举报

我的人缘0
chaosMonkey 发表于 2016-11-11 15:43:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (8)
 
 
11% (1)  踩
zzgzzm 发表于 2016-11-10 21:13
嗯,看LZ的回复就是转90度。若有多个角度就得多个判断了。
. 留学申请论坛-一亩三分地
这个有办法优化吗? 感觉做法太直白不像是follow-up的风格啊,总觉得应该有个什么比较巧妙的规律
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-23 10:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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