春雨天下笔试面试

<!--?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上编辑的~

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));
}
}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));
}
}

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