IS-Job-Hunting
IS-Job-Hunting copied to clipboard
GingerBear
分享一些找工作的信息和面试题
OOP和Design Pattern的知识是面试经常问到的方面，希望能有一位同学能自告奋勇跟大家总结一下这方面的知识，不仅大家都会从你的总结里受益，自己也会对这方面的知识有更深的理解。 你不需要对OOP和Design Pattern有多么熟悉，只需要查查资料，介绍一下基本概念，讲讲经典的题目，然后提供一些面试的应对策略就行，对于Design Pattern，面试的要求应该不高，介绍几个常见的Pattern，和各自的使用场景应该就可以了。 讲得不需要多好，同学们会跟着一起讨论。如果发现有拓展知识需要专门总结，也可以指定其他同学（使用@，比如 @GingerBear）来讲。
快速攻陷正则表达式
说实话，应该说正则表达式在面试的时候比较少碰到，不是刷题的重点。但本着 **“打好基础”** 的精神，快速攻破这个 **“看似牛逼，其实不难，又很有用”** 的东西能够填补上我们知识上的漏洞，如果在面试时能用到，一定会加分不少。正则表达式也是Steve Yegge的[技术面试题的五个大方向](https://github.com/GingerBear/IS-Job-Hunting/issues/2)的一个大方向。 > 下面摘自Google工程师徐宥的这篇博客[编程珠玑番外篇-C.正则表达式精义-1](http://blog.youxu.info/2009/03/05/ree1/) ### 正则表达式是什么?为啥会有这个东西？ 正则表达式是一种描述性的语言, 用来概括一类字符串 (或者说一个字符串集合). 我们当然可以用自然语言来描述一类字符串, 比如我们说, - 以 “010 开头的电话号码”, - “夹在HTML 的 和 中间的内容”, - “含有 hello 的字符串”, - “负数”,...
动态规划：堆积木
有n块积木，每块积木有体积vol和重量weight两个属性，用二元组(vol, weight)表示。积木需要搭成竖直的塔状，上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。 #### 示例 ``` 有7个积木boxes: [(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110), (80, 12)] 最多可以搭6个积木，从上到下分别为： (56, 90), (60, 95), (65, 100), (68, 110), (70,...
> source: https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions
> 注：好久没做题的，热个身吧 > 来源：[The Five Essential Phone-Screen Questions ](https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions)
既然之前说到了Heap，这里有必要聊聊Priority Queue，因为一般Priority Queue使用Heap来实现。 #### Priority Queue是啥？ Priority Queue（简称PQ）就是根据某个权重排序的一个Queue，换句话说，排好序的数组也可以算是一个PQ，权重就是元素值的大小。PQ有两个操作，第一是Insert操作，要求Insert一个元素到PQ之后，PQ能够自动把它放到合适的位置。第二个是Delete操作，也就是删除并返回最高权重的那个元素。（这不是就是Heap嘛）。 #### Priority Queue的实现 PQ最简单的实现方法当然就是排序了，把所有元素放到一个list里，每次insert之后都sort一下，delete操作就是最前面那个item摘掉。但这么做的问题是代价太大，每次Insert都要sort，也就是O(n log n)，delete倒是很快O(1)，但考虑到PQ可能经常添加新元素的话，效率明显就太低了。 上面那个方法太笨了，对于排好序的list（使用linked list实现list，为了使中间的插入操作只需要O(1)），insert新元素只需要找到自己的合适位置就好了，用不着每次都重排一次，所以insert操作只需要进行n-i次比较能找到合适位置，即O(n)，delete还是O(1)。 还不够好，如果是排好的数组，为啥不用binary search来找到合适的位置呢？找到位置是O(log n)了，但由于是数组实现，需要移动剩余的元素，所以insert操作还是需要O(n)，如果用linked list来存放元素的话虽然插入操作是O(1)，但由于不能用binary search，找位置还是需要O(n)，delete还是O(1)。 还是不行？heap来了。heap的插入操作终于达到了O(log n)，尽管它的delete是O(log n)，具体实现方法看[这里](https://github.com/GingerBear/IS-Job-Hunting/issues/10)。 另外一种实现方法是Binary Search Tree (BST)，Insert和Delete也是O(log n)，但它较heap的劣势是，heap的初始化操作只需要O(n)，但BST需要O(n log...
关于动态规划
动态规划的题基本就是难题了，一直觉得如果面试碰到基本上就投降了，直到今天读到了两篇文章，让我重拾起了一些信心。 [动态规划：从新手到专家](http://hawstein.com/posts/dp-novice-to-advanced.html) [动态规划之背包问题（一）](http://hawstein.com/posts/dp-knapsack.html) 动态规划一般涉及到找最优方案，解题的核心是找到**“状态”**和**“状态转移方程”**。两篇文章都用了非常详细的例子讲了动态规划的使用方法。尽管我看的还是一知半解，但对于这类题已经有了一个入手方向。
先前在亚马逊面试的第一道就碰到了哈弗曼树。虽然早有准备，不过匆忙之中写出的代码还是忽略了诸多要点。以下是鄙人对哈弗曼树的一些肤浅理解。诸君若要深入了解请务必亲自实践。 哈弗曼树主要应用于数据压缩、字符编码中。与大部分树的构建方式不同，哈弗曼树是自底而上构建的。算法的输入通常为字符串，根据字符出现的频率由小到大构建产生，其叶节点（且只有叶节点）为字符串的每一个字符。   其大致的原理是： 1. 在队列中输入一连串字符。此处假设所有字符为ASCII。（队列的节点结构可以是字符及其频率） 2. 从中选出并删除两个出现频率最小的节点（由此引出最小优先队列的应用） 3. 将以上两个节点看做两个叶节点，在两者顶部新建父节点。叶节点的值如先前定义的，包含字符的值及其频率；而父节点的值的字符部分为空，频率则是其两个子节点频率的和。 4. 将新的父节点加入队列。 5. 重复2-4 以下为部分代码： 树节点结构： ``` Java private class Node implements Comparable{ private char ch; private int freq;...
看到马汉超 @Marco1989 在微博上分享了好文一篇，我在这里转发一下。我也碰到过多表join导致一个查询需要6秒以上，添加索引后效果拔群，瞬间到0.5秒以内。 
链表排序
``` java public class ListNode { public int val; public ListNode next; } ``` 热身基础题，使用上面的ListNode。 输入链表表头，输出排序后的链表表头。 注意考虑特殊情况。