Saturday, September 27, 2014

欢迎参加『IT面试这点事儿』校园行第四期!网上同步直播





时间:Oct 12, 2014 (Sun) 3pm to 5pm. 
地点:UW Savery Hall (SAV) 264. Google MapUW campus Map.
内容:亚马逊,微软,Google,Facebook,Groupon等工程师为你详细介绍IT面试的现状,流程和技巧。帮助你早日拿到offer!
特邀嘉宾,Microsoft Imagine Cup 2008 冠军 Leon Liu也会与大家分享经验。
网上同步直播:请使用Google Hangout加入baozitrainingblog@gmail.com

更多详情请关注:http://baozitraining.org/video.html



Tuesday, September 16, 2014

Regular Expression Matching Problems 1

包子IT面试培训 助你拿到理想的offer!

有问题,问包子!Got question? Ask Baozi!


这篇博文我们探讨一下regular expression matching的问题,我们先由一道简单的题入手


[例题1]

Given a string of 1, 0 or ?, return all the matching strings that ? could be either 0 or 1.

For example,

input : 1??

output: {100, 101, 110, 111}.

input: 100100?00?

output: {1001000000,1001000001,1001001000,1001001001}

[思路1]

我们最直观的想法就是逐个字符扫描input. 当input里字符是0或者是1就原样输出. 问题在于当字符是?时我们该怎样处理. 这里就用到recursive编程方法最基本的套路:

分支加存储

所谓分支就是定义一个recursive function,让它的param list包含input和下一个input里访问字符的位置。当遇到可wild card字符时,对于wild card可替换的每一个字符,都call一下recursive function。所谓存储就是把这些用不同字符替代的情况都存储起来。一般来说,可以在param list加一个string表示部分结果。这样当我们访问完input里最后一个字符以后,输出该部分结果(现在是一个有效结果)。而且,当每一层recursive call返回以后,都删除这个recursive call所产生的替代字符,以便下一个recurisve call的替代字符使用

[代码1]
public static void returnAll(String input) {
        if(input == null || input.isEmpty()) {
            return;
        }
        
        StringBuilder current_string = new StringBuilder();
        returnAllRecursion(input, 0, current_string);
    }

    public static void returnAllRecursion(String input, int current_location, StringBuilder current_string){
        if (input.length() == current_location) {
            System.out.println(current_string);
            return;
        }
        
        while (input.length() > current_location && input.charAt(current_location) != '?') {
            current_string.append(input.charAt(current_location));
            current_location++;
        }
        
        if (input.length() == current_location) {
            System.out.println(current_string);
            current_string.deleteCharAt(current_location - 1);
            return;
        }
        
        if (input.charAt(current_location) == '?') {
            current_string.append(0);
            returnAllRecursion(input, current_location + 1, current_string);
            current_string.deleteCharAt(current_string.length() - 1);
            current_string.append(1);
            returnAllRecursion(input, current_location + 1, current_string);
            current_string.deleteCharAt(current_string.length() - 1);
        }
    }
    
    public static void main(String[] args) {
        returnAll("0100");
        System.out.println("---------------");
        returnAll("01??");
        System.out.println("---------------");
        returnAll("???0");
        System.out.println("---------------");
        returnAll("????");
    }


[思路2]

为什么要提出思路2呢?因为recursive call消耗大量stack空间,所以有时面试官要求不用recursive求解。

其实,大家知道recursive call原理就是用stack来储存function call信息,那我们就可以用stack来模拟compiler做的事情。而且,我们只在stack里存贮我们需要的信息,比如这道题目里存贮究竟?字符是当作0还是1,然后用stack入栈模拟我们进到更深的一级recursive call,而用出栈模拟我们退到上一层

[代码2]
public static void returnAllUsingStack(String input) {
        if(input == null || input.isEmpty()){
            return;
        }
        
        Stack positionToReVisit = new Stack();
        positionToReVisit.push(-1);
        
        StringBuilder currentString = new StringBuilder();
        int currStartPosition = 0;
        
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '?') {
                positionToReVisit.push(i);
                currentString.append(0);
                break;
            }
            currentString.append(input.charAt(i));
            currStartPosition++;
        }
        
        if (currentString.length() == input.length()) {
            System.out.println(currentString);
            return;
        }
        
        while (!positionToReVisit.isEmpty()) {
            for (int i = currStartPosition + 1; i < input.length(); i++) {
                if (input.charAt(i)== '?') {
                    currentString.append('0');
                    positionToReVisit.push(i);
                } else {
                    currentString.append(input.charAt(i));
                }
            }
            
            if (currentString.length() == input.length()) {
             System.out.println(currentString);
            }
            
            currStartPosition = positionToReVisit.pop();
            
            if (currStartPosition == -1) break;
            
            currentString = new StringBuilder(currentString.substring(0, currStartPosition));
            currentString.append('1');
        }         
        
        return;
    }

[思路3]

其实这个题目完全可以像解决powerset一下,列举出所有的2^n种可能性。
[代码3]


public static void matchingQuestionMark(String s) {
        if (s == null || s.isEmpty()) return;
        
        List questionMarkIndex = new ArrayList();
        int totalQuestionMarkCount = 0;
        
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '?') {
                totalQuestionMarkCount++;
                questionMarkIndex.add(i);
            }
        }
        
        if (totalQuestionMarkCount == 0) return;
        
        for (int i = 0; i < (1 << totalQuestionMarkCount); i++) {
            StringBuilder sb = new StringBuilder(s);
            int j = 0;
            int temp = i;
            while (j < totalQuestionMarkCount) {
                int index = questionMarkIndex.get(j);
                if ((temp & 1) == 0) {
                    sb.replace(index, index + 1, "0");
                } else {
                    sb.replace(index, index + 1, "1");
                }
                j++;
                temp = temp >> 1;    
                
            }
            System.out.println(sb.toString());
        }
    }

