攒人品发Google onsite面经

发信人: Zhuimeng1314 (  追梦一生), 信区: JobHunting
标  题: 攒人品发Google onsite面经
发信站: BBS 未名空间站 (Thu Jul 31 16:47:52 2014, 美东)

session 1一个class {int a,  bool c, int b} 里面每个variable所占的空间都不同
，比如a,b是int 所以分别占4byte. bool的c只占1byte。还有其他变量，可能占8bytes
或者16bytes。都是2的次方就是。
问题是写一个程序让他们可以很好的被放到8byte为单位的block里面去然后空间不会浪
费。
比如如果是 就按照a, c, b的话它一共要占12个byte。因为当把a和c放到一个block的
时候就会浪费一些空间。
所以最好摆成a，b，c这样的话更合理。占9个byte。剩下的空间还可以放一些小的
object。
其实这个就是用排序，然后从大的变量依次放进block。
有个followup的问题就是：因为我不想过多移动这些变量，所以怎么才能设计一个算法
所需要移动的object最少。
比如如果变量的size一次是4, 4, 1, 1, 8, 8, 1, 1最好的排法是4, 4, 8, 8, 1, 1,
1, 1.而不是8 8 4 4 1 1 1 1因为前一种所需要移动的cost最小。这个没想出来了。。
应该用divide and conquer？
session 2： 1. 设计算法找出平面上点的convex hull 不用写code（不熟。讨论下想
出，但是应该悲剧）
                   2. code 插入元素到max heap。
session 3： 1. 一个bit的stream， 每次读取6个bit。转化成char。
                   2. 很多URL，找到所有distinct的URL。（分布式计算）
session 4:   写出长度小于N的所有旋转对称数。
                   例子 689 顺时针旋转180度还是689
                   递归。也可以dp。
session 5: 设计数据结构，满足insert,delete,getRandom都是O(1)
就是这样了。结果估计不咋地。
anyway move on。
希望后面的面试结果不错。
--
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 172.]

http://www.mitbbs.com/article_t/JobHunting/32748027.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

京东江苏沃卡超万人使用，送100元京东优惠券京券 ， 更多京东优惠券