长兴二日游

其实去长兴是很久以前的事情了,话说可以去公费郊游应该是件很爽的事儿,但可我怎么也happy不起来:1、我已经2个周末没有休息了,好不容易盼来了一个周末,又要一大早去公司楼下集合去郊游。2、长兴又没啥好玩的,还不如去南京郊游呢,好歹可以顺道回家转转。当然了,我是没有反抗的权力的,老大一声令下,市场部的人全部都要去!好吧,我真的宁愿加班,有吃有喝有空调。
早上7点半集合,三个小时的车就到了长兴,四周无遮无挡的,大太阳明晃晃的照在脸上,戴着墨镜都没用。同行的mm一个劲的喊热的吃不消~一车人一下大巴就朝对面的小卖部杀过去,直接把店里冰镇的可乐和冰淇淋洗劫一空,那架势跟鬼子进村似的~
来之前听说住的是准3星的旅馆,我还想着这种小地方有标间就不错了,结果一打开房门,瞬间shock到了,居然是套房~ 里面一间是2张大床,外面一间有一个空调柜机和一张及其华丽的——自动麻将桌!哈哈,人生第一次见到自动麻将桌,一帮人直接坐下来开始搓麻将~ 这么一搓就是一下午加一晚上。。。我们不是来郊游的,我们是来聚众赌博的。顺便说一下打上海麻将还是挺好玩的,我很bt的胡了两次小七对~~
真正的游玩项目其实比较一般啦,号称会见到一行白鹭上青天的壮观景象,结果也只是看到零星的几只~ 姗姗同学总结的好:节假日,白鹭不上班,只有值班的。
时间过去的太久了,别的细节都不太记得了。只记得谁麻将打的比较好,谁手气比较臭,哈,具体的就不点名啦,不然损rp的~~ hoho

说说滤霸

这两天国内IT界最耀眼的明星显然就是绿坝-花季护航了。这么一款集流氓、严重侵犯知识产权、质量低劣的山寨软件无疑在挑逗着公众的娱乐底线。甚至一度怀疑是某一小撮别有用心的受反华势力资助的反动分子在造谣破坏党国形象。本来懒得发篇博客表表态,看了和菜头这篇博客后,还是决定为抵制这个东西出份力。以后如果修电脑碰上了这东西,自然手起刀落。
法律上的乱七八糟的问题漏洞撇开不谈,不离本行地说说技术。这里推荐一篇强文:绿坝-花季护航软件技术分析,应该是由网民像维基百科那样协同编写的。里面简要道出了滤霸的主要技术问题,比如极度脑残的密码保存。直接存密码MD5在一伪装成DLL的文本文件,I服了YOU,这帮严重缺乏山寨敬业精神富有娱乐精神的金惠公司。只要简单修改替换密码文件即可视密码为无物。
但更多的技术内幕不得不让人怀疑这个软件的潜在用途,比如应用程序监控和屏蔽。
另外值得担心的是,以如此薄弱技术班底开发出来的软件,显然很快就会被木马编写者盯上并制作一些利用软件漏洞进行传播运行的木马,从此成为肉鸡的乐园。不怀疑还会出现类似“绿坝专杀程序”的病毒,在删除绿坝的同时还顺带做做系统优化工作。

肉鸡

导师的项目借用了某公司的一台服务器对外服务,Windows2003 Server。需要用Windows是无可奈何的事情,虽然程序是用Java写的,试运行的时候也跑在Linux上,但一个比较重要的功能–导入数据需要处理access文件,而读取mdb文件在linux上没有什么成熟的方案,故只能迁就Windows。

拿到帐户登进去的时候被两个情况雷焦了。第一,查看系统属性的时候,发现装的竟然是雨林木风版的Windows。我们个人用户这么盗版也无所谓了,在公网上跑商业应用也用这个,看来真不怕微软的律师信。第二打开浏览器,居然跳出一个类似黄网的页面,哎,居然还中木马。这么没装杀毒软件防火墙的在公网上裸奔,还是需要一点勇气的。既然人家一直这么用都好好的,我也管不了了。

后来两次发现有骇客入侵,手动把骇客的帐号禁用了也就暂时相安无事。把这个情况报告给服务器管理者,似乎没啥反应。前天碰到一个比较狠的骇客,直接把两个管理员的帐号给干掉了。恢复后简单用360查了个木马,揪出来9个程序。

