Menu Sidebar
Menu

Google

[Google] isPowerof4 O(1)找4的倍数.

Google电面的Bit操作题, 问你能不能用一个O(1)的方法, 判断n是不是4的倍数. 既然是O(1), 所以不能用循环, 先把n对n-1取&, 假设n = 16, 即10000. n-1=15,即01111.  但是我们还需要判断这个数是不是0. 所以我们让n对一个比它小的质数取mod. 比如4%3==1, 这样就可以判断n是不是4的倍数了.

下边是power of 8

 

[Google] Given an array of Integer, return all valid triangles 给一个int数组, 返回所有可能的三角形

这个题目好像有很多变种, 比如给一个int数组, 返回所有的不重复数字组成的三角形, 或者返回所有等腰/直角三角形. 反正就是多几个限制和少几个限制. 我遇到的这个是返回所有的可能的三角形, 这其中包含:等边,等腰等等, 只要是Valid就可以. 传统解法就是O(n^3)的暴力, 当然, 这肯定不是我们想要的. 就不多说了. 说到三角形,基本看懂中文的都知道两个特性: 两边之和大于第三边 两边之差小于第三边 对于一个已经排序的数组, 我们用第一条就可以了. 证明: Assume,x,y,z are three int, 0<x<=y<=z, if z < x-y, then y+z < x (against to 1), so z < x-y false 最后, 我们还要去重, 因为数组会有{4,4,4}, 所以要把选出的三边排序一下, 然后用HashSet的原理去重.

算法思路是: 双指针i和j, i扫全部, j从i开始往后扫 每次j扫的时候, 用k往前扫到可能的所有边. 然后sort一下这些边, 放进result里 这个是O(n^2)的算法, 在第二个for […]

[Google]Return all divisors of n 返回n的所有除数

Google电面: 这个算电面的简单题了. 没帕金森的基本都能写… 其实就是Prime Factorization, 只是code略有不同.  然后这个不是O(n) 算法, 是伪多项式的算法, 因为input和n本身的大小有关系.

与Prime Factorization的区别就是中间第二个if, 多加了个除数, 仅此而已

[Google] Serialization and Deserialization BST 二叉树编码和解码

这是一道Google的面试题. 当我第一次看到这题的时候, 第一个感觉, 树, 编码,解码, 那不就是Prufer Code么. 拿起笔就开始写, 后来感觉电面不应该这么复杂, 而且Prufer code对象是Labeled Tree, 这里并没有使用到BST的特殊性质. 于是赶紧回想刷过的题, 突然想起Leetcode上面的编码方式: 这个编码的特点是: Inorder Traversal. Null = # Code容易写. 所以编码的code是:

解码的特点是: 因为已知编码是Inorder, 所以解码也是Inorder 要注意如果解码到#, 需要return null. 所以解码的code是:

 

书脊

倾城与倾国, 佳人难再得