系统设计面试题目总结

java 使用心得

String.split()
Once you want to plit '.', you have to use it like below:
String.split("\\.")

 PriorityQueue que= new PriorityQueue(len,new Comparator(){
                public int compare(ListNode a,ListNode b){
                if(a.val < b.val)
                    return -1;
                if(a.val > b.val)
                    return 1;
                return 0;
                }
        }); 

How to sort an ArrayList.
Collections.sort(arrays, new Comparator(){
     public int compare(a, b){
     }
})

Number Validation

We start with trimming.

• If we see [0-9] we reset the number flags.
• We can only see . if we didn't see e or ..  E后面不能有小数点
• We can only see e if we didn't see e but we did see a number. We reset numberAfterE flag.
• We can only see + and - in the beginning and after an e
• any other character break the validation.

看leetcode一个题很好的解答 Simplify Path

其实理解题意比较困难，因很多corner case都不清楚
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".
题目就这些case，其实没有说清楚是遇到"/../"其实只退一层，遇到"."也不退，只是不显示这一层而已，用stack就可以解决这题
用"/"可以把string 分成很多份，如果最后是空的，就返回"/"

public String simplifyPath(String path) {
        String[] res = path.split("/");
        Stack st = new Stack();
        for(String s:res){
            if(s.equals(".")==true||s.equals("")==true){
                ;
            }
            else if(s.equals("..") == true){
                if(st.empty() == false)
                    st.pop();
            }
            else{
                st.push(s);
            }
        }
        String tes = "";
        while(st.empty() == false){
            tes = "/" + st.pop() + tes;
        }
        if(tes.length() == 0)
            tes = "/";
        return tes;
}

转 一个system design的帖子

发信人: flamingos (flamingos), 信区: JobHunting
标  题: 我的System Design总结
发信站: BBS 未名空间站 (Mon Sep  8 02:49:55 2014, 美东)

我的面试也结束了 因为知道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的同学
这有一个facebook talk讲storage的https://www.youtube.com/watch?v=5RfFhMwRAic

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
Structured Data(uses DynamoDB) vs Unstructured Data(uses S3)http://smartdatacollective.com/michelenemschoff/206391/quick-guide-structured-and-unstructured-data http://stackoverflow.com/questions/18678315/amazon-s3-or-dynamodb

10 给有兴趣深入研究的人看的
Mining Massive Datasets --讲很多big data和data mining的东西
Big Data: Principles and best practices of scalable realtime data systems --
twitter的前员工讲述如何处理实时数据

10 凌乱的资料 随便看看吧
http://highscalability.com/blog/2013/10/28/design-decisions-for
== 小结＝＝
看多了以后 你的最终目标应该是心里有了一个大框架 一个基本的distributed system
是怎么搭起来的 然后心里有很多if condition 如果要是满足这个条件 我应该用什么
技术 比如如果read heavy那么用cache会提升performance之类的 同时知道应该避免什
么东西 比如避免single point of failure 再比如时间和空间的tradeoff在read 
heavy的时候应该倾向于时间 Write heavy的时候倾向于空间等等

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

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

线性时间创建suffix tree

在复习string算法的时候容易遇到需要用suffix tree处理的题目，但是一直对如何创建suffix tree不是很清楚，看似很复杂的样子就不想继续深入看了。最近因为时间比较多，好不容易静心看了看一个牛逼的算法而且也不算太复杂难懂，在面试的时候虽然很难能写完整代码，但是至少能够写伪码。
数据结构
childern 是一个256位的node数组，start是连接这个节点的边start的index，end是结尾的index，因为所有的叶子节点的end会根据输入pos一直变化都string parse完毕，所以每个叶子的节点的end需要是一个存int的object。
全局变量

remainingSuffixCount 表示还需要处理的suffix，每次开始遍历一个字母的时候都需要把这个数加一，在处理完毕之后需要减1，不是每次遍历都需要处理，

activeEdge 也是 如果不需要回溯，activeEdge = 当前pos 否则 pos - remainingSuffixCount + 1

public class NSInteger{

    int value;

    public NSInteger(int i){

    value = i;

    }

}

public class Node{

   Node[] children;

   Node suffixLink;

   int start;

   NSInteger end;

   int suffixIndex;

}

遍历是从头开始的，而不是从最后一个，每次遍历的原则是如果这个字母是从root开始没有出现过，是一个新的字母就创建一个新的leaf node，例如abcabxabcd
前面三个遍历完的情况如下，下面遍历第四个字母a和第五个字母b，因为从root开始遍历

longest palindrome substring

自己能想到的最优算法就是把每个char作为中心，分别在奇数和偶数的情况下，外扩张找palindrome，算法复杂度是n平方
wiki出来的算法很牛逼，线性解，虽然不是最优的但是还是比较易懂
1. 首先为了避免处理两种情况，算法在输入string插入了特别符号“|”
2. 处理过程用了O(N)空间，可以算是dp解法