Monday, March 30, 2015

Reverse Bits

    uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16);
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        return n;      
    }

for 8 bit binary number abcdefgh, the process is as follow:
abcdefgh -> efghabcd -> ghefcdab -> hgfedcba




method 2


The idea is to check the 32 bits one by one from left to right. We will get final result after we finish that loop with 32 times. In each loop, we will always do 3 things:

1. The final result multiply by 2

2. If the modular of original value(n) is 1, then final result add 1.

3. Make the original value divided by 2.


The code is as follow:

    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for(int i = 0; i < 32; ++i)
        {
            res = res << 1;
            if(1 == n%2)
                ++res;
            n >>= 1;
        }
        return res;        
    }

Number of 1 Bits

    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n)
        {
            n &= n - 1;
            ++ res;
        }
        return res;      
    }

"n &= n - 1" is used to delete the right "1" of n. For example:
  • if n = 5 (101), then n-1 = 100, so n & (n-1) = 100, the right "1" is deleted;
  • if n = 6,(110), then n-1 = 101, so n & (n-1) = 100, the right "1" is also deleted;
  • and so on...
So time complexity is O(m), and m is the count of 1's, also m is less than or equal to 32.

Monday, March 23, 2015

典型有计划有目标找工经历



from here



先说下背景
master一年半项目毕业,gpa 3.6,修了一些distributed system方向的课。lc刷了3遍,cc150 两遍,glassdoor大致看了看,面试遇到的题目八九不离十。从去年九月份学校的career fair到年底签字,前后花了三个月找full time。一共认真面了11家公司,拿到GF等8个offer,最后从了G。

