一亩三分地论坛

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

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

G家Onsite~

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

2014(10-12月) 码农类 硕士 全职@Google - Other - Onsite |Other

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

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

x
在YouTube面的。一上来被问了一大堆关于Android threading的问题,比如foreground thread 和background thread有什么区别,怎样设计程序防止UI卡顿之类的。简历里果然不能乱写。。。. from: 1point3acres.com/bbs
然后是一个设计题,已经有一个程序使用了标准的一个容器(比如List),现在有一堆第三方容器,怎样尽可能少更改源程序来利用这些新的类。其实就是写一个Wrapper Class,直接被面跪了。

算法题倒是挺简单的,两道二分查找。另外有一题给一个数列要求调整成小大小大小大。。的模式,有线性的贪心算法。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
另外还有一题是对稀疏向量求点积,HashMap或者直接归并都是可以的~. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

感觉面得好奇葩,求加RP求过>.<


补充内容 (2014-11-8 09:59):
.1point3acres缃口头offer了,谢谢大家帮忙加RP~~^-^

评分

3

查看全部评分

 楼主| lunaughty 发表于 2014-11-7 09:32:48 | 显示全部楼层
jyt0532 发表于 2014-11-3 15:41
請問一下sparse vector怎麼求dot product呢 可以請lz詳細一點說明嗎 謝謝~~

稀疏向量的存储方法是存储一个列表,里面存非零元素的位置和值,也就是<index, value>,按index排序

两个稀疏向量做点积的时候需要对index做归并,碰到有index相等的时候就把对应的两个value相乘,然后加到结果当中。归并完了就可以啦~

另外一个做法是用HashMap<index, value>,这样的话求点积就是遍历其中一个HashMap,在另外一个里面查找对应的index是否存在,这样也是可以的。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 1 反对 0

使用道具 举报

 楼主| lunaughty 发表于 2014-11-11 05:01:01 | 显示全部楼层
YY大帝 发表于 2014-11-11 04:57
请问LZ,那个数列要求调整成小大小大小大的贪心算法是什么样的,搜了半天没搜到,能简单介绍一下吗. 鍥磋鎴戜滑@1point 3 acres
Good l ...

从左往又扫,碰到不符合性质的相邻数对,直接调换就可以了,只有好处没有坏处,仔细想想就能证出来:)
回复 支持 1 反对 0

使用道具 举报

casey512 发表于 2014-11-8 06:28:10 | 显示全部楼层
lz有消息了吗
回复 支持 1 反对 0

使用道具 举报

ellenren 发表于 2014-10-25 14:32:25 | 显示全部楼层
感谢分享 bless
回复 支持 反对

使用道具 举报

lvchaoshuai 发表于 2014-10-25 15:39:57 | 显示全部楼层
不同公司同今天遇到小大小大小大……太巧了
回复 支持 反对

使用道具 举报

lin126 发表于 2014-11-1 11:42:57 | 显示全部楼层
感谢楼主分享啊~~~
回复 支持 反对

使用道具 举报

jyt0532 发表于 2014-11-3 15:41:04 | 显示全部楼层
請問一下sparse vector怎麼求dot product呢 可以請lz詳細一點說明嗎 謝謝~~
回复 支持 反对

使用道具 举报

 楼主| lunaughty 发表于 2014-11-8 09:14:36 | 显示全部楼层

没有啊,本来说好今天来消息的=,=
回复 支持 反对

使用道具 举报

loverszhaokai 发表于 2014-11-8 11:06:03 | 显示全部楼层
楼主加油(⊙o⊙)哦
回复 支持 反对

使用道具 举报

盼小梨 发表于 2014-11-8 20:51:08 来自手机 | 显示全部楼层
恭喜恭喜!马上也要onsite了,同求好运!
回复 支持 反对

使用道具 举报

 楼主| lunaughty 发表于 2014-11-11 04:04:39 | 显示全部楼层
盼小梨 发表于 2014-11-8 20:51
恭喜恭喜!马上也要onsite了,同求好运!

祝好运:P
回复 支持 反对

使用道具 举报

YY大帝 发表于 2014-11-11 04:57:29 | 显示全部楼层
请问LZ,那个数列要求调整成小大小大小大的贪心算法是什么样的,搜了半天没搜到,能简单介绍一下吗
Good luck
回复 支持 反对

使用道具 举报

YY大帝 发表于 2014-11-11 05:10:48 | 显示全部楼层
lunaughty 发表于 2014-11-11 05:01
从左往又扫,碰到不符合性质的相邻数对,直接调换就可以了,只有好处没有坏处,仔细想想就能证出来:)
.1point3acres缃
回复 支持 反对

使用道具 举报

盼小梨 发表于 2014-11-11 09:51:52 | 显示全部楼层
YY大帝 发表于 2014-11-11 04:57.鐣欏璁哄潧-涓浜-涓夊垎鍦
请问LZ,那个数列要求调整成小大小大小大的贪心算法是什么样的,搜了半天没搜到,能简单介绍一下吗 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Good l ...

同问,,,,,
回复 支持 反对

使用道具 举报

YY大帝 发表于 2014-11-11 10:05:32 | 显示全部楼层
盼小梨 发表于 2014-11-11 09:51. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
同问,,,,,

LZ回答了
回复 支持 反对

使用道具 举报

wanxin0001 发表于 2014-11-13 09:27:55 | 显示全部楼层
楼主 给一个数列要求调整成小大小大小大   这题如果有相邻重复元素怎么办 eg: 1,1,1,1,2,2,2,2
回复 支持 反对

使用道具 举报

 楼主| lunaughty 发表于 2014-11-13 09:40:44 | 显示全部楼层
wanxin0001 发表于 2014-11-13 09:27
楼主 给一个数列要求调整成小大小大小大   这题如果有相邻重复元素怎么办 eg: 1,1,1,1,2,2,2,2
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
好问题!不过当时是说好了>=和<=的。严格要求的话我暂时只能想到排序~
. visit 1point3acres.com for more.
补充内容 (2014-11-13 10:00):
错了这种情况下单纯排序好像也不行,得仔细想想……
回复 支持 反对

使用道具 举报

 楼主| lunaughty 发表于 2014-11-13 10:43:23 | 显示全部楼层
wanxin0001 发表于 2014-11-13 09:27
楼主 给一个数列要求调整成小大小大小大   这题如果有相邻重复元素怎么办 eg: 1,1,1,1,2,2,2,2

考虑了一下,这种情况要复杂很多。

首先注意到如果数组里中位数的重复次数超过了(N+1)/2次的话,则由抽屉原理肯定不存在可行解。所以我们先用线性时间找出中位数,然后排除以上无解的情况。. Waral 鍗氬鏈夋洿澶氭枃绔,
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果数组长度为奇数,先取出并输出一个中位数。. visit 1point3acres.com for more.

这样我们的数组的剩余长度一定为偶数,我们可以将所有数分为4组:A(小于中位数),B(等于),C(等于)和D(大于),且len(A)+len(B)和len(C)+len(D)都为N/2

然后不断重复以下步骤
1.取出一个大元素,如果D未空则从D中选取,否则从C中选取,输出
2.取出一个小元素,如果B未空则从B中选取,否则从A中选取,输出. visit 1point3acres.com for more.

重复至所有组为空即可。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 23:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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