Thursday, September 11, 2014

How to prepare system design questions in a tech interview? | 如何准备系统设计题目?




包子IT面试培训 助你拿到理想的offer!

有问题,问包子!Got question? Ask Baozi!


如何准备面试中的系统设计问题一直都是包子的学员,尤其是fresh new grad比较头疼的一个问题。我们的好朋友在mitbbs上面与大家分享了他准备系统设计方面的一些资料和心得,包子在这里和大家再一次分享一下,也感谢我们的好朋友允许我们在这里转载,希望对正在找工作的同学有所帮助。

【转载自mitbbs

我的面试也结束了 因为知道FLAG这类公司都会问到System Design的问题 所以这次面
试着重准备了一下 在这里分享给大家 如果有不对或者需要补充的地方 大家可以留言

这里说的System Design和OO Design不同 System Design在FLAG以及很多大公司中主要
是design scalable distributed systems 这里只讨论如何准备这种题目

== 入门 ==
对于0基础的同学们 下面的资料可以按顺序开始看
1. http://www.hiredintech.com/app#system-design
这是一个专门准备面试的网站 你只用关心system design部分 有很多的link后面会重
复提到 建议看完至少一遍

2. https://www.youtube.com/watch?v=-W9F__D3oY4
非常非常好的入门资料 建议看3遍以上!
这是1里面提到的资料 是Harvard web app课的最后一节 讲scalability 里面会讲到很
多基础概念比如Vertical scaling, Horizontal scaling, Caching, Load balancing,
Database replication, Database partitioning 还会提到很多基本思想比如avoid 
single point of failure
再强调一遍 非常好的资料!

3. http://www.lecloud.net/post/7295452622/scalability-for-dummies-part-1-clones
1里面提到的 Scalability for Dummies 还算不错 可以看一遍 知道基本思想

结束语:当你结束这一部分的学习的时候 你已经比50%的candidate知道的多了(因为很
多人都不准备 或者不知道怎么准备system design) 恭喜:)

== 进阶 ==
这一部分的资料更加零散 每个看的可能不一样 但是你每多看一篇文章或者一个视频 
你就比别人强一点
这部分你会遇到很多新名词 我的建议是每当你遇到一个不懂的概念时 多google一下 
看看这个概念或者技术是什么意思 优点和缺点各是什么 什么时候用 这些你都知道以
后 你就可以把他运用到面试中 让面试官刮目相看了

4. http://highscalability.com/blog/2009/8/6/an-unorthodox-approach-to-database-design-the-coming-of-the.html
Database Sharding是一个很重要的概念 建议看一看

5. http://highscalability.com/all-time-favorites/
这个里面会讲到很多非常流行的网站架构是如何实现的 比如Twitter, Youtube, 
Pinterest, Google等等 我的建议是看5-6个 然后你应该已经建立起了一些基本的意识
还有知道了某些技术和产品的作用和mapping 比如说到cache你会想到memcached和
Redis 说到
load balancer你会想到 Amazon ELB, F5一类的

6. http://www.infoq.com/
5里面很多的文章都会有链接 其中有很多会指向这个网站 这里面有很多的tech talk 
很不错 可以看看

7. https://www.facebook.com/Engineering/notes
Facebook非常好的技术日志 会讲很多facebook的feature怎么实现的 比如facebook 
message:https://www.facebook.com/notes/facebook-engineering/the-underlying-
technology-of-messages/454991608919 建议看看 尤其是准备面facebook的同学

8. 一些国内网站上的资料
http://blog.csdn.net/sigh1988/article/details/9790337
http://blog.csdn.net/v_july_v/article/details/6279498

9. 最后一些概念很有用 都是我再看这些资料的时候发现的 如果你没有遇到或者查过 
建议查查
Distributed Hash Table
Eventual Consistency vs Strong Consistency
Read Heavy vs Write Heavy
Consistent Hashing
Sticky Sessions

== 小结==
看多了以后 你的最终目标应该是心里有了一个大框架 一个基本的distributed system
是怎么搭起来的 然后心里有很多if condition 如果要是满足这个条件 我应该用什么
技术 比如如果read heavy那么用cache会提升performance之类的 同时知道应该避免什
么东西 比如避免single point of failure 再比如时间和空间的tradeoff在read 
heavy的时候应该倾向于时间 Write heavy的时候倾向于空间等等

你总结出来的和我总结出来的大框架和if conditions肯定不完全一样 但因为system 
design本来就是一个open ended question 所以不用害怕 能够自圆其说 就不会有问题

最后 本文纯属抛砖引玉 如果有大牛发现有错误或者有补充 欢迎留言 大家一起讨论

== FAQ ==
1. New Grad需要看System Design么?

答案是it depends. 有的公司会考system design 有的公司只考到OO design 有的公司
压根不考 当然 考到的公司对new grad的期望值会稍微低一点 但是 你有这么一个机会
能让你gain leverage over other candidates why not? 为什么要让自己在面试前害怕
面试官出system design的题目呢?

Sunday, September 7, 2014

有问题,问包子!Got question? Ask Baozi!






包子IT面试培训 助你拿到理想的offer!

有问题,问包子!Got question? Ask Baozi!


As commonly requested from Baozi’s Facebook and Wechat group, we are now accepting interviews questions that you find challenging to solve.

Please send us the detailed interview questions through either of the following ways:

WeChat Group: baozitraining,
Facebook: https://www.facebook.com/baozitraining

Team Baozi