面试经过
1. AutoDesk: 按组招人。面的三番的office,电面一轮随便聊聊,直接就onsite了。面试当天三番交通非常堵,傻乎乎从南湾开过去,差点迟到。好在几轮面试都很简单。AutoDesk很像一个老人公司,所有面试官都是从senior 到principle,再到architect级别的。越是级别高的面试官越不会问算法题,聊聊对开源项目的理解,手上的project,谈笑风生一下就可以了。
2. HP Vertica: 按组招人。这家是在学校的careerfair投的,on campus面了一轮。因为是做数据库的公司,问到很多ds的设计问题,基本上课堂的理论就能应付。第二轮对方发过来一段代码,让你改进,提高效率,这个时候刷题锻炼出来的各种排序算法,复杂度分析就有用了,几个小时之内提交搞定。最后是去on site,按组招人的一个特点就是面试几轮不定,一般都是和组里的骨干一一见面,让大家觉得你不太差才可以。on site很顺利,题目也都不难。
3. Bloomburg: 统招。大B是非常想去的一家公司,传说逼格很高,整个面下来也确实如此。On campus面了一轮,两个面试官一个白练一个红脸,问了重复率很高的一道题,直接最优解答复,他们很高兴。On site的时候传闻如果面不到四轮就基本挂了,这个在我这得到证实。早上面试之前会发一张100刀的gift card,然后面试官过来领人。第一轮面的不错,谈笑风生。第二轮栽在了一个亚裔手上,看气场很像manager,非抓住c的东西不放,从头问到底。虽然面大B不一定要c和c++,但是如果简历里面出现,还是会被面试官抓住不放,几轮都是如此。所以对c++不熟,还是不要把相关项目放进简历了,哪怕列在最后一个也会被揪出来,因为面试官自己不懂java,所以肯定要去找自己明白的地方下手。第三轮是个hr,聊了之后被赶出。
4. Epic: 统招。前面面的不好,尤其是大B给我打击很大,于是海投各种公司,有点不淡定。Epic门槛比较低,电面瞎聊没有题,然后online做题,网上可以搜到无数真题,原封不动,看个三四个小时很足够了,最后的编程题居然不需要编译就可以了。On site就是一个tour,各种参观,话说他们的campus真的很漂亮。当地消费很低,Epic给的公司两三年就能买房了。全部行程的费用各种报销,非常大方,给个赞!
5. Yahoo:组招。学校careerfair,网申,内推都投过,等了两三个月终于有一个Director发信联系,介绍了自己的组,都是些非常火的big data的技术,问有没有兴趣面个试。拿到这个面试非常激动,Glassdoor上面搜了好多面经。电面两轮,果然和传闻一样,整个一个开心辞典,把java基础知识问了个底朝天。电面都没上coding,全是凭空胡侃。然后onsite去了sunnyvale的总部,我迟到了十分钟,烙印面试官看起来很忙的样子,有点不爽,上来也不寒暄,直接上题,记得是一道关于二叉树的,开始没想出来,后来他给了提示,还是勉强做出来了;第二轮白人director亲自上,开始问了些java虚函数的东西,我完全不会,他有点不爽;后来问了leetcode的原题,我用标准解法做出,他很满意,也把之前的不爽冲淡了些,开始谈笑风生,老白还是很容易满足的。
6. Ebay:组招。很早网申的,过了好久才有消息。一个国人manager的组,一看schedule,四轮面试三个中国人,心想妥妥的了。直接驱车前往onsite,和国人大哥们聊得很开心啊,题目也非常简单,是他们放水。。。心里一直觉得妥妥的。最后一轮是个烙印,描述了半天问题自己也没说明白,总是试图补充,二十分钟之后我断定这家伙是个二百五,对分布式key-value数据库完全不了解,还试图装作自己很懂。我那个无语了,都不想理他了。onsite之后被hr告知director要我去加面一轮,估计就是烙印那轮没过,报告了同样是烙印的director。去了之后director也没寒暄,直接出题,lc原题,我五分钟接触,然后他说this is a easy question,然后follow up,我想了半天写出来,他看了眼直接说very buggy,我当时就明白就是故意难为我,也不想和他follow up了。
7. AppDynamic:组招。三番的一家做网站性能分析的startup,非常有朝气,里面的人也非常牛逼。面我的都是senior,director级别的工程师,谈话很顺利,交流起来非常愉快,完全没有架子或者当面试官一口要吃掉你的感觉。startup的气氛我还是很喜欢的。现在想想startup style真的可以从细节当中体现出来。聊了很多开源项目,主要都是我在说遇到的各种bug,然后他们说,啊,这个bug是因为什么什么。。。顿时觉得被大神笼罩。
8. Nutanix:组招。非常有前景的一家公司,计划今年上市。面的偏前端网站的组,组里人不多,聊了六七个人,都非常愉快。有一轮techlead面,有一题卡住了,他直接告诉了我正确答案。感觉面试最后能不能中主要取决于组里有多缺人。
9. Linkedin: 统招。终于迎来了三巨头的第一站。面试之前重刷了lc,glassdoor上面面经又看了一遍,信心满满。L家的特点是题库小,原题重复率特别高,个人感觉把glassdoor做过一遍就差不多了。电面一轮,两个白人小哥,出了两道原题,我半小时那些,然后小哥就是,一般呢我们是要面五十分钟的,要不你再做一道,或者问问题。我果断说不做了,随便聊聊吧,心想做了两题已然拿下,万一第三题出了岔子就太亏了。onsite是一个campus day,早上大家先聚餐做游戏自我介绍,折腾两个小时,然后十点多才开始面试。一共四轮,一轮design,一轮纯聊天,两轮coding。前三轮都非常顺利,心想八九不离十了,把我带走吧。最后一轮coding三姐出了个题我一下子卡住了,她给的hint不多,可能自己也理解的不透彻,只是从某处找了题和答案过来考。我只能硬着头皮想,最后也没弄出来,三姐还说don’t worry,人挺好的,但是题真的是没做出来。开始还觉得三姐估计为难,结果回家一看glassdoor,擦,第一页第三题!!
10. Facebook: 统招。三巨头第二家,听说F今年大扩招,广发offer。临近毕业,和hr说时间比较赶,直接去onsite了,五轮。四轮coding,一轮manager,整体发挥不错,题目比较接近lc。有一轮国人面试官问对sql的底层了解多少,我顿时没话说了,如实答不怎么懂,然后就开始听他滔滔不绝,面试的最后还说good,我都不好意思了。国人大哥还是非常帮忙的。
11. Google: 统招。面试季的收官之战。说实话虽然刷了很多题,看了很多面经,听了很多算法课,但是面对G还是发虚的,原因就是题目太灵活多变,范围不确定,和面试官关系很大,一句话,就是看人品。所以面试之前还是抱着虚心求虐的态度去的。第一轮是个烙印面,出了题目和我讨论了一会,然后我开始coding,他说他要查查公司的邮件,让我不要介意。写完代码他问finished?我说yes,他花了十秒钟扫了一遍,就说好,开始用手机牌照了,完全没有要challenge我的意思,就这样水果了。第二轮国人大哥,非常帮忙,全程汉语,而且给了个灰常简单的题目,还被我写出几个bug,他也没在乎,改过来就好了。后面两轮都是老白,题目不难,也没有challenge。


