春雨天下笔试面试

<!--?xml version="1.0" encoding="UTF-8" standalone="no"?-->

三位面试官，第一位是曾伯毅（CTO）。

1、反转字符串，例如"I am a student＂转成＂student a am I＂ ，不许使用字符串的高级方法和函数。

a、使用额外储存空间，一个stack。首先遍历求出字符串的长度，然后从末尾开始遍历，将单词push入栈，然后遇到空格后，将栈全部pop清空。

b、 定义两个函数，int  length（）和void  reverse（），首先将所有字符反转，然后将倒序的单词反转。

    这种方法不需要借助额外的空间，但是效率不如a高。

 

2、快速排序的partition函数

    略 

 

3、修改partition函数，将小于key，等于key和大于key的元素分开 （时间复杂度）

这个问题要考虑周全，无法在事先得知整个数组中有多少个等于key的元素，要保证出现多个等于key值的元素后，仍然可以正常终止循环。  

 

4、二叉树的中序遍历

略

 

5、将二叉树的中序遍历的结果改为双向链表 

加深对递归的理解，即先将整个二叉树从树抻成链，再将其与root结点相连。

 

6、 将一个双向链表倒转，返回倒转后的头结点，注意各种边界条件。

三个指针prv，cur和next。指定cur之后，判断prv和next的存在性。 

 

 

还有电话面试的两道题

1、什么是多态？什么时候使用多态？

2、如何找到两个数组中的重复元素？ 

两种情况：有序数组和无序数组

       有序： 

两个指针直接比较遍历 O（n）

       无序：

hashing算法  O（n）无需额外空间

字符统计counting 需要额外空间 

 

本文是在Evernote上编辑的~

评论

6 楼 ShadowDai 2012-03-08  

jtlmei 写道

第一道：利用了String类的函数
package com.jtlyuan;

public class Reverse {
public String reverse(String str) {
String[] s = str.split(" ");
StringBuffer sb = new StringBuffer();
for (int i = s.length - 1; i >= 0; --i) {
sb.append(s[i] + " ");
}
return sb.toString();
}

public static void main(String[] args) {
String str = "I am a student";
System.out.println(new Reverse().reverse(str));
}
}

呵呵，之前说过是不允许使用这种类函数的，只能使用指针去做。

5 楼 jtlmei 2012-03-05  

第一道：利用了String类的函数
package com.jtlyuan;

public class Reverse {
public String reverse(String str) {
String[] s = str.split(" ");
StringBuffer sb = new StringBuffer();
for (int i = s.length - 1; i >= 0; --i) {
sb.append(s[i] + " ");
}
return sb.toString();
}

public static void main(String[] args) {
String str = "I am a student";
System.out.println(new Reverse().reverse(str));
}
}

4 楼 ShadowDai 2012-03-02  

qq123zhz 写道

1、反转字符串：
直接正则表达式，利用空格匹配，填充字符数组，然后拼接3个数组。

高级啊，正则表达式接触的不多，能不能说的详细点？我好好学习研究一下。

3 楼 qq123zhz 2012-03-02  

1、反转字符串：
直接正则表达式，利用空格匹配，填充字符数组，然后拼接3个数组。

2 楼 ShadowDai 2012-03-02  

dicmo 写道

多是数据结构啊！~

是的，非常注重数据结构和代码的优化。相同的代码重写了很多次~就是为了能够精简和优化。这个CTO曾伯毅很厉害，清华毕业的~

1 楼 dicmo 2012-03-02  

多是数据结构啊！~