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的倍数了. public static boolean isPowerof4(int n) { return (n&n-1)+n%3==1; } 下边是power of 8 public static boolean isPowerof8(int n) { return (n&n-1)+n%7==1; }
这个题目好像有很多变种, 比如给一个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的原理去重. public static HashSet<ArrayList<Integer>> findAllTriAngle(int[] A) { HashSet<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>(); […]
Google电面: 这个算电面的简单题了. 没帕金森的基本都能写… 其实就是Prime Factorization, 只是code略有不同. 然后这个不是O(n) 算法, 是伪多项式的算法, 因为input和n本身的大小有关系. public static List<Integer> getAllDivisors(int n) { List<Integer> divisors = new ArrayList<Integer>(); for (int denominator = 1; denominator <=Math.sqrt(n); denominator++) if (n % denominator == 0) { divisors.add(denominator); if (denominator * denominator != n) divisors.add(n / denominator); } Collections.sort(divisors); return divisors; } 与Prime Factorization的区别就是中间第二个if, 多加了个除数, 仅此而已
这是一道Google的面试题. 当我第一次看到这题的时候, 第一个感觉, 树, 编码,解码, 那不就是Prufer Code么. 拿起笔就开始写, 后来感觉电面不应该这么复杂, 而且Prufer code对象是Labeled Tree, 这里并没有使用到BST的特殊性质. 于是赶紧回想刷过的题, 突然想起Leetcode上面的编码方式: 这个编码的特点是: Inorder Traversal. Null = # Code容易写. 所以编码的code是: public static String serialize (TreeNode root) { StringBuilder sb = new StringBuilder(); if (root == null) sb.append(“#”); else { sb.append(root.val); sb.append(serialize(root.left)); sb.append(serialize(root.right)); } return sb.toString(); } 解码的特点是: 因为已知编码是Inorder, 所以解码也是Inorder 要注意如果解码到#, 需要return null. […]