早早聊面试场逐字稿。

前言

开场先来标题党一下，和 Scott 聊天的时候正好说到我入职的经历，然后就有了这次分享，当时我随口报了一个，刷了 5 道题，不过后来我仔细的数了一下发现是 4 道题。

不过问题不大，这次半个小时的分享会从「招聘要求」、「怎么刷题」、「大小公司的区别」以及「*做业务和基础设施的区别」四个点进行分析。

- 阅读剩余部分 -

双端队列，也就是栈和队列的结合，同时可以从头和尾进行进出栈 / 队列的功能，看一下他的数据结构就懂了：

public class Deque<Item> implements Iterable<Item> {
   public Deque()                           // construct an empty deque
   public boolean isEmpty()                 // is the deque empty?
   public int size()                        // return the number of items on the deque
   public void addFirst(Item item)          // add the item to the front
   public void addLast(Item item)           // add the item to the end
   public Item removeFirst()                // remove and return the item from the front
   public Item removeLast()                 // remove and return the item from the end
   public Iterator<Item> iterator()         // return an iterator over items in order from front to end
   public static void main(String[] args)   // unit testing (optional)
}

双端队列的实现还是比较简单的（虽然实际上还会是踩了一些微小的坑）。

- 阅读剩余部分 -

前两周的时候看到有人推荐https://www.coursera.org/learn/algorithms-part1/的算法课，正好基础也忘得差不多了，觉得也是应该复(yu)习(xi)一下了，普林斯顿的这个公开课确实不错。

好了，废话不多说，来总结一下第一周，说说并查集和渗漏问题吧。

数据结构介绍

并查集是一个处理连接问题的数据结构，可以用这个结构快速的找到两个元素是否属于同一集合（或者说连通），和图的连通算法不同的是它忽略了路径的概念，只需要结果。

- 阅读剩余部分 -

上次去Google Girls送了我一本面试金典，前天无聊就看了起来，看到的部分目前还是比较基础也有些意思的，在我看到第一堆算法题的时候我说了一句，这个题看着有点简单啊……然后秒被打脸，可以说，所有的题都是想简单就简单，想难就难，主要看你考虑了多少。

今天就拿其中一道题来说说上面的观点。

实现一个算法，确定一个字符串的所有字符是否不同，假设不允许使用额外的数据结构，又该如何处理。

- 阅读剩余部分 -

好了，这一篇我们顺着上面几篇的思路来说说rsync，所有的内容在参考链接中都可以看到更详细应该也是更有深度的说明……

rsync科普级介绍

如果你在寻找一个差异同步上传机制，那么rsync就是你想要的，在目录中选择性拷贝，安全保障，提供多种传输方式，具体的功能可以从之后的介绍和扩展阅读中看出。

rsync算法介绍

酷壳有一篇介绍，不过一些名词介绍的比较让人郁闷，先给个总结：rsync = 分块hash check + 滑动窗口。

- 阅读剩余部分 -

排列与组合在我们日常生活中其实也是挺常用的，包括在算法中，也算是比较实用的东西，但是排列组合也是一个难点，这里我们先从简单的出发。

最简单的是全排列和全组合，其中组合的思路更加简单易行，因此我们先从全组合说起。

在说之前，我们先来确定一下定义（数学渣只能从自己下定义开始以免误导读者），我们的全排列，指的是PNN，也就是有n个数字，坑也有n个，求全部的排列情况；全组合，则是除了空集外，n个字母能组成多少种可能性（不一定要全部使用）。

由此，我们开始了我们的全组合之旅：

- 阅读剩余部分 -

在小鱼的gayhub看到了这样的一题，其中就需要用到洗牌程序，当然，我在看到排序算法的时候就想到这样可以用于排序，所以很快就有了第一个排序算法：

var shuffleHack = function(arr) {

    var result = arr.slice();

    result.sort(function() {

        return Math.random() - 0.5;

    });


    return result;

};


- 阅读剩余部分 -

依旧还是面试题，比较麻烦的是，这个排序的关键在于，我们需要时间复杂度为O(n)，空间复杂度为O(1)。

题目大概是这样的，看了输入输出基本就会明白了：

input: arr = ['', 'a', 'b', '', 'a', 'c', '*', 'm']
output: [ '', '', '*', 'a', 'a', 'b', 'c', 'm' ]
问题描述：将数组中的字母与星号分开

这里其实主要没做出来是因为我没有很好地理解怎么计算复杂度，尤其是空间复杂度，时间复杂度我勉强记忆成for循环的嵌套还是可以的，但是空间复杂度呢？

- 阅读剩余部分 -

从我学习至今，我有三大心理阴影：递归、正则表达式、动态规划——这三个导致让我怀疑智商怀疑人生。

在这次假期刷题的时候，前两个似乎都已经不是问题了，就差动态规划——昨天不行random到一道题，一眼望着就是动态规划了——可是我不会啊。

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

题目来自LeetCode，本来是不准备写LeetCode的题了，全都在GitHub上了大家看看就行了，不过这题有助于让我们更好地理解（第一次理解）动态规划。

- 阅读剩余部分 -

题目：

截获了Bobwu的检讨以后，Linkinpaoger突然想到可以用自己的加密方式来加密情书。Linkinpaoger写了一封给Anonymous的情书并加密，然后发现密文中出现了很多类似ABBCCC的字符串。经过思索，Linkinpaoger决定按以下规则压缩密文：

1.任何包含k个相同字符的子串被替换为kX，X表示该子串中的唯一字符。

2.若某个这样的子串长度为1，那么省略‘1’。

按以上规则，ABBCCC将被压缩为A2B3C。现在请你帮Linkinpaoger压缩密文。

输入：

输入的第一行为一个正整数N，表示共有N组测试数据，接下来的每一行表示一组密文，密文仅由‘A'-’Z'组成。

1≤N≤100，每组密文的长度不超过10000个字符长度。

输出：

对于每组输入数据，输出一行压缩后的密文。

- 阅读剩余部分 -