不知道下次服务器的沦陷会是多久以后,怕人家下次直接把数据库给干掉了,只能干瞪眼。

仙林运转记

今天去仙林转了一圈,不过很遗憾没有去南大,因为那里不通普通的公交车(除了一个定点班车,一天对开10班)。

仙林给我的感觉是,比较适合南大呆的地方,特别是相对建设落后的浦口高新区而言。虽然相比市区差别依然很大,但毕竟有名校的中学分校、大型社区和中大型的卖场,也还有肯德基,这些都是浦口不具备的,加上明年通车的地铁2号线,南大搬迁还是获得很多好处的。

20090607205.jpg

南邮,校门很大,但是感觉没什么特色

20090607208.jpg

文苑路东端西望。这条主干道上自西向东,在道路的北侧,排列着南师、南财和南邮

20090607211.jpg

仙境路仙林大道路口西望。高架桥上是地铁2号线东延线,远处是站台,暂名为学海路站。

20090607212.jpg

仙境路口上的地铁仙境路东站,原名中医药大学站,南大是唯一一个保住地铁站名的学校了。底站原来是体育学院站,现在改成了经天路站。

20090607213.jpg

从这里往东2公里,就是南大仙林。

20090607215.jpg

平时奄奄一息的166居然有这么多人坐,学生周末出行还是很可怕的。

20090607216.jpg

中医药的大门,也没什么特色。

20090607217.jpg

仙林灵山。山不在高,有仙则灵。

20090607220.jpg

仙林灵山公交底站。

20090607222.jpg

回城路上,坐97到火车站去。南财的大门,挺气派的,不愧是搞财经的。

20090607223.jpg

南师和南财之间的公路,通往312国道。图里还有138路公交车,仙林东郊是公交公司的天下,基本以D部的线路为主,很少看到中北雅高。

20090607224.jpg

南师的正门。不知为啥两边要这么大的保安室干嘛。

xljt.jpg

最后送一张仙林的交通图,参见此帖

安全

和菜头的博客我常看,前几天和菜头贴出一篇让我大跌眼镜的文章。当时早上还没起床,在床上用手机看的,看得我顿时睡意全无。

和老师举了一个例子:

2000个人,分为A、B两组。A组乘汽车往返北京—广州1000次。B组乘飞机往返北京—广州1000次。结束之后,哪一组更可能全部活着报道?

他们再分为C、D两组。A组乘汽车往返北京—天津1000次,每次1小时。B组乘飞机往返北京—青岛1000次,每次1小时。结束之后,哪一组更可能全部活着报道?

显然,和老师给大家透露的意思,第一个是飞机,第二个是汽车。单位里程的安全系数,飞机是最高的,这个有明确的数据支持;单位时间的安全系数却不一定,手里没有资料。下面是单位里程的安全系数的资料:

Deaths per billion kilometres
Air: 0.05
Bus: 0.4
Rail: 0.6
Van: 1.2
Water: 2.6
Car: 3.1
Bicycle: 44.6
Foot: 54.2
Motorcycle: 108.9

来源就不追究了。为什么统计数字上来说,飞机最安全?这往往有悖于直觉。飞机在数千米上万米以几百公里的速度飞行,想想都危险。原因在于,统计的单位是按里程计算的。拿和老师的第一个例子来说,从北京到广州,飞机虽然运行环境恶劣(高空高速),但挺一挺两个多小时就过去了;而火车至少需要20个小时,虽然运行环境比较稳定,但难免夜长梦多。这也是长痛不如短痛的道理。

但这个统计单位往往也是质疑者如和老师的攻击把柄。诚然,以每小时死亡率这个角度分析交通工具的安全系数,对于交通业内来说更加合理。但是这个结果来说对消费者而言毫无意义。消费者在选择交通工具的时候,对于安全的考虑不会是单位时间内所冒的风险,而是这个旅程给他带来的风险。对于一名需要从北京出差的广州的旅客而言,虽然飞机每小时死亡率比较高,但这种风险却被飞机较短的运行时间大大抵消了。对于乘客,每次出行的里程是基本固定的,而时间却是不固定的。乘客出行只会要求到1000公里外的某个地方,而不会出现要求乘坐3个小时的运输工具的需求。因此,对于乘客而言,有意义的统计单位还是单位里程死亡率。

