一亩三分地论坛

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

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

G家YouTube组 电面

[复制链接] |试试Instant~ |关注本帖
Cyn1014 发表于 2014-6-25 15:10:39 | 显示全部楼层 |阅读模式

2014(4-6月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Pass

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

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

x
网上海投的,昨天刚面的,问了两道题,然后今天拿到了onsite。来发面经攒人品面试官应该是个老美,人很nice。先让说了自己做过的project。然后开始coding题。全程50分钟左右
1. 给一个矩阵A,要求输出一个矩阵B,要求B[i,j]=sum(A[l,k]) l<=i,k<=j;
例如 A=[1,1,2;
             0,3,1;.鐣欏璁哄潧-涓浜-涓夊垎鍦
             2,1,0]
         B=[1,2,4;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
               1,5,8;
               3,8,13];
follow up: 1.时间复杂度+如何测试
                2. 给定矩形块的upperx,uppery,lowerx,lowery,求矩形块的面积
                3. 如果 要多次运行函数求矩形块的面积,如何提高效率.鐣欏璁哄潧-涓浜-涓夊垎鍦
2. 给定一种单词缩略的方式如下:保留单词首字母,保留单词最后一个字母,保留单词首末字母间的字母数。如work-->w2k,food-->f2d, fold-->f2d
    如何判断两个不同单词的缩略是否相同. from: 1point3acres.com/bbs
    给一个字典,给一个任意的单词,判断这个单词在字典中是否拥有唯一的缩略形式,就是字典中是否有其他单词与所给单词有相同的缩略。
follow up:如何测试,hashtable 跟balance tree的比较
. 鍥磋鎴戜滑@1point 3 acres

评分

4

查看全部评分

本帖被以下淘专辑推荐:

readman 发表于 2014-6-25 15:30:49 | 显示全部楼层
楼主好命, 真心不难...
回复 支持 反对

使用道具 举报

tianyangche 发表于 2014-6-26 05:35:10 | 显示全部楼层
楼主好~
我刚才做了一下第一题~是不是第二个矩阵的最后一个数应该是11?
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2014-6-26 07:11:25 | 显示全部楼层
楼主好命,确实真心不难....1point3acres缃
回复 支持 反对

使用道具 举报

 楼主| Cyn1014 发表于 2014-6-26 07:31:51 | 显示全部楼层
tianyangche 发表于 2014-6-26 05:35
楼主好~. 鍥磋鎴戜滑@1point 3 acres
我刚才做了一下第一题~是不是第二个矩阵的最后一个数应该是11?

是的,口算不过关,不好意思啊~~
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2014-6-26 08:33:17 | 显示全部楼层
@金妮韦崽  你来看人家的第一题。当年你的数学比他好吧。
回复 支持 反对

使用道具 举报

tianyangche 发表于 2014-6-26 09:44:24 | 显示全部楼层
Cyn1014 发表于 2014-6-26 07:31. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
是的,口算不过关,不好意思啊~~

没事~~~感觉第一题和那个从(0,0) 走到(m,n)很像呢~
楼主onsite加油!!!
回复 支持 反对

使用道具 举报

Meva 发表于 2014-6-26 14:07:35 | 显示全部楼层
lz多久收到的电面啊???
回复 支持 反对

使用道具 举报

 楼主| Cyn1014 发表于 2014-6-26 18:45:14 | 显示全部楼层
Meva 发表于 2014-6-26 14:07
lz多久收到的电面啊???

申完一周以内的感觉,我各种海投记得不是很清楚
回复 支持 反对

使用道具 举报

 楼主| Cyn1014 发表于 2014-6-26 18:45:21 | 显示全部楼层
Meva 发表于 2014-6-26 14:07
lz多久收到的电面啊???

申完一周以内的感觉,我各种海投记得不是很清楚
回复 支持 反对

使用道具 举报

 楼主| Cyn1014 发表于 2014-6-26 18:56:09 | 显示全部楼层
tianyangche 发表于 2014-6-26 09:44. more info on 1point3acres.com
没事~~~感觉第一题和那个从(0,0) 走到(m,n)很像呢~
楼主onsite加油!!!

谢谢。你这么一说是有点像呢
回复 支持 反对

使用道具 举报

nathanwong 发表于 2014-7-17 05:00:49 | 显示全部楼层
楼主,第一题 following up 从第二问开始,是具体什么意思, 求矩形面积是说长*宽? 还是说每一格里面的value 加起来 是矩形面积
回复 支持 反对

使用道具 举报

violethaze 发表于 2014-7-23 15:17:19 | 显示全部楼层
nathanwong 发表于 2014-7-17 05:00. from: 1point3acres.com/bbs
楼主,第一题 following up 从第二问开始,是具体什么意思, 求矩形面积是说长*宽? 还是说每一格里面的va ...

同问, lz解释一下呗
回复 支持 反对

使用道具 举报

readman 发表于 2014-7-23 21:49:37 | 显示全部楼层
violethaze 发表于 2014-7-23 15:17.鏈枃鍘熷垱鑷1point3acres璁哄潧
同问, lz解释一下呗

- = 我觉得
先高位排序, 然后再低位排序.
出来的循序就是答案了...
回复 支持 反对

使用道具 举报

readman 发表于 2014-7-23 21:57:06 | 显示全部楼层
violethaze 发表于 2014-7-23 15:17
同问, lz解释一下呗

- = 错了..我看题了...
那个是字典树把..
-google 1point3acres树高的差代表中间的数字.
搜索一下就知道有没有重复的了
回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2014-9-13 19:27:51 | 显示全部楼层
楼主是neu的is专业吗,跪求找coop和fulltime的情况
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
另外求问spring 对coop有什么影响吗?
回复 支持 反对

使用道具 举报

熊笨笨 发表于 2014-9-14 01:02:07 | 显示全部楼层
最近面youtube的好多啊
姐居然还有第二轮电面。哭了
回复 支持 反对

使用道具 举报

siren01 发表于 2014-9-14 09:15:43 | 显示全部楼层
熊笨笨 发表于 2014-9-14 01:02
最近面youtube的好多啊
姐居然还有第二轮电面。哭了

你们都是13fall入学,1年半毕业的么?
回复 支持 反对

使用道具 举报

熊笨笨 发表于 2014-9-14 13:35:26 | 显示全部楼层
siren01 发表于 2014-9-14 09:15. visit 1point3acres.com for more.
你们都是13fall入学,1年半毕业的么?
. Waral 鍗氬鏈夋洿澶氭枃绔,
俺已经不记得神马时候入学的了。。。反正是年底毕业
回复 支持 反对

使用道具 举报

littlecoolblaxk 发表于 2014-9-15 07:39:05 | 显示全部楼层
谢谢分享 onsite好运!!!!我也要面YouTube了 所以跟着做一下. Waral 鍗氬鏈夋洿澶氭枃绔,

路过的小伙伴能否帮忙看下我这么写能不能pass.鐣欏璁哄潧-涓浜-涓夊垎鍦

第一题:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
public static int[][] sumMatrix(int[][] a) {. 1point3acres.com/bbs
    if (a == null) {
        return null;
    }. 1point 3acres 璁哄潧
    if (a.length == 0) {
        return new int[0][0];
    }
    if (a[0].length == 0) {
        return new int[1][0];
   }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    int rows = a.length;
    int cols = a[0].length;

    int b[][] = new int[rows][cols];
    b[0][0] = a[0][0];

    for (int i = 1; i < cols; i++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        b[0][i] = a[0][i] + b[0][i - 1];
    }

    for (int i = 1; i < rows; i++) {
        b[i][0] = a[i][0] + b[i - 1][0];
    }
. 1point 3acres 璁哄潧
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
        }
    }

    return b;
}


时间和空间复杂度是 M*N 就是输入数组的行乘以列
测试数据主要是输入数组长度或者宽度为0或者1 时的特殊案例 然后普通案例就是随便写几个数吧 还有都是0 或者都是1

矩形面积就是 右下角 减去 右上角  再减去左下角 再加左上角 经典的sub matrix求和问题。
运行的话。。暂时能想到的就是预处理输入数组 把它的运行结果存在额外空间里 这样就不用每次都计算一下B数组了

第二题

. from: 1point3acres.com/bbs 判断是不是同样的简写
public boolean sameAbbr(String s1, String s2) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    if (s1.length() != s2.length()) {
        return false;
    }
    int len = s1.length();
    return (s1.charAt(0) == s2.charAt(0) && s1.charAt(len - 1) == s2.charAt(len - 1)
}


大概就这样吧 不知道怎么优化了
然后第二问 字典应该是set吧?
只能想到一个一个比较。
如果函数要运行多次的话 类似anagrams 那道题 用hashmap存 key是缩写 value是 ArrayList<String> 用来存所有的是这个缩写的string。
然后判断containsKey。。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
tree结构的思路还没太思考。。

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 12:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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