一亩三分地论坛

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

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

google 电面

[复制链接] |试试Instant~ |关注本帖
celtspirit 发表于 2015-4-7 07:08:00 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Passfresh grad应届毕业生

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

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

x
刚刚结束的电面,答得其实很烂,但竟然拿到onsite了,看来bar真的降低了。上来赞赞人品! 然后求米。。。。。。对,有点儿俗. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

白人妹子,人太好了,竟然给我过了. visit 1point3acres.com for more.

1.wiggle sort a<=b>=c<=d>=e........
一开是想得太复杂了,还要sort,其实就是local比较就行了。

2.2D matrix,while or black stone. find if there are rectangels whose four corner are black stone.
wbwbw
wbwbw. 鍥磋鎴戜滑@1point 3 acres
wwww 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
只要有一个就行,如图。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
其实只要line之间用 and check一下就行了,请自行脑补。

祝好!


.1point3acres缃

评分

2

查看全部评分

jeager 发表于 2015-4-10 10:38:24 | 显示全部楼层
resoy 发表于 2015-4-10 02:24
楼主楼主,但是
(100001 - 1) & 101000 也是 != 0 呀, 但是是不合理的, 楼主能讲的更详细点吗?

我来解释一下吧

1000&0100 = 0,fail;
1000&1000 = 1000 > 0 => (1000-1) = 0111, 0111&1000 = 0, fail;
1001&1010 = 1000 > 0 => (1000-1) = 0111, 0111&1000 = 0, fail;
1010&1010 = 1010 > 0 => (1010-1) = 1001, 1001&1000 > 0, success;
1011&1010 = 1010 > 0 => (1010-1) = 1001, 1001&1000 > 0, success;
1011&1011 = 1011 > 0 => (1011-1) = 1010, 1010&1011 > 0, success;
回复 支持 1 反对 0

使用道具 举报

sunfish 发表于 2015-4-7 07:24:36 | 显示全部楼层
louzu什么时候去onsite 啊
回复 支持 反对

使用道具 举报

 楼主| celtspirit 发表于 2015-4-7 07:26:36 | 显示全部楼层
sunfish 发表于 2015-4-7 07:24
. 鍥磋鎴戜滑@1point 3 acreslouzu什么时候去onsite 啊
. visit 1point3acres.com for more.
刚拿到,hr还没发具体的安排
回复 支持 反对

使用道具 举报

jeager 发表于 2015-4-8 04:26:44 | 显示全部楼层
第二题
brute force是O(n3)
bitmap是O(n2)
感觉没有比bitmap更好的方法了.....
回复 支持 反对

使用道具 举报

 楼主| celtspirit 发表于 2015-4-8 05:33:58 | 显示全部楼层
jeager 发表于 2015-4-8 04:26
第二题 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
brute force是O(n3). Waral 鍗氬鏈夋洿澶氭枃绔,
bitmap是O(n2)

010010 line0
110010 line1
000000 line2

line0 & line1 直接就出答案了
回复 支持 反对

使用道具 举报

jeager 发表于 2015-4-8 05:43:19 | 显示全部楼层
celtspirit 发表于 2015-4-8 05:33
010010 line0
. Waral 鍗氬鏈夋洿澶氭枃绔,110010 line1
000000 line2

我也是这么想的
预处理 matrix to bitmap O(n2)
line对比line worst 是O(n2)
所以复杂度是O(n2)
回复 支持 反对

使用道具 举报

 楼主| celtspirit 发表于 2015-4-8 06:18:02 | 显示全部楼层
jeager 发表于 2015-4-8 05:43 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我也是这么想的
预处理 matrix to bitmap O(n2)
line对比line worst 是O(n2)
. 鍥磋鎴戜滑@1point 3 acres
恩恩,是的嘞!
回复 支持 反对

使用道具 举报

resoy 发表于 2015-4-8 08:00:54 | 显示全部楼层
最后&得出的结果怎么确定至少两个1啊? 还得一个一个bit的process吗?
110011
100000 . 鍥磋鎴戜滑@1point 3 acres
&的结果是100000, 怎么判断这个是不合理的呢?感觉复杂度会增加。。
      
回复 支持 反对

使用道具 举报

 楼主| celtspirit 发表于 2015-4-8 11:15:25 | 显示全部楼层
resoy 发表于 2015-4-8 08:00
最后&得出的结果怎么确定至少两个1啊? 还得一个一个bit的process吗?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
110011
100000

(100000-1) &100000 = 0;

(101000-1) & 101000 != 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

貌似是这样的
回复 支持 反对

使用道具 举报

