九阴真经

招聘

单链表根据某个value排序，小的在前面，相对顺序不能变

• 插入排序

实现函数，判断链表是否有环

• 快慢指针

正则匹配算法实现

• ?

M进制转换为N进制程序实现

• 思路
  M进制转10进制，10进制再转N进制

• M进制转10进制
  进制 ^ 下标 * 倒序数位和
  8进制1356转10进制：
  

  $$8^0*6 + 8^1*5 + 8^2*3 + 8^3*1 = 750$$

• 10进制转N进制：
  商留取余，逆序排列

数组中有一个数重复，找出来空间要求O(1)

• 二叉搜索树，节点自下沉过程中如果遇到相等的，即找到

有100万个数，找出其中最大/最小的1000个数

• 找最大用小顶堆下沉法，找最小用大顶堆沉淀法
• 以取最大的N个数为例：
  
  1. 初始化长度为1K(1M的前1K个数)的小顶堆
  2. 遍历1M剩余元素并插入堆并下沉
  3. 遍历完成后整个堆里的值即是这1M个数中最大的那1K个
  4. 前序遍历输出即可

给一个数字序列，找出他的逆序数

• 归并排序，发现右边大于左边的，就是逆序数

各自时间复杂度的算法熟悉一下

设计一个扑克牌的洗牌算法，设计出来后自己要算出该算法的时间复杂度

• 倒序遍历数组，每一个元素与未被遍历过的随机元素进行交换
• 时间复杂度 O(n)，空间复杂度 O(1)

已知一个rand5函数(随机生成0-4的数)，用他生成一个rand7函数(随机生成0-6的数)

$rand5() * (6 / 4)$

一个N长度的int数组，里面的数字是1到N-1，多出了一个重复的数字，写一个函数把重复的数字写出

• 遍历一次，把数组按下标放入即可

一个链表，含一个int值，给定一个数字，把小于这个数字的放链表前面，大于的放链表后面，要求两个的顺序不变

• 没看懂

十进制到26进制转换的代码实现

• 商留取余，逆序输出

逻辑题：

两列火车相向而行，一只鸟在中间来回飞，到火车相遇时，鸟的飞行距离。

设两辆火车的距离为 $D$，两辆火车的速度为 $X$ 和 $Y$，鸟的飞行速度为 $S$
所以，火车从开始到相遇的时间 $T=D / (X+Y)$
鸟的飞行时间与火车相遇时间相同
所以，鸟的飞行距离 $Z = S * D / (X+Y)$$

在一个二维坐标系里面，从原点坐标 $(0,0)$ 走到 $(n,m)$ 坐标的位置，每次只能向右走 $(x+1)$ 或向上走 $(y+1)$，不可以向左走 $(x-1)$ 或向下走 $(y-1)$，请问总共有多少种可能的走法；

总共要走 $N+M$ 步，设右为 $A$，上为 $B$。把 $n$ 个 $A$，$m$ 个 $B$ 放入 $n+m$ 的数组排列有多少种？

相当于在n+m个座位中排n个A剩下的填入B。
(n+m)*(n+m-1)…m
(n+m)!/m!

12个经典的行程问题

http://www.matrix67.com/blog/archives/4881

有一批微信用户，怎样知道是否能将这些用户分成两组，其中每组中，两两互不为好友

奇偶校验，遍历用户。选A设0，A的好友设1.
从A的好友B为1，B的好友设0
递归遍历好友，设置key:value。当设置过程中发现设置上的数字与原来的value不同时失败。