Algorithm

Z Algorithm 一个和KMP,Boyer Moore并列的字符串搜索

KMP和Boyer Moore应该是最常见的两个子串搜索算法. 相比之下, KMP比较适合用在字符串基数少的string, 比如DNA, 然后BM相反. 和z相比, z的优势也就是短点… 今天看到GeeksforGeeks上介绍了Z function(Z algorithm).我都快忘了还有这个了. Z algorithm的时,空间复杂度和KMP类似, 采用的技术也类似.简单来说, Z algorithm采用了一个Z数组来保留已知子串信息. 和KMP一样, 我们需要预先计算Z数组. 如何计算Z数组?, Z数组的思想就是Longest Common Prefix (最长公共前缀,下面简称lcp). Z数组中在i位的元素表示lcp(s[0,s.length-1], s[i,s.length-1]). 就是包含i位的子串与串s的最长公共前缀. 比如 s: abbabbaa z: [0, 0, 0, 4, 0, 0, 1, 1] 在第二个a的时候, z是4, 表示abba是和s的最长公共子串, 即:lcp(abbabbaa,abbaa) = |abba|= 4. 如何使用z数组呢? 其实很简单, 只要把目标串s和匹配串p放在一个串中, 中间加个特殊符号, 就可以做子串搜索了.比如: s: abc p:abaedfbabcabd our string: […]

Date July 27, 2015
Category Algorithm
Comments No Comments

[Google] Longest Arithmetic Sequence 求最长等差数列

这题是我3年前面G家的原题.所以就写上google, 估计这么简单的题g家再也不会问了. 前几天朋友面G家, 已经上模拟退火了, 我也不知道当场白板模拟退火是什么感觉. 不过听说某神牛能IOI就当场写神经网络, 我也就感叹人和牛的差距比人和人的差距都大. 这题其实就是3-sum问题, code改了改就可以了. 所以想想g家onsite,出个3sum, 刷Leetcode的孩子们不要太高兴了, 是不是很良心. 不过写出来代码还是很容易bug的, 然后问时间复杂度,因为求的不是最长的长度, 而是数列, 所以是3-sum-hard 问题. 必然O(n2), 前几天听说有人破了这个hard bound, 不知道是不是真的. 也没关注. 具体思路就是从前往后扫, 如果没排序, 先排序一下,扫的时候, 让游标i在中间, 前边是j, 后边是k, 所以满足, 0<= j < i < k < Array.length, 然后i从1开始往后扫到Array.length-2, 因为j和k是从i初始化的, 每次i走一步, j往后扫,k往前扫, 所以总体的复杂度是O(n2) 代码: public static ArrayList<Integer> longestArith (int[] items) { ArrayList<Integer> res = new ArrayList<>(); […]

Ramsey Theorem 拉姆齐定理

– – 首先吐槽一下这个wiki的翻译, 看了一下是一个台湾人翻译的, 虽然语言很标准..但是读着不是很流畅. 我看Ramsey Number是看 Combinatorics Through Guided Discovery 的时候看到的. 里面第二章介绍Double Induction and Ramsey Number 说的非常详细, 而且很简洁. 这本书是免费的, 伯克利也在用, 强烈推荐. 下面介绍Ramsey Number: Ramsey Number可以从两个方面考虑: 一个是实际问题: 请多少的客人吃饭, 能正好让他们有至少m个互相认识或者n个都不认识. 这里有几点需要注意: 所求的值和条件都为至少 m和n是或者的关系另一个描述是从图论出发: 一个无向完全图中,最少多少个顶点, 有m大小的Clique或者n大小Independent Set. Clique的定义是:一个顶点的集合,其中任意两点都有边. Independent Set的定义是: 一个顶点的集合, 其中任意两点都没有边. 通过定义, 我们可以很清楚的看出, Ramsey Number是对称的, 即: R(m.n) = R(n,m) 证明Ramsey Number是非常复杂的, 借用wiki上的话就是: 想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了虽然证明一个不容易, 但是通过一个不等式,可以知道其大概的范围: 如果R(m-1,n)和R(m,n-1)不全是偶数: R(m, […]

Find a pair with maximum product in array of Integers 找出数组中最大乘积的一对

给一个数组, 找出里面的两个数, 使得这两个数的乘积最大.这是geeksforgeeks上的题, 我看原题下面的代码有点复杂, 就重新想了想. 先看两个例子: Input: arr[] = {1, 4, 3, 6, 7, 0} Output: {6,7} Input: arr[] = {-1, -3, -4, 2, 0, -5} Output: {-4,-5} 但是上面的例子不能完全说明问题, 比如说{0,1,-5}, 这时候, pair应该是0, 1 OR 0, -5. 思路很简单, 通过观察上面的例子, 不难发现, 这个pair和四个数字有关: 数组中, 正数的最大值pmax和第二大值psec, 负数的最大值nmax和第二大值nsec. 而最大值应为Math.max(pmax*psec, nmax*nsec). 代码如下: public int[] find(int[] nums) { if (nums == null […]

Date July 18, 2015
Category Algorithm Geeksforgeeks Interview Question Others Interview Question
Comments No Comments

URL to TinyURL 生成短链接

最近好像这个面试题很流行, 因为考点很多, 而且出题人可以从这个题延展到很多基础知识, 所以是很好的面试题, 也是很好的准备基础知识的题, 大概设计的考点如下: 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) […]

Date July 17, 2015
Category Algorithm Geeksforgeeks Interview Question
Comments No Comments

Find kth smallest element in BST 找第k个小(大)的值在BST中

今天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 […]

Date July 17, 2015
Category Algorithm Geeksforgeeks Interview Question
Comments No Comments

Boyer-Moore

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 […]

Date July 16, 2015
Category Algorithm
Comments No Comments

[LiveRamp]设计一个Key-Value Store

这是我面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了.

Date July 15, 2015
Category Algorithm Interview Question Others Interview Question
Comments No Comments

[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的原理去重. public static HashSet<ArrayList<Integer>> findAllTriAngle(int[] A) { HashSet<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>(); […]

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

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, 多加了个除数, 仅此而已

Date July 14, 2015
Category Algorithm Interview Question Others Interview Question
Comments No Comments