sunfish 发表于 2015-4-8 12:04:27 | 显示全部楼层
celtspirit 发表于 2015-4-8 11:15
(100000-1) &100000 = 0;

(101000-1) & 101000 != 0;

如果矩阵的宽度很大这么办,会overflow吗?
回复 支持 反对

使用道具 举报

stochasticer 发表于 2015-4-8 18:23:19 | 显示全部楼层
内个,请教LZ第一题,如何不sort涅?想不通了……(⊙﹏⊙)b
我的code如下,大家多指教: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

/* wiggle sort
flg=0: a>=b<=c>=d<=e........
flg=1: a<=b>=c<=d>=e........
*/
template<typename T>
void wigglesort( vector<T> &v, int flg ){. more info on 1point3acres.com
        if(v.size()<=2)
                return;. from: 1point3acres.com/bbs
        sort(v.begin(),v.end());
        int first;
        if(flg==0) //
                first=0;
        else if(flg==1)
                first=1;-google 1point3acres
        int idx=first;
        while(idx<v.size()-1){
                swap(v[idx],v[idx+1]); idx+=2;
        }. 鍥磋鎴戜滑@1point 3 acres
};
回复 支持 反对

使用道具 举报

 楼主| celtspirit 发表于 2015-4-9 04:22:44 | 显示全部楼层
stochasticer 发表于 2015-4-8 18:23
内个,请教LZ第一题,如何不sort涅?想不通了……(⊙﹏⊙)b.鐣欏璁哄潧-涓浜-涓夊垎鍦
我的code如下,大家多指教:

只要分奇偶一个个往右比较就可以了,35421=>53421=>53421=>53421=>53412.
回复 支持 反对

使用道具 举报

 楼主| celtspirit 发表于 2015-4-9 04:24:38 | 显示全部楼层
sunfish 发表于 2015-4-8 12:04
如果矩阵的宽度很大这么办,会overflow吗?

这还真没有考虑过,电面时间比较短。没问这么细。懂的人麻烦解答一下哈!
回复 支持 反对

使用道具 举报

stochasticer 发表于 2015-4-9 18:11:58 | 显示全部楼层
celtspirit 发表于 2015-4-9 04:22
只要分奇偶一个个往右比较就可以了,35421=>53421=>53421=>53421=>53412.

突然发现确实是想复杂了!这题貌似是个坑啊,不小心就会掉进去。多谢提点!
回复 支持 反对

使用道具 举报

pidouki 发表于 2015-4-9 22:02:49 | 显示全部楼层
celtspirit 发表于 2015-4-8 11:15
(100000-1) &100000 = 0;

(101000-1) & 101000 != 0;

good idea~ learn it, thanks~
回复 支持 反对

使用道具 举报

resoy 发表于 2015-4-10 02:24:48 | 显示全部楼层
celtspirit 发表于 2015-4-8 11:15
(100000-1) &100000 = 0;

(101000-1) & 101000 != 0;

楼主楼主,但是
(100001 - 1) & 101000 也是 != 0 呀, 但是是不合理的, 楼主能讲的更详细点吗?
回复 支持 反对

使用道具 举报

 楼主| celtspirit 发表于 2015-4-10 04:20:40 | 显示全部楼层
resoy 发表于 2015-4-10 02:24.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主楼主,但是
(100001 - 1) & 101000 也是 != 0 呀, 但是是不合理的, 楼主能讲的更详细点吗?

你是已经先进行与运算了,现在的问题是判断有几个1啊。 你跳过了一步,你看看前面的回复。
回复 支持 反对

使用道具 举报

xuchen1m3fd 发表于 2015-4-10 04:54:31 | 显示全部楼层
jeager 发表于 2015-4-8 05:43. From 1point 3acres bbs
我也是这么想的
预处理 matrix to bitmap O(n2)
line对比line worst 是O(n2)

想问一下一些细节,预处理是指把每一行存成bitset吗?
如果这么做的话line对比是O(n^2),但是line和line的and操作是O(n),所以总的应该是O(n^3)吧。
不知道我理解的对不对
回复 支持 反对

使用道具 举报

jeager 发表于 2015-4-10 10:24:52 | 显示全部楼层
xuchen1m3fd 发表于 2015-4-10 04:54
想问一下一些细节,预处理是指把每一行存成bitset吗?. 鍥磋鎴戜滑@1point 3 acres
如果这么做的话line对比是O(n^2),但是line和line ...

首先 我表示 长见识了 头一次听说BitSet
我的方法是直接处理成一个Integer.鐣欏璁哄潧-涓浜-涓夊垎鍦
这样的话 and操作就是O(1)了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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