Split ways
这是一个Google的OA题. 给一个string, 问通过切分后, 左边string和右边string的unique的char的个数相同, 这样的切分有几个? 说切分, 其实就是counting问题, 先counting一下unique char的个数, 然后再次counting一遍, 从左往右扫, 做切分.
Others Interview Question
Min Amplitude
这是一道google的oa题, 给一个数组, 通过改变三个数后, 使得数组最大值和最小值的差, 最小. 狗家的题都是先观察, 然后再coding, 主要是找到好的思路. 这题也是这样, 首先观察我们可以使用的操作, 就是改变数组中任意的三个数. 因为最后求最值的差, 所以这三个数的选择肯定是选择和最值有关的数. 首先排序一下, 然后找到两头(最大数列,和最小数列). 发现因为只有三个数可以改变, 那么改变后的最值肯定出在以下几种情况: 改变了最小的三个值, 答案= 第四小的值与最大值的差…由此类推即可发现答案有四种可能. 具体实现上, 因为要找到最大的四个数和最小的四个数, 可以sort, 也可以用priority queue.
定时的任务调度分布系统
场景如下, 你在淘宝买了一个衣服, 然后忘了评论了, 淘宝为了让你的购物更有意义, 自动给了好评. 这个就是一个定时的(几个小时或者几天)的任务. 如何分布式处理这些任务,是今天的话题. 对于这个问题, Java的原生代码有一个完全符合需求的实现, DelayQueue. 这个queue是一个blocked queue, 他可以让消费者通过take方法, 获得最靠前的已经到期的item(比如已经可以自动好评的淘宝买单). 而生产者通过实现java.util.concurrent.Delayed 借口, 可以往queue里放入item. 另外就是 http://www.cse.wustl.edu/~cdgill/courses/cs6874/TimingWheels.ppt 这是一个名为 HashedWheelTimer的环状计时器. 每个环上的节点都有一个计数器, 代表当前节点是第几圈到期. 而一个环被分为512个ticks, 每个tick是100 毫秒.这样就可以通过mod把过期的具体时间分配到换上的不同tick上. 以下是Netty的具体实现 HashedWheelTimer.java 最后就是 Redis Keyspace Notification, 让人意想不到的是…Redis对Expire( https://redis.io/commands/expire), 仅仅是用unix的timestamp…而整个系统, 也只是配合了pub/sub的架构. 没有新的算法
读Sharding & IDs at Instagram
原文地址 https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c 文章说提到的一个环境是, 在ins中, 每秒有25的照片和90个赞, 那么怎么把这个量级的数据存储在Django和PostgreSQL中, 在数据库的集群中, 如果用单一的递增id查找数据(严格递增), 会让查找非常慢. 在分析过系统需求后, ins的工程师做出以下几点具体需求: 生成的ID要是天然地sorted by time. 这里的天然地指的是不需要其他id上的数据支持. id最好能64位. 最好能有一个简单移动的解决方案. 并且让数据的迁移变小. 在现有的解决方案下, ins的工程师有两个选择, 一个是在app端生成id (减少服务器端生产id所需资源消耗), 另一个是用现成的UUIDs的算法几何. 使用这些现有的工具的优点有: 在客户端生产id, 可以最大程度减少failure和id重复. 如果用timestamp作为id的一个part, 那么自然就是sorted. 但是缺点很明显: 这些解决方案会让整体的系统结构变得复杂. (这里我不知道为什么作者要写这个, 因为snowflake本来就是twitter开发用来做这个功能的, 当时在退休前已经是很完善的分布式id生成器了) 另一种思路是用数据库自带的id生成器. Flickr用两个sql做ticket db. 然后前边用一个load balancer 挡着, 两个sql一个奇数, 一个偶数. 用这种解决方案的优点是: 因为id生成器靠近服务器端, 所以有更好的控制能力和整体性. 缺点是: 当数据不断扩大, 最后write操作还是会成为bottleneck. tickets servers需要额外的维护. sorted by time 只能粗略的保证. 现在来看看ins的最终解决方案: 在ins中, […]
关于面试中设计题的一些想法
最近面了很多家公司, 几乎现在无论大小公司都会出几道设计题, 这些设计题很难预先准备, 除非题库非常准确, 但是准备了也没什么用, 因为临场的时候, 面试官会随机加入条件, 让你讨论trade-off, 或者让你谈谈你的设计的缺陷是什么, 会在什么特殊情况下fail. 所以现在慢慢觉得, 面试中, 算法虽然很重要, 但是算法可以补的很快, 多刷题, 多做题就可以提高, 偶尔碰到原题直接背靠背就出来了. 但是设计题则
Zenefits 一道面试题
一亩三分地上看的一道题. 给两个string,A和B A = XYZ A^2 = XXYYZZ ….. B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh return k = 2, 因为b中有A^2的subsequence. 我用的run-length encode做的, 先找下a的count, 然后找下b的count, 这里的技巧是把在b但是不在a的字符存成负数. 这样encode的时候, 我们只encode a和b中共同的字符. 然后走一下数字的最小值就好了, 时间o(n). package Interview; /** * Created by chenguanghe on 9/2/15. */ public class Zenefits { public int findK(String a, String b) { int[] count_a = new int[256]; int[] count_b = […]
WePay 面试
Wepay的面试很容易拿, 扔个简历过去,很快就换个oa回来. oa的题也很固定2个选择题, 1个设计hashtable题. 但是这个hashtable题很奇葩, 因为oa就30分钟, 而且用的是hackerrank的环境, 根本没法复制粘贴,全靠手敲代码+测试, 要求是能支持put和get方法, 并且是有抽象参数, 并且还要能解决hash冲突. 然后我敲了下面的代码, 居然说oa没过..然后发网上, 问了过了的同学怎么写的…大家纷纷表示我写的很好- – move on 了 import java.util.ArrayList; import java.util.Iterator; import java.util.LinkedList; public class myHashTable<K, V> { class Entry<K, V> { public Entry(K key, V value) { this.key = key; this.value = value; } K key; V value; } private int size = […]
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 […]
[Facebook] Given an integer, add its binary number by 1 without “+” 整数加一, 不用加号.
一亩三分地上看的,不是我的面试, 写一个吧…感觉不是很难 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; } […]
[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了.