一亩三分地论坛

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

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

随便写写骨骼家两次电面

[复制链接] |试试Instant~ |关注本帖
sothink 发表于 2016-10-19 15:57:07 | 显示全部楼层 |阅读模式

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

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

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

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

加面是这样的,

1 给定一个字符串,只有两种字符,左右括号,写一段代码统计有多少种配对方案
2.从map reduce开始讨论了一些和大数据处理有关的问题
.鐣欏璁哄潧-涓浜-涓夊垎鍦
感觉G家喜欢问map reduce,楼主没特别准备过,估计要挂

评分

1

查看全部评分

本帖被以下淘专辑推荐:

zzgzzm 发表于 2016-11-10 00:31:55 | 显示全部楼层
chaosMonkey 发表于 2016-11-9 18:11. from: 1point3acres.com/bbs
怎么判断一个矩阵是从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) {
  6.       for (k = 0; k < n; ++k)
  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.   }
  11.   return -1; // no rotated matrix found
  12. }
复制代码
回复 支持 1 反对 0

使用道具 举报

zzgzzm 发表于 2016-11-11 23:36:48 | 显示全部楼层
chaosMonkey 发表于 2016-11-11 15:43
这个有办法优化吗? 感觉做法太直白不像是follow-up的风格啊,总觉得应该有个什么比较巧妙的规律

其实我也在想这个题的考点在哪里。也许LZ可以有当时更多的上下文信息来澄清一下。.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果仅仅从这里字面的题意上看的话,给定一个任意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本身这道题就不存在这个问题了。.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

使用道具 举报

zzgzzm 发表于 2016-10-24 04:57:51 | 显示全部楼层
何打发123 发表于 2016-10-23 23:58. visit 1point3acres.com for more.
感谢分享~~~

是不是左边括号的数量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) {-google 1point3acres
  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.     }
  7.     return res;
  8. }
复制代码
回复 支持 1 反对 0

使用道具 举报

小飞侠我去 发表于 2016-10-20 13:58:19 | 显示全部楼层
楼主,字符串那道题是什么意思啊?是说本来没配对,可以删一些字符变成配对的,还是找出所有的subarray,使其是配对的?
回复 支持 反对

使用道具 举报

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

比如 ())) 返回3, (())返回4
回复 支持 反对

使用道具 举报

小飞侠我去 发表于 2016-10-21 01:51:18 | 显示全部楼层
sothink 发表于 2016-10-20 17:34
比如 ())) 返回3, (())返回4

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

使用道具 举报

 楼主| sothink 发表于 2016-10-21 16:38:49 | 显示全部楼层
小飞侠我去 发表于 2016-10-21 01:51. more info on 1point3acres.com
呃,想了想没什么好思路,楼主能讲一下思路吗?谢谢

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴这。。。O(N) 的遍历就可以了
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-23 23:58:19 | 显示全部楼层
sothink 发表于 2016-10-21 16:38
这。。。O(N) 的遍历就可以了

感谢分享~~~

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

使用道具 举报

lzy315754058 发表于 2016-10-24 03:59:00 | 显示全部楼层
楼主你好,可以详细说说矩阵旋转那道题的题目吗?是旋转90度还是什么?
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-10-24 07:15:56 | 显示全部楼层
zzgzzm 发表于 2016-10-24 04:57
数valid括号:One pass O(N) time complexity and O(1) space complexity.
Note: 每个valid pair都有一 ...

赞!~~~~~~·
回复 支持 反对

使用道具 举报

gabrielleL 发表于 2016-10-24 08:31:48 | 显示全部楼层
可以问一下投的什么职位么?software也会店面就问到大数据的问题么
回复 支持 反对

使用道具 举报

 楼主| sothink 发表于 2016-10-24 10:18:57 | 显示全部楼层
lzy315754058 发表于 2016-10-24 03:59
楼主你好,可以详细说说矩阵旋转那道题的题目吗?是旋转90度还是什么?

对,就是转90度
回复 支持 反对

使用道具 举报

 楼主| sothink 发表于 2016-10-24 10:20:17 | 显示全部楼层
gabrielleL 发表于 2016-10-24 08:31
可以问一下投的什么职位么?software也会店面就问到大数据的问题么
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我是工作多年,跳槽的,不知道fresh grad会不会问
最好也关注一下吧
回复 支持 反对

使用道具 举报

 楼主| sothink 发表于 2016-10-24 10:20:40 | 显示全部楼层
gabrielleL 发表于 2016-10-24 08:31
可以问一下投的什么职位么?software也会店面就问到大数据的问题么

G HR 找来的,面完再match
回复 支持 反对

使用道具 举报

pst242 发表于 2016-10-24 11:13:24 | 显示全部楼层
請問樓主,矩陣旋轉角度有給定嗎?

补充内容 (2016-10-24 11:15):
抱歉耍笨了,現在才看到璇轉90度, 祝樓主順利拿offer
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-11-9 18:11:35 | 显示全部楼层
怎么判断一个矩阵是从N个矩阵中某一个旋转得到的呢
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

zzgzzm 发表于 2016-11-10 21:13:02 | 显示全部楼层
chaosMonkey 发表于 2016-11-10 15:32
都是旋转90的判断是吧 我还以为可以旋转180 270这种

嗯,看LZ的回复就是转90度。若有多个角度就得多个判断了。
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-11-11 15:43:50 | 显示全部楼层
zzgzzm 发表于 2016-11-10 21:13
嗯,看LZ的回复就是转90度。若有多个角度就得多个判断了。
. Waral 鍗氬鏈夋洿澶氭枃绔,
这个有办法优化吗? 感觉做法太直白不像是follow-up的风格啊,总觉得应该有个什么比较巧妙的规律
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 10:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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