Java的几个术语(覆写, 重载, 隐藏, 遮蔽, 遮掩)

这几天看Java Puzzler,被里面的题目折腾得死去活来,特别是标题里的几个概念。于是决定发篇小文澄清下几个概念。
覆写(Override)
即子类的实例方法覆写了父类的实例方法,即函数的多态。
陷阱1:覆写仅仅对于实例方法有效,对于属性和静态方法不适用。后两者的情况属于隐藏(hide)的范畴。覆写的函数调用时动态绑定的,根据实际类型进行调用;而隐藏的调用则是静态绑定,编译期间就确定了。
陷阱2:覆写要求父类函数的参数和子类函数的参数类型相同。举两个例子:

        public class Base{
                public void foo(Object a){}
                public void bar(int a){}
        }
        public class Derived extends Base{
                @Override
                public void foo(String a){}
                @Override
                public void bar(Integer a){}
        }

上面的代码能通过编译吗?结论是都不行。Java要求类型严格的一致,所以上面的例子实际上表现的是函数的重载。
正如例子中写的那样,对于Java5以上的版本,确定子类函数是否覆写了父类函数,只需要给子类函数添加一个@Override注释,如果子类函数并未覆写任何父类函数,则无法通过编译。
陷阱3:覆写要求父类函数的访问限制对子类可见(public/protected/package)。上例子:

        public class Base{
                private void foo(){System.out.println("base foo");}
                public void bar(){foo();}
        }
        public class Derived extends Base{
                public void foo(){System.out.println("derived foo");}
                public void static main(String[] args){new Derived().bar();}
        }

上面的例子将会输出base foo。子类并没有覆写父类的函数。
在Java虚拟机中,多态的调用通过invokevirtual和invokeinterface两条指令进行调用,前者用于类引用,后者用于接口引用。上面两个方法均是动态绑定。而invokestatic和invokespecial指令使用静态绑定。前者用于静态方法的调用,后者用于实例方法的调用,分为三种情况:第一种用于构造函数(<init>),显然构造函数不需要动态绑定;第二种情况用于调用私有的实例方法,也是上面这个例子里的情况,原因在于,既然这个方法不可能被子类方法覆写,所以直接使用静态绑定(不能推广到final关键字上);第三种情况用于super关键字,在子类方法中强行指定调用父类方法时使用super指代父类,但此类的调用JVM使用动态绑定,具体不再赘述,参见《深入Java虚拟机》第19章的内容。
重载(Overload)
重载这个技术,仅仅是针对语言而言,而在JVM中其实并没有重载的概念。函数的调用匹配本身是通过函数名+函数参数确定的,在匹配函数名后,再匹配函数参数。在选择相同名字的方法时,编译器会选择一个最精确的重载版本。举个例子

public class Main {
        public int a = 1;
        public static void main(String[] args){
                new Main().test(3);
                new Main().test(new Integer(3));
                new Main().test(new ArrayList());
        }
        public void test(int a){System.out.println("int");}
        public void test(Object a){System.out.println("object");}
        public void test(List a){System.out.println("intlist");}
}

上面的方法会打印int int intlist。第一个调用匹配了同为int,Integer类型的函数;第二个调用在寻找Integer类型的参数未果的情况下,把Integer自动拆箱,匹配到了int类型;第三个调用则匹配了最精确的类型List,而不是不精确的Object。如果我们增加一个Integer类型作为参数的函数:

public class Main {
        public int a = 1;
        public static void main(String[] args){
                new Main().test(3);
                new Main().test(new Integer(3));
                new Main().test(new ArrayList<int>());
        }
        public void test(int a){System.out.println("int");}
                public void test(Integer a){System.out.println("integer");}
        public void test(Object a){System.out.println("object");}
        public void test(List<int> a){System.out.println("intlist");}
}

则会精确匹配类型,打印int integer intlist。
再看一个例子,思想来自于Java Puzzlers #46

public class Main {
        public int a = 1;
        public static void main(String[] args){
                new Main().test(null);
        }
        public void test(int[] a){System.out.println("intarray");}
        public void test(Object a){System.out.println("object");}
}