一点小体会
1. 刷好题就完成90%了
一般技术面试前五分钟闲聊,可以当做热身,真正有用的是实打实的coding。遇到开心辞典一类的面试,基础知识也重要。极端的想,假如口语留意可以聊的风生水起,但是coding不过关,面试官还是会记下一笔。现有coding的硬实力,交流上面不太差就足够了。
2. 面到最后,面的最好
可以明显的感到公司招人时的心态是不一样的。一般公司都是前紧后松,开始筛选小心翼翼,只要最好的一类,然后过了一两个月,牛人都拿到offer然后拒了这家公司,hr发现名额没满,就开始放水。另外,个人觉得快到年底,面试官的心态越放松,出题难度有所降低。从自己的角度看,开始的几个面试因为没有经验,面试紧张,发挥不一定好,越是到了后面心里准备越充分,各种难题,硬场合,屎面试官都见多了,也就来着不拒了。所以我自己的策略是开始面入门级的,不是真心想去的公司,然后开始增加难度,挑战一下,面面startup。经过了极简单和极难,最后心态平和的去面最想去的公司。

最后
准备面试的过程中从地里获得了大量的信息和帮助,入职G之后希望帮助大家内推,尽自己的一份力。刷完了题,做好了准备的童鞋可以把简历和一小段英文自我介绍(自己的强项,优点)发到我邮箱,我一定第一时间帮大家内推。gneitui2015@gmail.com
非new grad请到https://www.google.com/about/careers搜下职位一起发给我吧。

Tuesday, March 17, 2015

Google面经



from here




这周之内刚刚面的,趁还没忘,记下来给大家分享一下。因为签了NDA不想混不下去,具体题目内容就不说了,大概以leetcode难度为参考说一下。

总体感受:难度不是特别大,着重用算法知识解决问题的能力(当然还有算法复杂度分析的方法)。个人觉得Cracking the Code Interview里三句话很重要:

1. 做过的题就老实说做过了;

2. 如果你想要做任何假设,请先和面试官确认,尽量别等他/她问;

3. 重新看一遍你找工作时给recruiter的简历,确保别人问到上面的每个项目你都说得出来。




早上第一位面试官(第一位就迟到了,差点误了整天的日程)好像比较junior,所以问的问题比较入门+标准:

1. (easy)二叉树输出

2. (easy)矩阵输出

note: 第二题上来就花时间想了时空复杂度最优的方法,所以也没什么follow-up的讨论。




第二位显然比前一位淡定多了,可能是看前一位问的太简单了,所以加了一点难度:

1. (easy/medium)大量数据找少量最大值

2. (medium)字符串分割相关

notes:

1. 第一题是常见套题,就不细说了;

2. 第二题写了一白板的code,不过我先讲了思路,然后follow-up questions也回答上来了,估计面试官还算满意。

3. 第二题限于面试官约束的数据结构,写出的不是平均时间复杂度最优的方法。




中间是午饭不叙。




第三位目测介于上午两位中间,还没看同事问过什么问题,就甩出了一个和上午第一位本质类似的问题。我老实说我已经答过了,他又甩出了这个问题的扩展版:

1. (easy/medium)二叉树输出的扩展版,区别在于二叉树里的数据都有规律,问怎么迅速输出某一个节点的值,我用了log(N)的方法(懒得算数学的情况下是最优的);

2. (easy)多路数据合并。

notes:

1. 第一题有follow-up是问怎么写test case测试我的算法是对的;

2. 第二题也是常见套题的变形,主要是实现细节;

3. 面试官问了很多简历上的问题。




第四位面试官感觉可能是四个人里最senior的,临时顶替另一位同事都毫无压力。只甩出了一个他自己的原创问题,看我怎么解决。
notes:

1. 问题细节不便透露,但总体来说是一个很开放的问题,他在不断观察你设定了什么假设,以及利用你的知识背景做出的什么样的决定;
2. 有什么疑问随时和面试官交流,在这种开放性问题里这个很重要;

3. 在面试官提示的时候积极思考解决方案,尽量不要让他指出你的bug,并给出合理的解决方案;

4. 这位面试官是street view组的,所以问的问题里面工程性的坑非常深,需要你做出很多合理假设,并规避一些可能存在的现实问题。