经典面试问题, 终于出现在Leetcode了, 写完后看了下discuss, 基本大家写的都差不多. 可见这题多容易考, 我身边的朋友就有被问过这题的. 题目很简单, 就是给一个大小为k的窗口, 然后给一个数组, 问在k下的最值是什么. 就用Leetcode的例子吧. 单调队列解区间最值 nums 输入数组 k 队列窗口大小 Given nums = [1,3,-1,-3,5,3,6,7], and k = 3. Window position Max ————— —– [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 […]
最近好像这个面试题很流行, 因为考点很多, 而且出题人可以从这个题延展到很多基础知识, 所以是很好的面试题, 也是很好的准备基础知识的题, 大概设计的考点如下: Hash vs Encoding: 一般会问, 生成url的时候, 为什么不能通过生成hash来查找? 回答: hash有冲突. 1个tinyurl, 在decode的时候会map到多个url上. Encoding利用了URL中字符串的可能字符为定值(a->z, A->Z, 0->9, 符号不算), 把每位字符转换成数字, 然后对其用62(26(小写)+26(大写)+10(数字))位编码. 确保了唯一性.代码如下: private static final String alphabet = “abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789”; public static int encode(String s) { int res = 0; for (int i = 0 ; i < s.length(); i++) { if (‘a’ <= s.charAt(i) […]
今天geeksforgeeks上刷出来的题.一看不能用stack, 基本就是Morris遍历了. 但是做了一下, 发现需要注意的地方挺多的, 比如当我们算visit的时候, 在rebuild link后, 我们也需要increase counter. 不然打印出来的是The Bottom of Tree 代码: public static int find(TreeNode root, int k) { int count = 0;// int res = Integer.MAX_VALUE; TreeNode cur = root; while (cur != null) { if (cur.left == null) { // if left == null, then we print(or do something, in […]
一亩三分地上看的,不是我的面试, 写一个吧…感觉不是很难 public int add(int n) { for(int i = 0; i < 32; i++) { if (((1 << i) & n) == 0){ //until we find the first 1 bit n = n | (1 << i); break; } else n = n & ~(1 << i); // clean bits } return n; } […]
Features Time: O(m+n), where m is the length of pattern, and n is the length of input string. Space: O(N), right array holds, if finite number of different chars as pattern. Times of compare: It will take O(m/n) times compares. However, it is normally less than that. You may apply some rules to define a […]
==比较的是:是否obj1和obj2在同一个内存.相比下,equals就是比较内容. 所以Object 要override equals() /*Integer vs Integer*/ Integer a = new Integer(256); Integer b = new Integer(256); System.out.println(a == b); //false System.out.println(a.equals(b)); // true /*Integer vs int*/ Integer a1 = new Integer(256); int b1 = 256; System.out.println(a1 == b1); //true (这里证明了, a1的内存地址和b1是一样的// ) System.out.println(a1.equals(b1)); //true /*Integer deep copy*/ Integer a2 = new Integer(256); Integer b2 […]
这是我面LiveRamp的面试题:这题是电面,所以只用说清楚思路, 但是用嘴说一个分布式系统的思路实在太困难了, 而且对面小哥貌似是伯克利的,我说一段,他就问一段,节奏太快,面的感觉不好,后来写了封感谢信,人家推荐我学一下伯克利的CS162,Link:http://cs162.eecs.berkeley.edu/.知耻近乎勇, 赶紧看了一下. 真是很好的课. 特别是Phase3到Phase4.建议大家有时间看看. 面试的过程是这样的: 第一个问题是: 请设计一个Key-Value Store for 1mb data. 我脑子都不转就说HashMap<Key,Value>, 然后聊了一下时间复杂度,还有重复怎么办, 注意put操作默认是override value的. 讨论了五分钟后, 接着问, What if the size of data increase to 1tb, 我说不能HashMap了, 因为HashMap是存在内存中的, 这么大的data存不进去, 丢了也不好办, 所以就开始分布式设计了, 但是我考虑了一下, 1tb的data存本地硬盘就好了, 所以我说, 存在硬盘里,但是考虑到存的是stable storage里,而不是普通的硬盘, 做个RAID什么的…然后聊了聊怎么存取, 简单说就是用key划分一下目录层级什么的. 又过了十五分钟后, 问如果有1pb data 怎么办, 这个果断开始分布式了, 我当时是按照着dynamo的概念说的, 但是在讨论trade off的时候, 明显没有对方熟悉一些概念和设计模式, 所以就挂了. 确实很遗憾, 因为对方最后也说前边面的都不错. 看来基础还是最重要的. Move On了.
这题看着挺简单, 各种corn case唉. 如果不是仔细写, 会被面试官直接按到死. 先举几个栗子: 输入： 1 2 3 4 5 6 7 8 9 输出： 4 1 2 7 5 3 8 9 6 输入： 1 2 3 4 5 6 7 8 9 10 输出： 6 1 2 3 4 7 8 9 10 5 输入： 1 2 3 4 5 6 […]
这个题目好像有很多变种, 比如给一个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, 多加了个除数, 仅此而已