一亩三分地论坛

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

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

热腾腾的Google电面

[复制链接] |试试Instant~ |关注本帖
LosivE 发表于 2016-1-23 03:53:50 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
运气真的不错了,遇到了期待已久的中国小哥,在google工作了三年。上来他的电话吱吱啦啦的听不清,我换了耳机也不行,只能强行听,感觉是个三哥我就直接跪了。题也出的特别简单,感觉把我去年年底的运气全攒到这时候了,我觉得应该是过了。上题:
1. 判断一个binary tree是不是bst,leetcode原题应该
2. 在一个Grid里算有多少正方形,给一个m一个n的边长. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
看了很多面经,感觉很看运气啊,在面的时候脑子少根筋的情况下来个难题真的吃不消,祝愿小伙伴们都能遇到好心的中国人。
最后,求大米!!!

评分

3

查看全部评分

chm34 发表于 2016-1-23 06:55:06 | 显示全部楼层
正常解法就行吧
  1. public static int solve(int matrix[][])
  2.         {
  3.                 if(matrix==null || matrix.length==0) return 0;
  4.                 int m=matrix.length; int n=matrix[0].length;

  5.                 int max_len=Math.min(m,n);
  6.                 for(int len=1;len<=max_len;len++)
  7.                 {
  8.                         int updown=m-len+1; int leftright=n-len+1;. more info on 1point3acres.com
  9.                         result+=updown*leftright;
  10.                 }. From 1point 3acres bbs
  11.                 return result;. 1point3acres.com/bbs
  12.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| LosivE 发表于 2016-1-23 09:02:35 | 显示全部楼层
hulahu 发表于 2016-1-23 04:48
能具体说说吗?在一个Grid里算有多少正方形,给一个m一个n的边长
. Waral 鍗氬鏈夋洿澶氭枃绔,
楼下的做法是对的,比如2*2的grid,就有4+1=5个正方形,3*3的话就有9+4+1=14个,我这么说能懂么?
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-1-23 04:24:18 | 显示全部楼层
第二题直接用公式 S = (1/6) * N *(N+1)* (3M-N+1) ?
回复 支持 反对

使用道具 举报

hulahu 发表于 2016-1-23 04:48:27 | 显示全部楼层
能具体说说吗?在一个Grid里算有多少正方形,给一个m一个n的边长
回复 支持 反对

使用道具 举报

lubor 发表于 2016-1-23 05:19:52 | 显示全部楼层
hulahu 发表于 2016-1-23 04:48
能具体说说吗?在一个Grid里算有多少正方形,给一个m一个n的边长

Assume M>N
鏉ユ簮涓浜.涓夊垎鍦拌鍧. .鏈枃鍘熷垱鑷1point3acres璁哄潧
# of squares = (m-n+1)*1 + (m-n+2)*2 + (m-n+3)*3+...+(m-n+n)*n
                     = (m-n)*1+(m-n)*2+(m-n)*3+...+(m-n)*n +(1*1+2*2+3*3+...+n*n)
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷                     = (m-n)*(n*(n+1))/2 + n*(n+1)(2n+1)/6. From 1point 3acres bbs
                     = (n*(n+1)*(3m-n+1))/6
回复 支持 反对

使用道具 举报

 楼主| LosivE 发表于 2016-1-23 09:05:27 | 显示全部楼层
wtcupup 发表于 2016-1-23 04:24. from: 1point3acres.com/bbs
第二题直接用公式 S = (1/6) * N *(N+1)* (3M-N+1) ?

我用一个循环做的,正方形的边长从1循环到min(m,n),不知道还有这么厉害的公式
回复 支持 反对

使用道具 举报

raoyin 发表于 2016-2-1 13:15:18 | 显示全部楼层
用一个循环,正方形的边长从1循环到min(m,n)
  1. class Solution():
  2.         def numSquare(self, m, n):
  3.                 ans = 0. Waral 鍗氬鏈夋洿澶氭枃绔,
  4.                 for i in range(1, min(m,n) + 1):. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.                         ans += (m - i + 1) * (m - i + 1)
  6.                 return ans

  7. if __name__ == "__main__":
  8.         print Solution().numSquare(3,3)
复制代码
回复 支持 反对

使用道具 举报

tianlu1 发表于 2016-2-29 02:09:08 | 显示全部楼层
我的算法和raoyin一样
回复 支持 反对

使用道具 举报

yuan311 发表于 2016-3-1 06:40:01 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

yuan311 发表于 2016-3-1 06:42:03 | 显示全部楼层
sorry, first time. finding how to remove previous garbage ...
解法就按楼主的正方形的边长从1循环到min(m,n)不就可以了,为什么还要(m-i+1) * (n - i + 1)...
回复 支持 反对

使用道具 举报

yuan311 发表于 2016-3-1 06:49:45 | 显示全部楼层
明白了,要考虑给出grid不是square的情况,所以(m - i + 1) * (n - i + 1).
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 17:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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