Menu Sidebar
Menu

Others Interview Question

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).

   

WePay 面试

Wepay的面试很容易拿, 扔个简历过去,很快就换个oa回来. oa的题也很固定2个选择题, 1个设计hashtable题. 但是这个hashtable题很奇葩, 因为oa就30分钟, 而且用的是hackerrank的环境, 根本没法复制粘贴,全靠手敲代码+测试, 要求是能支持put和get方法, 并且是有抽象参数, 并且还要能解决hash冲突. 然后我敲了下面的代码, 居然说oa没过..然后发网上, 问了过了的同学怎么写的…大家纷纷表示我写的很好- –  move on 了

 

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

给一个数组, 找出里面的两个数, 使得这两个数的乘积最大.这是geeksforgeeks上的题, 我看原题下面的代码有点复杂, 就重新想了想. 先看两个例子:

但是上面的例子不能完全说明问题, 比如说{0,1,-5}, 这时候, pair应该是0, 1 OR 0, -5. 思路很简单, 通过观察上面的例子, 不难发现, 这个pair和四个数字有关: 数组中, 正数的最大值pmax和第二大值psec, 负数的最大值nmax和第二大值nsec. 而最大值应为Math.max(pmax*psec, nmax*nsec). 代码如下:

需要注意的是else if在判断时候使用, 还有初始化时,应该把值初始为0.

[Facebook] Given an integer, add its binary number by 1 without “+” 整数加一, 不用加号.

一亩三分地上看的,不是我的面试, 写一个吧…感觉不是很难

算法思路: i是游标, (1 << i) 就是对n的每个位从右往左扫. if判断的是, 如果这位是 0, 那么就变成1. 如果不是, 那么这位肯定是1, 那么在未来的某次循环需要把0 变成1时, 这位肯定要变成0, 所以如果是1 就是0. 这里用的是clean bits的方法. 先去取反做mask, 再取与(and).  

[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了.

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

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

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

书脊

倾城与倾国, 佳人难再得