这次的输出会是什么?答案是intarray。如果我们调用的是new Main().test(new int[0]),那么结果总是很好理解;而如果传递一个null,则就有违直觉了。关键在于,编译器总是需要寻找更加精确的类型,而匹配的测试并没有使用实参(参数的实际类型)进行匹配。对于编译器来说,null都可以是Object类型变量和int[]类型变量的合法值,而int[]变量可以是Object类型,但Object类型变量不一定是int[]类型,相较之下int[]更为精确,所以编译器选择了int[]。如果一定要让编译器选择Object,那我们只需要通过new Main().test((Object)null)的形式即可。编译器在重载的时候只认形式参数,不认实际参数。
如何匹配重载函数的代码,Spring里有一个查找constructor的例子,在org.springframework.beans.factory.support.ConstructorResolver的autowireConstructor()函数,以前曾经在Spring配置的时候发生过问题Trace到这里。这个匹配算法使用了贪心的思想(代码里这么注释的),对于每个候选的构造函数都通过一个评估函数(getTypeDifferenceWeight())评估与调用参数类型(constructor-arg里配置的)的相似度,最后取最相似的候选函数。有兴趣的朋友可以自己看看。
隐藏(Hide)
隐藏的概念应用于父类和子类之间。子类的域、静态方法和类型声明可以隐藏父类具有相同名称或函数签名的域、静态方法和类型声明。同final方法不能被覆写类似,final的方法也不能被隐藏。考虑下面的代码:

class Point {
        int x = 2;
}
class Test extends Point {
        double x = 4.7;
        void printBoth() {
                System.out.println(x + " " + super.x);
        }
        public static void main(String[] args) {
                Test sample = new Test();
                sample.printBoth();
                System.out.println(sample.x + " " + ((Point)sample).x);
        }
}

上面的代码将打印4.7 2 \n 4.7 2。子类中的x变量隐藏了父类中的x变量,尽管两个变量类型不同。要访问父类中的变量必须使用super关键字或者进行类型强制转换。下面的代码展示了实例变量隐藏静态变量:

class Base{
        public static String str = "Base";
}
public class Main extends Base{
    public String str = "Main";
    public  static void main(String[] args){
        System.out.println(Main.str);
    }
}

上面的代码不能正确编译,原因是子类中的实例域把父类中的静态域给隐藏了。如果去掉子类中str的声明就可以正确编译。
静态方法和类型声明的隐藏的情况,和域隐藏的情况大同小异,不再给出具体的例子。
遮蔽(shadow)
遮蔽(shadow)指的是在一个范围内(比如{}之间),同名的变量,同名的类型声明,同名的域之间的名称遮蔽。我们最常见到的遮蔽就是IDE为我们自动生成的setter:

public class Pojo{
        private int x;
        public void setX(int x){
                this.x = x;
        }
}

