Google Onsite 面经

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)。讨论见这里。

旋转数字那个的判断方法和palindrome差不多：

for (size_t i = 0; i < s.size() / 2; ++i) {
  if (s[i] == '0' || s[i] == '1' || s[i] == '8') {
    if (s[s.size() - 1 - i] != s[i]) {
      return false;
    }
  }
  if (s[i] == '6') {
    if (s[s.size() - 1 - i] != '9') {
      return false;
    }
  }
}

 

From：

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

http://www.mitbbs.com/article_t1/JobHunting/32748027_0_3.html