Tango的面试题记录

最近一共去了三家公司面试,Honeywell、快的打车和 Tango。前两家公司的面试太水了直接忽略,都是些什么乱七八糟的问题嘛。还是 Tango 的面试比较靠谱,不过由于本人能力有限还是挂了,那么在这里记录下面试的问题以供大家和我今后参考。

 

(1)第一面

一上来就要写一个 BlockingQueue 的实现(也就是队列满的时候,把执行入队操作的线程阻塞掉直到有空位置,出队操作如果没元素也阻塞掉,直到有元素),我一听大喜,正好看过 JDK 的 ArrayBlockingQueue 的实现。要求以下两个方法:

interface BlockingQueueImp<E> {
	
	public void add(Collection<? extends E> items);
	
	public Collection<? super E> get(int count);
	
}

原来稍微改造了一下,一次性要操作多个元素,不过没有关系,大致思路是一样的。使用一个 ReentrantLock 和两个 Condition 就可以啦。不过我在写这个程序的时候犯了两个错误,就是 Condition 的对应方法是 await() 和 signal(),我写成 wait() 和 sign() 了,被面试官鄙视了一下。而且,应该要调用 signalAll() 而不是 signal(),面试官提示我了,还问为什么不能用 sign() 还好答出来了他才勉强给了一个“多线程掌握得不错”的结论。

然后又问了一下 java 里面相关的类,比如问 HashTable 是怎么保证线程安全的。我说用 CAS,他说不是,我说难道是锁整个哈希表?他说没错,ConcurrentHashMap 才是 CAS。我一想我擦,我一个做 C# 的我咋记得那么多 Java 的类库。然后他就说既然说道了 CAS,要我解释下。我说底层就是用 CompareExchange ,然后他又说不是 Swap 吗?我说就是用硬件上的 CompareExchange 实现的,目测他也搞不清,所以也没多问了。

接着问了一些 SQL Server (他们用 MySQL)方面的问题,比如怎么性能调优,ACID,隔离级别什么的,都是一些很弱智的问题。

接着又回到了算法上,比如 redis 是怎么实现 Hashmap 的,怎么进行 rehash 和迁移,为什么要用跳跃表而不是平衡二叉树。

最后要我设计一个弹幕系统,结果我说的和他想的不一样,他那叫啥弹幕嘛,整个一个聊天室。接着他又问怎么做聊天室呢?我说了一堆,然后他又扯到 socket  上问我怎么通信。我说上学的时候用过,不就是 listen,accept,然后就可以发数据了吗?他说看来你确实忘光了。我一想,尼玛,socket还能怎么连?目测他自己也不知道。

总结:这个面试官主要想表现得他很牛B,没有他不知道的。如果有他不知道的就转移话题或者和你胡扯,比如他说的 CAS,而且我觉得他数据库学得也一般,要不怎么问隔离级别哪个并发程度高这种问题。而且最不能让我接受的是我不管回答什么他一直在摇头,然后过一会又说,对,是这样。搞得别人什么都不会他什么都知道一样。

 

(2)第二面

第二面的面试官就非常和蔼可亲,一直笑呵呵的。刚开始问了一些我原来公司的情况,还聊了一些项目的问题,然后开始聊天。搞得我以为技术面已经通过了,他是经理,所以随便聊天就好啦。结果最终证明是我高兴得太早了。

没过多久就进入正题,问了一些 Java 里面多线程的最基本的问题,比如 wait() 和 sleep(),没有对象锁去调用 wait() 会怎么样啊一些很弱智的问题。然后又问了泛型,比如<?>和<Object>的区别,<? extends E>的意思等等。后来他想要我写一个 Comparator ,我说我一般直接写 lambda,然后他就没追问了(目测他不会),他表示他们还在用 Java 6。

接着就开始悲剧的算法题了:

有一个整数数组,实现一个方法,求这个数组的连续子串元素间的或运算一共有多少种结果。

比如我们有数组 A = {1, 2, 5, 7, 9},其中 {1}, {2}, {2,5}, {2,5,7,9} 等多种子串,对于 {2,5,7,9},记 x=2|5|7|9。求这些子串求得的 x 一共有多少种不同的取值。

如果说我之前的表现都还不错(至少称得上符合要求)的话,那么这道题我真的跪了。没想出来倒不是问题,关键是面试官一直在给我提示我还是没想到,最终他把题目的解法告诉我才恍然大悟。这里就不说具体解法了,大家可以试试,他给的解法时间复杂度是 O(n),空间复杂度是常数 O(1),确实比较好。

如果说我这道题做出来了,那面试肯定没有问题了,关键是…… 唉…… 他看我没做出来,直接把我赶走貌似不太好,于是接着出题。

求约瑟夫环的问题,要求O(1)。这个题目每本书上都有,我就不说了。

他看我貌似表现得不好(主要是被那个求子串的题目搞晕了),给我出了一道简单的:

有一个字符串,其中只有 a、b 两种字符,比如 abbaaabaabba。任取其中的一个子串,比如”aabaabba”,把连续的重复的元素压缩成一个,就变成了”ababa”。如果压缩后字符串是回文的,就称这个子串是“好的回文子串”(如果取的子串是”baaabaa”,压缩后变成”baba”,不回文,就不是“好的”)。求这个字符串一共有多少个好的回文子串。

经过大约3分钟“艰苦卓绝”的思考(其中还有他“关心”的问“你在想什么”),总算是想到了方法。这个题目是如此简单,我应该很快就能反应出来,不过由于前面的题目的“洗礼”导致我反应迟钝了不少。

后来他继续追问:如果要求得有多少个奇数长度和偶数长度的子串怎么办呢?还好我此处没有SB,稍微挽回了一点颜面。不过最终我写程序的时候把奇数和偶数的情况搞反了,他也提了出来。然后就面试结束了。

 

可想而知结果是要我等通知,那就意味着跪了。

总结起来,其实我这次面试原本是比较有希望的,可是该死的第一个算法题没想出来(最可恶的是他提示了这么多还没想出来),而后面他给的那个简单的题还犯了个小错误,那么挂掉也是在情理之中。

猎头原来也推荐了两个人去面试,让我奇怪的是为啥他们的题目都是那么基础,而我这个算法题就从来没见过。他们的题目如下:

1. 循环队列的实现。  2. 二叉树的Z型遍历。

我擦啊,为啥我的不是这种问题,唉,只能说是运气不佳。不过据说有个人把两道题都答出来了,但是还是挂了,原因是“面试官对算法能力不满意”。那我就纳闷了,如果说是实现得不好那面试官肯定当场会指出来,既然都做出来了为啥还是“不佳”呢?

没办法,既然不是ACM的大神,那么我还是继续刷题好了,为以后面试别的公司做准备。不过话说回来,这种东西准备是一方面,但和当时的状态有很大关系,比如我没做出来的那个题如果放在别的时候要我做,应该是能想出来的。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s