c***p
发帖数: 221 | 1 最近面了几个公司，经验说不上，教训有几条：
1. 一个on-site面试通常4-5个小时，越到后来越要坚持住。回顾最近的这几次on-site
，都是面到最后一个人的时候出的问题最多。一个建议，在面最后一个人之前，要求去
趟卫生间，趁机休息一下，喘口气。
2. coding的要求越来越高了。几乎就是要可以编译执行的那种。一定要注意细节。比
如函数的signature,变量的declaration。所以在做coding题的时候，就当做是在电脑
上输入，然后编译运行。对于C++程序，参数是传值还是传引用，需不需要const声明等。
3. 对于用C++语言，基本的stl container要熟悉。比如，vector, queue, stack,
dequeue, map。这样，在写算法的时候，可以集中精力整理思路，而不必为细节分心。
最近遇到的几个常考coding题：
1. LRU Cache
2. Hash Table的实现（定义hash function, 处理collision, 实现get, put）
3. 合并两个BST 为一个平衡的BST。 |
s**********v
发帖数: 1379 | 2 总结得不错！
site
等。
【在 c***p 的大作中提到】
: 最近面了几个公司，经验说不上，教训有几条：
: 1. 一个on-site面试通常4-5个小时，越到后来越要坚持住。回顾最近的这几次on-site
: ，都是面到最后一个人的时候出的问题最多。一个建议，在面最后一个人之前，要求去
: 趟卫生间，趁机休息一下，喘口气。
: 2. coding的要求越来越高了。几乎就是要可以编译执行的那种。一定要注意细节。比
: 如函数的signature,变量的declaration。所以在做coding题的时候，就当做是在电脑
: 上输入，然后编译运行。对于C++程序，参数是传值还是传引用，需不需要const声明等。
: 3. 对于用C++语言，基本的stl container要熟悉。比如，vector, queue, stack,
: dequeue, map。这样，在写算法的时候，可以集中精力整理思路，而不必为细节分心。
: 最近遇到的几个常考coding题：
|
p*****2
发帖数: 21240 | 3 3. 合并两个BST 为一个平衡的BST。
这个好像不容易吧？有什么trick吗？ |
q***y
发帖数: 236 | 4 合并两个BST 为一个平衡的BST。 O(n)time O(1)space
Hashtable 不好写啊。选啥hash function呢。
【在 p*****2 的大作中提到】
: 3. 合并两个BST 为一个平衡的BST。
: 这个好像不容易吧？有什么trick吗？
|
l*****a
发帖数: 14598 | 5 报过offer吗？
site
等。
【在 c***p 的大作中提到】
: 最近面了几个公司，经验说不上，教训有几条：
: 1. 一个on-site面试通常4-5个小时，越到后来越要坚持住。回顾最近的这几次on-site
: ，都是面到最后一个人的时候出的问题最多。一个建议，在面最后一个人之前，要求去
: 趟卫生间，趁机休息一下，喘口气。
: 2. coding的要求越来越高了。几乎就是要可以编译执行的那种。一定要注意细节。比
: 如函数的signature,变量的declaration。所以在做coding题的时候，就当做是在电脑
: 上输入，然后编译运行。对于C++程序，参数是传值还是传引用，需不需要const声明等。
: 3. 对于用C++语言，基本的stl container要熟悉。比如，vector, queue, stack,
: dequeue, map。这样，在写算法的时候，可以集中精力整理思路，而不必为细节分心。
: 最近遇到的几个常考coding题：
|
l*****a
发帖数: 14598 | 6 我根你的经验有点区别
都是开始热身不够，一上来面对头1-2个人头脑发蒙，很不清醒
虽然后面越站越勇，但是总被前两个人淘汰
site
等。
【在 c***p 的大作中提到】
: 最近面了几个公司，经验说不上，教训有几条：
: 1. 一个on-site面试通常4-5个小时，越到后来越要坚持住。回顾最近的这几次on-site
: ，都是面到最后一个人的时候出的问题最多。一个建议，在面最后一个人之前，要求去
: 趟卫生间，趁机休息一下，喘口气。
: 2. coding的要求越来越高了。几乎就是要可以编译执行的那种。一定要注意细节。比
: 如函数的signature,变量的declaration。所以在做coding题的时候，就当做是在电脑
: 上输入，然后编译运行。对于C++程序，参数是传值还是传引用，需不需要const声明等。
: 3. 对于用C++语言，基本的stl container要熟悉。比如，vector, queue, stack,
: dequeue, map。这样，在写算法的时候，可以集中精力整理思路，而不必为细节分心。
: 最近遇到的几个常考coding题：
|
c***p
发帖数: 221 | 7 有时候觉得面试就是在走钢丝，从开始到结束，一步都不能错。很多公司的面试都是一票否决的。
哪个都不能含糊。
【在 l*****a 的大作中提到】
: 我根你的经验有点区别
: 都是开始热身不够，一上来面对头1-2个人头脑发蒙，很不清醒
: 虽然后面越站越勇，但是总被前两个人淘汰
:
: site
: 等。
|
c***p
发帖数: 221 | 8 有了一定报。从这个版面学到了太多。
【在 l*****a 的大作中提到】
: 报过offer吗？
:
: site
: 等。
|
c***p
发帖数: 221 | 9 我的方法是分别把每个BST按照in-order转换成linked list; 然后merge;从merge后的
linked list 建立新的BST.创建新的BST的时候，把list的中点作为root,这样就尽可能
使得tree是balanced.
【在 p*****2 的大作中提到】
: 3. 合并两个BST 为一个平衡的BST。
: 这个好像不容易吧？有什么trick吗？
|
c***p
发帖数: 221 | 10 一般来说，可以自己定义一个hash function.有的人会继续问下去，比如不同类型的
data（int, float, string等）有什么常用的hash 方法。当然，对于int,最简单的就
是modulo了.
【在 q***y 的大作中提到】
: 合并两个BST 为一个平衡的BST。 O(n)time O(1)space
: Hashtable 不好写啊。选啥hash function呢。
|
|
|
p*****2
发帖数: 21240 | 11
我的思路也是这个。不过这个写起来可不容易。这个好像是G，F级别的难题了。
【在 c***p 的大作中提到】
: 一般来说，可以自己定义一个hash function.有的人会继续问下去，比如不同类型的
: data（int, float, string等）有什么常用的hash 方法。当然，对于int,最简单的就
: 是modulo了.
|
c***p
发帖数: 221 | 12 这个题，折腾了半天。最后面试官也没有仔细看，解释了一下思路。
不过，面试官问了一下如何优化。我的方法在重新构造平衡bst的时候要取list中点作
为root.然后再分别对左右两段做recursion。所以每次都要走一遍list来去找中点。他
建议的优化是先转换成array,这样取中点就是const时间了。
【在 p*****2 的大作中提到】
:
: 我的思路也是这个。不过这个写起来可不容易。这个好像是G，F级别的难题了。
|
O******i
发帖数: 269 | 13 这是zhangchitc的G面经中的一道题吧，那个面试官要的就是这个雷人的解法。
【在 c***p 的大作中提到】
: 这个题，折腾了半天。最后面试官也没有仔细看，解释了一下思路。
: 不过，面试官问了一下如何优化。我的方法在重新构造平衡bst的时候要取list中点作
: 为root.然后再分别对左右两段做recursion。所以每次都要走一遍list来去找中点。他
: 建议的优化是先转换成array,这样取中点就是const时间了。
|
Z*****Z
发帖数: 723 | 14 这题够写一阵子的。。
leetcode上有一个list -> BST的经典做法
【在 c***p 的大作中提到】
: 这个题，折腾了半天。最后面试官也没有仔细看，解释了一下思路。
: 不过，面试官问了一下如何优化。我的方法在重新构造平衡bst的时候要取list中点作
: 为root.然后再分别对左右两段做recursion。所以每次都要走一遍list来去找中点。他
: 建议的优化是先转换成array,这样取中点就是const时间了。
|
c***p
发帖数: 221 | 15 看了一下，leetcode大侠的方法很巧妙。用linklist也能做到O(N).
http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced
binary.html
看来leetcode上的题目还要仔细看啊。
【在 Z*****Z 的大作中提到】
: 这题够写一阵子的。。
: leetcode上有一个list -> BST的经典做法
|