即使是变量类型不相同也可以遮蔽。在上个例子中把setX(int x)的参数类型改为short,也能通过编译。函数的遮蔽常见于匿名类里的函数遮蔽原先类的函数等情况。
上面的几种遮掩比较常见,下面情况就比较特殊了(来源于Java Puzzlers#71)。其中Arrays.toString()方法提供了多个重载版本,可以方便的把基本类型数组转换为字符串。

import static java.util.Arrays.toString;
public class ImportDuty{
        public static void main(String[] args){
                printArgs(1, 2, 3, 4, 5);
        }
        static void printArgs(Object... args){
                System.out.println(toString(args));
        }
}

结果是不能编译,并且返回的信息告诉我们,Object.toString()方法不适用。这是为什么呢?原因在于,Object.toString()方法把Arrays.toString()方法给遮蔽了。下面的代码虽然可以编译,但运行时会提示找不到main方法入口:

class String{
}
public final class Main{
        public static void main(String[] args){
        }
}

原因在于我们自定义的String类型把java.lang.String类型遮蔽了。而如果强行加入import java.lang.String;语句,则不能通过编译。
遮掩(obscure)
遮掩很容易与遮蔽(shadow)混淆。其最重要的区别在于,遮蔽是相同元素之间的遮蔽,变量遮蔽变量,类型声明遮蔽类型声明,函数遮蔽函数。而遮掩却是变量遮掩类型和包声明,类型声明遮掩包声明。
遮掩的例子不多,看下面的例子,来自Java Puzzlers#68:

class ShadesOfGray{
        public static void main(String[] args){
                System.out.println(X.Y.Z);
        }
}
class X{
        static class Y{
                static String Z = "Black";
        }
        static C Y = new C();
}
class C{
        String Z = "White";
}

上面的例子不仅能通过编译,还将打印White。原因就在于当一个变量和一个类型具有相同名称,且具有相同作用域时,变量名优先级大。而类型的声明又具有比包声明更高的优先级。下面一个例子也不能通过编译:

public class Obscure{
        static String System;//变量遮掩了java.lang.System类型
        public static void main(String[] args){
                System.out.println("hello, obscure world!");
        }
}

小结
只有覆写是运行时的技术,另外其他的技术都是编译期的技术。
除了重载、覆写和作为setter的遮蔽,其他特性都强烈不推荐使用,这只会给你和你的继任者带来无穷无尽的麻烦,事实上,重载我认为也少用为妙,特别是结合了使用不确定参数个数的”…”函数的重载,会使你回头看代码时晕头转向。
p.s. 准备技术笔试/面试的语言类题目,C/C++的话,程序员面试宝典里有一些题目,另外就是C++的那些effective系列的书,具体还请C++达人列举(被点名的同学请自觉回帖)。Java的话,首推Joshua Bloch的Effecitve Java;第二就是Java Puzzlers,而后者其实更适合要参加技术笔试面试的同学。剩下的书,应该还有Practical Java,不过我没看过。

百度在线笔试(实习)

今天同学参加百度在线笔试,有幸分享了一下题目。每道题我都做了一些思考,一并记录下来。其中可能有一些重大的纰漏,也欢迎高手指正。

一、编程题(30分)
输入:N(整数)
输入:数据文件A.txt,不超过6条记录,字符串长度不超过15个字节
文件格式如下:
字符串\t数字\n

说明:
每行为1条记录;字符串中不含有\t。
数字描述的是该字符串的出现概率,小于等于100的整数。
多条记录的出现概率之和为100,如果A.txt不满足该条件,程序则退出;
如果文件格式错误,程序也退出。

要求:
编写一个程序,输入为N(正整数),读入文件A.txt,按照字符串出现概率随机地输出字符串,输出N条记录

例如:
输入文件A.txt
abc\t20
a\t30
de\t50
输入为:10

即 abc有20%的概率输出,a有30%的概率输出,de有50%的概率输出,输出10条记录
以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
de
abc
de
a
de
a
de

二、算法题(35分)
题目描述:
设有n个正整数,将它们联接成一排,组成一个最小的多位整数。

程序输入:n个数
程序输出:联接成的多位数

例如:
n=2时,2个整数32,321连接成的最小整数为:32132,
n=4时,4个整数55,31,312, 33 联接成的最小整数为:312313355

[题目要求]
1. 给出伪代码即可,请给出对应的文字说明,并使用上面给出的例子试验你的算法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。(非常重要)

三、系统设计题(35分)
在一个有1000万用户的系统中,设计一个推送(feed)系统。以下是一些预定义概念
1、用户:在这个系统中,每个用户用一个递增的unsigned int来表示user id(简写为uid);则uid的范围是从1到1000万的正整数。
2、好友:用户之间可以形成好友关系,好友是双向的;比如说uid为3和uid为4的两个用户可以互为好友。每个用户好友的上限是500个;用户之间的好友关系可以被解除
3、活动:每个用户只能发文章;文章可以被作者删除,其他人不能删除非自己发表的文章;每篇文章通过一个blogid表示。
4、feed:我们希望,每个用户可以看到他所有好友的活动列表,在这个简化的系统中就是所有好友的文章更新列表。
5、访问量要求:所有feed访问量每天在1亿量级;所有的blogid增加量每天在百万量级。

题目:请在以上限制条件下,设计一个高效的feed访问系统。

要求:
1、能够尽快的返回每个用户的好友feed列表,每个用户可以最多保留1000条feed;feed的展现按照时间倒排序,最新的在最前面
2、用户删除某篇文章后,被推出去的feed需要及时消失。即每个用户看到的好友feed都是未被删除的
3、尽可能高效。

我的解答:

一、这个题目感觉意思有歧义。什么是”按照字符串出现概率随机地输出字符串,输出N条记录”?可以有几种理解。第一,每次掷骰子,掷出了哪个就输出哪个,不管前面输出了什么。第二,要考虑前面出现的字符串。按照题目里的例子,如果前面输出了两次abc,那接下来的无论随机出了什么数,都不能输出abc,最后的结果在数量上符合开始给的概率条件,只是顺序有所不同。这让我想起了排列组合里的袋中取黑球红球问题。把字符串abc,a,de当作2个红球,3个黑球和5个白球,放入袋中。每次拿一个球出来,并记录拿出球的颜色。第一种情况就是拿出球后,把球放回袋中进行下一次抽取;而第二种自然就是不放回的抽取。

顺着百度的笔试不可能那么弱智的想法,同时给出的例子也符合第二种情况的形势,就照着第二种思路往下做。这个题目在从鼓楼到浦口的鼓扬线上最近刚看过,就是编程珠玑II(More Programming Pearls) ,第13章的内容(绝妙的取样)。对于这个题,就是给出abc*2, a*3, de*5,输出随机排列。比较笨的算法就是每次得到一个随机数,如果这个随机数代表的球已经耗尽,那就取下一个随机数。这样的缺点是效率低,越往后效率越低,基本是在拼RP。还是拿例子说事儿,如果随机数为1-2,则输出abc,3-5输出a,6-10输出de。如果到了第9次,还剩下一个abc没输出,则要一直随机到出现1,2为止才结束。

第二种办法是Floyd提出来的(似乎就是那个Floyd-Warshall)。算法如下:

S = []
for j= 1 to N do
        T = RandInt(1, j);
        if T is not in S then
                prefix T to S
        else
                insert J in S after T

不过这个题目还有一个问题:对于每个字符串,生成的期望个数并不一定为整数。例子中的N改成5的话,那就是期望输出1.5个a和2.5个de,随机序列自然没法搞。这个时候回到第一个方法仍然可以做,不过题目也因此解释不通了。同学的解释是,如果是期望输出1.4个a和2.6个de,这一个a和de的争议值,在2/5的情况下输出a,剩下的情况输出b。不过我们其实是没有理由把这个不确定的情况限制在一个整数单位区间里的,即对于1.4个a和2.6个de,必须输出1a+3de或者2a+2de才算合法输出,而把4de,3a+1de的情况定位非法。我觉得这块说不同,所以不需要考虑非整数的不确定情况(如果直接四舍五入到整数,还是算整数的确定情况的)。

二、这题我没怎么考虑。同学的思想在于,把n个正整数按优先级排个序,然后按照排序的结果从小到大排列组成最小的整数。注意这个排序并不是普通的算术排序,而是基于一定的规则。比较的时候把两个数字当成字符串进行字典排序,如果一个数字正好是另外一个数字的前缀的时候,去掉较长字符串的前缀,继续进行比较,直到分出胜负。当然也有旗鼓相当的时候,比如31和313131,这两者的优先级即相同。

时间复杂度,每次比较的平均时间复杂度为O(1),假设输入为随机整数;排序使用快排,复杂度为O(nlgn),所以最终时间复杂度为O(nlgn)。空间复杂度就是O(n)。

算法证明的话我倒是一时半会儿没搞出来。

三、考虑了很久还是决定用数据库做,设计表。完全没有海量数据的表结构设计的经验,因此都是靠感觉来。没用什么技巧,除了数据库的水平分库。

数据库结构设计为4张表,结构如下(引用只是表示关联关系,并非加上外键约束):
User
int uid#主键
char(12) username
Friend
int uid#用户uid,引用User.uid,加索引
int fuid#朋友uid,引用User.uid,加索引
Blog
int blogid#主键
int uid#发表用户uid,引用User.uid,加索引
varchar(60) title
text content
datetime publish_time
Feed#存储每个用户的好友feed列表
int uid#引用User.uid,加索引
int blogid#引用Blog.blogid,加索引
varchar(60) title#可有可无,根据生成Feed是否需要Feed标题决定

在存储方面,Friend表和Feed表数量较大,因此采用水平分库存储的形式。即Friend表分散在几个数据库内,按照第一个uid的最后几位进行划分。如有10个数据库,即可根据个位数映射到0-9号数据库上。同理可得Feed表的存储方式,按照uid进行水平分库。

如果用户a和用户b是好朋友,则在Friend表中添加(a,b)和(b,a)两条记录,分别添加到a,b所属的库里。解除关系的话删除这两条记录。

用户发表文章的时候,首先在Blog表添加一条记录;第二,查询Friend表得出当前用户的所有好友,然后给Feed表添加记录,格式为(好友id, blogid, title),一共添加好友个数条记录。第三查询所有好友的Feed数记录,如果Feed超过了1000条,则删除该好友最早的一条Feed。第二第三步可以根据好友uid,把存储在相同库的好友Feed在同一次操作里批量添加/查询/删除。

用户要得到自己的Feed列表,只需要先计算自己的uid属于哪个数据库,然后从该数据库里取出所有的Feed记录,即可以快速得到Feed列表,只需要一个数据库查询,不需要做表间的连接操作。

用户删除文章的时候,把Feed表里blogid等于目标文章id的记录都删除。

IBM面经(电面)V2

经历了昨天的英文折磨后,今天特意准备了几个关键的问题,有关problem-solving和project management。但面试往往就是出其不意。今天的电面全中文,问的问题也比较general,和个人的特质、做事的风格这些相关,更像是非技术的面试,所以问题也没回忆起几个。当然今天面试的很可能是部门经理,所以问题也不会一直围绕technical stuff。

过程比较顺利,虽然我的时间其实不是合他的胃口,但面试官还是说会考虑给我intern offer。和ebay一样,被hold了。

面试结束,宿舍兄弟们纷纷表示我很有希望就直接留在IBM,直接喊我IBM男。的确从开发的东西(Java,Eclipse,Web)这个角度而言,专业基本对口;而这年头在上海(剔除了SUN)、大量用Java(很多外企还是主打C/C++)、还招人(SAP去年一个都没招)的大型外企似乎也已经不多了,除了BS我的ebay,还能想起来的还有大摩,Oracle似乎在上海没有R&D。其他符合上面条件的公司欢迎大家补充。

另外老板这边稍许还有些不确定。大三的考试结束应该就不会在继续开发了,暑假的工作应该以维护为主,出了啥子问题也不用on-site。开学了以后找个周末做彻底的work transfer。希望会是这个样子,不要再横生枝节了。

IBM面经(电面)V1

上上周周末参加的笔试,考得感觉一般,很多题目在接下来一周的复习算法和Java的过程中发现自己做错了。这周周一周二发面试通知,但BBS上的消息说IBM把除京沪穗三地以外的学生都BS了。正在残念之时,2号(周二)下午通知了3号上午电面。

因为以前本科的时候面过一次,所以这次没准备啥就上阵了。一开始上来做一个英文的intro,脑子空白了一会儿,嘴里开始蹦单词,手忙脚乱的找电脑里的self intro。对付完这个,没想到下一个还是英文问题。这时我还不知道今天是全英文面。

问题基本是围绕简历来问的。问完了我上次实习的项目,下一个就是Java Web的经历,让谈了谈APIS是干啥的。说到Web,问我对Dojo熟不熟,我只好说我没用过,ExtJS倒是知道咋用。每次我回答完问题,感觉他没有听到他想要的答案,于是就有一段沉默。我只好说So that is something about…来圆场。

技术问题问了Java Threading和数据库查询分析性能调优。第一个糊过去了,第二个实在没做过,扯了一个做项目时用到的Profiling。

小结:对全英文面试完全没准备,每次听到他问:Do you have any exp in …就开始头皮发麻。虽然基本都有经验,但是英文表达跟不上。

结论:对一些很可能问到的英文问题,做事先的准备。比如你解决一个问题的经历,如何管理团队,如何面对变更,项目的简介以及其中的贡献(后面两个之前都有准备,不过似乎还不太够)。

结果:感觉一般,但下午接到了二面通知。4号早上11点。所以,还会有V2。

p.s. 发现yingjiesheng上基本没啥消息,饮水思源倒是好几屏的帖子了。小白。。俺赤裸裸的伸手要你的sjtu号。。。